基于兩階段求解的動(dòng)態(tài)車(chē)輛路徑問(wèn)題研究

陳　誠(chéng)，邱榮祖

(福建農(nóng)林大學(xué)交通與土木工程學(xué)院，福建 福州 350002)

?

基于兩階段求解的動(dòng)態(tài)車(chē)輛路徑問(wèn)題研究

陳誠(chéng)，邱榮祖

(福建農(nóng)林大學(xué)交通與土木工程學(xué)院，福建 福州 350002)

[摘要]采用兩階段求解思想，通過(guò)設(shè)置定時(shí)間隔，將動(dòng)態(tài)信息轉(zhuǎn)化成靜態(tài)信息，從而實(shí)現(xiàn)對(duì)動(dòng)態(tài)車(chē)輛路徑問(wèn)題的求解.分別建立了初始優(yōu)化和實(shí)時(shí)優(yōu)化階段的數(shù)學(xué)模型，以節(jié)約算法解為初始解，利用禁忌搜索算法完成初始優(yōu)化階段的車(chē)輛路徑問(wèn)題求解；在實(shí)時(shí)優(yōu)化階段，分別對(duì)節(jié)約算法和禁忌搜索算法進(jìn)行適當(dāng)修正后再進(jìn)行求解.利用數(shù)值測(cè)試實(shí)驗(yàn)對(duì)客戶(hù)不同地理位置分布下定時(shí)間隔的設(shè)置進(jìn)行測(cè)試分析.結(jié)果表明，該算法簡(jiǎn)單明了，易于實(shí)現(xiàn).此外，客戶(hù)的地理位置分布不同，對(duì)定時(shí)間隔的敏感性也不同，混合分布最為敏感，其次是隨機(jī)分布，集聚分布最不敏感；最后，給出了相應(yīng)的累計(jì)服務(wù)客戶(hù)數(shù)量曲線，并結(jié)合車(chē)輛總行駛距離，明確了不同客戶(hù)位置分布下的較優(yōu)定時(shí)間隔設(shè)置.

[關(guān)鍵詞]動(dòng)態(tài)車(chē)輛問(wèn)題；兩階段求解；定時(shí)間隔；禁忌搜索

0引言

車(chē)輛路徑問(wèn)題(vehicle routing problem，VRP)自1959年Dantzig和Ramser提出后[1]，成為了國(guó)內(nèi)外眾多學(xué)者研究的熱點(diǎn).在過(guò)去幾十年中，對(duì)該問(wèn)題的研究取得了豐富的研究成果.然而在這些研究成果中，大多是在靜態(tài)的環(huán)境下進(jìn)行的，即靜態(tài)VRP(Vehicle Routing Problem)，但這與現(xiàn)實(shí)環(huán)境動(dòng)態(tài)變化的特點(diǎn)不相符.因此，為了更好地解決實(shí)際問(wèn)題，有必要對(duì)動(dòng)態(tài)VRP進(jìn)行研究.

對(duì)動(dòng)態(tài)車(chē)輛路徑問(wèn)題研究，最早可以追溯到20世紀(jì)70年代Wilson對(duì)動(dòng)態(tài)dial-a-ride問(wèn)題的研究[2].動(dòng)態(tài)車(chē)輛路徑問(wèn)題的一大特征在于與問(wèn)題相關(guān)的信息是隨時(shí)間的推移而出現(xiàn)或發(fā)生變化的.這一特征表明了所研究對(duì)象的復(fù)雜性很大一部分取決于所考慮的動(dòng)態(tài)因素?cái)?shù)目的多寡.若綜合考慮各種動(dòng)態(tài)信息對(duì)所研究問(wèn)題的影響，將會(huì)使問(wèn)題變得十分復(fù)雜、難解.大多數(shù)學(xué)者在研究中往往只考慮少數(shù)幾種動(dòng)態(tài)因素對(duì)問(wèn)題的影響.例如，Gendrea[3]等研究了客戶(hù)請(qǐng)求新增的實(shí)時(shí)車(chē)輛調(diào)度問(wèn)題；Zhu[4]等研究了車(chē)輛旅行時(shí)間變化的動(dòng)態(tài)車(chē)輛調(diào)度問(wèn)題，建立了問(wèn)題的數(shù)學(xué)模型，并為其設(shè)計(jì)了爬山算法；Haghani[5]等研究了考慮即時(shí)服務(wù)要求和時(shí)變車(chē)輛旅行時(shí)間的動(dòng)態(tài)車(chē)輛路徑問(wèn)題[2]；Azi[6]等研究了客戶(hù)需求動(dòng)態(tài)變化的車(chē)輛路徑問(wèn)題，決策變量包括是否接受客戶(hù)請(qǐng)求.動(dòng)態(tài)車(chē)輛路徑問(wèn)題的求解難度源于對(duì)動(dòng)態(tài)信息的處理，有些學(xué)者采用判斷準(zhǔn)則，將新客戶(hù)添加到已經(jīng)制定的調(diào)度方案中[7-8]，有些學(xué)者采用現(xiàn)代優(yōu)化算法重新進(jìn)行整個(gè)調(diào)度方案的優(yōu)化[9-10]，基本思路都是將動(dòng)態(tài)信息轉(zhuǎn)換成靜態(tài)信息再進(jìn)行路徑構(gòu)造，并分別提出了“時(shí)間軸”和“時(shí)間片”的概念，以明確動(dòng)態(tài)信息處理的時(shí)間間隔.可以說(shuō)時(shí)間間隔的設(shè)定是動(dòng)態(tài)信息分批處理過(guò)程中的重要參數(shù)，因?yàn)檫^(guò)短的時(shí)間間隔會(huì)增加求解負(fù)擔(dān)，而過(guò)長(zhǎng)的時(shí)間間隔既不利于客戶(hù)的實(shí)時(shí)響應(yīng)，也會(huì)增加配送成本，在已有研究中缺乏該參數(shù)對(duì)求解結(jié)果影響的研究.

本文通過(guò)預(yù)優(yōu)化和實(shí)時(shí)優(yōu)化相結(jié)合的方法研究動(dòng)態(tài)車(chē)輛路徑問(wèn)題，設(shè)置時(shí)間間隔及關(guān)鍵點(diǎn)將動(dòng)態(tài)信息靜態(tài)化，分別建立了兩階段的數(shù)學(xué)模型；采用節(jié)約算法構(gòu)造初始解，禁忌搜索算法尋優(yōu)的方法進(jìn)行預(yù)優(yōu)化階段車(chē)輛路徑問(wèn)題的求解，在仿真實(shí)驗(yàn)階段，采用隨機(jī)分布、集聚分布和混合分布三種不同分布地理位置的客戶(hù)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明本文提出的求解方法的可行性與合理性，同時(shí)還分析了定時(shí)間隔設(shè)置對(duì)求解結(jié)果的影響，在考慮客戶(hù)服務(wù)水平的前提下，明確了客戶(hù)地理位置不同分布下定時(shí)間隔的優(yōu)化設(shè)置.

1動(dòng)態(tài)車(chē)輛路徑問(wèn)題描述

本文研究的動(dòng)態(tài)車(chē)輛路徑問(wèn)題可以描述如下：某一配送中心有K輛車(chē)型相同且最大負(fù)載能力均為Qk的車(chē)輛，中心每天需滿足客戶(hù)的配送需求，客戶(hù)i的位置及其需求量qi的出現(xiàn)事先未知，每個(gè)客戶(hù)只能被一輛車(chē)訪問(wèn)一次，車(chē)輛完成運(yùn)輸任務(wù)后需回到配送中心；伴隨時(shí)間的改變，客戶(hù)需求可能發(fā)生動(dòng)態(tài)變化，配送中心需要進(jìn)行合理的車(chē)輛調(diào)度以適應(yīng)客戶(hù)及其需求的動(dòng)態(tài)變化.如圖1所示，配送中心首先為車(chē)輛規(guī)劃一條路線，但是在車(chē)輛運(yùn)行過(guò)程中，由于客戶(hù)的動(dòng)態(tài)變化，車(chē)輛的運(yùn)行路線也將發(fā)生相應(yīng)的變化.本文中考慮的客戶(hù)動(dòng)態(tài)變化主要考慮客戶(hù)需求的變化.

2求解思路

對(duì)于車(chē)輛路徑問(wèn)題中的動(dòng)態(tài)因素，主要求解思路之一是將動(dòng)態(tài)因素轉(zhuǎn)變成靜態(tài)因素再進(jìn)行求解[10].通過(guò)定時(shí)間隔和關(guān)鍵點(diǎn)的設(shè)置將動(dòng)態(tài)因素靜態(tài)化，對(duì)靜態(tài)化后車(chē)輛路徑問(wèn)題進(jìn)行多次實(shí)時(shí)求解，從而實(shí)現(xiàn)對(duì)動(dòng)態(tài)車(chē)輛路徑問(wèn)題的實(shí)時(shí)優(yōu)化，即兩階段求解，也是目前的主流求解思路[11-13].

2.1　定時(shí)間隔

把按照一定原則劃分的小時(shí)間段稱(chēng)為定時(shí)間隔，每個(gè)間隔結(jié)束的時(shí)刻記為對(duì)應(yīng)的時(shí)刻1，…，n(初始優(yōu)化階段記為時(shí)刻0).因此在初始時(shí)刻對(duì)已知客戶(hù)按靜態(tài)車(chē)輛路徑問(wèn)題進(jìn)行優(yōu)化，車(chē)輛開(kāi)始按初始優(yōu)化結(jié)果開(kāi)始運(yùn)行，之后在每個(gè)定時(shí)間隔結(jié)束時(shí)進(jìn)行實(shí)時(shí)優(yōu)化，在下一個(gè)定時(shí)間隔開(kāi)始時(shí)，所有車(chē)輛按實(shí)時(shí)優(yōu)化結(jié)果繼續(xù)運(yùn)行.

2.2　關(guān)鍵點(diǎn)

在實(shí)時(shí)優(yōu)化階段，執(zhí)行初始行駛計(jì)劃的車(chē)輛已經(jīng)離開(kāi)配送中心，可能已經(jīng)滿足部分客戶(hù)的需求，此時(shí)每輛車(chē)的剩余載重都不同，且車(chē)輛所在位置不同，因此將在定時(shí)間隔結(jié)束時(shí)，已派出的車(chē)輛所在的位置定義為關(guān)鍵點(diǎn)[16].關(guān)鍵點(diǎn)只發(fā)出對(duì)應(yīng)的車(chē)輛，而不接受其他車(chē)輛的訪問(wèn)，于是實(shí)時(shí)優(yōu)化階段的車(chē)輛路徑問(wèn)題可以看成是多配送中心車(chē)輛路徑問(wèn)題，限制位于關(guān)鍵點(diǎn)的虛擬配送中心發(fā)且只能發(fā)出一輛車(chē)，容量為定時(shí)間隔結(jié)束時(shí)的剩余容量，且最后必須返回配送中心.

本文動(dòng)態(tài)車(chē)輛路徑問(wèn)題的具體求解思路如圖2所示.

3數(shù)學(xué)模型

對(duì)于動(dòng)態(tài)車(chē)輛路徑問(wèn)題，分別建立其初始優(yōu)化階段和實(shí)時(shí)優(yōu)化階段的數(shù)學(xué)模型.模型中：0為配送中心；L為靜態(tài)客戶(hù)集合；K0為初始車(chē)輛集合；K1為定時(shí)間隔結(jié)束時(shí)已派出車(chē)輛集合；N為車(chē)輛路徑中仍未被服務(wù)的對(duì)象和新增的客戶(hù)集合；T為實(shí)時(shí)優(yōu)化階段增派的車(chē)輛數(shù)；M表示關(guān)鍵點(diǎn)集合；Qk為車(chē)輛k的最大載質(zhì)量；qi為客戶(hù)i的需求量；Qik為車(chē)輛k從需求點(diǎn)i出發(fā)時(shí)的載質(zhì)量，若車(chē)輛k從配送中心出發(fā)則Q0k=Qk；cij為客戶(hù)i與客戶(hù)j之間的距離；xijk為0-1變量，若車(chē)輛k從客戶(hù)i行駛至客戶(hù)，則等于1，否則等于0；yik為0-1變量，若客戶(hù)i由車(chē)輛k服務(wù)j，則等于1，否則等于0；

3.1　初始優(yōu)化階段數(shù)學(xué)模型

總費(fèi)用最小的目標(biāo)函數(shù)如式(1)所示，表示車(chē)輛總行駛路徑最短.

(1)

3.2　實(shí)時(shí)優(yōu)化階段數(shù)學(xué)模型

目標(biāo)函數(shù)如式(2)所示，保證在滿足當(dāng)前所有客戶(hù)需求的前提下，從關(guān)鍵點(diǎn)及配送中心出發(fā)的車(chē)輛，行駛的總路徑最短.

(2)

4動(dòng)態(tài)車(chē)輛路徑問(wèn)題兩階段求解算法

以上設(shè)計(jì)的兩階段求解策略中涉及了兩個(gè)階段不同的路徑問(wèn)題的求解，第一階段即靜態(tài)車(chē)輛路徑問(wèn)題的求解，第二階段類(lèi)似于多配送中心車(chē)輛路徑問(wèn)題的求解，而禁忌搜索算法在快速求解車(chē)輛路徑問(wèn)題上有著十分明顯的優(yōu)勢(shì)，故本研究采用禁忌搜索算法進(jìn)行兩個(gè)階段的車(chē)輛路徑問(wèn)題的求解.

4.1　初始優(yōu)化階段禁忌搜索算法設(shè)計(jì)

初始優(yōu)化階段的車(chē)輛路徑問(wèn)題為靜態(tài)車(chē)輛路徑問(wèn)題，本文采用的禁忌搜索求解算法中的主要要素及參數(shù)設(shè)置如下：

1)解的表示采用客戶(hù)直接排列的方法；2)初始解的生成方法采用節(jié)約算法進(jìn)行；3)將目標(biāo)函數(shù)值作為解的評(píng)價(jià)標(biāo)準(zhǔn)；4)同時(shí)采用任意兩點(diǎn)交換和將一點(diǎn)插入至另一點(diǎn)后的方法進(jìn)行鄰域構(gòu)造；5)將每一次迭代得到的最好解作為禁忌對(duì)象放入禁忌表中；6)根據(jù)問(wèn)題的規(guī)模選取一個(gè)固定的長(zhǎng)度為禁忌長(zhǎng)度；7)終止準(zhǔn)則采取給定一個(gè)最大迭代步數(shù).

4.2　實(shí)時(shí)優(yōu)化階段的禁忌搜索算法設(shè)計(jì)

實(shí)時(shí)優(yōu)化階段的車(chē)輛路徑問(wèn)題的禁忌搜索算法求解流程及主要參數(shù)同初始優(yōu)化階段，但關(guān)鍵點(diǎn)(虛擬配送中心)做如下處理：

1)配送中心0至虛擬配送中心的距離設(shè)置為零，虛擬配送中心發(fā)出車(chē)輛的容量為原車(chē)輛容量減去關(guān)鍵點(diǎn)前路線上所有客戶(hù)的需求量之和.

2)節(jié)約算法階段，首先將虛擬配送中心的一端和配送中心相連，這樣若虛擬配送中心的另一端和客戶(hù)端相連后，虛擬配送中心就成為了路線的內(nèi)點(diǎn)，不能再和其他點(diǎn)相連；其次將兩個(gè)虛擬配送中心的節(jié)約值設(shè)為零，保證兩個(gè)虛擬配送中心不會(huì)相連.

3)禁忌搜索算法編碼階段，虛擬配送中心按客戶(hù)點(diǎn)方式直接排列；解碼階段，按客戶(hù)排列順序?qū)⒖蛻?hù)加入到路線中，遇到虛擬配送中心則重新開(kāi)始一條新路線，從而保證虛擬配送中心發(fā)且只能發(fā)出一輛車(chē)，而不能接受其他車(chē)輛的訪問(wèn).

5仿真實(shí)驗(yàn)與討論

為了評(píng)價(jià)客戶(hù)不同地理位置分布對(duì)求解結(jié)果的影響，采用soloman的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)(R101，C101，RC101)，因時(shí)間窗不在本文研究范圍內(nèi)，故去掉測(cè)試數(shù)據(jù)中的時(shí)間窗數(shù)據(jù)；但是因需采集定時(shí)間隔結(jié)束關(guān)鍵點(diǎn)的信息，因此保留客戶(hù)服務(wù)時(shí)間數(shù)據(jù).三類(lèi)數(shù)據(jù)中的地理位置均在100×100的歐幾里得平面坐標(biāo)系中產(chǎn)生，其中，R類(lèi)數(shù)據(jù)中的客戶(hù)地理位置為隨機(jī)生成；C類(lèi)數(shù)據(jù)中的客戶(hù)地理位置具有顯著的集聚特征；RC類(lèi)數(shù)據(jù)的客戶(hù)地理位置同時(shí)具有隨機(jī)分布和集聚分布兩種特征.各類(lèi)客戶(hù)位置分布如圖3所示.

在將動(dòng)態(tài)信息靜態(tài)化的過(guò)程中，定時(shí)間隔是一個(gè)關(guān)鍵因素.若定時(shí)間隔短，則每次優(yōu)化時(shí)客戶(hù)數(shù)較少，能取得較好的優(yōu)化結(jié)果，但同時(shí)由于兩次優(yōu)化間隔短，兩次優(yōu)化的客戶(hù)信息及關(guān)鍵點(diǎn)信息變化不大，也可能造成計(jì)算時(shí)間和計(jì)算資源的浪費(fèi)；若定時(shí)間隔長(zhǎng)，則路徑優(yōu)化時(shí)無(wú)法對(duì)客戶(hù)信息的變化做出最及時(shí)的反應(yīng)，同樣無(wú)法做出最佳的服務(wù)決策.因此，對(duì)于測(cè)試數(shù)據(jù)中的100個(gè)客戶(hù)點(diǎn)，分別設(shè)置24、48、60、120、40的定時(shí)間隔.定時(shí)間隔為24時(shí)，靜態(tài)客戶(hù)數(shù)為10，每個(gè)定時(shí)間隔內(nèi)出現(xiàn)10個(gè)客戶(hù)；定時(shí)間隔為48時(shí)，靜態(tài)客戶(hù)數(shù)為20，每個(gè)定時(shí)間隔內(nèi)出現(xiàn)20個(gè)客戶(hù)；定時(shí)間隔為60時(shí)，靜態(tài)客戶(hù)數(shù)為25，每個(gè)定時(shí)間隔內(nèi)出現(xiàn)25個(gè)客戶(hù)；定時(shí)間隔為120時(shí)，靜態(tài)客戶(hù)數(shù)為50，每個(gè)定時(shí)間隔內(nèi)出現(xiàn)50個(gè)客戶(hù)；定時(shí)間隔為240時(shí)，每個(gè)定時(shí)間隔出現(xiàn)100個(gè)客戶(hù)，即靜態(tài)問(wèn)題.實(shí)驗(yàn)采用C++語(yǔ)言編程，在Inter Core(TM)i7-3610QM CPU2.3GHz，windows7的主機(jī)上運(yùn)行.

不同定時(shí)間隔的求解結(jié)果不同,如表1所示.首先，在R101中，最好情況與最壞情況解的差距為8.68%；在C101中，最好情況與最壞情況解的差距為3.37%；在RC101中，該值為15.50%.表明：1)客戶(hù)的不同地理位置分布對(duì)定時(shí)間隔的敏感性不同，混合分布最為敏感，其次是隨機(jī)分布，集聚分布最不敏感.2)總行駛距離長(zhǎng)短也并不嚴(yán)格與定時(shí)間隔的大小成反比關(guān)系，如在R101中，定時(shí)間隔24就取得了比定時(shí)間隔48要短的總行駛距離，而在C101中，定時(shí)間隔24、48、60、120所取得的總行駛距離幾乎一致，差異量小于0.43%，在RC101中，也因問(wèn)題規(guī)模越小優(yōu)化效果越好的原因，定時(shí)間隔120反而取得了比定時(shí)間隔240(全部靜態(tài))要短的總行駛距離.3)由于車(chē)輛發(fā)出后，只有在剩余容量不足時(shí)才返回配送中心，故車(chē)輛數(shù)在不同的定時(shí)間隔設(shè)置下并無(wú)差異.因此，若客戶(hù)地理位置為集聚分布時(shí)，定時(shí)間隔可以設(shè)置的稍微大些，能在節(jié)約優(yōu)化計(jì)算時(shí)間和資源的同時(shí)幾乎不影響車(chē)輛的總行駛路徑；而當(dāng)客戶(hù)地理位置為隨機(jī)分布，尤其是當(dāng)其為混合分布時(shí)，則需要慎重制定合適的定時(shí)間隔.

表1　不同定時(shí)間隔的仿真結(jié)果

圖4給出了不同客戶(hù)地理位置分布下不同定時(shí)間隔設(shè)置時(shí)累計(jì)客戶(hù)服務(wù)數(shù)量曲線，每一時(shí)間間隔取最小的定時(shí)間隔24作為單位.累計(jì)客戶(hù)服務(wù)數(shù)曲線表達(dá)在不同時(shí)刻已經(jīng)被服務(wù)的客戶(hù)數(shù)量，可以作為衡量服務(wù)質(zhì)量的指標(biāo)之一.在某一時(shí)刻，累計(jì)服務(wù)客戶(hù)數(shù)越多，說(shuō)明在這一時(shí)刻已經(jīng)被服務(wù)的客戶(hù)數(shù)量越多.總的來(lái)說(shuō)，在同一時(shí)刻，定時(shí)間隔越小的累計(jì)客戶(hù)服務(wù)數(shù)越大，這是因?yàn)槎〞r(shí)間隔設(shè)置的越小時(shí)，初始服務(wù)路線越早制定，服務(wù)車(chē)輛也就越早出發(fā).但是如圖4所示，不同定時(shí)間隔的累計(jì)客戶(hù)服務(wù)數(shù)量曲線出現(xiàn)了交疊的現(xiàn)象.在R101中，定時(shí)間隔48和定時(shí)間隔60的累計(jì)服務(wù)客戶(hù)數(shù)不相上下，在第16個(gè)時(shí)間間隔后，定時(shí)間隔60的累計(jì)服務(wù)客戶(hù)數(shù)就超過(guò)了定時(shí)間隔48的累計(jì)服務(wù)客戶(hù)數(shù).結(jié)合總行駛距離來(lái)看，顯然在R101中，定時(shí)間隔設(shè)置為60優(yōu)于48.在C101中，定時(shí)間隔24、48、60的累計(jì)服務(wù)客戶(hù)數(shù)都比較接近，和總行駛距離指標(biāo)顯示的結(jié)果類(lèi)似，客戶(hù)地理位置集聚分布時(shí)，對(duì)定時(shí)間隔的設(shè)置不敏感.不過(guò)在R101和C101中，定時(shí)間隔24的累計(jì)客戶(hù)服務(wù)數(shù)一直保持在其他定時(shí)間隔之上，呈現(xiàn)出一定的優(yōu)越性.而在RC101中，除定時(shí)間隔240(全部靜態(tài))外，其余4條曲線均十分接近，定時(shí)間隔24、48和60的曲線出現(xiàn)了互相交疊的情況，在第12個(gè)時(shí)間間隔后，定時(shí)間隔48的累計(jì)服務(wù)客戶(hù)數(shù)就超越了定時(shí)間隔24的累計(jì)服務(wù)客戶(hù)數(shù)，并且定時(shí)間隔60的累計(jì)服務(wù)客戶(hù)數(shù)也與定時(shí)間隔24的十分接近，因此當(dāng)客戶(hù)地理位置為混合分布時(shí)，由于總行駛距離上的優(yōu)勢(shì)定時(shí)間隔48和60要優(yōu)于定時(shí)間隔24.

6結(jié)束語(yǔ)

本文研究了一類(lèi)動(dòng)態(tài)車(chē)輛路徑問(wèn)題，首先，通過(guò)定時(shí)間隔策略將動(dòng)態(tài)車(chē)輛路徑問(wèn)題轉(zhuǎn)化為一系列相應(yīng)的靜態(tài)車(chē)輛路徑問(wèn)題，分別建立該問(wèn)題初始優(yōu)化階段和實(shí)時(shí)動(dòng)態(tài)優(yōu)化階段的數(shù)學(xué)模型；其次，設(shè)計(jì)了模型求解禁忌搜索算法，為了加快尋優(yōu)速度，利用節(jié)約算法為禁忌搜索算法確定初始解，并通過(guò)對(duì)節(jié)約算法中關(guān)鍵點(diǎn)的限制以及禁忌搜索算法中解碼過(guò)程的設(shè)置，使設(shè)計(jì)的禁忌搜索算法能適用于實(shí)時(shí)優(yōu)化階段的求解；最后，通過(guò)對(duì)模型的求解，分析了不同客戶(hù)地理位置分布、不同定時(shí)間隔設(shè)置下的車(chē)輛總行駛距離和累計(jì)服務(wù)客戶(hù)數(shù)量曲線，實(shí)驗(yàn)結(jié)果表明，在客戶(hù)地理位置不同分布時(shí)，設(shè)置不同的定時(shí)間隔對(duì)車(chē)輛總行駛距離的影響不同，影響最小的是集聚分布，其次是隨機(jī)分布，對(duì)混合分布的影響最大；結(jié)合累計(jì)服務(wù)客戶(hù)數(shù)量曲線，得出了算例R101取定時(shí)間隔60較優(yōu)，算例C101取定時(shí)間隔24較優(yōu)，算例RC101取定時(shí)間隔48較優(yōu)的結(jié)論.

[參考文獻(xiàn)]

[1]DANTZING G B，RAMSER J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.

[2]郎茂祥.配送車(chē)輛優(yōu)化調(diào)度模型與算法[M].北京：電子工業(yè)出版社，2009.

[3]GENDREAU M,GUERTIN F,POTVIN J Y，et al.Parallel tabu search for real-time vehicle routing and dispatching[J].Transportation Science，1999，33(4):381-390.

[4]ZHU K Q，ONG K L.A Reactive Method for Real Time Dynamic Vehicle Routing Problem[C].Vancouver：Proceedings of 12th IEEE International Conference on Tools with Artificial Intelligence，2000:176-180.

[5]HAGHANI A,JUNG S.A dynamic vehicle routing problem with time-dependent travel times[J].Computers & Operations Research，2005，32(11):2959-2986.

[6]ZI N,GENDREAU M,POTVIN J Y.A dynamic vehicle routing problem with multiple delivery routes[J].Annals of Operations Research，2012，199(1):103-122.

[7]陳久梅，張旭梅，肖劍，等.隨機(jī)動(dòng)態(tài)裝卸混合問(wèn)題的分區(qū)求解策略[J].管理科學(xué)學(xué)報(bào)，2012，15(1):43-53.

[8]熊浩，符卓，鄢慧麗.動(dòng)態(tài)車(chē)輛路徑問(wèn)題的隱分期靈活分批策略[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2013,41(5):676-679.

[9]葛顯龍，王旭，鄧?yán)?基于聯(lián)合配送的開(kāi)放式動(dòng)態(tài)車(chē)輛路徑問(wèn)題及算法研究[J].管理工程學(xué)報(bào),2013,27(3):60-68.

[10]王仁民，閉應(yīng)洲，劉阿寧，等.改進(jìn)變鄰域搜索算法求解動(dòng)態(tài)車(chē)輛路徑問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用，2014,50(2):237-241.

[11]PILLAC V,GENDREAU M,GUéRET C，et al.A review of dynamic vehicle routing problems[J].European Journal of Operational Research，2013,225(1):1-11.

[12]李兵，鄭四發(fā)，曹劍東，等．求解客戶(hù)需求動(dòng)態(tài)變化的車(chē)輛路徑規(guī)劃方法[J]．交通運(yùn)輸工程學(xué)報(bào)，2007，7(1):106-110．

[13]張景玲，趙燕偉，王海燕，等．多車(chē)型動(dòng)態(tài)需求車(chē)輛路徑問(wèn)題建模及優(yōu)化[J]．計(jì)算機(jī)集成制造系統(tǒng)，2010，16(3):543-550.

[14]王旭，葛顯龍，代應(yīng).基于兩階段求解算法的動(dòng)態(tài)車(chē)輛調(diào)度問(wèn)題研究[J].控制與決策，2012，27(2):175-181.

(責(zé)任編輯陳敏英文審校周云龍)

Research on Dynamic Vehicle Routing Problems Based on Two-stage SolvingCHEN Cheng，QIU Rong-zu

(School of Transportation and Civil Engineering，F(xiàn)ujian Agriculture and Forestry University，F(xiàn)uzhou 350002，China)

Abstract：The idea of two-stage solving is applied and dynamic information is converted into static information by setting timing intervals.Two mathematic models are set up respectively for the periods of initial optimization and real-time optimization.Saving algorithm is used for initial solutions while Tabu search algorithm is used to obtain solutions for vehicle routing issues after initial optimization.In the period of real-time optimization,solutions are obtained after relevant amendments to both algorithms.Then,simulation experiments are carried out to test and analyze settings of time intervals for clients in different geographical locations,and the results prove the simplicity and viability of the proposed solving method.Different sensibilities are shown with different location distributions: mixed distribution is the most sensible to timing intervals;followed by random distribution and then cluster distribution.Finally,the curves corresponding to accumulative numbers of customers served are presented,which,combined with the total travel distances,are used to optimize the setting of timing intervals under different geographic distributions of customers.

Key words：dynamic vehicle routing problems;two-stage solving;timing interval；tabu search

[中圖分類(lèi)號(hào)]F253.4

[文獻(xiàn)標(biāo)志碼]A

[文章編號(hào)]1007-7405(2015)06-0435-07

[作者簡(jiǎn)介]陳誠(chéng)(1982—)，女，講師，博士生，從事物流系統(tǒng)優(yōu)化與仿真研究.通訊作者：邱榮祖(1961—)，男，教授，博士，博士生導(dǎo)師，從事物流工程與管理研究.E-mail：875693642@qq.com.

[基金項(xiàng)目]福建省科技廳重點(diǎn)項(xiàng)目(2014H0010)；福建農(nóng)林大學(xué)科技創(chuàng)新(培育)團(tuán)隊(duì)資助計(jì)劃(pytd12006)

[收稿日期]2015-04-18[修回日期]2015-07-06