mtsp模型及求解word版(更新版)
【正文】 Cij分別表示從訂單i轉(zhuǎn)換到訂單j的懲罰,定義如下：Cij=λij|Gj－Gj+1|+βij|Wj－Wj+1|+μij|Hj－Hj+1|其中:1 if (|Gj－Gj+1|) ≤ΔGλij= i, j∈{1,…,N}, i≠j∞ if (|Gj－Gj+1|) ﹥?chǔ) 1 if (|WjWj+1|) ≤ΔWβij= i, j∈{1,…,N}, i≠j∞ if (|WjWj+1|)﹥?chǔ) 1 if (|HjHj+1|) ≤ΔHμij= i, j∈{1,…,N}, i≠j∞ if(|HjHj+1|) ﹥?chǔ)其中:Gj、Wj、Hj分別表示訂單j的厚度、寬度和硬度。這個(gè)虛擬節(jié)點(diǎn)既是源點(diǎn)也是收點(diǎn)，這樣就構(gòu)成了閉合回路。一種合理的辦法是并行方法，即從訂單池中同時(shí)編制出M個(gè)軋制單元計(jì)劃。本文從全局最優(yōu)觀點(diǎn)提出能夠同時(shí)產(chǎn)生一個(gè)班次中的M個(gè)軋制單元計(jì)劃的并行策略，并且根據(jù)實(shí)際生產(chǎn)約束，可以熱軋調(diào)度問(wèn)題歸結(jié)為多旅行商問(wèn)題模型。由于熱軋生產(chǎn)調(diào)度問(wèn)題中的軋制單元計(jì)劃是一條開放路徑，每一個(gè)訂單只能軋制一次。因此，兩節(jié)點(diǎn)之間的距離可定義為相鄰軋件軋制參數(shù)的改變(跳躍)值；將相鄰板坯之間的寬度、厚度和硬度跳躍值之和作為懲罰值，對(duì)超出軋制規(guī)范約束的賦予一個(gè)較大的懲罰值。約束式(2)表示任務(wù)i之后軋制的任務(wù)有且只有一個(gè)；約束式(3)表示在訂單j之前有且只有一個(gè)任務(wù)被軋制；約束式(4)~(6)表示軋制規(guī)范，其中式(4)表示相鄰板坯寬度跳躍約束，式(5)表示相鄰板坯厚度跳躍約束，式(6)表示硬度等級(jí)跳躍約束；約束式(7)是為了避免在可行解中構(gòu)成子回路而引進(jìn)的約束；約束式(8)表示變量是01變量[6]。在兩交換啟發(fā)交叉規(guī)則中，由2個(gè)父代生成1個(gè)子代，當(dāng)2個(gè)父代的鏈結(jié)構(gòu)接近時(shí)，通過(guò)HGA交叉后，子代不會(huì)有很大的改善[9]。當(dāng)3個(gè)父代的平均值(設(shè)為f′)和當(dāng)前代中最優(yōu)值相差較大時(shí)，說(shuō)明這3個(gè)父代和當(dāng)前最佳值還有很大差距，需要通過(guò)交換產(chǎn)生更好的排序結(jié)果。方法3實(shí)際上在756代時(shí)便已經(jīng)達(dá)到了最優(yōu)解，因此可見當(dāng)采用改進(jìn)的遺傳算法不論是收斂速度和解的質(zhì)量都是最好的[11]。 (自然科學(xué)版), 2004（05） [9] 陳繼業(yè),謝政. 求解旅行商問(wèn)題的一種混合遺傳算法. 計(jì)算機(jī)工程與應(yīng)用, 2004, (12).[10] (TSP)(自然科學(xué)版)[J]， 1999,(02):41一42.[11] 尚智強(qiáng), 鄭耀林. 一種改進(jìn)遺傳算法在旅行商(TSP)問(wèn)題中的應(yīng)用[J]. 福建電腦, 2002,(08
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1