基于列生成的鐵鋼區(qū)批量計劃與物流調度.pdf

1、鐵鋼區(qū)的批量計劃和物流調度是鋼鐵企業(yè)生產(chǎn)運作管理中急需解決的重大關鍵問題，科學的制定有利于提高生產(chǎn)效率和資源利用率、降低生產(chǎn)成本和能源消耗。由于鐵鋼區(qū)的批量計劃和物流調度問題都可歸結為NP-Hard的組合最優(yōu)化問題，因此，探討適合這類問題的有效和實用算法已成為學術界和工業(yè)界關注的熱點研究課題。列生成作為一種重要的最優(yōu)化技術，與其他算法相結合已經(jīng)成功地求解許多NP-Hard的經(jīng)典組合最優(yōu)化問題，獲得問題的最優(yōu)解或次優(yōu)解。本文從影響列生成算

2、法性能的要素出發(fā)，分別針對算法體系結構、價格子問題的求解以及整數(shù)解的獲取三個方面進行了理論和改進研究；并以從鐵鋼區(qū)提煉出來的煉鋼-連鑄Lot批量計劃問題、煉鋼-連鑄澆次批量計劃問題、鐵水流向分配問題、鐵水機車調度問題為背景，對列生成方法進行了應用研究。針對鐵鋼區(qū)的實際煉鋼-連鑄批量計劃問題，設計并提出了有效的智能優(yōu)化算法，以此為核心開發(fā)了相應的決策支持系統(tǒng)。具體內容概括如下：
　　 1)算法體系結構改進。將基于次梯度的拉格朗日松

3、弛(LR)算法嵌入列生成算法框架中，形成拉格朗日松弛和列生成的混合算法。該算法包含雙重迭代，在內環(huán)通過求解拉格朗日松弛子問題和基于次梯度更新乘子來獲得LR對偶問題的下界同時生成列；在外環(huán)將內環(huán)生成的負消減費用列加入限制主問題，通過求解獲得其最優(yōu)解（對應LR對偶問題的上界）以及影子價格，并將影子價格同歷史最好次梯度乘子進行加權組合并傳遞給內環(huán)作為初始乘子。以煉鋼-連鑄Lot批量計劃問題為研究對象，對該算法進行了應用研究。對該問題建立一個混

4、合整數(shù)規(guī)劃模型，通過松弛模型中一組耦合約束獲得拉格朗日松弛問題，并將其分解為兩級子問題，分別設計了有效動態(tài)規(guī)劃算法，進一步將LR對偶問題等價轉換為適合列生成的粗放型線性規(guī)劃模型，從而結合基于次梯度的拉格朗日松弛算法和列生成算法，形成LR&CG混合算法，共同求解LR對偶問題。
　　 2)求解價格子問題方法的改進。提出三種不同改進策略，包括：狀態(tài)空間松弛技術、降低搜索空間策略以及基于啟發(fā)式生成列的策略。
　　 (1)狀態(tài)空間

5、松弛技術以消弱主問題的下界為代價，來降低價格子問題的復雜度，從而加速價格子問題的求解。以鐵水流向分配問題為研究對象，進行了該策略的應用研究。通過對NP-Hard單機調度子問題的狀態(tài)空間進行松弛而設計了一個偽多項式動態(tài)規(guī)劃算法，同時允許單機子問題的偽調度（列）加入限制主問題，從而對子問題求解的加速和主問題下界的削弱進行了折衷，提高了算法的整體性能。
　　 (2)降低搜索空間策略主要是針對那些采用探索技術獲得價格子問題最優(yōu)解的方法，

6、通過對價格子問題性質的分析，識別那些不可能擴充為最優(yōu)解的部分解，將其盡早排除，從而節(jié)約搜索無效空間帶來的計算時間。以煉鋼-連鑄澆次批量計劃問題和鐵水機車調度問題為研究對象，分別進行了該策略的應用研究。煉鋼-連鑄澆次批量計劃問題列生成算法的價格子問題可歸結為帶有資源約束“族單元”最短路徑問題，為該問題設計了廣義Dijkstra算法，提出統(tǒng)治規(guī)則和標簽下界估值來抑制標簽的快速增殖，從而限制了無效的搜索空間，提高價格子問題的求解效率。這個策略

7、還可擴展到鐵水機車調度問題列生成算法的價格子問題，歸結為帶有非線性目標函數(shù)和時間約束的“單元”最短路徑問題。
　　 (3)基于啟發(fā)式生成列的策略是在列生成算法迭代的初始階段，采用啟發(fā)式生成負消減費用列，從而降低價格子問題最優(yōu)求解的復雜性，節(jié)約計算時間。以煉鋼-連鑄澆次批量計劃問題列生成算法的價格子問題為例，針對當前基變量對應的列，采用貪婪思想進行先插入后刪除，由此形成新的負消減費用列，并加入限制主問題。以煉鋼-連鑄Lot批量計劃

8、問題的拉格朗日松弛子問題為例，通過對子問題進一步松弛獲得松弛子問題的最優(yōu)解，基于此改造獲得子問題的可行解，從而搜尋合適的下降方向和負消減費用列。
　　 3)整數(shù)解的獲取。提出三類不同方法獲取最優(yōu)或次優(yōu)整數(shù)解，即分枝-定界，基于列生成的分數(shù)解改造策略和基于拉格朗日松弛問題解的改造策略。
　　 (1)通過探究原模型同Dantzig-Wolfe分解模型之間變量的等價關系和問題自身的性質，提出有效分枝策略，從而實現(xiàn)基于列生成的分

9、枝-價格算法獲取最優(yōu)解，應用于煉鋼-連鑄澆次批量計劃問題、鐵水流向分配問題以及鐵水機車調度問題。
　　 (2)通過改造列生成算法所獲得的最優(yōu)分數(shù)解來獲取原問題的整數(shù)解（上界），包含兩種不同類型的改造。針對煉鋼-連鑄澆次批量計劃問題，基于當前分數(shù)解，采用一種過濾策略獲取部分整數(shù)解，剩余的列和行構成降維問題，進行新一輪的列生成。最后對獲得的整數(shù)解進行局域搜索來獲得改進，并且僅在根節(jié)點處執(zhí)行該策略，不執(zhí)行分枝操作。針對鐵水機車調度問題

10、，在每個分枝節(jié)點都針對分數(shù)解進行改造，首先通過計算任務和機車之間的分配關系，然后按照字典序關系將任務插入機車調度。這種策略試圖在分枝樹上搜尋較好上界，以幫助修剪分枝節(jié)點、抑制分枝樹的規(guī)模。
　　 (3)拉格朗日松弛算法中，常對拉格朗日松弛問題的最優(yōu)解進行改造來得到原問題的可行解，稱為LR啟發(fā)式，但LR啟發(fā)式?jīng)]有固定的實現(xiàn)模式。在煉鋼-連鑄Lot批量計劃問題的LR&CG混合算法中，通過固定Lot的選取，以及松弛部分約束，將原問題轉