基于多旅行商問題模型的熱軋計劃問題的算法研究.pdf

1、受全球供需趨緊和市場競爭日益激烈的影響，鋼鐵工業(yè)正面臨一系列嚴重的挑戰(zhàn)，在能源供應緊張和激烈的市場競爭下，要求最大限度地降低生產(chǎn)成本，這要求企業(yè)的生產(chǎn)計劃編制方法更加先進和科學。 鋼鐵企業(yè)在熱軋生產(chǎn)調(diào)度中，編制熱軋軋制計劃的目標是在滿足熱軋軋制規(guī)范約束條件下，依照用戶訂單的交貨期的需求，以及訂單生產(chǎn)的緊急程度，對待生產(chǎn)的板坯按照軋機的產(chǎn)能，編制出板坯的軋制序列，使相鄰的板坯之間滿足工藝需求的若干約束條件，以滿足軋機的實際生產(chǎn)的需

2、要。在自動化水平不斷提高的今天，只靠計劃人員手工編制軋制計劃，已不能滿足生產(chǎn)需要。為了充分發(fā)揮軋機的能力、合理利用資源，必須借助計算機技術(shù)，用優(yōu)化的方法和科學的手段來編制熱軋生產(chǎn)計劃。鋼鐵企業(yè)在實際編制熱軋生產(chǎn)調(diào)度時，一般都是從預選池的Ⅳ個任務當中依次編制出M個軋制單元計劃，這種策略為串行策略，但是這種串型策略類似于貪婪方法，先編制的計劃可能很好，后編制的計劃可能很差，即有可能陷入局部最優(yōu)，一個合理的辦法是從N個任務池當中同時編制出M個

3、軋制單元計劃，這種方法稱并行方法。若把軋制計劃中全部的板坯看成一個個節(jié)點(城市)，一個軋制生產(chǎn)單元看成是經(jīng)過一定數(shù)目的節(jié)點的一條旅行路徑，則上述熱軋計劃編制與優(yōu)化問題可歸結(jié)為非對稱多旅行商(MTSP)模型。 旅行商問題(TSP)是一個典型的組合優(yōu)化問題，并且是一個NP難題。很多實際應用問題，如印制電路板的鉆孔路線方案，連鎖店的貨物配送路線等，經(jīng)過簡化處理后，均可建模為旅行商問題，因而對旅行商問題求解方法的研究具有重要實際價值。然

4、而，對于一類更具有實際應用價值的TSP擴展問題——多旅行商問題(Multiple TravelingSalesman Problem，簡稱MTSP)目前尚未引起人們的足夠重視。所謂MTSP通常可以描述如下：M個旅行商從同一城市(或者不同的城市)出發(fā)，分別走一條旅行路線，使得每個城市有且僅有一個旅行商經(jīng)過(出發(fā)城市除外)，且總旅行路程最短。 另外，在車輛調(diào)度方面，機器人運籌學、經(jīng)濟學、管理學、通訊網(wǎng)絡系統(tǒng)中也存在大量的多旅行商問題

5、，因此，對MTSP問題的研究，找到一個優(yōu)化的解決方法，對科學技術(shù)及工程技術(shù)各方面具有很大的意義。而多旅行商問題是NP難問題，傳統(tǒng)的最優(yōu)化方法和近似方法很難求解或者根本無法進行求解，所以只能借助于近年來興起的智能優(yōu)化算法來不斷逼近其最優(yōu)解，比較有效的智能優(yōu)化算法有：遺傳算法(Genetic Algorithms，簡稱GA)、蟻群算法(Ant Colony Algorithm，簡稱ACO)、禁忌搜索(Tabu Search，簡稱TS)、模擬

6、退火(Simulated Annealing，SA)、捕食搜索(Predatory Search，PS)等等。 本文把多旅行商問題分為4種情況，對這四類不同情況分別進行了分析，主要通過把MTSP問題轉(zhuǎn)化為TSP問題來解決，然后分別建立了數(shù)學模型，然后針對．上述軋制批計劃的編制與優(yōu)化問題的特點，和一般的多旅行商問題作了對比分析，建立了軋制計劃編制和優(yōu)化問題的數(shù)學模型，然后分別設計了針對基于多旅行商問題模型的軋制計劃編制和優(yōu)化問題的