曹劍東，李家文

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

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

曹劍東1，李家文2

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

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

關(guān)鍵詞：運(yùn)輸經(jīng)濟(jì)；動(dò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

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

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

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

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

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

考慮到集送貨問題的復(fù)雜性、典型性和特殊性，以運(yùn)輸車輛的燃油成本Cg、折舊成本Ct、車廂整理成本Cs以及司機(jī)工資成本Cd之和為目標(biāo)函數(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為當(dāng)前所需服務(wù)的客戶總數(shù)，M為配送中心當(dāng)天最多可用的車輛總數(shù)，假設(shè)各待服務(wù)客戶的序號(hào)為i，其中i=0表示第i個(gè)待服務(wù)客戶為配送中心；h(i)表示第i個(gè)客戶的收貨重量；g(i)表示第i個(gè)客戶的發(fā)貨重量；nkj為車輛k的行駛路徑上客戶j的實(shí)際編號(hào)；Nk為車輛k的行駛路徑包含的路段總數(shù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(11)

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

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

(12)

(13)

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

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

(14)

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

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

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

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

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

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

(15)

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

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

2應(yīng)用驗(yàn)證

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

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

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

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

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

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

3結(jié)論

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

參考文獻(xiàn)：

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

[2]王飛.帶時(shí)間窗車輛調(diào)度問題的改進(jìn)粒子群算法[J].計(jì)算機(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ā)，李兵，等.考慮分時(shí)模糊車速的帶時(shí)間窗的市內(nèi)集送貨問題[J].系統(tǒng)仿真學(xué)報(bào)，2009，21(3)：823-826。

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

[6]陳嶷瑛，李文斌，王舵，等.使用面向離散搜索空間的蛙跳算法求解TSP[J].計(jì)算機(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ā)，曹劍東，等.求解客戶需求動(dòng)態(tài)變化的車輛路徑規(guī)劃方法[J].交通運(yùn)輸工程學(xué)報(bào),2007,7(1):106-109。

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

中圖分類號(hào)：U492

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

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

作者簡介：曹劍東(1980—)，男，江蘇蘇州人，副研究員，工學(xué)博士，研究方向?yàn)橹悄芙煌?，E-mail:caojiandong@catsic.com。

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

收稿日期：2014-11-25