何俊生，史 昊 HE Jun-sheng,SHI Hao

（重慶交通大學 交通運輸學院，重慶 400074）

車輛路徑問題 （Vehicle Routing Problem,VRP）在交通運輸、工業(yè)生產(chǎn)等各領域應用廣泛，目前基于VRP問題研究的成果很多，盡管對于該類問題的求解方法層出不窮[1-5]，其中不乏一些關于末端物流配送問題的管理學模型成果[6]，但是對于這類問題的量化研究成果尚未見文獻報道。

末端配送是指送達給消費者的物流活動，是以滿足配送環(huán)節(jié)的終端 （客戶）為直接目的。隨著社會經(jīng)濟活動越來越以消費者的需求為中心， “用戶第一”的基本觀念深入人心，因此末端物流越來越受到重視。能否快速送達是顧客衡量快遞公司的一個重要標準。而末端物流配送需要考慮的很重要的一點則是最短時間配送路徑，因此本文對這一問題進行深入研究。

1 城市末端物流配送路徑模型

1.1 城市末端物流配送路徑模型建立。為了不失一般性，將快遞企業(yè)抽象為配送中心，將各個顧客抽象為配送節(jié)點。模型建立的目的是為了求得配送中心到各個需求節(jié)點的總配送時間最短。變量dij表示節(jié)點i到節(jié)點j的距離；若從i到j無路徑到達則用dij=∞表示。變量vijTi（）表示Ti時刻車輛從節(jié)點i到節(jié)點j的行駛速度。變量tijTi（）表示從節(jié)點i到節(jié)點j所用的時間，同理，若從i到j無路徑則用tijTi（）=∞表示；其中Ti表示到達節(jié)點i的時刻，從配送中心出發(fā)的時刻用T0表示。tijTi（）可用公式tijTi（）=dijvijTi（）計算得到。令物流配送中心某車配送的客戶集合為N（其中0代表物流配送中心，配送節(jié)點的個數(shù)為n），Ti（）,i,j∈N為Ti時刻從i點出發(fā)到j點的最短行駛時間。則城市末端物流配送問題數(shù)學模型如下：

式 （2）到式 （6）為約束條件。xij為決策變量，意為判定節(jié)點i與節(jié)點j之間是否有可通行路徑；如果節(jié)點i和節(jié)點j在可通行路徑上i≠（）j，則xij=1，否則xij=0。式 （2）和式 （3）是平衡條件，表明路徑的可逆性；式 （4）表示對每個節(jié)點的配送為一次且僅為一次，若為配送中心，則表示車輛離開配送中心后完成配送任務仍回到配送中心；式 （5）表示從節(jié)點j出發(fā)的時刻；式 （6）為確保配送回路通過配送中心。

1.2 城市末端物流配送路徑模型的遺傳算法。VRP問題屬于NP-Hard問題，解決這類問題多用啟發(fā)式算法。遺傳算法是美國密執(zhí)安大學Holland教授受生物模擬技術啟發(fā)，創(chuàng)造出的一種適合于復雜系統(tǒng)計算優(yōu)化的啟發(fā)式算法。該算法具有較強的魯棒性，廣泛應用于車輛路徑問題的尋優(yōu)計算中，并在多數(shù)情況下能得到比較滿意的解。1.2.1 編碼。本文采用自然編碼方式。例如有6個配送節(jié)點，其編號分為為1到6號。首先將需要配送的節(jié)點進行隨機排列，如假設0為配送中心，這里可在染色體兩邊添加0，形成染色體；就形成了0與0之間的一條配送路徑 （從配送中心出發(fā)，最后回到配送中心），即0→1→3→4→6→5→2→0。

通常的研究認為節(jié)點間由直線相連[7-11]，但更多情況下節(jié)點與節(jié)點間是由路網(wǎng)相連的，即從節(jié)點到節(jié)點的路徑不唯一；因此單一的認為節(jié)點間由直線組成是不符合實際的，本文從節(jié)點間由路網(wǎng)組成出發(fā)，兩點間的路網(wǎng)最短時間路徑由Dijkstra算法求得。

1.2.2 適應函數(shù)。這里以目標函數(shù)作為適應函數(shù)，即完成一條配送路徑所需的時間。個體所對應目標函數(shù)值Z即為此個體的適應值。

1.2.3 選擇操作。取種群各染色體適應值倒數(shù)除以倒數(shù)之和，作為各染色體被選擇的概率；采用輪盤賭的方式選擇染色體復制到新種群，直到新種群規(guī)模與父代相同為止。

1.2.4 交叉、變異操作。本文采用部分映射交叉法，從種群第一個染色體開始，兩兩成組，對每組染色體，隨機生成數(shù)若小于等于交叉概率pc，則染色體兩端0不動，取中間隨機一段進行交叉互換，否則，該組染色體不進行交叉操作。對于交叉操作，染色體若有與交叉區(qū)段沖突數(shù)字 （下劃線表示）， 兩染色體互相一一對應交換，交叉結束。例如：

變異操作是對種群每一個染色體，隨機生成數(shù)若小于等于變異概率pm，則染色體兩端0不動，隨機取染色體兩個數(shù)字并交換位置，形成新染色體，否則，該染色體不進行變異操作。

1.2.5 計算過程

Step 1：各參數(shù)初始化，并設置達到最大迭代次數(shù)gen max為算法終止條件；

Step 2：gen:=1時，隨機產(chǎn)生初始群體chromgen；

Step 3：計算種群各個體的適應值，并選出得到最優(yōu)的適應值和最優(yōu)的個體；

Step 4：根據(jù)輪盤賭選擇法，復制染色體生成新的種群；

Step 5：對新的種群進行交叉、變異操作；

Step 6：采用精英策略，取上一代最優(yōu)個體替代新一代對應位置染色體；

Step 7： gen:=gen+1；

Step 8：若滿足終止條件，轉到step 9，否則轉到step 3；

Step 9：取種群最優(yōu)的適應值benefitgen即為最短時間，對應個體bestpopgen為最優(yōu)方案。

2 算例分析

設路網(wǎng)中共有25個節(jié)點，利用random函數(shù)生成的隨機點坐標如表1所示。由表1生成的路網(wǎng)拓撲圖如圖1所示。

其中的數(shù)字為各個節(jié)點編號，紅色方塊表示配送中心，紫紅色圓形表示各個配送點。

考慮到實際情況，在不同時段不同路段的行車速度不同。故設所有路段在非高峰時段行車速度為40km/h，某些路段高峰時段 （7:30-9:00，17:00-19:00）平均行車速度如表2所示。

若上午8:00從節(jié)點6發(fā)車，設種群規(guī)模為40，迭代次數(shù)為100次。在CPU2.0GHz，內(nèi)存2GB的計算機上多次利用遺傳算法求出的最短時間為1小時54分鐘，其中一條行駛路徑為：6→17→12→3→11→7→24→16→19→14→8→13→15→22→9→10→6 （見圖 2）。

3 結 論

本文討論了實時路網(wǎng)下的一類直接面對消費者的末端物流配送問題，建立了末端物流配送路徑模型。通過結合Dijkstra算法的優(yōu)化遺傳算法求得最優(yōu)解，經(jīng)過數(shù)值算例的驗證，該模型更加符合物流配送的實際情況，該算法能在實時路網(wǎng)環(huán)境下有效地找到最短時間路徑，減少車輛行駛的總時間。進一步的研究工作可以從多車輛路徑實時路網(wǎng)末端物流配送路徑建模及模型快速求解優(yōu)化算法等方面展開。

[1] 孫國華.基于真實路網(wǎng)的車輛路徑問題研究[J].物流技術，2011,30(1):43-45.

[2] 韓世蓮.帶時間窗的多目標配送線路選擇問題的目標規(guī)劃模型[J].物流技術，2008,184(1):44-45.

[3] 賀竹磬，孫林巖.動態(tài)交通下車輛路徑選擇模型及算法[J].交通運輸工程學報，2007,7(1):111-115.

[4] Babak Farhang Moghadam,Seyed Mohammad Seyedhosseini.A particle swarm approach to solve vehicle routing problem with uncertain demand[J].International Journal of Industrial Engineering Computations,2010(1):55-66.

表1 路網(wǎng)節(jié)點坐標

表2 高峰時段路段擁堵平均行車速度

[5] Yiyo Kuo,Chi-Chang Wang.Optimizing the VRP by minimizing fuel consumption[J].Management of Environmental Quality,2011,4(22):440-450.

[6] 藍伯雄，張躍.一種新型的末端物流配送服務模式[J].管理世界，2003(6):147-148.

[7] 郎茂祥.基于遺傳算法的物流配送路徑優(yōu)化問題的研究[J].中國公路學報，2002(3):76-79.

[8] 宋少忠，孔繁森.時變路網(wǎng)下VRP準時路徑的選擇[J].吉林大學學報 （理學版），2012,3(50):309-314.

[9] 洪聯(lián)系.帶時間窗口動態(tài)車輛路徑規(guī)劃模型及其求解算法[J].計算機工程與應用，2012,48(4):244-248.

[10] 周長峰，譚躍進，廖良才.實時條件下多車輛路徑與調(diào)度[J].系統(tǒng)工程，2006,5(24):35-39.

[11] 劉勇，崔丙謀，王小東.物流配送路徑優(yōu)化問題的模型及改進混合算法[J].物流科技，2008(4):26-30.