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

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

0引言

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

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

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

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

1問題描述

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

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

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

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

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

2.1符號說明

問題的決策變量有：

(1)

t0k=車輛k離開起始點的時刻，

(2)

tik=車輛k離開節(jié)點i的時刻.

(3)

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

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

(4)

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

(5)

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

(6)

配送車輛必須離開起始點為

(7)

配送車輛平衡為

(8)

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

(9)

消除子回路為：

(10)

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

t0k=Tk，?k∈v;

(11)

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

(12)

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

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

(13)

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

(14)

其中

(15)

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

2.3一個特例

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

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問題在這個特例中轉(zhuǎn)化為混合整數(shù)線性規(guī)劃問題，從而可以通過已有的程序包進(jìn)行求解.在每邊的通過時間成本對于車流量是多項式的形式時，類似的變形依然成立.

3實驗與分析

3.1算例描述

Sioux Falls網(wǎng)絡(luò)是交通科學(xué)領(lǐng)域應(yīng)用最廣泛的測試網(wǎng)絡(luò)之一，該網(wǎng)絡(luò)有24個節(jié)點、72條邊.為了描述通勤車輛的交通分配，我們分別假設(shè)10對起點/終點與207條路徑以及496對起點/終點和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)行了計算.

3.2結(jié)果與分析

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

表1　通勤車輛有10對起點/終點與207條路徑

表2　通勤車輛有496對起點/終點與1 941條路徑

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

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

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

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

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

4結(jié)語

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

[參考文獻(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

[基金項目]國家自然科學(xué)基金資助項目(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