快遞服務動態(tài)車輛路徑問題的多目標優(yōu)化模型

快遞服務動態(tài)車輛路徑問題的多目標優(yōu)化模型

近年來，動態(tài)車輛路徑問題（dap）成為研究的熱點。v浦模型可以用于包裹郵件、出租車服務、急救維修、急救等。車輛駕駛員應隨時根據(jù)當前信息調整線路，并隨時根據(jù)當前信息調整線路。20世紀90年代以前的研究已經(jīng)結束。chen等人研究了基于時間窗口的動態(tài)車輛生成方法。伯里等人研究了基于在線交通信息的dvp?；趂laischmann等人的研究開發(fā)基于在線交通信息的dvp。bent等人提出了基于場景的隨機信息計劃方法。胡明偉等人提出了基于紀念場景的高效啟動算法。劉世新等人研究了基于dvp的局部搜索算法。本文以與快遞服務相關的動態(tài)車輛路徑問題為研究對象,將其描述成帶時間窗口的動態(tài)旅行修理員問題,提出包含最大化服務客戶數(shù)、最小化客戶等待時間和最小化總旅行時間的多目標優(yōu)化模型,開發(fā)了改進的ChainedOr-opt局部搜索算法.1dvrp的特性,主要體現(xiàn)依照Psaraftis的定義,如果問題的信息(輸入)是在決定路徑的同時才為決策者所知曉或者更新,VRP就是動態(tài)的;相反,如果所有輸入在決定路徑之前就都已知并且隨后不發(fā)生變化,VRP就是靜態(tài)的.DVRP的特性主要體現(xiàn)在如下方面:①時變性和隨機性顯著.DVRP的輸入信息都是時間的函數(shù),即客戶需求、車輛位置和狀態(tài)、路網(wǎng)交通狀況等都是隨時間變化的,而且其變化規(guī)律是隨機的,無法事先預知,已制定的路徑計劃需要實時優(yōu)化和調整;②信息實時更新.DVRP中的信息實時更新且反映在優(yōu)化進程中,路線計劃需根據(jù)更新的信息做出重新優(yōu)化;③目標函數(shù)復雜.DVRP的目標函數(shù)要復雜得多,需要根據(jù)具體問題選擇適當?shù)哪繕撕瘮?shù);④實時響應.DVRP要求實時響應,路線重新優(yōu)化過程要求在很短的時間內(nèi)完成,并將新的任務指派到司機,因此對優(yōu)化算法和支撐技術提出了比靜態(tài)VRP更高的要求.1.1節(jié)點市場的drp體本文重點研究與快遞服務相關的動態(tài)車輛路徑問題,即帶時間窗口的動態(tài)旅行修理員問題(dynamictravelingrepairmanproblemwithtimewindows,DTRPTW).其實際應用背景是快遞員從客戶所在位置收集信件和小包裹,然后將其運回到郵件處理站.其動態(tài)體現(xiàn)在并非所有客戶都在路線構造前為決策者所知,而且在任務執(zhí)行過程中新出現(xiàn)的服務請求必須被立即安排到已有的服務路線中.DTRPTW定義為,有向圖G=(N,A)上,N={0,1,2,...,n}代表包括車場0和客戶位置(N0})的點集;A為N內(nèi)每對節(jié)點最短路徑的弧集;弧(i,j)∈A的最短路徑旅行時間為tij;對每一個節(jié)點i∈N,都有一個時間窗口[ei,li];ei和li分別為窗口的開放和關閉時間.定義D?N0}為動態(tài)客戶集,要求提取貨物的位置和時間窗口只有在其請求到達后才知道.定義P?N0}為優(yōu)先客戶集,希望提取貨物的時間與時間窗口的開放時間盡可能接近,即愿意當時間窗口開放后有最短的等待時間.令發(fā)出請求事先已知的客戶為已知客戶,記作(N-D)0},DTRPTW找到一個起點和終點都是車場0的旅行線路τ,滿足:①在節(jié)點i∈N0}初始,提取服務滿足時間窗口[ei,li],即服務開始的時間bi滿足ei≤bi≤li;②在每個節(jié)點i∈N0},如果車輛到達的時間ai比ei早,只能等待時間窗口開始,在每個點有一定的當場服務時間si;③車輛路線只能在客戶位置點更新,即車輛不能在兩個節(jié)點間旅行的時候變更目的地.DTRPTW要優(yōu)化多目標包括:①最小化總旅行時間O1.采用總旅行時間衡量運營費用,以尋找具有最小旅行時間的路徑,即O1=min∑(i?j)∈τAtij(1)Ο1=min∑(i?j)∈τAtij(1)其中,τA是一個組成車輛路徑τ的弧集.②最小化客戶等待時間O2.客戶等待時間直接關系到對服務質量的感受,因此要安排訪問客戶的順序以保證所有客戶的總等待時間最短,即O2=min∑i∈P(bi?ei)(2)Ο2=min∑i∈Ρ(bi-ei)(2)其中,P是N0}的子集或等于N0}.③最大化服務客戶的總數(shù)O3.受系統(tǒng)限制,某客戶可能被拒絕服務,因此提升客戶滿意度需要增加服務客戶的總數(shù),O3=max|τC|(3)Ο3=max|τC|(3)其中,τC為被車輛路線τ訪問的客戶集合.1.2基于最晚行動策略的車輛路線改進考慮到快遞服務的特性,多目標DTRPTW采用基于詞典式的排序方法來構造求解算法.最小化被拒絕的客戶數(shù)給予最高優(yōu)先級(或者最大化服務的客戶數(shù)),最小化優(yōu)先客戶的等待時間給予次高優(yōu)先級,最后是最小化總旅行時間,也就是O3優(yōu)先于O2,O2優(yōu)先于O1.采用這樣的排序策略是考慮到快遞服務行業(yè)的現(xiàn)狀,就是客戶的滿意度(服務的客戶數(shù)最大化并且客戶等待時間降低)比單純的運營費用最小化(最小化旅行時間)更重要.求解多目標DTRPTW采用基于事件驅動的算法,如圖1,即只有當新的事件產(chǎn)生,即出現(xiàn)新的客戶請求時,路徑方案才進行更新.流程由如下步驟組成:①根據(jù)已知客戶的信息創(chuàng)建初始路線方案.利用已知客戶的信息創(chuàng)建初始車輛路徑降級為一個多目標的TSPTW(travelingsalesmanproblemwithtimewindows).客戶等待時間最小化和旅行時間最小化各自按照詞典式的順序得到考慮,先通過一個修改的I1插入過程創(chuàng)建初始路線,然后通過ChainedOr-opt過程進行改進;②根據(jù)該客戶提出服務的時間更新當前的路線方案.車輛路徑依據(jù)最晚行動策略更新,如果駕駛員在下一個計劃的目的地預計要等待一些時間(也就是如果立刻離開當前位置,將會在下一位置時間窗口開始前到達),就安排駕駛員在當前位置等待;③為納入新客戶進行局部改進.如果新動態(tài)客戶的服務請求不能被直接插入到已有的車輛路線中,就需要啟動局部的改進過程修改車輛路線,使其可被納入.這一局部改進過程按如下方法操作:隨機從車輛路線中去掉一些計劃?？奎c,然后重新在路線方案不同位置安排(盡量不同于去掉前所在位置),檢查動態(tài)客戶能否被插入到當前的車輛路線中,如果能夠則終止,否則繼續(xù);用ChainedOr-opt改進當前的車輛路線,如果動態(tài)客戶能被插入則停止,否則拒絕這個動態(tài)客戶;④ChainedOr-opt改進過程.在多目標優(yōu)化改進車輛路線的步驟⑤中(如圖1),迭代地運用改進的Or-opt局部搜索,若局部最優(yōu)達到,程序就產(chǎn)生一個小擾動以脫離局部最優(yōu).步驟為:置迭代指標q=0和經(jīng)典Or-opt過程一樣,在當前的車輛路線中檢查3個、2個或1個連續(xù)節(jié)點改變位置,如果從時間窗口約束這種改變位置可行,且從多目標評價角度改進了當前的車輛路線,就確認.若局部最優(yōu)到達,即不能通過Or-opt改變來得到改進,則令q:=q+1;若q>α(事先設定參數(shù)),輸出當前最好的解,否則繼續(xù)執(zhí)行下一步;隨機從車輛路線中去掉一些計劃?？奎c,重新安排在不同位置(盡量不同于去掉前所在位置),繼續(xù)前述操作.通過修改解的評價函數(shù),改進ChainedOr-opt過程能處理多目標DTRPTW中詞典式的目標排序模型,與VRP中經(jīng)常使用的禁忌搜索算法相比,ChainedOr-opt在計算上更有優(yōu)勢,其計算量可用參數(shù)α控制(若希望算法迭代次數(shù)為20次,則令α=20),且該法可得到與禁忌搜索算法同樣高質量的解.2計算和分析2.1客戶時間窗口生成為檢驗多目標DTRPTW優(yōu)化模型及算法,設計了兩組實驗,如表1.這些實驗在兩類基準問題的數(shù)據(jù)上進行.第一類由TSPTW的rbg現(xiàn)實世界數(shù)據(jù)組成,由Norbert等引入.第二類由Solomon為VRPTW提供的基準問題得來,由于Solomon數(shù)據(jù)為多輛車設計,其時間窗口不適合單車路徑問題的實驗場景,這里只采用Solomon數(shù)據(jù)的旅行時間和服務時間,客戶時間窗口的生成基于Mingozzi等研究對稱TSPTW提出的方法.為仿真動態(tài)路徑場景,動態(tài)和優(yōu)先的客戶以及動態(tài)客戶出現(xiàn)的時間都是隨機生成的.動態(tài)客戶集D在N0}中隨機選擇,概率上偏向那些有較晚開始時間的,優(yōu)先客戶P在(N(D)0}中隨機選擇,動態(tài)客戶i發(fā)出服務請求的時間ri根據(jù)在區(qū)間(c1×ei,c2×ei]的均勻分布隨機生成,c1和c2(0≤c1≤c2≤1)是兩個參數(shù).2.2實驗與結果分析2.2.1基于等待時間的旅行時間生成第一組實驗設計用來檢驗對時間窗口約束較松的DTRPTW多目標優(yōu)化模型及算法,由于時間窗口足夠寬,將沒有任何客戶被拒絕服務,因此對這一組實驗只需要檢驗優(yōu)先客戶的等待時間和總旅行時間兩個目標.表1創(chuàng)建了兩類數(shù)據(jù),第一類基于不對稱的rbg問題,即rbg92a,其旅行時間、服務時間和時間窗口都未作改變,第二類源于Solomon的基準問題,包括6組數(shù)據(jù)集,即R1、R2、C1、C2、RC1和RC2,由于R1和R2、RC1和RC2中的旅行時間與服務時間相同,分別命名為R和RC.C1和C2的旅行時間和服務時間雖然不同,但以同樣手段生成,只選擇C1,命名為C.基于Solomon問題構造的時間窗口根據(jù)前面實驗設計部分所述的方法隨機生成.表1中rbg和Solomon問題的動態(tài)客戶和優(yōu)先客戶也是根據(jù)前面實驗設計部分所述的方法隨機選擇.對于每一個子類問題,例如在rbg92a中,|D|=20?|P|=20|D|=20?|Ρ|=20,又隨機生成5個例子.表1為對5次運行的平均值.為檢驗多目標優(yōu)化算法的質量,這些結果又與“后驗”的TSPTW解進行比較.“后驗”的解基于旅行時間最小化的目標用ChainedOr-opt啟發(fā)式算法得到,假定所有與問題有關的信息都已知,而在動態(tài)場景下當計劃路徑在執(zhí)行過程中動態(tài)客戶才出現(xiàn).因此,TSPTW的解就提供了動態(tài)場景下的總旅行時間的下界.表1中,總旅行時間表示相應解的路徑的總旅行時間,等待時間為優(yōu)先客戶的總等待時間.由表1可見,多目標優(yōu)化的總旅行時間僅有少許增長,而客戶等待時間得到明顯改進.對rbg92a類問題,平均等待時間的平均值由6579下降至558.8,降幅為91.5%;對R、C和RC類問題,平均等待時間的平均值由9651.7下降至712.7,降幅為92.6%.2.2.2動態(tài)車輛路徑模型第二組實驗用來檢驗高度動態(tài)和時間窗口約束較緊的多目標DTRPTW優(yōu)化,半數(shù)例子的動態(tài)客戶出現(xiàn)的時間比時間窗口開始時間的80%晚,也就是[c1,c2]=[0.8,1],相當于很緊的時間窗口.用多目標優(yōu)化方法得到的DTRPTW的解與通過單目標最小化旅行時間得到的解在表2中進行了比較.表2顯示,在動態(tài)車輛路徑問題中考慮多目標的效益非常明顯.例如,在Solomon問題的例子中,平均的多目標DTRPTW結果中只有0.2個被拒絕客戶,而在旅行時間最小化的單目標模型中平均被拒絕的客戶達到4.4個.且多目標模型平均降低等待時間超過34%,盡管旅行時間稍有增長.對于rbg類問題從被拒絕的客戶的角度沒有出現(xiàn)明顯的不同,因為rbg類問題例子的時間窗口對高度動態(tài)的場景仍然足夠寬.基于事件驅動的多目標優(yōu)化模型和算法本文以與快遞服務相關的動態(tài)車輛路徑問題為研究對