車路協(xié)同環(huán)境下多配送中心DVRP研究*

張 赫 郭文倩 張健松 胡治杰

(大連海事大學(xué)交通運輸工程學(xué)院 大連 116026)

車路協(xié)同環(huán)境下多配送中心DVRP研究*

張 赫 郭文倩 張健松 胡治杰

(大連海事大學(xué)交通運輸工程學(xué)院 大連 116026)

大數(shù)據(jù)時代的到來，車路協(xié)同技術(shù)的應(yīng)用，使得車輛之間、車輛與交通控制部門、企業(yè)之間能夠?qū)崿F(xiàn)實時信息共享，克服傳統(tǒng)運輸問題中城市配送與實際道路網(wǎng)絡(luò)脫節(jié)的問題，貨物能更快更好地到達客戶手中，提高企業(yè)的配送速度和降低運營成本.路徑選擇以總費用最小為目標(biāo)，去掉V/C較大的路段，同時考慮交叉口延誤，利用TransCAD與MATLAB結(jié)合，求解多配送中心、存在車輛共享和租賃的軟時間窗限制的開環(huán)VRP問題.結(jié)果表明，考慮真實道路網(wǎng)的交通負(fù)荷對配送車輛順暢運行具有重要意義，能夠使配送時間減少17.64%，配送費用降低14.85%.

智能交通；車輛路徑問題；TransCAD；MATLAB；車路協(xié)同；多配送中心

0 引 言

車輛路徑問題(vehicle routing problem，VRP)是指在道路線網(wǎng)中，在滿足客戶需求前提下，找到符合配送車輛載重量要求的線路，使總費用(包括固定成本，運輸費用不滿足時間窗要求的機會成本和懲罰成本)最少、運輸時間最短等目標(biāo).通常意義上的靜態(tài)VRP已經(jīng)不能適應(yīng)現(xiàn)代運輸?shù)男枨?因此，文中在車路協(xié)同環(huán)境下，配送中心、客戶通過交通管理信息的共享，構(gòu)建配送信息平臺，研究動態(tài)車輛路徑問題(DVRP)，使其既能滿足客戶的需要，又使企業(yè)達到效益最大化.

關(guān)于DVRP的研究，Victor等[1]對動態(tài)路徑問題進行了研究綜述.Potvin等[2]針對客戶需求動態(tài)和行駛時間動態(tài)，提出了不同的調(diào)度策略.王旭等[3]建立了基于時間軸的DVRP模型，設(shè)計了“初始優(yōu)化+實時優(yōu)化”兩階段的求解策略，根據(jù)動態(tài)客戶需求局部調(diào)整計劃路徑.張婷等[4]將動態(tài)車輛路徑問題轉(zhuǎn)化為靜態(tài)，針對需求量變化、需求點增減、道路中斷、車輛故障四種動態(tài)情形下的配送線路實時優(yōu)化問題.李妍峰等[5]提出車輛接受實時交通信息，在關(guān)鍵點更新配送線路.

對于多配送中心車輛路徑問題，于濱等[6]提出“先分類，后優(yōu)化”的思想，將多配送中心問題轉(zhuǎn)化為多個單配送中心VRP問題，然后用改進的蟻群算法進行求解.王萬良等[7]對存在多配送中心、車輛共享的軟時間窗動態(tài)需求VRP問題，建立了兩階段模型，并運用混合3-opt量子進化算法進行求解.劉家利等[8]提出了多配送中心、存在車輛共享和租賃的有時間窗限制的開環(huán)VRP問題，引入虛擬配送中心，將多配送中心轉(zhuǎn)化為單配送中心，并通過混合遺傳算法求解.

雖然對于多配送中心VRP問題已有大量研究，但大多并沒有結(jié)合實際路網(wǎng)，考慮在實時交通信息下道路網(wǎng)絡(luò)對配送車輛的影響.針對目前研究存在的問題，文中考慮了在實時交通網(wǎng)路中，存在配送中心之間車輛共享且能夠從其他機構(gòu)租賃車輛的多配送中心VRP問題，并且考慮車輛不必返回原配送中心，就近回到配送中心，以達到配送中心間運力均衡，總費用最小的目的.

1 車路協(xié)同系統(tǒng)

車路協(xié)同系統(tǒng)[9](cooperative vehicle infrastructure system，CVIS)主要由無線通信模塊、路邊協(xié)調(diào)控制模塊以及智能車載設(shè)備構(gòu)成，這與現(xiàn)代物流配送系統(tǒng)的需求不謀而合.現(xiàn)代物流配送系統(tǒng)信息傳遞是根據(jù)客戶需求，結(jié)合交通管理中心獲取服務(wù)區(qū)域的基本路況、車輛位置、服務(wù)地點，計劃當(dāng)前路徑，反饋給配送中心及車輛，實現(xiàn)物流配送和道路網(wǎng)絡(luò)的協(xié)調(diào)互動，見圖1.城市運輸調(diào)度系統(tǒng)在信息平臺的基礎(chǔ)上，通過借助GIS、GPS、ITS等技術(shù)獲取動態(tài)信息，使得客戶能夠在靈活地變更貨運需求，配送中心車輛能夠靈活地調(diào)度，見圖2.

圖1 現(xiàn)代物流運輸信息傳遞

圖2 城市運輸調(diào)度系統(tǒng)

2 問題描述與模型建立

2.1 問題描述

文中描述的存在車輛共享和實時交通信息的多配送中心動態(tài)需求的車輛路徑問題描述如下.

假設(shè)有M個配送中心，儲備同種貨物，N個客戶，每個配送中心擁有額定載重量為Q的配送車輛Km輛.配送車輛從配送中心出發(fā)，完成配送任務(wù)后返回使總體費用最小的配送中心.每個客戶只能由一輛車為其服務(wù)且只能服務(wù)一次，客戶的需求量不能超過車輛的額定載貨量.在一個計劃期內(nèi)，每輛車的工作時間不能超過規(guī)定的最大工作時間T，最長運輸距離為D，配送車輛在配送中心的裝卸時間為wtomk，在客戶點的裝卸時間為wtnmk，客戶n的需求量為qn，其服務(wù)時間窗為[ETn，LTn]在服務(wù)過程中會有新的客戶需求.如果某個配送中心所需的車輛數(shù)多于該配送中心目前擁有的車輛數(shù)，可以從其臨近的配送中心調(diào)用車輛.所尋求的目標(biāo)是在實時交通信息下找出合適的調(diào)度方案，滿足客戶的時間窗要求，并使總的運輸成本最小.文中僅考慮送貨情況.

2.2 參數(shù)說明

Wr為單位車輛的固定成本；Wf為單位時間單位配送車輛的運輸成本；tijmk為配送中心m第k輛車從點i到點j的實際運輸時間；M為無窮大的懲罰成本；P(t)為未滿足時間窗要求，配送車輛所需付出的成本損失(懲罰費用)；Tnmk為配送中心m第k輛車到達客戶點n的時刻；qnmk為配送中心m的車輛k運輸?shù)目蛻鬾的需求量.

決策變量：

xijmk=

ynmk=

2.3 模型建立

1) 預(yù)優(yōu)化模型 在預(yù)優(yōu)化階段，根據(jù)已知客戶信息和靜態(tài)交通信息安排車輛的初始運行線路，若某個配送中心車輛供不應(yīng)求，可從其他配送中心調(diào)用車輛.假設(shè)車輛共享是在對客戶進行服務(wù)之前完成，即對客戶服務(wù)的時間窗沒有影響.

(1)

式中：P(t)為分段函數(shù)，函數(shù)關(guān)系見式(2).

(2)

注：a=100元/h;b=200元/h.

2) 實時優(yōu)化模型 配送車輛每經(jīng)過一個關(guān)鍵點(交叉口和客戶點)，配送線路會根據(jù)實時交通信息和新的客戶需求進行更新.此時，預(yù)優(yōu)化階段的車輛已經(jīng)服務(wù)了部分客戶，車輛所載貨量也相應(yīng)減少，在實時交通狀況和車輛剩余貨量的情況下，將新客戶加入到配送線路中，如若現(xiàn)有配送車輛不能滿足新客戶需求，則需要重新安排.

在實時優(yōu)化階段，U為第一階段未服務(wù)客戶數(shù)和新加入的客戶數(shù)量，第一階段車輛的剩余載貨量為Qe，第二階段各配送中心派車Pm.

(3)

s.t.

k∈{1,2,…,Km},m∈{1,2,…,M}

(4)

k∈{1,2,…,Km},m∈{1,2,…,M}

(5)

(6)

(7)

m∈{1,2,…,M}

(8)

n∈{1,2,…,N}，k∈{1,2,…,Km},

m∈{1,2,…,M}

(9)

n,h∈{1,2,…,N}，Tnmk

(10)

k∈{1,2,…,Km},m∈{1,2,…,M}

(11)

xinmk(Tnmk+tinmk+wtnmk-Thmk)≤0,

i∈{1,2,…,M,M+1,…,M+N},

n,h∈{1,2,…,N},

k∈{1,2,…,Km},m∈{1,2,…,M}

(12)

(?S?{1,2,…,N},且2≤|S|≤n-2)(13)

式(3)為目標(biāo)函數(shù)，總費用最?。皇?4)保證車輛載重量不超過額定載重量；式(5)保證配送車輛行駛距離不超過車輛單次能夠行駛的最大距離；式(6)保證一輛配送車輛最多只能到達客戶點一次；式(7)保證每個客戶只能被一輛車服務(wù)；式(8)保證車輛滿載出發(fā)；式(9)保證車輛在服務(wù)某客戶前，剩余載貨量能夠滿足該客戶的需求量；式(10)為配送車輛服務(wù)完客戶后，剩余載貨量的變化關(guān)系；式(11)保證配送車輛的工作時間不大于最大工作時間；式(12)若兩客戶被同輛車服務(wù)，服務(wù)時間要滿足先后順序；式(13)避免子回路.

3 車路協(xié)同環(huán)境下的多配送中心動態(tài)車輛路徑問題

3.1 考慮交叉口延誤的動態(tài)最短路徑

在城市道路系統(tǒng)中，交叉口是交通順暢運行的瓶頸，由于交叉口轉(zhuǎn)向而引起的時間延誤可以達到全部行程時間的17%～35%，因此，文中在計算道路網(wǎng)絡(luò)的最短路徑時，考慮了交叉口延誤，粗略按路段行程時間的20%計算.

文中用10×10的網(wǎng)格模擬道路網(wǎng)，見圖3.該路網(wǎng)中有100個交叉口，180條路段.假設(shè)路網(wǎng)中所有路段均是雙向，任意兩個客戶之間有多條路徑可以連通，每條路段的實時行程時間由式(14)交通阻抗函數(shù)得出[10].由于交通流具有相似性，同時為了避免海量數(shù)據(jù)計算的復(fù)雜性，文中每15 min收集一次交通流數(shù)據(jù)，并取上一個15 min的數(shù)據(jù)用于實時計算.

(14)

式中：toijmk為配送中心m第k輛車在自由流條件下，從點i到點j的運輸時間dij/v;Cij為點i到點j的路段的通行能力；xij為點i到點j的路段的實際交通量；α，ρ為參數(shù)(取α=0.15，ρ=1.00).

圖3 道路網(wǎng)及客戶點

3.2 車路協(xié)同環(huán)境下的運行流程

DVRP問題的求解，屬于NP-hard問題，很多學(xué)者已經(jīng)對其作出了大量研究，文中利用TransCAD與MATLAB的結(jié)合，采用混合遺傳算法進行求解，其流程圖見圖4.

圖4 運行流程圖

4 實例分析

文中所用10×10的道路網(wǎng)，每條路段的長度為5 km，路網(wǎng)中的主干道、次干道和支路，其自由流情況下的速度分別為50,40和20 km/h，分為對應(yīng)的自由流狀態(tài)下的路段行程時間分別為0.1,0.125和0.2 h.文中隨機生成18個靜態(tài)客戶，兩個動態(tài)客戶，動態(tài)客戶19，20分別在10 min，1 h時發(fā)出送貨請求，客戶點、配送中心分布見圖5.假定配送車輛的額定載貨量為4 t，單次能夠行駛的最大距離為100 km，配送中心的工作時間為[0 h,10 h]，客戶能夠接受的等待時間是在發(fā)出送貨請求后的兩小時之內(nèi)，且每個客戶的送貨需求都為1 t.配送過程中每使用一輛車所產(chǎn)生的固定成本為1 000元/輛，單位時間每輛車的配送成本為50元/h.配送中心Ⅰ擁有車輛V1，配送中心Ⅱ擁有車輛V2，V3，配送中心Ⅲ擁有車輛V4，V5.

根據(jù)以上數(shù)據(jù)，圖5a)的路線表示初始狀態(tài)下的配送線路，服務(wù)順序及費用見表1.在運行過程中，根據(jù)實時交通流信息，道路V/C大于0.8，認(rèn)為比較擁堵，在路徑選擇過程中去掉這些路段，避免加重這些路段的交通壓力，導(dǎo)致送貨延遲.利用實時交通信息，結(jié)合新的客戶信息，車路協(xié)同環(huán)境下的配送路線服務(wù)順序，見圖5b).

圖5 配送路線圖

車輛編號優(yōu)化前后起始配送中心服務(wù)客戶順序返回配送中心服務(wù)時間/h費用/元1初始Ⅰ18-17-12-5Ⅰ4.2851851.250優(yōu)化Ⅰ11-2-4-20Ⅰ3.9471262.9502初始Ⅱ3-10-13-16Ⅱ2.3281142.580優(yōu)化Ⅱ3-10-16-13Ⅱ2.0331101.6253初始Ⅰ11-2-4Ⅰ4.5571502.825優(yōu)化Ⅱ5-12-17-18Ⅰ2.7581182.8754初始Ⅲ15-8-7-1Ⅰ2.3121115.575優(yōu)化Ⅲ15-8-7-1Ⅰ2.3121115.5755初始Ⅲ9-14-6Ⅰ3.2561199.000優(yōu)化Ⅲ9-14-6-19Ⅱ3.1561157.675初始合計16.7386811.23優(yōu)化合計13.7865820.70

由表1可知，如果不進行實時線路優(yōu)化，按照初始線路配送貨物時，運輸時間長，費用高，并且有六位客戶未滿足時間窗要求，沒有在規(guī)定時間內(nèi)送達.而根據(jù)實時交通流信息調(diào)整線路，避免了配送車輛進入擁擠路段，加快了運輸速度，更易滿足客戶的時間要求，配送時間減少17.64%，也節(jié)省的企業(yè)的運輸成本，配送費用降低14.54%.

5 結(jié) 束 語

針對目前車輛路徑問題的研究所存在的缺少與實際路網(wǎng)有效結(jié)合，造成了配送車輛在道路網(wǎng)運行過程中無法達到預(yù)計效果的問題，同時從物流企業(yè)本身的效益出發(fā)，能使企業(yè)在投入最少的車輛成本的情況下，通過車輛共享實現(xiàn)企業(yè)內(nèi)車輛的有效利用，也可借助租賃的方式實現(xiàn)企業(yè)效益的最大化.在車路協(xié)同環(huán)境下，利用實時的交通流信息，從大數(shù)據(jù)帶來的海量數(shù)據(jù)著手研究動態(tài)車輛路徑問題對于現(xiàn)代物流企業(yè)的調(diào)度管理具有重要的實踐價值.

[1] VICTOR P, MICHEL G, CHRISTELLE G. A review of dynamic vehicle routing problems[J]. European Journal of Operational Research,2013,225(1):1-11.

[2] POTVIN J Y, XU Y, BENYAHIA I. Vehicle routing and scheduling with dynamic travel times[J]. Computers &Operations Researvh,2006,33(4):1129-1137.

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

[4] 張婷,賴平仲,何勤飛，等.基于實時信息的城市配送車輛動態(tài)路徑優(yōu)化[J].系統(tǒng)工程,2015,33(7):58-64.

[5] 李妍峰,高自幼,李軍.動態(tài)網(wǎng)絡(luò)車輛路徑派送問題研究[J].管理科學(xué)學(xué)報,2014,17(8):1-9.

[6] 于濱,靳鵬歡,楊忠振.兩階段啟發(fā)式算法求解帶時間窗的多中心車輛路徑問題[J].系統(tǒng)工程理論與實踐,2012,32(8):1793-1800.

[7] 王萬良,黃海鵬,趙燕偉，等.基于車輛共享的軟時間窗動態(tài)需求車輛路徑問題[J].計算機集成制造系統(tǒng),2011,17(5):1056-1063.

[8] 劉家利,馬祖軍.存在車輛租賃及共享且有時間窗的多配送中心開環(huán)VRP[J].系統(tǒng)工程理論與實踐,2013,33(3):666-675.

[9] TANIKELLA H, SMITH B L, ZHANG G. Development of a VII-enabled prototype intersection collision warning system[J]. Journal of Computing in Civil Engineering,2007,11:434-440.

[10] 楊忠振,穆雪,朱曉聰.交通流變化下的多配送中心：多需求點配送網(wǎng)絡(luò)優(yōu)化模型[J].交通運輸工程學(xué)報,2015,15(1):101-107.

Research on Multi-depot Dynamic Vehicle Routing Problem Under IntelliDriverSM

ZHANGHeGUOWenqianZHANGJiansongHUZhijie

(TransportationManagementCollege,DalianMaritimeUniversity,Dalian116026,China)

With the advent of big data era, the application of vehicle road technology makes the real-time information sharing between vehicles, traffic control departments and enterprises, which overcomes the problems of urban transportation and the actual road network in traditional transportation problems, makes the goods faster and better, and improves the delivery speed and reduces operating costs. The target of path selection is to minimize the total cost, removing the largerV/Cvalue during path selection. Taking the intersection delay into consideration and combining TransCAD with MATLAB, the open-loop vehicle routing problem (VRP) under multi-depot and soft time Windows restriction based on vehicle sharing and leasing, is solved. The results show that considering the real road network traffic load is significant to keep vehicle running smoothly. The delivery time will reduce by 17.64% and the distribution costs will reduce by 14.85%.

intelligent transportation; vehicle routing problem(VRP); TransCAD; MATLAB; IntelliDriverSM; multi-depot

U491.2

10.3963/j.issn.2095-3844.2017.06.001

2017-10-26

張赫(1971—)：男，博士，副教授，主要研究領(lǐng)域為智能運輸系統(tǒng)、交通運輸規(guī)劃與管理、交通控制、智能物流系統(tǒng)

*國家重點研發(fā)計劃重點專項項目資助(2017YFC0805309)