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

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

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

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

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

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

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

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

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

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

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