考慮交通擁堵及工作量平衡性的一致性車輛路徑問題

（北京交通大學經(jīng)濟管理學院，北京100044）

（北京交通大學經(jīng)濟管理學院，北京100044）

為研究快遞公司在提供一致性配送服務時，交通擁堵以及快遞人員工作量平衡性因素對配送路徑的影響，在傳統(tǒng)車輛路徑問題研究的基礎(chǔ)上，提出了考慮擁堵和工作量的一致性車輛路徑問題，并構(gòu)建了混合整數(shù)規(guī)劃模型.針對該模型的NP難性質(zhì)，提出了基于模板路徑的兩階段模擬退火算法（template-based simulated annealing heuristic，TSA）.該算法通過構(gòu)建模板路徑求解初始路徑方案，再利用模擬退火算法優(yōu)化路徑方案，降低車輛總行駛時間.將該模型和算法應用于3組基準數(shù)據(jù)（benchmark data set）的數(shù)值實驗，結(jié)果表明：本文模型和算法能有效解決此類問題，交通擁堵使最優(yōu)配送路徑的總行駛時間平均增加18.38%，使快遞人員在任意兩天到達同一顧客的最早與最晚時刻之差平均增加12.92%；當快遞人員配件量的不平衡性平均下降35.82%后，二者僅分別平均增加2.29%和1.68%.

一致性車輛路徑問題；快遞業(yè)；交通擁堵；工作量平衡性

自文獻［1］提出車輛路徑問題（vehicle routing problem，VRP）以來，VRP問題引起了學者們的廣泛關(guān)注.文獻［2-4］對VRP問題進行了各類擴展，文獻［5］對VRP問題做了詳盡的綜述.近年來，電商的迅速崛起促進了快遞市場高速發(fā)展，2013年中國網(wǎng)絡(luò)購物交易規(guī)模達到1.85萬億，其中70%產(chǎn)生了快遞量［6］.顧客對快遞服務質(zhì)量也提出了越來越高的要求，文獻［7］指出，顧客對高質(zhì)量快遞服務的重要衡量指標是服務一致性，文獻［8］基于服務一致性要求提出了一致性車輛路徑問題.眾多位學者從應用、模型改進和算法優(yōu)化等方面進行了進一步的研究［7，9-13］.

文獻［14］考慮了司機工作量的平衡性，但是忽略了交通擁堵因素.這兩個因素在快遞公司提供一致性服務的過程中都很重要.

（1）交通擁堵

傳統(tǒng)一致性車輛路徑問題中，兩點之間的行駛時間是固定的，即車輛以勻速行駛，此假設(shè)在交通擁堵情況日益嚴重的現(xiàn)狀下并不成立，以北京二環(huán)為例，部分主干路早晚高峰時段運行速度低于15 km/h，全路網(wǎng)工作日日均擁堵時間超過4 h［15］，因此，按照此假設(shè)規(guī)劃得到的配送路徑將產(chǎn)生巨大偏差.文獻［16］提出，由于交通擁堵造成的行駛時間不確定性影響了物流運作效率，并導致一致性服務受到重大影響.需要指出的是，越來越多的消費者在電商平臺上購買的大型電器，只能通過大中型車輛進行配送，不具備小型機動車輛的靈活性，因此受交通擁堵影響巨大.

（2）工作量平衡性

越來越多的學者開始關(guān)注公平性問題，例如，文獻［17］指出，對快遞人員來說，一方面其收入構(gòu)成很大一部分取決于計件工資，快遞人員之間的派件數(shù)量差別過大會直接導致明顯的收入差異；另一方面，因為一致性車輛路徑問題的特殊性，要求快遞人員在一個時間段內(nèi)對同一個顧客進行配送服務，若對快遞人員所服務片區(qū)中的顧客分配不當，會加劇工作量的不平衡性.

綜上分析，本文提出了考慮交通擁堵和快遞人員工作量平衡性的一致性車輛路徑問題，建立了基于該問題的混合整數(shù)規(guī)劃模型.該模型保證了服務一致性要求，并利用3組基準數(shù)據(jù)集的數(shù)值實驗，檢驗了交通擁堵和工作量平衡因素對快遞公司運營成本和服務質(zhì)量的影響.

1 模型建立

1.1 相關(guān)假設(shè)及參數(shù)定義

一致性車輛路徑問題定義為有向圖G=｛N，A｝，其中N=｛0，1，2，…，n｝表示點集合，點0代表快遞站，NC=N?｛0｝對應各需求點顧客；A=｛（i，j）∶i，j∈N，i≠j｝表示弧集合.

本文將每位顧客視為運輸網(wǎng)絡(luò)中的一個需求點.每位顧客在D天中的某一天或某幾天有需求，且提前已知所需服務時間與需求量.K輛完全相同的車（即K名司機）為顧客服務，每位顧客每天最多只能被服務一次.車的最大容量為Q，每天都在同一時刻從快遞站出發(fā)，且在T個時間單位內(nèi)返回.為保證服務一致性，司機在顧客有需求的幾天中，任意兩天到達該顧客的最早與最晚時刻之差不超過L個時間單位.令在第d天為顧客i的服務時間為tid，需求量為qid，任意兩個顧客之間的行駛時間對應著對稱矩陣（未考慮擁堵因素）T=（tij），即tij=tji.

本問題為混合整數(shù)規(guī)劃問題，引入以下參數(shù)：車輛在第d天到達顧客i處的時刻為taid.若在第d天顧客i有需求，則令0-1變量wid=1，否則wid=0；引入決策變量xijkd，如果車輛k在第d天服務完顧客i后緊接著服務顧客j，則xijkd=1，否則xijkd=0；引入決策變量yikd，如果在第d天由車輛k為顧客i提供服務，則yikd=1，否則yikd=0.本問題目標函數(shù)是路徑規(guī)劃后D天中車輛的總運行時間最短.

1.2 交通擁堵

文獻［18］根據(jù)不同的時間段，將車輛行駛速度分為4個等級.根據(jù)文獻［19］，70%～87%的擁堵時間在早晚高峰.本文中假設(shè)每天上午8：00～9：00、晚上18：00～20：00分別為早晚高峰時間段，車輛若在這兩個時間段中行駛會處于低速狀態(tài)，否則處于常速狀態(tài).假設(shè)所有車輛均每天上午8：00從快遞站出發(fā)，且必須在24：00之前返回快遞站.如果某位司機在第d天為顧客i服務完畢的離開時刻taid+tid處于早晚高峰時間窗中，那么該車輛在前往下一顧客處的行駛路程中，行駛時間會增加μ倍（擁堵因子μ≥0）.引入0-1變量σid，

車輛在兩個顧客之間的實際行駛時間為tij（1+μσid）.

1.3 工作量平衡性

將司機k在D天中的工作量定義為

即在D天中由司機k服務的所有顧客的總需求量，根據(jù)文獻［20］提出的用均方差形式刻畫工作量不平衡性，定義快遞人員工作量的不平衡量為

為體現(xiàn)快遞公司對此問題的不同重視程度，引入常量M，可以得到以下約束條件：

fWl≤M.

1.4 混合整數(shù)規(guī)劃模型

混合整數(shù)規(guī)劃方程如下：

式中：wid為0-1變量，若顧客i在第d天有需求，則令wid=1，否則為0；

widα為0-1變量，若顧客i在第（d-α）天有需求，則令wid-α=1，否則為0；

wid，β為0-1變量，若顧客i在第（d-β）天有需求，則令wid-β=1，否則為0；

taid為車輛第d天到達顧客i處的時刻.

約束式（1）和（2）要求每輛車每天在時刻0從快遞站出發(fā)（實際應用中可將時刻0設(shè)置其他時刻）；約束式（3）保證了每位顧客每天最多被服務一次；約束式（4）限制了車的容量為Q；約束式（5）為各顧客處流量守恒約束；快遞人員的一致性要求通過約束式（6）保證；約束式（7）和（8）為考慮了交通擁堵后車輛到達各顧客的時刻，約束式（7）還可以防止產(chǎn)生子回路；約束式（9）同樣為了防止子回路的產(chǎn)生；約束式（10）保證了各快遞人員必須在T個時間單位內(nèi)返回；約束式（11）保證了快遞人員在任意兩天dα和dβ到達顧客i的最大時間差不超過L個時間單位；約束式（12）保證了整體工作量的不平衡量不超過M個需求單位；約束式（13）定義了決策變量和相關(guān)參數(shù).

2 用TSA算法求解模型

一致性車輛路徑問題是典型NP難問題，根據(jù)服務一致性的特征，文獻［8，11］提出了模板路徑思想，本文在此基礎(chǔ)上提出了基于模板路徑的模擬退火法（template-based simulated annealing method，TSA）求解路徑方案，算法分析和編碼過程可參考文獻［11-21］的研究成果.

2.1 TSA算法基本思想

用TSA算法先后求解主、從兩個子問題，其中主子問題針對多天需求顧客利用貪婪算法構(gòu)建模板路徑，確定為多天需求顧客提供服務的快遞人員及訪問先后順序；從子問題則根據(jù)所有顧客的實際需求，首先逐天刪除當天沒有需求的多天需求顧客，再通過貪婪算法插入僅當天有需求的單天需求顧客，得到每天路徑方案.SA（simulated annealing）算法分別應用到兩個子問題中優(yōu)化初始模板路徑和初始路徑方案［21］.

2.2 模板路徑獲得

利用TSA算法，先將顧客分為兩個子集：多天需求顧客集合Nf和單天需求顧客集合Nnf.因為模板路徑中只包含多天需求顧客，作為最終路徑方案的參考，可以保證多天需求顧客每天都由同一快遞人員提供服務.模板路徑的求解過程如下：

（1）對多天需求顧客集合Nf進行初始化，求得各多天需求顧客在整個服務時間范圍中的平均需求量qi和服務時間tsi，

式中：qid為顧客i在第d天的需求量；

tid為顧客i在d天需要被服務的時間.

（2）再為每位多天需求顧客安排一輛車進行服務，然后利用貪婪算法獲得模板路徑，優(yōu)先選擇可使合并后總行駛時間減少量最多的兩條路徑進行合并，當路徑數(shù)目等于K時停止.每次合并后，立即對新產(chǎn)生路徑對車容量限制和司機最長工作時間約束進行可行性檢查，只接受可行的新路徑.

2.3 最終路徑方案獲取

基于模板路徑獲得最終路徑方案.首先，根據(jù)各天實際需求情況，刪除模板路徑中當天沒有需求的多天需求顧客；然后，插入僅當天有需求的單天需求顧客.單天需求顧客插入位置的選擇遵循貪婪算法：選擇插入后使總行駛時間增量最少的位置進行插入.在每次插入顧客后，立即對新路徑進行可行性檢查，除車容量限制和司機最長工作時間約束外，還需要檢查多天需求顧客的時間一致性要求，只接受可行的新路徑.

2.4 SA法

SA算法主要涉及6個參數(shù)：Iiter、Nnon-impr、W0、Wf、B和θ，其中，Iiter表示在特定溫度進行鄰域搜索的次數(shù)；Nnon-impr表示能接受的通過連續(xù)降溫當前最優(yōu)解仍未被優(yōu)化的最大次數(shù)；W0和Wf分別表示起止溫度；B為Boltzmann常數(shù)；θ（0＜θ＜1）用于控制溫度下降速度.在SA算法開始時將初始溫度W設(shè)定為W0，初始最優(yōu)解Sbest和當前解S均設(shè)為初始模板路徑或初始路徑方案，定義δobj（S）為路徑方案S對應的總行駛時間，tbestT為最優(yōu)解Sbest對應的總行駛時間.在某個溫度下的每次迭代產(chǎn)生鄰域解Sneigh，令Δ=δobj（Sneigh）-δobj（S）.若Δ＜0，則接受Sneigh為新的當前解；若Δ≥0，則隨機產(chǎn)生一個0到1的數(shù)v2～R（0，1）.如果

v2＜exp（-Δ/（BW）），則接受Sneigh為當前解.一旦找到更優(yōu)解，更新Sbest和tbestT.在每個溫度進行Iiter次迭代后，溫度下降到θW.SA法終止的條件有兩個，滿足其一即可：

（1）經(jīng)過連續(xù)Nnon-impr次降溫后，當前的最優(yōu)解仍未被優(yōu)化；

（2）當前的溫度已經(jīng)下降到終止溫度Wf或以下.

當算法停止時，即可從Sbest讀取近似最優(yōu)方案.

3 數(shù)值實驗

3.1 參數(shù)設(shè)定及數(shù)據(jù)說明

在實驗開始前，先選取一組數(shù)據(jù)反復測試不同參數(shù)組合來確定實驗的最終參數(shù)設(shè)置.對每組參數(shù)組合，本文進行了5次測試，測試參數(shù)可選值如下：

Iiter=｛1 000N，3 000N，5 000N，7 000N，9 000N｝， N為顧客數(shù)；

Nnon-impr=｛100，200，300｝；

W0=｛10，20，30，40｝；

Wf=｛0.01，0.10｝；

B=｛1/10，1/8，1/6，1/4，1/2，1｝；

θ=｛0.96，0.97，0.98，0.99｝.

在權(quán)衡算法的收斂速度和解的質(zhì)量后，本文選定如下參數(shù)：

Iiter=9 000N， Nnon-impr=100，

W0=20， Wf=0.01，

B=1/6， θ=0.98.

本文選擇文獻［8］給定的基準數(shù)據(jù)集中的3組中等規(guī)模數(shù)據(jù)進行實驗：Christofides_3_5_ 0.7，Christofides_6_5_0.7和Christofides_12_5_ 0.7，用數(shù)據(jù)集1、2、3分別代表3組數(shù)據(jù).3組數(shù)據(jù)的服務時間范圍為5 d，顧客數(shù)從50人到199人不等，各天具體的需求量和服務時間均提前已知.

3.2 交通擁堵檢驗

為刻畫不同的交通擁堵程度，擁堵因子μ在（0，1）中取11組值.針對每組實驗數(shù)據(jù)，均給出了總行駛時間ttotal和時間一致性指標lmax.用和分別表示交通擁堵比不存在交通擁堵情況下ttotal和lmax增加量的百分比，實驗結(jié)果如表1所示.

從表1可知，相較于μ=0的第1列數(shù)據(jù)，在考慮交通擁堵因素后，各組數(shù)據(jù)的ttotal和lmax均有所增加.3組數(shù)據(jù)的總行駛時間ttotal分別平均增加了20.65%、8.56%和25.94%，整體平均增加18.38%，可以直觀地理解為由于交通擁堵造成低速行駛導致總行駛時間增加.對于時間一致性指標lmax，3組數(shù)據(jù)中有2組數(shù)據(jù)的lmax大幅增加，其中，第1組數(shù)據(jù)的lmax值平均增加了18.87%，第3組數(shù)據(jù)的lmax值平均增加了18.14%，而第2組數(shù)據(jù)小幅增加1.74%，整體平均增加12.92%.造成lmax增加的原因是交通擁堵導致行駛時間的不確定性增加，最終擾亂了原有路徑規(guī)劃，如圖1所示.

圖1中，ts為服務時間，tt為行駛時間，灰色部分表示常速行駛，黑色部分表示低速行駛，服務時間共2 d，A和B為多天需求顧客，C為單天需求顧客.

假設(shè)A在2 d中均先于B接受服務，C只在第2天有需求，且在A和B之間接受服務，從圖1（b）可以看出，快遞人員在服務完C后的時刻恰好處于晚高峰期間，因此，快遞人員前往顧客B處的行駛時間增加，最終導致第2天顧客B的服務時間增加了1 h.綜上分析，交通擁堵對快遞公司的運營成本ttotal和服務質(zhì)量lmax均會造成較大負面影響，若在路徑規(guī)劃中忽略這些因素，規(guī)劃方案會嚴重偏離實際情形.

表1 不同交通擁堵情況下數(shù)據(jù)結(jié)果Tab.1 Results for data sets of different degrees of traffic congestion

圖1 交通擁堵圖例Fig.1 Example of traffic congestion

3.3 工作量平衡性檢驗

區(qū)別于傳統(tǒng)的一致性車輛路徑問題，本文研究一致性車輛路徑問題時增加了新約束條件式（12）.

為刻畫快遞公司對工作量平衡性問題的不同重視程度，令

M=γM′，

式中：M′為司機平均工作量水平，

γ為重視程度因子，其值越小表示快遞公司越重視此問題.

在本實驗中，γ在（1，2）中取11個值，檢驗了工作量平衡性對快遞公司運營成本和服務質(zhì)量的影響.針對每組實驗數(shù)據(jù)，除指標ttotal、lmax、和外，本文還給出了不同重視程度下快遞人員的平均工作不平衡量bwl，以及隨著重視程度提高導致快遞人員平均工作量比γ=2時平均工作量減少的百分比，結(jié)果如表2所示.

由表2可知，隨著重視程度的提高，ttotal和lmax都呈現(xiàn)增長趨勢，以數(shù)據(jù)集3為例，相較于重視程度最低γ=2時，ttotal和lmax分別平均增加了3.13%和1.60%.ttotal和lmax增加是因為新約束條件導致解空間縮小.

從表2可以發(fā)現(xiàn)，小幅度增加ttotal和lmax可以使bwl大幅度提高，以數(shù)據(jù)集2為例尤其明顯，當ttotal和lmax分別平均增加1.00%和3.38%時，bwl平均下降了50.01%.

從整體上看，當快遞人員的工作量平衡性平均提高35.82%時，僅使總行駛時間和快遞人員在任意兩天到達同一顧客的最早與最晚時刻之差分別平均增加2.29%和1.68%.由此可見，快遞公司在進行路徑規(guī)劃時，提高對快遞人員工作量平衡性的重視程度，不會以大幅度提高運營成本或降低服務質(zhì)量作為代價.

表2 對工作量平衡性不同重視程度下數(shù)據(jù)結(jié)果Tab.2 Results for data sets of different degrees of emphasis on workload balance

4 結(jié)束語

本文提出了考慮交通擁堵和工作量平衡性的一致性車輛路徑問題，此問題從兩方面體現(xiàn)出了重要現(xiàn)實意義：

（1）交通擁堵逐漸成為不可避免的日常問題，對快遞公司的一致性服務提出了新挑戰(zhàn)，若在路徑規(guī)劃中忽略此因素，將得到不切實際的路徑方案；

（2）快遞人員通常以計件工資的形式獲取收入，若不能合理安排各個快遞人員的派件量，將會加劇快遞人員之間的收入差距.針對新問題，本文設(shè)計了兩階段TSA算法，并通過對3個數(shù)據(jù)集的數(shù)值實驗，驗證了交通擁堵和工作量平衡性因素對快遞公司運營成本和服務質(zhì)量的影響.

實驗結(jié)果表明：交通擁堵會大幅度提高運營成本，服務質(zhì)量也會有所下降；當小幅度提高運營成本且服務質(zhì)量下降不多的情況下，快遞人員的工作量平衡性將得到顯著提高.

［1］ DANTZIG G B，RAMSER J H.The truck dispatching problem［J］.Management Science，1959，6：80-91.

［2］ NAGY G，WASSAN N A，SPERANZA M G，et al.The vehicle routing problem with divisible deliveries and pickups［J］.Transportation Science，2015，49（2）：271-294.

［3］ 鄒書蓉，黃曉濱，張宏偉.有容量約束車輛路徑問題的多目標遺傳算法［J］.西南交通大學學報，2009，44（5）：782-786.

［4］ SCHNEIDER M，STENGERA，GOEKED.The electric vehicle routing problem with time windows and recharging stations［J］.Transportation Science，2014，48（4）：500-520.

［5］ LAPORTE G. Fiftyyearsofvehiclerouting［J］. Transportation Science，2009，43（4）：408-416.

［6］ 王雅琪，楊雪梅.電子商務與快遞業(yè)融合發(fā)展的動力機制研究［J］.物流工程與管理，2015，37（1）：150-151.

［7］ KOVACS A A，PARRAGH S N，HARTL R F.A template-based adaptive large neighborhood search for the consistent vehicle routing problem［J］.Networks，2014，63（1）：60-81.

［8］ GROER C，Golden B，WASIL E.The consistent vehicle routing problem［J］.Manufacturing Service and Operations Management，2009，11（4）：630-643.

［9］ WOODWARD C A，ABELSON J，TEDFORD S，et al. Whatis important to continuity in home care？perspectives of key stakeholders［J］.Social Science and Medicine，2004，58（1）：177-192.

［10］ FEILLET D，GARAIX T，LEHUEDE F，et al.A new consistent vehicle routing problem for the transportation ofpeople with disabilities［J］. Networks，2014，63（3）：211-224.

［11］ TARANTILIS C D，STAVROPOULOU F，REPOUSSIS P P.A template-based tabu search algorithm for the consistent vehicle routing problem［J］.Expert Systems with Applications，2012，39（4）：4233-4239.

［12］ GOLDEN B L，KOVACS A A，HARTL R F，et al. The generalized consistent vehicle routing problem［J］. Transportation Science，2015，49（4）：796-816.

［13］ LUO Z X，QIN H，CHE C H，et al.On service consistency in multi-period vehicle routing［J］. European Journal of Operational Research，2015，243（3）：731-744.

［14］ JANSSENS J，DEN BERGH J V，SORENSEN K，et al.Multi-objective microzone-based vehicle routing for courier companies： From tactical to operational planning［J］. European Journal of Operational Research，2015，242：222-231.

［15］ 北京交通發(fā)展研究中心.北京市2010年交通運行報告［R］.北京：北京交通發(fā)展研究中心，2011.

［16］ FIGLIOZZI M A.The impacts of congestionon commercial vehicle tour characteristics and costs［J］. Transportation Research Part E，2010，46：496-506.

［17］ TAN T F，NETSSINE S.When does the devil make work？an empirical study of the impact of workload on worker productivity［J］.Management Science，2014，60（6）：1574-1593.

［18］ SOYSAL M，BLOEMHOF-RUWAARD J M，BEKTAS T.The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations［J］. International Journal of Production Economics，2015，164：366-378.

［19］ KOK A L，HANS E W，SCHUTTEN J M J.Vehicle routing under time-dependent travel times：the impact of congestion avoidance［J］.Computers and Operations Research，2012，39：910-918.

［20］ JANSSENS J，DEN BERGH J V，SORENSEN K，et al.Multi-objective microzone-based vehicle routing for courier companies： from tactical to operational planning［J］. European Journal of Operational Research，2015，242：222-231.

［21］ YU V F，LIN S Y.A simulated annealing heuristic for the open location-routing problem［J］.Computers and Operations Research，2015，62：184-196.

考慮交通擁堵及工作量平衡性的一致性車輛路徑問題

劉恒宇， 汝宜紅

Consistent Vehicle Routing Problem Considering Traffic Congestion and Workload Balance

LIU Hengyu， RU Yihong
（School of Economics and Management，Beijing Jiaotong University，Beijing 100044，China）

In order to investigate the effects of transportation congestion and workload balance on the delivery routing of express delivery companies which wish to provide consistent services，a consistent vehicle routing problem considering traffic congestion and workload balance was proposed and a mixed integer programming model for this problem was constructed.In view of the model's NP-hard property，a two-phase template-based simulated annealing method（TSA）was applied to solve this problem.The TSA attains an initial route plan by constructing template routes first，and then optimizes them using the simulated annealing method to decrease the total travel time.To verify the validity of the proposed model and algorithm，numerical experiments were conducted using three benchmark data sets.Results show that the model and TSA can solve this problem effectively.The traffic congestion will significantly increase the total travel time by an average of 18.38%and increase the difference between the earliest and latest arrival time at the same customer within any two days by an average of 12.92%.Besides，when the average difference of the delivery men＇s shipment quantity decreases by 35.82%，the total travel time and the difference between the earliest and latest arrival time at the same customer are only increased by 2.29%and 1.68%，respectively.

book=932,ebook=121

consistent vehicle routing problem；express delivery industry；traffic congestion；workload balance

0258-2724（2016）05-0931-07

10.3969/j.issn.0258-2724.2016.05.016

U116.2

A

2015-09-07

云南省教育廳課題（SYSX201412）；北京市科委課題（Z141100003614059）

劉恒宇（1990—），男，博士研究生，研究方向為城市物流，E-mail：14113138@bjtu.edu.cn

汝宜紅（1953—），女，教授，博士生導師，研究方向為逆向物流，E-mail：yhru@bjtu.edu.cn

劉恒宇，汝宜紅.考慮交通擁堵及工作量平衡性的一致性車輛路徑問題［J］.西南交通大學學報，2016，51（5）：931-937.

（中文編輯：秦萍玲 英文編輯：蘭俊思）