基于遺傳算法的車輛路徑問題ExtendSim仿真與優(yōu)化

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

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

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

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

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

所以，運(yùn)輸問題是物流領(lǐng)域中值得研究的關(guān)鍵問題。其中車輛路徑問題（Vehicle Routing Problems，VRP）是運(yùn)輸問題中的一個(gè)熱點(diǎn)問題。該問題是指：在物資流通過程中，每個(gè)需求點(diǎn)的位置和需求量已知，供方如何調(diào)度車輛和安排行車路徑向需方供應(yīng)物資，使得在滿足需方需要的同時(shí)也達(dá)到某些關(guān)鍵目標(biāo)（如車輛數(shù)盡量少、花費(fèi)時(shí)間盡量少、費(fèi)用最少、路程最短等）。

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

1 VRP數(shù)學(xué)模型及遺傳算法

1.1 VRP的基本數(shù)學(xué)模型

VRP的一般描述[5]：

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

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

（3）每個(gè)需求點(diǎn)的需求都只能被同一輛送貨車滿足；

（4）設(shè)定每輛車都是從中心出發(fā)開展配送任務(wù)，任務(wù)完成后再重新回到中心。

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

以上式（1）中，cij表示由點(diǎn)i到點(diǎn)j的運(yùn)輸成本，該函數(shù)為最小運(yùn)輸成本目標(biāo)函數(shù)；（2）為車容量的約束；（3）表示每個(gè)客戶僅有一輛車服務(wù)；（4）、（5）表示到達(dá)和離開某一客戶僅有一輛車。xijk和yki為變量，定義為：

1.2 遺傳算法

本文中的仿真軟件ExtendSim擁有一個(gè)自帶遺傳算法的優(yōu)化模塊。遺傳算法在處理車輛優(yōu)化調(diào)度問題時(shí)，有以下幾個(gè)步驟：

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

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

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

（2）確定目標(biāo)函數(shù)

根據(jù)所研究的具體問題，數(shù)學(xué)模型的目標(biāo)函數(shù)可以表示相應(yīng)問題（如運(yùn)費(fèi)最少問題、車輛數(shù)最少問題、路徑最短問題、運(yùn)輸時(shí)間最少問題等）的最優(yōu)解方程。

（3）約束的處理

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

（4）遺傳算子

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

（5）確定最終方案

經(jīng)過上述遺傳過程后，最終產(chǎn)生性能最優(yōu)的染色體串。

2 仿真優(yōu)化方法在VRP上的運(yùn)用

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

仿真方法是利用以計(jì)算機(jī)和軟件為工具的仿真技術(shù)對(duì)實(shí)際或者設(shè)想的系統(tǒng)進(jìn)行建模并運(yùn)行，結(jié)合某種算法對(duì)系統(tǒng)分析，從而得出結(jié)果。它結(jié)合優(yōu)化算法來計(jì)算模型，則可以求解出最優(yōu)解。

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

3 ExtendSim對(duì)VRP建模優(yōu)化

3.1 運(yùn)輸問題

運(yùn)輸問題，解決的是如何組織一個(gè)合理的運(yùn)輸方案，使得物資在供求地運(yùn)送到需求地所需要的總運(yùn)費(fèi)最小。其數(shù)學(xué)模型如下[8]：

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

設(shè)xij（i=1,2,…,n）為第i個(gè)產(chǎn)地到第j個(gè)需求地的運(yùn)量，則該運(yùn)輸問題的數(shù)學(xué)模型可寫為：

3.2 對(duì)具體問題建模

設(shè)有A1,A2兩個(gè)工廠面向B1,B2,B3三個(gè)客戶服務(wù)，工廠可供應(yīng)產(chǎn)品數(shù)量分別為10,8個(gè)單位，客戶需求量分別為5,6,7個(gè)單位，A1到B1,B2,B3的每單位產(chǎn)品運(yùn)費(fèi)分別為3,2,6個(gè)單位，A2到B1,B2,B3的每單位產(chǎn)品運(yùn)費(fèi)分別為5,3,8個(gè)單位。根據(jù)以上信息，如何安排一個(gè)運(yùn)輸計(jì)劃，使總運(yùn)費(fèi)最少。

對(duì)此問題，本文采用ExtendSim仿真軟件，實(shí)現(xiàn)了模型的整體構(gòu)建。其整體結(jié)構(gòu)如圖1所示。

3.3 模塊說明

ExtendSim中的每一個(gè)模塊都有其特定的功能，這種功能可以是多個(gè)的，另外模塊內(nèi)部還有能輸入和輸出參數(shù)的結(jié)構(gòu)。

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

3.4 優(yōu)化

以上模型只能直觀地演示系統(tǒng)的運(yùn)行，還不能對(duì)該系統(tǒng)進(jìn)行計(jì)算最優(yōu)方案，所以要求解最佳方案，必須使用優(yōu)化模塊Optimizer。

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

圖1 整體模型

在Optimizer的Objectives中，對(duì)分別輸入運(yùn)量的最小值0和最大值（客戶B的需求量），以及表示總費(fèi)用最少的目標(biāo)函數(shù)：Mincost=yunfei1+yunfei2+yunfei3。

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

最后，點(diǎn)擊New Run，系統(tǒng)自動(dòng)運(yùn)行，最終求解出最優(yōu)結(jié)果，結(jié)果顯示，軟件運(yùn)行了24秒，最小總成本值為82，最優(yōu)解方案為best行：A1向B1,B2,B3分別運(yùn)送1、3、6單位的產(chǎn)品；A2向B1,B2,B3分別運(yùn)送4、3、1單位的產(chǎn)品。

4 結(jié)論

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

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

[2]紀(jì)紅任，游戰(zhàn)清，劉克勝,等.物流經(jīng)濟(jì)學(xué)[M].北京：機(jī)械工業(yè)出版社，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]彭揚(yáng)，伍蓓.物流系統(tǒng)優(yōu)化與仿真[M].北京：中國物資出版社，2007.

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

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

[8]熊偉.運(yùn)籌學(xué)[M].2版.北京：機(jī)械工業(yè)出版社，2009.