基于遺傳算法的車輛路徑問題ExtendSim仿真與優化

詹長書，陳勇汛（東北林業大學 交通學院，黑龍江 哈爾濱 150040）

ZHAN Chang-shu,CHEN Yong-xun (Northeast Forestry University Traffic College,Harbin 150040,China)

我國國家標準《物流術語》 （GB/T 18354-2006）中，給物流下的定義是：“物流是指物品從供應地向接收地的實物流動過程。根據實際需要，將運輸、存儲、裝卸、搬運、包裝、流通加工、配送、信息管理等基本功能實施有機結合。”物流有多方面的功能，而運輸和儲存保管則是其主要功能。在整個物流活動過程中，運輸是其中各項子活動的核心活動，它是第三利潤源的主要的源泉[1]。

日本在20世紀70年代就對物流有深刻的認識了，日本早稻田大學的西澤修教授在其著作中把物流稱作不為人知的利潤源泉，他認為，物流能為企業創造價值，是企業的利潤源泉。石油危機后這一觀點得到證實，物流也因而在企業管理中得到更加重視。目前我國生產型企業的物流成本占到總成本的20%～30%，而發達國家的則為10%左右[2]。因此，為了降低企業經營成本，獲得更多的利潤，必須盡量降低物流成本的比重，這對于國民經濟的更好發展具有十分重要的作用。

在商品經濟社會中，人們的生活質量與商品消費息息相關，而商品的價格直接影響人們的生活水平，如果商品價格不合理，超出人們普遍的可接受范圍，那么人們的生活幸福度將會大大降低。而商品價格的構成部分除了有生產成本，還有更重要的一部分是物流成本，并且物流成本中的運輸費又占了較大的比重。商品運輸需要耗費大量的能源動力，消耗越多，花費成本越高，如果運輸組織的不合理，就會加大運輸成本，因而抬高物流成本，商品價格也因而升高，結果是不僅降低企業的利潤，也間接提高人們的生活成本。

所以，運輸問題是物流領域中值得研究的關鍵問題。其中車輛路徑問題（Vehicle Routing Problems，VRP）是運輸問題中的一個熱點問題。該問題是指：在物資流通過程中，每個需求點的位置和需求量已知，供方如何調度車輛和安排行車路徑向需方供應物資，使得在滿足需方需要的同時也達到某些關鍵目標（如車輛數盡量少、花費時間盡量少、費用最少、路程最短等）。

學者們很早就開始對車輛路徑問題進行了研究，積累了豐富的研究成果。在20世紀50年代末，車輛路徑問題首先被G.Dantzig和J.Ramser[3]提出，兩位學者根據如何運送汽油到加油站這個現實中的問題，利用數學方法對其建立模型，并得出求解算法。在1964年，Clark和Wright這兩位學者研究了G.Dantzig和J.Ramser的方法后，認為后者的方法有改進的空間，并最后提出了Clark-Wright節約算法（即C-W算法）。從此VRP成為運籌學領域的研究熱點。五年后，Christofides與Eilon又想出新的方法，他們應用2-opt和3-opt處理VRP，取得較好的效果。到1981年，Fisher、Jaikumar和Gullen、Ratliff、Jarvis提出不同的研究方法。前者主要利用數學規劃，來對VRP進行最優化處理，后者則是運用人機互動的啟發式方法處理VRP。到90年代，學者們開始利用人工智能構造大量的啟發式算法來解決VRP，如禁忌搜索發、模擬退火法、遺傳算法等。首先采用遺傳算法（Genetic Algorithm，GA）的學者是Holland[4]，他利用遺傳算法中的編碼方法處理了VRP。在這幾種人工智能方法中，遺傳算法能較好地逼近最優解的同時具有較高的運算速度和效率，具有很好的發展前途。

1 VRP數學模型及遺傳算法

1.1 VRP的基本數學模型

VRP的一般描述[5]：

（1）車輛的載重量大于等于配送路徑上總的需求量；

（2）任一配送路徑的長度小于等于車輛在一次配送任務中的最大行駛距離；

（3）每個需求點的需求都只能被同一輛送貨車滿足；

（4）設定每輛車都是從中心出發開展配送任務，任務完成后再重新回到中心。

將一個配送中心編號設為0，該配送中心擁有車k輛，車輛數m，車的額定載重量為q，該中心面向L個客戶，第i個客戶需求量為gi，且gi≤q（i=1,2,…,L），VRP的基本模型如下：

以上式（1）中，cij表示由點i到點j的運輸成本，該函數為最小運輸成本目標函數；（2）為車容量的約束；（3）表示每個客戶僅有一輛車服務；（4）、（5）表示到達和離開某一客戶僅有一輛車。xijk和yki為變量，定義為：

1.2 遺傳算法

本文中的仿真軟件ExtendSim擁有一個自帶遺傳算法的優化模塊。遺傳算法在處理車輛優化調度問題時，有以下幾個步驟：

（1）確定染色體的編碼和初始群體

對可行路線編碼，如長度為1+m的染色體編為：

i代表著每一項運輸任務，此染色體可理解為車輛從配送中心0出發，完成i11,i12,…,i1s后返回配送中心0，形成子路徑1；然后又從0出發，完成i21,…,i2t后返回0，形成路徑2，如此反復直至完成所有的任務。這個過程中，行走路徑不斷改變，使得函數目標也改變，這樣的遺傳迭代就能讓函數目標最小，也即趨向于最佳路徑。

（2）確定目標函數

根據所研究的具體問題，數學模型的目標函數可以表示相應問題（如運費最少問題、車輛數最少問題、路徑最短問題、運輸時間最少問題等）的最優解方程。

（3）約束的處理

遺傳算法中各個染色體對應的解在群體中是占有一定比重的，在遺傳算法迭代運算進程中，如果某個染色體的解不符合約束條件，則會受到遺傳算法的懲罰機制的懲罰，使得其在群體中所占比重越來越小，而相反，可行解則越來越大，通過這樣的一個機制最終可以得出最優解。

（4）遺傳算子

遺傳算子一般包括復制、交叉、變異。復制的目的是保留優良個體，提高全局收斂性和效率；交叉的作用是組合新個體，降低對有效模式的破壞概論；變異的目的，是為了減少基因的缺失和不成熟收斂對結果的影響。

（5）確定最終方案

經過上述遺傳過程后，最終產生性能最優的染色體串。

2 仿真優化方法在VRP上的運用

對VRP的研究，大多停留在理論層面上，這些研究是通過分析問題，運用運籌學知識，用各種數學符號將問題抽象為一系列公式，形成能解決VRP的數學算法。這一類方法稱為解析法，是通過建立某種符合邏輯推理的數學模型來解決VRP，具有精確求解的優點，但不足的是，它完全以數學公式的形式存在，所以它不易于理解，不具備良好的人機交互及可視化，也就無法讓人直觀地感受到所描繪系統是如何運行變化的。相反，仿真方法卻可以直觀方便地處理問題。

仿真方法是利用以計算機和軟件為工具的仿真技術對實際或者設想的系統進行建模并運行，結合某種算法對系統分析，從而得出結果。它結合優化算法來計算模型，則可以求解出最優解。

李先永[6]根據VRP模型，利用EM-Plant仿真軟件構建了相應的仿真模型，同時結合啟發式求解方法計算和優化，從而驗證了該仿真方法的可靠性。劉芳華、楊娟都采用了仿真平臺MATLAB結合遺傳算法對具體的VRP進行參數輸入并運算，得到很好的效果。白雪利用ProModel對某汽車租憑公司的運營方案進行建模優化并評比備選方案，得出最優排程方案。孫姝婷利用 VISSIM微觀仿真軟件對城市配送線路進行優化搜索，對多條配送路線進行評價分析，為配送車輛選出最優配送線路。陳靜靜[7]針對定位—路徑—庫存問題（Location—Routing—Inventory Problem，LRIP）這一物流領域中新的研究熱點問題，采用ExtendSim仿真軟件構造了該問題的模型，并用軟件的遺傳算法對其優化計算，求解出LRIP的最優方案。

3 ExtendSim對VRP建模優化

3.1 運輸問題

運輸問題，解決的是如何組織一個合理的運輸方案，使得物資在供求地運送到需求地所需要的總運費最小。其數學模型如下[8]：

設有m個產地，記為A1,A2,…,Am，生產某種物品，可供應產量分別為a1,a2,…,am；有n個需求地，記為B1,B2,…,Bn，其需求量分別為b1,b2,…,bn；供需平衡，即從第i個產地到j個需求地的單位物品的運費為cij，在滿足各地需要的前提下，求使得運費最小的調運方案。

設xij（i=1,2,…,n）為第i個產地到第j個需求地的運量，則該運輸問題的數學模型可寫為：

3.2 對具體問題建模

設有A1,A2兩個工廠面向B1,B2,B3三個客戶服務，工廠可供應產品數量分別為10,8個單位，客戶需求量分別為5,6,7個單位，A1到B1,B2,B3的每單位產品運費分別為3,2,6個單位，A2到B1,B2,B3的每單位產品運費分別為5,3,8個單位。根據以上信息，如何安排一個運輸計劃，使總運費最少。

對此問題，本文采用ExtendSim仿真軟件，實現了模型的整體構建。其整體結構如圖1所示。

3.3 模塊說明

ExtendSim中的每一個模塊都有其特定的功能，這種功能可以是多個的，另外模塊內部還有能輸入和輸出參數的結構。

首先，上述運輸問題是一個離散事件，需要放置Executive仿真時鐘模塊，讓軟件自動推進事件的發展。兩個Create模塊表示兩個工廠生產產品，Queue模塊表示存放產品的倉庫，Select item out模塊表示選擇不同的送貨路徑，Gate是個路徑開關，與Information、Math、Decition共同作用，具有能根據客戶是否得到滿足而控制路徑開通與否的功能。Get模塊可設置此路徑上每單位產品運費，而Activity模塊則是計算運送給某個B客戶的總成本，整個產品送貨流程以Exit模塊結束。

3.4 優化

以上模型只能直觀地演示系統的運行，還不能對該系統進行計算最優方案，所以要求解最佳方案，必須使用優化模塊Optimizer。

該模塊內置遺傳算法，在本問題中，有六個決策變量，該模塊對這六個量分別隨機編碼成二進制的基因bi（i=1,2,…,n），并使它們連接組成每一個都擁有六個基因的染色體個體，然后模塊自行隨機產生初始種群數，再根據目標函數來確定能評價染色體優劣的適應度函數，在本題中以值越小越優，并接著按照一定概率選擇較優個體淘汰較劣個體進而產生一個種群，然后按一定概率對這種群里的個體進行交叉、變異運算，最終產生新一代的種群，這一代個體的適應度的數值和平均值都比上一代的有了明顯的改進，也就是說向最優值靠攏，接著再繼續對這新一代種群不斷循環運算，經過運算多代直至不能搜尋到更優的解后，就停止運行并顯示最優解了。

圖1 整體模型

在Optimizer的Objectives中，對分別輸入運量的最小值0和最大值（客戶B的需求量），以及表示總費用最少的目標函數：Mincost=yunfei1+yunfei2+yunfei3。

在Optimizer的Constraints中，輸入決策變量的約束條件：

最后，點擊New Run，系統自動運行，最終求解出最優結果，結果顯示，軟件運行了24秒，最小總成本值為82，最優解方案為best行：A1向B1,B2,B3分別運送1、3、6單位的產品；A2向B1,B2,B3分別運送4、3、1單位的產品。

4 結論

本文論述了當前物流領域熱點問題車輛路徑問題及前人對其研究出來的解決方法，這些方法當中以某種算法來建立數學模型的理論研究居多，仿真建模層面上的研究比較少，因此重點探討了仿真優化方法在VRP上的應用，并基于ExtendSim仿真優化軟件對某一VRP問題進行了建模和優化，得出可靠結果，突顯出了仿真軟件界面友好、可視化強、操作簡單易懂、運算速度快的特點，是解決物流領域中VRP的一種有效的途徑。

[1]鄧紅星，韓銳，武慧榮.物流技術[M].哈爾濱：東北林業大學出版社，2010.

[2]紀紅任，游戰清，劉克勝,等.物流經濟學[M].北京：機械工業出版社，2007.

[3]C.G.Dantzig,J.Ramser.The truck dispatching problem[J].Management Science,1959(6)：80-91.

[4]J Holland.Adaptation in Natural and Artificial System[D].The University of Michigan Press,Ann Arbor,MI,1975.

[5]彭揚，伍蓓.物流系統優化與仿真[M].北京：中國物資出版社，2007.

[6]李永先.車輛路徑問題的仿真模型及優化方法研究[D].大連：大連理工大學（博士學位論文），2008.

[7]陳靜靜.基于ExtendSim的定位—路徑—庫存問題的仿真研究[D].哈爾濱：哈爾濱工業大學（碩士學位論文），2010.

[8]熊偉.運籌學[M].2版.北京：機械工業出版社，2009.