章宇，唐加福*,2

（1東北大學(xué)流程工業(yè)綜合自動化國家重點實驗室，沈陽110004；2東北財經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧大連116000）

基于風(fēng)險分擔(dān)的城市公交出行魯棒優(yōu)化模型

章宇1，唐加福*1,2

（1東北大學(xué)流程工業(yè)綜合自動化國家重點實驗室，沈陽110004；2東北財經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧大連116000）

本文面向城市中需要在給定期限內(nèi)到達終點的出行者，針對最短耗時公交換乘問題，利用基于風(fēng)險分擔(dān)的魯棒優(yōu)化方法進行了建模和求解.公交行車時間和發(fā)車間隔時間是不確定的，本文將其建模為區(qū)間數(shù)，并基于風(fēng)險分擔(dān)的思想給出了這些不確定參數(shù)的集合描述，該集合可以通過一個代表出行者保守程度的參數(shù)進行靈活調(diào)整，在此基礎(chǔ)上提出了城市公交換乘最短耗時魯棒優(yōu)化模型，給出了多項式時間精確算法.通過對一個算例的求解和仿真實驗，展示了該模型求解結(jié)果（相對于確定性模型的求解結(jié)果）具有更小的遲到概率；并通過分析討論，總結(jié)出換乘更少，運行更穩(wěn)定的換乘方案更傾向于成為魯棒最優(yōu)換乘方案.

城市交通；換乘路徑優(yōu)化；魯棒優(yōu)化；公交出行者；風(fēng)險分擔(dān)

1 引言

城市中公交出行者在出行前往往需要制定一套公交換乘方案，使得出行消耗的總時間最短.現(xiàn)實生活中，某些出行者必須在規(guī)定的最后期限前到達出行終點（如去開會、赴約、參加面試、趕火車、上班等）.如果公交車的行車時間和乘客的換乘等車時間是確定的，公交換乘問題很容易求解，此前已有大量的相關(guān)研究.公交換乘問題往往被視為變種的最短路問題，用改進的最短路算法即可求解.例如，樊曉春等人借助公交網(wǎng)絡(luò)通達矩陣利用改進的Dijkstra算法進行求解[1]；Zografos和Androutsopoulos用一種動態(tài)規(guī)劃方法進行求解[2].但這些研究都假設(shè)公交行車時間及換乘等待時間是確定的，運用求解得到的換乘方案出行很可能導(dǎo)致出行者的遲到.

事實上，公交行車時間及乘客等車時間是不確定的，同時它們相應(yīng)的分布函數(shù)也不可能準確地獲取，這就給公交出行換乘方案的制定帶來了困難和挑戰(zhàn).現(xiàn)實中，具有到達終點最后期限限制的出行者往往寧愿犧牲一些時間“提前”出發(fā)，使得對于絕大多數(shù)的不確定情況都不遲到，也不愿冒險“準點”到達；此外，“提前”量不是無限的，出行者希望定量地知道什么時刻出發(fā).

近年來，魯棒優(yōu)化方法論逐漸興起并得到了廣泛運用，它本質(zhì)上是一種“保守”的方法，所以正好適用于該問題.一些學(xué)者利用最小化最大遺憾準則對魯棒最短路問題進行建模和求解，導(dǎo)致該問題變?yōu)镹P難題，故不適用于現(xiàn)實場景[3-6].而針對魯棒最短路問題，Bertsimas和Sim基于風(fēng)險分擔(dān)的思想，考慮弧段車輛行駛時間為區(qū)間數(shù)，但只有給定個數(shù)的弧段消耗的時間能夠達到最壞值（卻沒給定哪些弧段），在這樣的前提下要求尋求最壞情況下的最短路徑；該模型可以在多項式時間內(nèi)求解，因此更具有實用性[7].

本文借鑒Bertsimas和Sim的方法，面向公交出行者，針對城市公交換乘問題，考慮公交行車時間及發(fā)車間隔時間的不確定性，以出行耗時最少為目標(biāo)，提出基于風(fēng)險分擔(dān)的魯棒優(yōu)化模型.給出公交行車時間和出行者換乘等待時間的不確定集合描述，以及多項式時間求解算法.并通過一個算例仿真地驗證了該模型的有效性，揭示了對于具有最后期限限制的公交出行者，一套魯棒換乘方案并不是“在確定性模型所求得的最優(yōu)方案基礎(chǔ)上提前一些時間出發(fā)”那么簡單.同時總結(jié)出對于偏好保守的出行者，即使出行距離相對更大，也要選擇換乘更少，運行更穩(wěn)定的換乘方案.本文不僅對魯棒優(yōu)化方法論在公交換乘優(yōu)化領(lǐng)域的應(yīng)用具有理論推動意義，而且對乘客公交出行安排具有管理學(xué)上的實際指導(dǎo)意義；此外，該模型可以作為子模型嵌套到公交網(wǎng)絡(luò)流分配模型和公交線路設(shè)計模型中，具有廣泛的應(yīng)用潛力.

2 公交網(wǎng)絡(luò)描述

圖1 城市公交網(wǎng)絡(luò)模型示意圖Fig.1 An urban bus network sample

圖1(a)和(b)分別展示了城市公交網(wǎng)絡(luò)物理結(jié)構(gòu)和對應(yīng)的網(wǎng)絡(luò)模型，下面進行詳述.

Aw：換乘弧段集，包括步行和等車兩個過程，兩節(jié)點間步行距離須小于某一給定閾值.

出行者每一次出行會給定起點no?N和終點nd?N，不失一般性地認為它們不正好在之前定義的節(jié)點上.則每當(dāng)給定起始點時，需在原網(wǎng)絡(luò)G中添加換乘弧段連接起點與終點.并令hl(no)=hl(nd)=h?l(no)=h?l(nd)=0.

3 公交換乘魯棒優(yōu)化模型

出行者欲制定一套換乘方案使得出行時間最短且盡量不遲到.欲確定最晚的出發(fā)時刻，可等價地最小化換乘方案總出行時間.本文假設(shè)：①公交車容量是無限的；②乘客出行期間各線路皆未停運；③站點間公交行車時間的不確定區(qū)間數(shù)能準確獲取.那么，不確定環(huán)境下城市公交換乘優(yōu)化模型可表示為目標(biāo)式(3)以及約束式(4)～式(6).如目標(biāo)式(3)所示，出行者以出行總耗時最短為目標(biāo)；決策變量為當(dāng)弧在最優(yōu)換乘方案上時否則則決策變量為0-1變量，如約束式(6)所示；約束式(4)保證所選擇的弧形成一條起始點間連通的路；兩條換乘弧段不能直接相連，如約束式(5)所示.

如果參數(shù)c～isj取其標(biāo)稱值cisj，則該問題不考慮不確定性，稱之為標(biāo)稱問題.它是最短路問題的一個變種，簡單修改Dijkstra算法即可在多項式時間內(nèi)高效求解.但其計算結(jié)果很可能導(dǎo)致遲到，所以必須考慮不確定性.

如每個參數(shù)c～isj同時取到對應(yīng)的最大值，將導(dǎo)致出行者提前太長時間出發(fā)，這樣的求解結(jié)果不能令人滿意.本文則借鑒Bertsimas和Sim的想法[7]，提出城市公交換乘魯棒優(yōu)化模型，設(shè)計目標(biāo)函數(shù)式(7)，滿足約束式(4)～式(6)及式(8)～式(9).其中，zisj為輔助變量，Γ={0,1,...,|A|}為控制保守 程度的參數(shù)，由出行者決定.如果 Γ=0，出行者很樂觀，但理論上有50%的概率會遲到，問題退化為前述標(biāo)稱問題；如果 Γ=|A|，出行者很悲觀，他不會遲到，但很可能提前太長時間到達目的地；Γ參數(shù)的設(shè)定正是根據(jù)出行者的保守程度，在可能遲到和提前太長時間到達目的地之間取一個折中.

4 多項式時間精確算法

由于弧段消耗的時間為不確定值，Dijkstra算法不能求解.本節(jié)給出上述模型的多項式時間精確解法.

定理約束式(8)、式(9)連同目標(biāo)式(7)等價于目標(biāo)式(10).證明：觀察目標(biāo)函數(shù)式(7)，它對于變量線性，且式(8)中Γ為整數(shù)，則結(jié)合式(9)可知只在端點0或1處取得最優(yōu)值；同時，通過反證法可證目標(biāo)函數(shù)中的使得約束式(8)等價于因為如果總可增大使增大.證畢.

目標(biāo)式(10)可直觀理解為網(wǎng)絡(luò)G中雖弧的耗時值是不確定的，但僅有Γ條弧會實現(xiàn)其最長耗時值，其它保持為標(biāo)稱值.本模型事實上是從風(fēng)險分擔(dān)的角度出發(fā)的，也就是說，真正耗時值比相應(yīng)標(biāo)稱值大的弧段可能很多（如＞Γ），但不都會實現(xiàn)其最大偏離值，本模型則以Γ條弧耗時最大偏離值之和來代表，從而分擔(dān)了風(fēng)險.

證明：根據(jù)Bertsimas和Sim的論文[7]，可得到該性質(zhì).

根據(jù)該性質(zhì)，欲求解上述魯棒優(yōu)化問題，可等價地求解|A|+1個確定性問題，再取最小值.每一個確定性問題是一個變種的最短路問題，可利用算法復(fù)雜度為O(n2)的Dijkstra算法求解.這樣，該不確定性問題就可等價地由最初窮舉式的求解個確定性問題變?yōu)榍蠼庾疃鄚A|+1個確定性問題.相應(yīng)地，求解算法也從非多項式時間縮減為多項式時間O((||A+1)n2).

本文默認讀者熟悉Dijkstra算法，基于以上性質(zhì)，下面給出求解該問題的算法步驟：

步驟1對于k=1,2,...,||A+1，分別利用Dijkstra算法求解目標(biāo)式(12)滿足約束式(4)～式(6)的優(yōu)化問題，令Gk問題對應(yīng)的最優(yōu)解為向量xk.

步驟2求

步驟3最優(yōu)目標(biāo)函數(shù)值最優(yōu)解

5 算例求解與分析

圖2為一個不確定環(huán)境下公交網(wǎng)絡(luò)示例，其物理結(jié)構(gòu)如圖1(a)所示.出行者設(shè)置起點為n20，終點為n21.他欲到終點見客戶，故希望獲得一套魯棒的公交換乘方案.

圖2 不確定環(huán)境下公交網(wǎng)絡(luò)示例Fig.2 A bus network example under uncertainty

每條公交弧段對應(yīng)括號中的兩個數(shù)中，第一個為通過該弧的期望耗時，第二個為最大偏差耗時，單位為s.線路1～4的期望發(fā)車間隔分別為480，360，360，300 s；最大偏差值分別為100，90，90，60 s.節(jié)點n1,n9,n15,n20兩兩間的距離均為0，因為它們在地理上是同一地點，只是被建模為多個節(jié)點；節(jié)點n8,n14,n19,n21同理兩兩間距離為0；節(jié)點對n5與n16，n3與n6，n4與n13間步行距離均為30 m，步行速度設(shè)定為1.5 m/s，則耗時均為20 s.

利用第4節(jié)所述方法對上述算例進行求解.隨機生成1 000個?！蕒1,2,...,|A|}，其平均求解時間為標(biāo)稱模型求解時間的8.64倍，與該算例對應(yīng)的理論值9倍（可由上述性質(zhì)計算）基本吻合.

對于Γ=0,1,...,|A|分別對該算例進行求解.計算可得，當(dāng)Γ=0時最優(yōu)換乘方案為出行耗時1640 s；Γ=1時，最優(yōu)換乘方案為，耗時1950 s；?！?時，最優(yōu)換乘方案為當(dāng)2 040，2 080，2 115 s.

此外，關(guān)心在給定不同的提前于最后期限出發(fā)時間的情況下，上述三套換乘方案究竟有多大的概率導(dǎo)致出行者遲到.假設(shè)所有的公交弧耗時和發(fā)車間隔時間均勻分布在給定區(qū)間，隨機取10 000個場景，對于每個場景分別計算三種換乘方案的時間消耗，則統(tǒng)計可得遲到概率如表1所示.

表1 不同換乘方案及不同的提前于最后期限出發(fā)的時間所對應(yīng)的遲到概率（單位：%）Table 1 late probabilities for different itineraries combined with different advanced departure time(in seconds)

對于以上結(jié)果，討論如下：

(1)雖然出行者提前最后期限于1 640 s出發(fā)時，p1遲到概率小于p3，但仍然有約50%的遲到概率，出行者顯然會提前更多的時間出發(fā)，而當(dāng)出行者至少提前2 040 s出發(fā)時，選擇p3基本上可保證不遲到.所以，一套魯棒換乘方案并不是“在標(biāo)稱模型所求得的最優(yōu)方案基礎(chǔ)上提前一些時間出發(fā)即可”那么簡單.另外，本文定量地計算出需要多“早”出發(fā).

(2)Γ=0即不考慮不確定性時，最優(yōu)方案為p1，這主要得益于該方案空間距離最短.但隨著Γ逐漸增大，p2和p3依次成為最優(yōu)換乘方案，這是因為p1比p2和p3多一次換乘，而一次換乘等待時間的不確定性遠大于一條公交弧段耗時的不確定性.所以保守的出行者應(yīng)該盡量少換乘，即使行駛距離更長.

(3)Γ=1時最優(yōu)換乘方案為p2，這主要得益于其空間距離比p3短.而同樣的換乘次數(shù)，當(dāng)?！?時，p3卻優(yōu)于p2，這是因為p3對應(yīng)的公交線路行車時間的最大偏離值較小.所以保守的出行者應(yīng)該盡量選擇穩(wěn)定性高的換乘方案，即使行駛距離更長.

6 研究結(jié)論

對于城市公交出行者需要在給定期限內(nèi)到達終點的情況，如果按照傳統(tǒng)的標(biāo)稱問題求解，其結(jié)果很可能導(dǎo)致出行者遲到；尋找一套魯棒換乘方案也并不是“在標(biāo)稱模型所求得的最優(yōu)方案基礎(chǔ)上提前一些時間出發(fā)即可”那么簡單.本文將不確定的公交行車時間和發(fā)車間隔時間給定為區(qū)間數(shù)，但是只有限定個數(shù)的參數(shù)能同時到達最壞值，隨后給出了城市公交換乘魯棒優(yōu)化模型與多項式時間精確算法.通過對一個算例的求解和仿真分析展示了該模型的正確性和實用性，給出了求解結(jié)果的置信度，總結(jié)出換乘少和運行穩(wěn)定的換乘方案更具有抗干擾的能力.

[1]樊曉春,張雪英,劉學(xué)軍,等.一種公交換乘優(yōu)化算法設(shè)計[J].地球信息科學(xué)學(xué)報,2009,11(2):157-160. [FAN X C,ZGANG X Y,LIU X J,et al.Design of an algo?rithm of public traffic transfer based on the least transfer [J].Geo-Information Science，2009,11(2):157-160.]

[2]Zografos K G,Androutsopoulos K N.Algorithms for itin?erary planning in multimodal transportation networks[J]. Intelligent Transportation Systems,IEEE Transactions on,2008,9(1):175-184.

[3]Yu G,Yang J.On the robust shortest path problem[J]. Computers&Operations Research,1998,25(6):457-468.

[4]Montemanni R,Gambardella L M.An exact algorithm for the robust shortest path problem with interval data [J].Computers&Operations Research,2004,31(10): 1667-1680.

[5]Catanzaro D,Labbé M,Salazar-Neumann M.Reduction approaches for robust shortest path problems[J].Comput?ers&Operations Rresearch,2011,38(11):1610-1619.

[6]Gabrel V,Murat C,Wu L.New models for the robust shortest path problem:complexity,resolution and gener?alization[M].Annals of Operations Research,2011:1-24.

[7]Bertsimas D,Sim M.Robust discrete optimization and network flows[J].Mathematical Programming,2003,98 (1-3):49-71.

A Risk-Pooling-Based Robust Model for Least-Time Itinerary Planning

ZNANG Yu1，TANG Jia-fu1,2
（1 State Key Lab of SyntheticAutomation of Process Industries,Northeastern University,Shenyang 110004 China;2 College of Management Science and Engineering,Dongbei University of Finance and Economics,Dalian 116025,Liaoning,China）

ract:This paper addresses the least-time itinerary planning problem for the urban public-transport travelers,especially those with deadlines imposed at their destinations.A risk-pooling-based robust model is used to solve the problem.Headway and travel time of each bus are uncertain,which are given in intervals in this paper.Based on the risk pooling concept,the set of combined uncertain travel times and headways are designated.This set could be adjusted flexibly by a parameter,which represents the conservativeness of each traveler.Subsequently,a robust model for the problem is proposed,as well as an exact polynomial time algorithm.Through an example and the associated simulation,the paper demonstrates that the solution of this model(compared with the solution of the deterministic model)is less likely to break the deadline.It is also concluded that an itinerary is more inclined to be a robust optimal solution with less transfer times or by more reliable bus lines.

rds:urban traffic;itinerary planning;robust optimization;bus traveler;risk pooling

1009-6744（2014）04-0107-00

U268.6

A

2013-12-12

2014-04-01錄用日期：2014-04-11

國家創(chuàng)新研究群體科學(xué)基金（71021061）.

章宇（1989-），男，四川內(nèi)江人，博士生. *

tangjiafu@dufe.edu.cn