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

（重慶交通大學(xué) 交通運(yùn)輸學(xué)院，重慶 400074）

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

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

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

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

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

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

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

1.2.2 適應(yīng)函數(shù)。這里以目標(biāo)函數(shù)作為適應(yīng)函數(shù)，即完成一條配送路徑所需的時(shí)間。個(gè)體所對(duì)應(yīng)目標(biāo)函數(shù)值Z即為此個(gè)體的適應(yīng)值。

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

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

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

1.2.5 計(jì)算過程

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

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

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

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

Step 5：對(duì)新的種群進(jìn)行交叉、變異操作；

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

Step 7： gen:=gen+1；

Step 8：若滿足終止條件，轉(zhuǎn)到step 9，否則轉(zhuǎn)到step 3；

Step 9：取種群最優(yōu)的適應(yīng)值benefitgen即為最短時(shí)間，對(duì)應(yīng)個(gè)體bestpopgen為最優(yōu)方案。

2 算例分析

設(shè)路網(wǎng)中共有25個(gè)節(jié)點(diǎn)，利用random函數(shù)生成的隨機(jī)點(diǎn)坐標(biāo)如表1所示。由表1生成的路網(wǎng)拓?fù)鋱D如圖1所示。

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

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

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

3 結(jié) 論

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

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

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

[3] 賀竹磬，孫林巖.動(dòng)態(tài)交通下車輛路徑選擇模型及算法[J].交通運(yùn)輸工程學(xué)報(bào)，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é)點(diǎn)坐標(biāo)

表2 高峰時(shí)段路段擁堵平均行車速度

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

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

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

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

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

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

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