国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于兩階段求解的動態(tài)車輛路徑問題研究

2015-03-03 08:12邱榮祖

陳 誠,邱榮祖

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

?

基于兩階段求解的動態(tài)車輛路徑問題研究

陳誠,邱榮祖

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

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

[關(guān)鍵詞]動態(tài)車輛問題;兩階段求解;定時間隔;禁忌搜索

0引言

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

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

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

1動態(tài)車輛路徑問題描述

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

2求解思路

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

2.1 定時間隔

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

2.2 關(guān)鍵點

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

本文動態(tài)車輛路徑問題的具體求解思路如圖2所示.

3數(shù)學模型

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

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

總費用最小的目標函數(shù)如式(1)所示,表示車輛總行駛路徑最短.

(1)

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

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

(2)

4動態(tài)車輛路徑問題兩階段求解算法

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

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

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

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

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

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

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

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

3)禁忌搜索算法編碼階段,虛擬配送中心按客戶點方式直接排列;解碼階段,按客戶排列順序?qū)⒖蛻艏尤氲铰肪€中,遇到虛擬配送中心則重新開始一條新路線,從而保證虛擬配送中心發(fā)且只能發(fā)出一輛車,而不能接受其他車輛的訪問.

5仿真實驗與討論

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

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

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

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

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

6結(jié)束語

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

[參考文獻]

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

[2]郎茂祥.配送車輛優(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]陳久梅,張旭梅,肖劍,等.隨機動態(tài)裝卸混合問題的分區(qū)求解策略[J].管理科學學報,2012,15(1):43-53.

[8]熊浩,符卓,鄢慧麗.動態(tài)車輛路徑問題的隱分期靈活分批策略[J].同濟大學學報:自然科學版,2013,41(5):676-679.

[9]葛顯龍,王旭,鄧蕾.基于聯(lián)合配送的開放式動態(tài)車輛路徑問題及算法研究[J].管理工程學報,2013,27(3):60-68.

[10]王仁民,閉應洲,劉阿寧,等.改進變鄰域搜索算法求解動態(tài)車輛路徑問題[J].計算機工程與應用,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ā),曹劍東,等.求解客戶需求動態(tài)變化的車輛路徑規(guī)劃方法[J].交通運輸工程學報,2007,7(1):106-110.

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

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

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

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

[中圖分類號]F253.4

[文獻標志碼]A

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

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

[基金項目]福建省科技廳重點項目(2014H0010);福建農(nóng)林大學科技創(chuàng)新(培育)團隊資助計劃(pytd12006)

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