王一甌，王海鵬，2

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

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

王一甌1，王海鵬1，2

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

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

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

0引言

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

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

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

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

1問題描述

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

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

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

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

2數學模型與分析

2.1符號說明

問題的決策變量有：

(1)

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

(2)

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

(3)

2.2數學模型

根據上述變量和模型假設得到VRP-UE問題的數學模型.其上層問題的目標函數為

(4)

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

(5)

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

(6)

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

(7)

配送車輛平衡為

(8)

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

(9)

消除子回路為：

(10)

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

t0k=Tk，?k∈v;

(11)

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

(12)

上層中經過每條邊的時間成本將由下層描述為

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

(13)

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

(14)

其中

(15)

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

2.3一個特例

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

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

(16)

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

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

3實驗與分析

3.1算例描述

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

3.2結果與分析

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

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

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

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

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

圖2　經典路徑選擇模型解出的物流車輛路徑

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

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

4結語

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

[參考文獻]

[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/.

(責任編輯：石紹慶)

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

[基金項目]國家自然科學基金資助項目(71372002).

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

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

[文獻標志碼]A

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