熱軋計劃中的多旅行商問題及其計算方法

摘要：針對熱軋批計劃問題進行了MTSP（多旅行商問題）建模，并對該問題設計了混合遺傳算法，經某大型鋼廠實例數據進行了仿真測試。計算結果表明，該算法給出了較優的軋制批計劃方案，解決了熱軋軋制批計劃的編制問題。

關鍵詞：多旅行商問題; 數學模型; 熱軋軋制計劃; 遺傳算法

中圖分類號：TP391； TH122文獻標志碼：A

文章編號：1001－3695(2007)07－0043－03

0引言

多旅行商問題是旅行商問題（TSP）的擴展和延續，它也是一個NP－難問題。MTSP通?？梢悦枋鋈缦拢邯玀個旅行商從同一城市（或不同城市）出發，分別各走一條旅行路線，使得每個城市有且僅有一個旅行商經過（出發城市除外），且總旅行路程最短。在實際生活中，鋼鐵熱軋調度、鐵路運輸、管道敷設、物流配送路線選擇、計算機網絡拓撲設計等均可以歸結為MTSP。因此對MTSP進行研究具有重大意義。

對于MTSP這種組合優化問題，使用運籌學方法很難得到滿意解。目前，國內外對于MTSP的研究主要集中在傳統MTSP算法的設計上，且算法較少。文獻[1，2]用神經網絡方法求解；文獻[3]用混合遺傳算法求解。對 MTSP各種情況分析和其他算法的研究還較少，主要是通過把MTSP轉換為TSP來解決[4]。

鋼鐵企業在實際編制熱軋生產調度時，一般都是從合同訂單預選池中挑選訂單，依次編制出M個軋制計劃單元[5]。這種策略模擬人工編制計劃的思想，采用串行策略建立了單旅行商模型[6]。但是這種策略類似于貪婪方法，有可能陷入局部最優。一種合理的辦法是并行方法，即從訂單池中同時編制出M個軋制單元計劃。并行方法可以歸結為MTSP。

1熱軋計劃的MTSP模型

1．1問題描述

熱軋軋制批計劃的編制過程通常為：從多個用戶訂單（熱軋板坯）中，按照其交貨期、訂單處理緊急程度及優先級別，一次編制出多個滿足軋制規范的加工生產合同序列的軋制單元，即軋制順序（板坯的先后軋制次序）序列；在同一加工序列中，前后加工的板坯必須滿足軋制規范要求，如相鄰板坯的寬度、厚度、硬度等必須滿足一定的約束條件。為簡化問題，設定每一板坯對應一個用戶訂單合同。根據軋制工藝的要求，以一定數量的連續軋制板坯序列作為一個生產軋制單元，不同的生產軋制單元對應不同的軋輥，即在生產完一個軋制單元后需要停機更換軋輥。從產能角度考慮，更換次數越少、產能越高。因此，追求生產軋制單元的最大軋制量也是熱軋計劃優化的一個重要的衡量指標。

一個軋制計劃（軋制單元）的好壞有多種評價標準，但一般而言可歸結為在軋制單元中相鄰板坯滿足軋制規范的某種評價之和[7]。將全部板坯看成一個個節點（相當于TSP中的城市），一個軋制生產單元看成是經過一定數目節點的一條旅行路徑，節點之間的距離（評價值）可定義為軋制規范的評價值，則上述熱軋計劃編制與優化問題可歸結為非對稱旅行商模型。將一個軋制單元看成是一個不閉合的TSP（最后不要求返回原出發節點），則軋制批計劃可歸結為非對稱多旅行商模型。由于熱軋計劃編制與優化問題中的軋制單元計劃是一條開放路徑，每一個訂單只能軋制一次。如果一個熱軋調度包括M條軋制單元計劃，則存在M個開放路徑。需要注意的是，與標準MTSP不同，MTSP中基于每個旅行商的出發城市已知；而對于熱軋計劃編制問題，任意兩個軋制單元計劃的開始和結束點的訂單都不相同。這意味著任意兩個軋制單元計劃之間沒有相同的點(訂單)，開始訂單也不確定，所以必須建立全新的軋制計劃模型。在求解這類模型時，一般是先把MTSP轉換為TSP，再對TSP求解。在轉換過程中，由于初始板坯不確定，需要加入M個虛擬節點，才能把TSP轉換為相對簡單的TSP。

1．2評價指標、變量和參數定義

提高產品質量、產出率和生產效益是企業生產追求的目標。對軋制計劃編制與優化的質量評價可選用一個綜合衡量指標：在同一軋制單元內，根據軋件（板坯）來對軋制的磨損程度進行衡量。影響軋輥磨損的因素包括板坯的規格、鋼種以及相鄰板坯之間的寬度、厚度和硬度變化等。按照軋制工藝規范約束，相鄰板坯之間的寬度、厚度和硬度等的變化越小，綜合衡量的指標越優。因此，兩節點之間的距離可定義為相鄰軋件軋制參數的改變（跳躍）值；將相鄰板坯之間的寬度、厚度和硬度跳躍值之和作為懲罰值，對超出軋制規范約束的賦予一個較大的懲罰值。對任一軋制計劃單元，其優化目標可定義為：每個軋制單元的總評價懲罰值（相鄰節點評價值之和）最小。

2．2混合算法設計

遺傳算法把握總體的能力較強，但局部搜索能力較差；模擬退火算法具有較強的局部搜索能力。因此可以將遺傳算法和模擬退火算法相互結合，取長補短。為了克服遺傳算法和模擬退火算法各自的缺點，發揚其優點，本文將遺傳算法和模擬退火算法綜合后設計出混合遺傳模擬退火算法。

混合遺傳模擬退火算法的基本思想是將遺傳算法與模擬退火算法的優點充分地結合而構成的一種優化算法。與基本遺傳算法的總體運行過程相似，遺傳模擬退火算法也是從一組用啟發式算法如最鄰近法產生初始解(初始群體) 開始全局最優解的搜索過程。它先通過選擇、交叉、變異等遺傳操作來產生一組新的個體，然后再獨立地對所產生出的各個個體進行模擬退火過程，以其結果作為下一代群體中的個體。這個運行過程反復迭代地進行，直到滿足某個終止條件為止。混合遺傳模擬退火算法大大提高了算法的效率[11]。

混合遺傳模擬退火算法的求解過程如下：

（1）初始化種群，令代數gener=0；

（2）計算各個體對應的路徑總路程；

（3）記錄種群中個體的最小路程和對應的最優路徑；

（4）判斷gener≥NG？如果是則停止，并輸出較優編碼路徑，否則轉(5)；

(5)計算種群中個體對應的適應值；

(6)初始退火溫度、中止溫度及內循環次數；

(7)對新種群的個體執行模擬退火操作；

(8)更新種群；

(9)gener=gener+1，轉(2)。

混合遺傳模擬退火算法通過選擇、交叉、變異等遺傳操作所產生的一組新個體獨立地隨機選擇各個體中的兩個基因作為擾動點。經擾動后的個體所得的適應值增強則一定接受該新個體，而新個體所得的適應度減小時，則以某一概率接受該新個體。在此采用

這里采用了閾值法作為溫度修改和算法終止兩準則的設計。因為這樣可以適應算法性能的動態變化，較好地兼顧算法的優化性能和時間性能。

混合遺傳模擬退火算法兼具遺傳算法和模擬退火算法兩者的優點，較適合于解決TSP這種組合優化問題，能夠做到很好的尋優。

3仿真結果及其對比

從某熱軋廠中取一天的合同訂單量（約1．1萬噸）來進行仿真測試，共計628個合同訂單（為簡化問題，這里假設一塊板坯對應一個合同訂單）。要求編制出10個軋制計劃單元，在每一軋制單元中，相鄰板坯盡可能地滿足軋制規范（總評價指標盡可能達到優化）。這里假設每個計劃單元能夠軋制的最大板坯數為100。

4結束語

本文的混合遺傳算法效果較好，比單獨的遺傳算法有不少改進。但通過對排程結果作進一步分析后仍發現其結果比較分散。這是因為大規模的MTSP很難找到其最優解，而且也需要很多時間，所以這方面的研究還應繼續，應對MTSP算法再進行改進，嘗試使用其他新算法，以便能盡快找到更好的解。

參考文獻：

[1]黨建武，靳蕃.神經網絡求解MTSP的應用研究[J].鐵道學報，1997，19(2):63－69.

[2]WACHOLDER E， HAN J，MANN R C. A neural network algorithm for the multiple traveling salesmen problem[J]. Biological Cybernetics， 1989，61(1):11－19.

[3]代坤，魯士文，蔣祥剛.基于遺傳算法的多人旅行商問題求解[J].計算機工程，2004，30(16):139－141.

[4]LENSTRA J K， RINNOOY K A H G. Some simple applications of the traveling salesman problem[J]. Operational Research Quarterly， 1975，26(4):717－733.

[5]金光熙，孫福興，柏世彬，等.寶鋼的生產管理[M].北京:冶金工業出版社，1994:104－130.

[6]KOSIBA E D， WRIGHT J R， COBBS A E. Discrete event sequencing as a traveling salesman problem[J]. Computers in Industry， 1992，19(3):317－327.

[7]TANG Li－xin， LIU Ji－yin， RONG Ai－ying， et al. Multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan iron steel complex[J].European Journal of Operational Research， 2000，124(2):267－282.

[8]玄光男，程潤偉.遺傳算法與工程設計[M].汪定偉，等譯.北京:科學出版社，2000.

[9]謝勝利，唐敏，董金祥.求解TSP問題的一種改進的遺傳算法[J].計算機工程與應用，2000，36（8）:58－60，245.

[10]劉懷亮，劉淼.一種混合遺傳模擬退火算法及應用[J].廣州大學學報:自然科學版，2005，4(2):141－145.

[11]王凌.智能優化算法及應用[M].北京：清華大學出版社，2001.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”