基于順路原則及位置預(yù)估的動態(tài)調(diào)度策略

曹劍東，李家文

(1.交通運輸部 科學(xué)研究院，北京 100029；2.浙江工業(yè)大學(xué) 機械工程學(xué)院,杭州 浙江 310014)

基于順路原則及位置預(yù)估的動態(tài)調(diào)度策略

曹劍東1，李家文2

(1.交通運輸部 科學(xué)研究院，北京 100029；2.浙江工業(yè)大學(xué) 機械工程學(xué)院,杭州 浙江 310014)

摘要：針對市內(nèi)貨物配送和收集這一典型的集送貨問題，在利用“混合禁忌搜索算法”進行靜態(tài)調(diào)度求解的基礎(chǔ)上，提出基于“順路原則”的局部調(diào)整策略實現(xiàn)集送貨問題的動態(tài)調(diào)度計算.計算過程中采用模糊推理方法選擇局部調(diào)整范圍，同時采用車輛位置預(yù)估方法消除計算、傳輸和執(zhí)行延遲帶來的車輛位置的變化對優(yōu)化結(jié)果的影響.以40個遍布于北京的客戶構(gòu)成的集送貨問題為例，驗證了動態(tài)調(diào)度策略的有效性。

關(guān)鍵詞：運輸經(jīng)濟；動態(tài)調(diào)度；順路原則；模糊推理；集送貨

Dynamic dispatch strategy based on by-way principle

and location pre-estimation

CAO Jiandong1, LI Jiawen2

(1.China Academy of Transportation Sciences, Beijing 100029, China;

2.College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310014, China)

Abstract:In order to solve the typical problem for urban cargo pickup and delivery, dynamic dispatch calculation is proposed by local adjustment strategy called as “by-way principle”, which is based on static dispatch solutions worked out by hybrid tabu search algorithm. Local adjustment range is selected using fuzzy reasoning method in calculation progress and influence of vehicle location change due to calculation, transmission and performance delay is lessened using pre-estimation method to determine vehicle location. Calculation obtained for a pickup and delivery problem example with 40 customers in Beijing validates the efficiency of dynamic dispatch strategy。

Keywords:transport economy; dynamic dispatch; by-way principle; fuzzy reasoning; pickup and delivery

配送和集貨是物流中的一個重要環(huán)節(jié)，是貨物在物流結(jié)點與收發(fā)貨人之間流動的過程[1].對運輸車輛的行駛線路進行有效的優(yōu)化調(diào)整，可大幅減少車輛的空駛里程.集送貨問題可以分為靜態(tài)調(diào)度和動態(tài)調(diào)度兩類.在靜態(tài)調(diào)度方面，唐俊、楊浩雄、王飛、鄭四發(fā)[2-6]等采用粒子群算法、蟻群算法和禁忌搜索算法對該問題進行研究并取得不錯的效果。

在集送貨動態(tài)調(diào)度方面，其主要的優(yōu)化策略包括兩類，即“重新優(yōu)化策略”和“局部調(diào)整策略”.“重新優(yōu)化策略”實際上可以看作是動態(tài)調(diào)度問題的一種靜態(tài)的求解策略，其計算量大，時效性低，因此不適于實時性要求高的動態(tài)調(diào)度計算.局部調(diào)整與重新優(yōu)化原理不同，是根據(jù)接收到的動態(tài)信息對現(xiàn)有行駛路徑進行局部改進.Madsen等人[7]提出插入法求解運送老人和殘疾人的問題，Gendreau等[8]針對一類比較特殊的信使服務(wù)優(yōu)化調(diào)度問題，提出一種適應(yīng)存儲的改進禁忌搜索算法.但是上述算法優(yōu)化大規(guī)模的實際集送貨問題時在計算時間和精度方面很難兼顧，另外，算法忽略由于計算、傳輸和執(zhí)行的延遲導(dǎo)致車輛位置變化而產(chǎn)生的誤差，將進一步降低優(yōu)化精度.針對集送貨動態(tài)調(diào)度問題，在采用車輛位置預(yù)估方法估計車輛當前位置和采用模糊推理方法選擇局部調(diào)整范圍的基礎(chǔ)上，應(yīng)用基于“順路原則”的局部調(diào)整策略實現(xiàn)集送貨問題的動態(tài)調(diào)度計算.40個客戶的計算實例表明：動態(tài)調(diào)度策略能夠在保證計算效率的前提下，提高計算精度和結(jié)果的可執(zhí)行性。

1基于局部調(diào)整策略的動態(tài)調(diào)度算法

1.1集送貨靜態(tài)路徑方案的構(gòu)造

市內(nèi)貨物的配送和收集是一個典型的車輛路徑問題，具有“帶時間窗約束”、“單一車場”、“涉及多種車型”以及“取貨和送貨一體化完成”等四個典型特征。

考慮到集送貨問題的復(fù)雜性、典型性和特殊性，以運輸車輛的燃油成本Cg、折舊成本Ct、車廂整理成本Cs以及司機工資成本Cd之和為目標函數(shù)，建立該調(diào)度問題的成本模型：

(1)

C(k)=Cg(k)+Cd(k)+Ct(k)+Cs(k)

(2)

(3)

Di(k)=d(nk,i-1,nki)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式中：變量i，j和k的取值范圍分別為i=1,2,…,N，j=1,2,…,N，k=1,2,…,M，N為當前所需服務(wù)的客戶總數(shù)，M為配送中心當天最多可用的車輛總數(shù)，假設(shè)各待服務(wù)客戶的序號為i，其中i=0表示第i個待服務(wù)客戶為配送中心；h(i)表示第i個客戶的收貨重量；g(i)表示第i個客戶的發(fā)貨重量；nkj為車輛k的行駛路徑上客戶j的實際編號；Nk為車輛k的行駛路徑包含的路段總數(shù)。

式(3~7)為運輸車輛燃油成本：β0為車輛空載運輸時的油耗與滿載運輸時的油耗比值；rg為燃油成本比例系數(shù)，即運輸車輛滿載行駛時單位公里的油耗成本，元/km；d(i,j)為運輸車輛從第i個客戶到第j個客戶的實際行駛距離，km；Hi(k)為運輸車輛k從第i個客戶開往第j個客戶時車上總的送貨重量，kg；Gi(k)為車輛k從第i個客戶直接開往第j個客戶時車上總的取貨重量，kg；W(k)為運輸車輛k的最大核定載重，kg。

式(8)為司機工資成本：r0表示司機單趟發(fā)車固定成本，元；rd表示司機行駛里程成本系數(shù)，元/km。

式(9)為運輸車輛折舊成本(其值與運輸車輛的行駛里程成正比)：rt為車輛折舊成本系數(shù)，元/km。

式(10)為重新整理車廂的成本：rs為被裝卸貨物的重量成本系數(shù)，元/kg，zij為客戶j處是否需要整理客戶i處收取的貨物。

考慮到靜態(tài)路徑方案是動態(tài)調(diào)度優(yōu)化的基礎(chǔ)，它的優(yōu)劣程度直接影響動態(tài)優(yōu)化的結(jié)果.因此，采用“混合禁忌搜索算法”(圖1)，針對這一車輛路徑問題進行初始方案的預(yù)求解，其思路主要是先采用經(jīng)過改進的Clarke-Wright節(jié)約算法[9]計算得到一個可行的初始調(diào)度方案.在此基礎(chǔ)上，再采用改進的禁忌搜索算法[10]對之前得到的初始調(diào)度方案進行優(yōu)化改進，最終實現(xiàn)整個集送貨調(diào)度問題的求解.應(yīng)用節(jié)約算法構(gòu)造初始的可行方案的主要優(yōu)勢在于“成本節(jié)約值較大的兩點將被優(yōu)先選擇”，從而使得產(chǎn)生的初始方案更加科學(xué)合理，這使得整個問題的求解速度顯著提升.而應(yīng)用改進的禁忌搜索算法對初始方案進行調(diào)整的優(yōu)勢在于能夠較容易的跳出局部最優(yōu)點，從而實現(xiàn)全局范圍內(nèi)的優(yōu)化搜索。

圖1　混合禁忌搜索算法框架Fig.1　Hybrid tabu search algorithm framework

1.2車輛位置的預(yù)估修正

動態(tài)調(diào)度是根據(jù)新出現(xiàn)客戶的信息和客戶出現(xiàn)時運輸車輛的當前位置進行調(diào)度計算[11].車輛的位置由車上安裝的GPS定位終端設(shè)備通過GPRS或者3G無線通信網(wǎng)絡(luò)發(fā)送至調(diào)度中心.然而實際工作中通常會遇到這樣的情況，當司機開始執(zhí)行新的調(diào)度方案時，已經(jīng)比開始調(diào)度計算的時刻T晚了一定的時間間隔ΔT，其數(shù)值主要包括動態(tài)調(diào)度計算時間、無線傳輸及司機確認時間等.在這一時間間隔ΔT之內(nèi)，正在執(zhí)行運輸任務(wù)的所有車輛，都有可能已經(jīng)沿著原來的調(diào)度方案設(shè)定的行駛路線繼續(xù)行駛了一段距離，極端情況是甚至有可能運輸車輛已經(jīng)到達某一個等待服務(wù)的客戶處并開始配送服務(wù)，從而造成新制定的動態(tài)調(diào)度計劃在執(zhí)行過程出現(xiàn)偏差.因此，在調(diào)度計算過程中需要對車輛位置進行提前預(yù)估。

以圖2(a)為例對車輛位置的預(yù)估方法進行描述.圖中虛線條為包含客戶A和B的車輛行駛線路，粗實線為車輛在時間間隔ΔT之內(nèi)的行駛軌跡.車輛位置預(yù)估方法描述如下：由車輛行駛車速和車輛預(yù)計行駛線路可分別求出車輛到達路口1，2，…，n的時間，因此可判斷車輛經(jīng)過時間間隔ΔT之后的位置。

具體分兩種情況：1) 車輛位于路段上：預(yù)估的運輸車輛的位置恰好在兩個路口之間.通常路段本身的長度較小，且路段上運輸車輛的行駛方向是單一的，對后續(xù)的動態(tài)調(diào)度優(yōu)化計算的影響可以忽略，因此，將路段中點作為車輛的預(yù)估位置P′.2) 車輛在客戶處，如圖2(b)所示.具體抽象方法如下：將客戶B抽象成一條路段，路段的通行時間為客戶B的裝/卸貨時間，路段兩端的路口的經(jīng)緯度值均為客戶B的經(jīng)緯度值。

圖2　車輛位置的預(yù)估Fig.2　Vehicle location pre-estimation

另外，考慮到時間間隔ΔT永遠小于客戶裝/卸貨時間，車輛在ΔT之內(nèi)穿越某一客戶的情況不會出現(xiàn)，因此，預(yù)估車輛位置時不考慮此種特殊情況。

1.3基于模糊推理的局部調(diào)整范圍選擇方法

局部調(diào)整算法是在設(shè)定搜索范圍的條件下，調(diào)整現(xiàn)有車輛調(diào)度計劃，使該調(diào)度計劃能夠及時而準確的滿足新增加的所有客戶的動態(tài)服務(wù)需求.因此，選擇合適的調(diào)整范圍(這里主要指參與調(diào)整優(yōu)化計算的線路集合)對于提升算法的精度和計算效率非常重要。

對調(diào)整范圍的選擇有較為重要影響的因素主要有兩個：即當前線路與新增加的客戶之間距離的遠近程度(定義新增加客戶至當前線路的距離為新客戶到線路上所有客戶直線距離的最小值)以及線路上車輛的平均空余體積大小，而平均空余體積的定義為

(11)

式中：Vd為線路上的送貨總體積；Vp為線路上的取貨總體積.顯然，“距離的遠近”及“平均空余體積的大小”這兩個概念是模糊的，因此筆者采用模糊推理方法來進一步確定合理的調(diào)整范圍，即判斷當前各條運輸線路是否應(yīng)該位于調(diào)整范圍之內(nèi)。

將兩個主要因素作為因素集合E={新客戶與線路之間的距離e1，車廂平均空余體積e2}，而將是否屬于調(diào)整范圍之內(nèi)作為評價集合F={線路在調(diào)整范圍之內(nèi)f1，線路在調(diào)整范圍之外f2}.因素e1和e2對評價值f1的隸屬度函數(shù)為

(12)

(13)

由于f1和f2是互為補集的兩個結(jié)論，因此，只需要列出e1和e2對f1的隸屬度函數(shù)。

將某一行駛線路和新增加的客戶的實際數(shù)據(jù)分別代入到兩個隸屬度函數(shù)式(12，13)，可計算得到因素e1和因素e2對評價集F的隸屬度矩陣R.另外，考慮到因素e1和因素e2對最終評價結(jié)果的影響程度也不盡相同，故需要定義兩個因素的權(quán)重矩陣A.顯然在判斷給定線路是否位于調(diào)整范圍之內(nèi)時，距離因素要比空余體積因素重要，因此選定權(quán)值矩陣A=(0.7,0.3).最后，可給出模糊推理的結(jié)果為

(14)

式中參數(shù)rij為隸屬度矩陣R的元素。

根據(jù)式(14)可求得模糊推理的計算結(jié)果b1和b2.當b1>b2時，推理的結(jié)果為線路在調(diào)整范圍之內(nèi).反之，則線路在調(diào)整范圍之外。

1.4基于“順路原則”的局部調(diào)整策略

一般情況下，局部調(diào)整策略往往采用“最接近的原則”作為判斷依據(jù)來選擇合適的調(diào)整對象，即選擇某一個給定范圍之內(nèi)離新增加的客戶“最近”的運輸車輛或者客戶作為局部調(diào)整對象.圖3(a)為“接近原則”的示意圖，圖3中虛線圓圈標識的新增加的客戶“9”與客戶“1”(在運輸車輛“2”的行駛線路中)的距離是相對而言最短的，因此，可以選擇客戶“1”作為此次局部調(diào)整的對象，并將新增加的客戶“9”直接插入到當前客戶“1”的前面，構(gòu)造出一個新的調(diào)度優(yōu)化方案.但是，由于動態(tài)集送貨調(diào)度問題的特殊性，距離的遠近通常無法有效反應(yīng)新增運輸成本的大小。

與“最接近的原則”不同，“順路原則”選擇調(diào)整對象的依據(jù)是“是否順路”，即當前運輸車輛服務(wù)新增加的客戶是否“順路”.對于“順路”的含義可以理解如下：在滿足時間窗、載重、體積等約束條件的前提之下，將新增加的所有客戶依次插入至當前運輸車輛的行駛線路中，額外增加的運輸成本ΔC越小就表示運輸車輛服務(wù)新增客戶越是“順路”.ΔC的求解方法為

ΔC(x,y,z)=Cx,z+Cz,y-Cx,y

(15)

式中：ΔC(x,y,z)為將客戶z插入x和y之間時新增加的額外成本.圖3(b)為基于“順路原則”局部調(diào)整的示例，當新增加的客戶“9”被插入至運輸車輛“1”的行駛路線上的客戶“4”和客戶“2”之間的時候，額外增加的運輸成本ΔC(4,2,9)最小.因此，將安排運輸車輛“1”在完成客戶“4”的送貨任務(wù)之后“順路”行駛至新增加的客戶“9”處收取貨物。

圖3　局部調(diào)整策略示意圖Fig.3　Local adjustment strategy diagram

2應(yīng)用驗證

以某大型物流企業(yè)實際的集送貨動態(tài)調(diào)度問題為例，驗證基于順路原則及位置預(yù)估的集送貨動態(tài)調(diào)度策略的有效性.動態(tài)調(diào)度開始時，共有40個不同的客戶(其中只有4個客戶是新增客戶).客戶位置、車輛位置以及現(xiàn)有路徑如圖4所示，圖4中圓圈內(nèi)的客戶即為新增客戶，另外由于顯示的原因，圖4中只加粗顯示其中的兩條路徑。

通過應(yīng)用基于模糊推理方法的調(diào)整范圍選擇策略，可以確定4個新增加客戶各自的局部調(diào)整范圍.以圖4中方框內(nèi)的客戶為例，采用模糊推理方法，確定其調(diào)整范圍僅限于圖中被加粗顯示的兩條路徑。

圖4　客戶位置、車輛位置以及現(xiàn)有路徑Fig.4　Customers location,vehicle location and directions

圖5為該動態(tài)調(diào)度問題采用基于順路原則及位置預(yù)估的集送貨動態(tài)調(diào)度策略之后的優(yōu)化結(jié)果，包括：7條行駛線路(行駛線路數(shù)目并未發(fā)生改變)，總的行駛里程為495km，總成本為996 元。

圖5　動態(tài)調(diào)整策略優(yōu)化結(jié)果Fig.5　Results of dynamic dispatch strategy

表1為兩類算法的對比情況，表1中基于“接近原則”的局部調(diào)整算法的調(diào)整范圍是所有路徑.通過對比分析可知：筆者提出的基于“順路原則”的局部調(diào)算法無論在精度還是效率方面均具有明顯優(yōu)勢。

表1　兩類算法對比分析

表2為車輛位置預(yù)估對調(diào)度結(jié)果的影響.通過對實際的集送貨調(diào)度數(shù)據(jù)分析，選定延遲時間ΔT=180 s，車輛當前車速是v=10 m/s.表2中位置誤差是指與GPS數(shù)據(jù)(即經(jīng)過ΔT之后車輛的真實位置)的誤差，而表2中的成本是指將車輛的真實位置代入兩類優(yōu)化結(jié)果之后計算得到的成本，因此，大于表1中的成本996 元.表2充分說明車輛當前位置對優(yōu)化結(jié)果具有重要影響，位置預(yù)估越準確則優(yōu)化結(jié)果越精確。

表2　車輛位置預(yù)估對優(yōu)化結(jié)果的影響

3結(jié)論

在順路原則及位置預(yù)估的集送貨動態(tài)調(diào)度策略的基礎(chǔ)上，得出基于模糊推理的局部調(diào)整范圍之選擇方法和基于“順路原則”的局部調(diào)整策略能夠在保證精度的前提下，有效提高動態(tài)調(diào)度優(yōu)化的效率；考慮優(yōu)化過程中對車輛位置的變化及車輛位置預(yù)估方法的采用，將提高動態(tài)調(diào)度優(yōu)化的精度以及優(yōu)化結(jié)果的可執(zhí)行性。

參考文獻：

[1]李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京：中國物資出版社，2001：99-112。

[2]王飛.帶時間窗車輛調(diào)度問題的改進粒子群算法[J].計算機工程與應(yīng)用，2014，50(6)：226-229。

[3]ZHENG Sifa, CAO Jiandong, LIAN Xiaomin. Urban pickup and delivery problem considering time-dependent fuzzy velocity[J]. Computers & Industrial Engineering，2011，60(4)：821-829。

[4]曹劍東，鄭四發(fā)，李兵，等.考慮分時模糊車速的帶時間窗的市內(nèi)集送貨問題[J].系統(tǒng)仿真學(xué)報，2009，21(3)：823-826。

[5]胡志華，陶莎.基于混合進化算法的甩掛配送問題[J].公路交通科技，2013，30(5)：147-152。

[6]陳嶷瑛，李文斌，王舵，等.使用面向離散搜索空間的蛙跳算法求解TSP[J].計算機工程與應(yīng)用,2009,45(27):50-52。

[7]MADSEN O B G, RAVN H F, VOELDS J. A heuristic method for dispatching repairmen[J]. Annals of Operations Reasearch,1995,61:193-208。

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

[9]CLARKE G, WRIGHT J W. Scheduling of vehicles from a central depot to a number of delivery points [J]. Operations Research,1964,12(4):568-581。

[10]OSMAN I H, WASSAN N A. A Reactive Tabu search meta heuristic for the vehicle routing problem with backhauls[J]. Journal of Scheduling,2002，5(4)：263-285。

[11]李兵，鄭四發(fā)，曹劍東，等.求解客戶需求動態(tài)變化的車輛路徑規(guī)劃方法[J].交通運輸工程學(xué)報,2007,7(1):106-109。

(責(zé)任編輯：陳石平)

中圖分類號：U492

文獻標志碼：A

文章編號：1006-4303(2015)02-0197-05

作者簡介：曹劍東(1980—)，男，江蘇蘇州人，副研究員，工學(xué)博士，研究方向為智能交通，E-mail:caojiandong@catsic.com。

基金項目：國家自然科學(xué)基金資助項目(51405438)

收稿日期：2014-11-25