基于雙層規(guī)劃的車輛路徑問題研究

王一甌，王海鵬，2

(1.賓夕法尼亞州立大學(xué)工程學(xué)院，賓夕法尼亞 16801；2.南開大學(xué)經(jīng)濟(jì)學(xué)院，天津 300071)

基于雙層規(guī)劃的車輛路徑問題研究

王一甌1，王海鵬1，2

(1.賓夕法尼亞州立大學(xué)工程學(xué)院，賓夕法尼亞 16801；2.南開大學(xué)經(jīng)濟(jì)學(xué)院，天津 300071)

[摘要]針對城市交通堵塞的問題，提出了一種基于車輛路徑問題(VRP)和使用者均衡問題(UE)的雙層優(yōu)化模型.在其上層是車輛路徑選擇問題的一種拓展，在其下層采用用戶均衡交通分配模型對城市交通中的貨運(yùn)車輛和客運(yùn)/通勤車輛進(jìn)行第一原理性的數(shù)學(xué)刻畫.結(jié)果表明：VRP-UE模型不但可以提出能夠規(guī)避堵塞的交通方案，而且可以減少車輛本身可能帶來的交通阻塞；采用雙層優(yōu)化模型可以顯著降低車輛出行的時(shí)間成本.

[關(guān)鍵詞]車輛路徑；雙層規(guī)劃；城市物流

0引言

自1959年Dantzig和Ramser提出車輛路徑選擇問題以來[1]，該問題已成為最著名的組合優(yōu)化問題之一.學(xué)術(shù)界在此領(lǐng)域取得了一系列的成果[2]，文獻(xiàn)中提出了幾個(gè)經(jīng)典車輛路徑選擇問題的擴(kuò)展，如隨機(jī)車輛路徑(SVRP)[3]、魯棒車輛路徑(RVRP)[4]以及帶時(shí)間窗口的車輛路徑選擇問題(VRP-TW)[5].

交通堵塞已經(jīng)成為影響城市發(fā)展和人民生活的重要問題之一.學(xué)術(shù)界對存在交通堵塞情況下的車輛出行問題的研究也已取得一些成果，如文獻(xiàn)[6]認(rèn)為物流車輛經(jīng)過不同節(jié)點(diǎn)時(shí)，所產(chǎn)生的時(shí)間成本不但與兩節(jié)點(diǎn)間的距離有關(guān)，而且與此時(shí)的時(shí)間相關(guān)(TD-VRP)，因而交通擁堵可以由動態(tài)變化的時(shí)間成本來描述.而文獻(xiàn)[7]采用的模型結(jié)構(gòu)對本文最具啟發(fā)性，該文獻(xiàn)認(rèn)為：在城市物流環(huán)境下，一方面就車輛路徑選擇問題的數(shù)學(xué)描述而言，物流車輛經(jīng)過不同節(jié)點(diǎn)之間所產(chǎn)生的時(shí)間成本應(yīng)由文獻(xiàn)[8]中的仿真模型進(jìn)行描述；另一方面，對城市交通狀況進(jìn)行模擬仿真的模型被認(rèn)為物流車輛會按最短路徑(shortest path)行駛于各個(gè)節(jié)點(diǎn)之間，但這仍然不是全局最優(yōu)的車輛路徑規(guī)劃.

此外，學(xué)術(shù)界對于交通擁堵的第一原理描述已經(jīng)發(fā)展得較為成熟，如用戶平衡交通分配模型[9]和動態(tài)用戶平衡交通分配模型[10]等.在城市交通環(huán)境下，多種車輛將參與交通，對這類行為的描述可以參見文獻(xiàn)[11]中提出的多重平衡行為模型.

車輛路徑選擇(VRP)與擁堵情況下的用戶動態(tài)均衡(UE)是2個(gè)交織在一起的相互動態(tài)影響的問題，單考慮一方面無法得到全局最優(yōu)解.本文運(yùn)用雙層規(guī)劃方法首次將兩者進(jìn)行結(jié)合，以(靜態(tài)的)用戶平衡交通分配模型描述城市物流中的交通擁堵現(xiàn)象，并得到基于全局最優(yōu)解的車輛出行方案.

1問題描述

城市物流環(huán)境下交通道路網(wǎng)絡(luò)上共有兩類車輛：(1)用“通勤車輛”指代交通網(wǎng)絡(luò)上已經(jīng)存在的車輛，其指代各類小型客運(yùn)車輛，本文采取用戶平衡交通分配模型對這類車輛的行為進(jìn)行描述；(2)用“物流車輛”指代需要本文模型進(jìn)行規(guī)劃的大型貨運(yùn)車輛.本文所提出的雙層規(guī)劃模型之所以將物流車輛置于問題的上層，是因?yàn)槲锪鬈囕v是城市道路交通中有組織的、長期的、頻繁的使用者，與一般通勤的交通參與者不同，這類使用者有能力利用此方面的優(yōu)勢對自身路徑進(jìn)行更好地規(guī)劃.換言之，從Stackelberg博弈的意義上看，物流車輛應(yīng)該在建模中處于博弈的領(lǐng)導(dǎo)層(Leader)，即上層.

在城市物流環(huán)境下雙層車輛路徑選擇問題的幾個(gè)特性.首先，在傳統(tǒng)的車輛路徑選擇問題中，需要配送服務(wù)的客戶由散落在二維平面中的點(diǎn)來描述，其位置和需求均已知.當(dāng)設(shè)計(jì)配送路線時(shí)，這些節(jié)點(diǎn)可以任意被所設(shè)計(jì)的路線連接.而在城市物流環(huán)境下，客戶位于描述城市交通網(wǎng)絡(luò)的已知節(jié)點(diǎn)上，即必須在已有的網(wǎng)絡(luò)上進(jìn)行路徑規(guī)劃.其次，由于交通網(wǎng)絡(luò)中存在上文所描述的兩類車輛，而它們一類由整數(shù)變量描述，一類由連續(xù)變量描述，本文將引入類似于文獻(xiàn)[11]對其進(jìn)行描述.

整個(gè)雙層規(guī)劃車輛路徑問題(VRP-UE)的數(shù)學(xué)模型是均衡約束規(guī)劃問題，上層將是整數(shù)規(guī)劃問題，其流程見圖1.

圖1　雙層規(guī)劃車輛路徑選擇模型的流程

2數(shù)學(xué)模型與分析

2.1符號說明

問題的決策變量有：

(1)

t0k=車輛k離開起始點(diǎn)的時(shí)刻，

(2)

tik=車輛k離開節(jié)點(diǎn)i的時(shí)刻.

(3)

2.2數(shù)學(xué)模型

根據(jù)上述變量和模型假設(shè)得到VRP-UE問題的數(shù)學(xué)模型.其上層問題的目標(biāo)函數(shù)為

(4)

(1)上層問題的約束條件.每個(gè)客戶只由某一輛配送車輛服務(wù)，即

(5)

每輛配送車輛的載貨量約束為

(6)

配送車輛必須離開起始點(diǎn)為

(7)

配送車輛平衡為

(8)

每個(gè)客戶僅能被一輛配送車輛服務(wù)一次，即

(9)

消除子回路為：

(10)

(2)連通雙層車輛路徑選擇問題的一系列約束條件.假定所有配送車輛離開起始點(diǎn)的時(shí)間已知，即

t0k=Tk，?k∈v;

(11)

實(shí)際上是變量ξ(i，j)的定義式表示將通過邊(i，j)的配送車輛數(shù)量，于是有

(12)

上層中經(jīng)過每條邊的時(shí)間成本將由下層描述為

tik-tjk≥vijkC(i，j)(h*，ξ(i，j))，?k∈v，i，j∈N.

(13)

下層的變分不等式(VariationalInequality)描述為求解h*∈Λ2使得

(14)

其中

(15)

綜上所述，本文所提出的雙層車輛路徑選擇問題實(shí)際上是均衡約束規(guī)劃問題的一個(gè)特例.其最優(yōu)解的存在性：對于下層的變分不等式而言，上層的任意可行解只會改變交通網(wǎng)絡(luò)相應(yīng)邊的車流量，從而使下層問題可解，又由于上層問題解空間的有限性，可知整體問題的最優(yōu)解的存在.但是雙層車輛路徑選擇問題最優(yōu)解的唯一性及研究一般交通成本時(shí)算法的收斂性不能被保證.

2.3一個(gè)特例

本節(jié)考慮交通網(wǎng)絡(luò)任意邊運(yùn)輸成本為線性的情況時(shí)，則有

C(i，j)(f(i，j)，ξ(i，j))=α(i，j)f(i，j)+βf(i，j)ξ(i，j)+γ(i，j).

(16)

為了刻畫物流車輛超大的體積等效應(yīng)，引進(jìn)系數(shù)β(i，j)以便將物流車輛轉(zhuǎn)換成等體積的通勤車輛流進(jìn)行考慮.則(14)—(15)可以轉(zhuǎn)化為：

(17)

ρod≥0，?(o，d)∈w；

(18)

(19)

ρod≤M(1-zod)，?(o，d)∈w；

(20)

(21)

hp≥0，?p；

(22)

(23)

zod∈{0，1}，?(o，d)∈w.

(24)

其中M是大的正整數(shù).于是VRP-UE問題在這個(gè)特例中轉(zhuǎn)化為混合整數(shù)線性規(guī)劃問題，從而可以通過已有的程序包進(jìn)行求解.在每邊的通過時(shí)間成本對于車流量是多項(xiàng)式的形式時(shí)，類似的變形依然成立.

3實(shí)驗(yàn)與分析

3.1算例描述

Sioux Falls網(wǎng)絡(luò)是交通科學(xué)領(lǐng)域應(yīng)用最廣泛的測試網(wǎng)絡(luò)之一，該網(wǎng)絡(luò)有24個(gè)節(jié)點(diǎn)、72條邊.為了描述通勤車輛的交通分配，我們分別假設(shè)10對起點(diǎn)/終點(diǎn)與207條路徑以及496對起點(diǎn)/終點(diǎn)和1 941條路徑2種情況.本文中Sioux Falls網(wǎng)絡(luò)的相關(guān)數(shù)據(jù)來自文獻(xiàn)[12]，將模型轉(zhuǎn)化至2.3中的混合整數(shù)規(guī)劃問題之后，在MATLAB2012下調(diào)用了Gurobi 5.5程序包對問題進(jìn)行了計(jì)算.

3.2結(jié)果與分析

將2種測試條件下得到的結(jié)果分別列于表1和2.在研究過程中分別設(shè)定了3個(gè)對照組：(1)對于不同客戶節(jié)點(diǎn)，其貨運(yùn)需求是否相同；(2)對于不同物流車輛，其最大容量是否相同；(3)對于網(wǎng)絡(luò)中通勤車輛，其總交通量是較大還是一般.為了驗(yàn)證雙層車輛路徑模型(VRP-UE)解的有效性，我們設(shè)計(jì)了對照計(jì)算實(shí)驗(yàn)方案：首先在忽略通勤車輛帶來的交通堵塞的條件下，計(jì)算經(jīng)典車輛路徑模型(VRP)，將所得到的物流車輛路徑選擇問題與通勤車輛在一起進(jìn)行使用者均衡交通分配，亦即在Ξ(i，j)已知的情況下求解(15)式，從而得到網(wǎng)絡(luò)上每條邊的通行時(shí)間成本，然后對所有物流車輛計(jì)算總的通行時(shí)間成本.在表1和2中，將以此方法得到的對照解稱為“納什-納什”解.

表1　通勤車輛有10對起點(diǎn)/終點(diǎn)與207條路徑

表2　通勤車輛有496對起點(diǎn)/終點(diǎn)與1 941條路徑

從表1和2可知:在所考慮的交通網(wǎng)絡(luò)中，對物流車輛的容量越細(xì)分，VRP-UE模型節(jié)約的時(shí)間成本越顯著；對通勤車輛的描述越細(xì)致，VRP-UE模型節(jié)約的時(shí)間成本越顯著.其中原因是由于VRP-UE 模型考慮了通勤車輛分配.這是本文提出的全局最優(yōu)車輛通勤方案的優(yōu)勢所在.

另外，在圖2和3中列出了由雙層車輛路徑選擇模型(VRP-UE)和經(jīng)典車輛路徑選擇模型(VRP)所給出的物流車輛的出行方案(參數(shù)設(shè)置對應(yīng)表2中的第3個(gè)算例).發(fā)現(xiàn)VRP-UE模型給出了與經(jīng)典VRP模型截然不同的物流車輛路徑.

圖2　經(jīng)典路徑選擇模型解出的物流車輛路徑

圖3　雙層規(guī)劃車輛路徑選擇模型解出的物流車輛路徑

綜上所述，本文方法較不考慮交通擁堵的車輛路徑優(yōu)化方法而言，采用的雙層優(yōu)化模型(VRP-UE)可以顯著降低貨運(yùn)的時(shí)間成本.

4結(jié)語

本文中的雙層VRP-UE模型是第一個(gè)通過第一性原理同時(shí)刻畫貨運(yùn)與客運(yùn)/通勤輛在交通網(wǎng)絡(luò)中行為的模型.一系列的計(jì)算實(shí)驗(yàn)表明，在以總貨運(yùn)時(shí)間成本最小為目標(biāo)函數(shù)的情況下，考慮交通堵塞成本的雙層模型所提出的貨運(yùn)方案，明顯優(yōu)于不考慮交通堵塞成本的VRP模型.在交通堵塞的情況下，VRP-UE模型不但可以提出能夠規(guī)避堵塞的貨運(yùn)方案，而且可以減小貨運(yùn)車輛本身可能帶來的交通阻塞.

[參考文獻(xiàn)]

[1]TOTH P，DANIELE V.The vehicle routing problem[M].Philadelphia：Society for Industrial and Applied Mathematics，2001：1-26.

[2]DANTZIG G，RAMSER J.The truck dispatching problem[J].Management Science，1959，6：80-91.

[3]GENDREAU M，GILBERT L，RENE S.Stochastic vehicle routing[J].European Journal of Operational Research，1996，88：3-12.

[4]ORDONEZ F.Robust vehicle routing[M].Maryland：TUTORIALS in Operations Research，2014:153-178.

[5]GARCIA B，POTVIN J，ROUSSEAU J.A parallel implementation of the Tabu search heuristic for vehicle routing problems with time window constraints[J].Computers Operations Search，1994，21:1025-1033.

[6]MALANDRAKI C，MARK S D.Time dependent vehicle routing problems：formulations，properties and heuristic algorithms[J].Transportation Science，1992，26：185-200.

[7]TANIGUCHI E，ROB E.An evaluation methodology for city logistics[J].Transport Reviews，2000，20：65-90.

[8]FUJII S，IIDA Y，UCHIDA T.Dynamic traffic simulation to evaluate vehicle navigation systems[C]//In Vehicle Navigation and Information Systems Conference，Yokohama：IEEE Xplore，1994：239-244.

[9]FRIESZ T L.Transportation network equilibrium，design and aggregation：key developments and research opportunities[J].Transportation Research Part A：General，1985，19：413-427.

[10]FRIESZ T L，HAN K，NETO P A，et al.Dynamic user equilibrium based on a hydrodynamic model[J].Transportation Research Part B：Methodological，2013，47：102-126.

[11]YANG H，ZHANG X，QIANG M.Stackelberg games and multiple equilibrium behaviors on networks[J].Transportation Research Part B：Methodological，2007，41：841-861.

[12]Transportation Network Test Problems[EB/OL].2013-05[2015-12-07].http://www.bgu.ac.il/-bargera/tntp/.

(責(zé)任編輯：石紹慶)

A bi-level vehicle routing problem in urban logistics

WANG Yi-ou1，WANG Hai-peng1，2

(1.College of Engineering，Pennsylvania State University，PA 16801，USA；2.School of Economics，Nankai University，Tianjin 300071，China)

Abstract:Traffic congestion，caused by growing traffic volume on limited road networks，has become one of the most significant phenomenon of people’s daily life.In this paper a novel formulation of vehicle routing problem (VRP)as a bi-level optimization problem is proposed.The upper level problem is a generalization of VRP for the freight service provider.The lower level，which is a characterization of urban traffic congestion from first principle，takes on the form of user equilibrium (UE)traffic assignment of the commuters traffic.A series of numerical experiments on different networks shows a significant saving on total travel cost for the freight service provider compared to native applications of VRP.

Keywords:vehicle routing problem；bi-level optimization；urban logistics

[文章編號]1000-1832(2016)02-0093-06

[收稿日期]2015-12-07

[基金項(xiàng)目]國家自然科學(xué)基金資助項(xiàng)目(71372002).

[作者簡介]王一甌(1987—)，男，博士研究生，主要從事動態(tài)網(wǎng)絡(luò)優(yōu)化、博弈論研究.

[中圖分類號]U 491.1[學(xué)科代碼]580·70

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

[DOI]10.16163/j.cnki.22-1123/n.2016.02.020