基于多線路換乘路徑優(yōu)化的班車線網(wǎng)運行方案研究

朱姝睿， 秦 浩， 王換軍， 劉瑞虎

(1.北京交通大學， 北京 100044； 2.河南省收費還貸高速公路管理有限公司濮鶴分公司， 河南 濮鶴 457000)

0 引言

隨著社會的飛速發(fā)展，一方面，由汽車保有量增長而引發(fā)的交通擁堵問題成為一些城市發(fā)展的瓶頸；另一方面，公交線路運力不足、線路更新滯后造成的高峰時段供需失衡，由此引發(fā)的“通勤難”問題增加了職工的通勤時間，在一定程度上影響了生活質(zhì)量. 基于這種現(xiàn)狀，越來越多的企業(yè)選擇開通企業(yè)通勤班車這項服務，在有力緩解城市的交通擁堵、助力綠色出行的同時，為企業(yè)職工通勤提供快捷、可控、省時、舒適的服務，改善職工的通勤體驗，進而提高職工的工作效率和工作滿意度. 調(diào)研發(fā)現(xiàn)，當前的企業(yè)班車運行方案主要存在服務率較低和耗時較長的問題. 鑒于可調(diào)配車輛、司機等運輸資源有限，如何基于有限的運輸資源調(diào)整班車線路開行方案，提高班車的服務水平，成為目前亟待解決的問題.

當前已有部分學者對企業(yè)班車線路優(yōu)化問題開展研究. 肖赟等[1]通過建立通勤班車線路優(yōu)化模型,有效提升了通勤線路的覆蓋率. 陶應虎等[2]采用節(jié)約里程法對超市購物免費班車路徑進行優(yōu)化分析,并得到較為滿意的方案. 祁坤等[3]以高校后勤總投入成本最小和優(yōu)化服務質(zhì)量為目標,對郊區(qū)高校教職工通勤班車路徑進行優(yōu)化. 馮存梅等[4]根據(jù)企業(yè)規(guī)模設計了班車站點選址及路徑優(yōu)化方法. 針對實際情況中的覆蓋面積廣、員工住宅工作區(qū)域分散的情況，部分企業(yè)開始提供多線路班車通勤服務. 在此情景下，可通過考慮換乘接駁模式對班車線路進行優(yōu)化，提高車輛的服務率，降低職工的乘車時長. 但是針對這一問題，現(xiàn)有研究較少的考慮多線路下允許換乘的情況. 因此，本文將考慮多線路換乘因素，對班車線路及發(fā)車時刻進行優(yōu)化設計.

1 多線路換乘模式

多線路換乘模式是指一種乘客可在不同線路之間輾轉(zhuǎn)乘坐的出行模式. 換乘主要分為同站換乘和異站換乘2種模式[5]，本文討論的為同站換乘. 圖1展示了2條線路下的同站換乘，乘客B和乘客F在換乘站進行了換乘. 在該模式下，乘客可在換乘站下車，在相同站點搭乘其他線路的班車. 這使得各線路班車可在一定的范圍內(nèi)運行，對于提高車輛服務率、縮短職工乘車時間大有益處. 該模式主要適用于員工出行需求覆蓋大規(guī)模路網(wǎng)的企業(yè)單位，即職工居住地點與上班地點較為分散、且需要采用多條線路進行運送的情況.

圖1 同站換乘模式示意圖

2 多線路換乘路徑優(yōu)化模型的建立

本文定義的網(wǎng)絡條件下的班車線路優(yōu)化問題是考慮換乘時間窗的路徑優(yōu)化問題，即在已知車輛數(shù)量、路網(wǎng)分布以及出行需求等信息的前提下，考慮車輛屬性、節(jié)點屬性、換乘時間窗等約束，通過優(yōu)化班車線路和班次，提高班車服務率、降低職工時間成本. 現(xiàn)有的存在換乘的車輛路徑規(guī)劃問題，考慮了換乘時間窗、流量守恒、節(jié)點屬性和載客容量四類約束，要求所有的需求均被服務. 文獻[6]可行之處在于未對可用車輛數(shù)進行限制，即在最差的情況下，1輛班車服務1個需求，也能保證所有需求均被滿足. 而本文基于有限的車輛數(shù)，且考慮到職工早起舒適度低，對車輛運行時間進行限制，無法保證所有需求均被服務，因此對服務需求進行了松弛處理.

本模型的集合由需求、節(jié)點和車輛構(gòu)成. 其中，N={1,2,…,n,…,|N|}表示需求的集合，1個需求可被視為需要從一個節(jié)點前往另一節(jié)點的，1組職工.C={1,2,…i,…,|C|}表示節(jié)點的集合，節(jié)點按屬性又可細分為：車場(即班車的收發(fā)車點)、需求起點(即職工的上車點)、需求終點(即職工的下車點)和換乘點. 其中，車場只能作為車輛路徑的起點或終點，不能進行職工上下車活動；在換乘點，為方便換乘站的職工行為表達，將換乘點r拆分成駛?cè)霌Q乘點s(r)和駛出換乘點f(r)2個虛擬節(jié)點[7]，發(fā)生換乘的職工需要在2個節(jié)點分別完成下車和上車兩種行為.V={1,2,…,v,…,|V|}表示可用的班車的集合.

為了簡化問題，做出以下合理假設：j車輛在每個節(jié)點只能進行一種行為(上車或下車)；k車輛從發(fā)車點駛出，最終駛?cè)胧哲圏c；l在換乘點，職工先完成下車活動，再完成上車活動；m為避免少數(shù)偏遠需求對總體效率的影響，部分職工需求可不被滿足.

2.1 班車服務率的計算

由于本優(yōu)化方法允許少量偏遠的需求不被滿足，班車服務率在一定程度上反映了班車的服務水平. 班車的服務率可表示為式(1)：

(1)

式中，集合N為職工的乘車需求集合；zn為0-1變量，用于判斷職工的需求n是否被服務，被服務記為1，否則記為0；對zn加和即可求得被服務的需求數(shù)量，與總需求作比可求得班車的服務率.

共有102只眼出現(xiàn)了眼底病變,占總數(shù)的14.7%,其中22只眼視網(wǎng)膜靜脈阻塞22只眼、19眼中心性漿液性視網(wǎng)膜病變、31眼視網(wǎng)膜靜脈周圍炎、19眼年齡相關性黃斑變性,其他11眼。眼底病變組的高度近視男性患者和高齡患者比無眼底病變組高,屈光度高、眼軸長的比例比較多,(P<0.05)。眼底病變高度近視患者定期檢查,及時更換眼鏡、用藥習慣良好等比例比無眼底病變組低,(P<0.05)。

2.2 職工平均出行時長的計算

職工的總出行時長可表示為：

(2)

2.3 職工額外等待時長的計算

經(jīng)典的車輛路徑問題對于時間成本的考慮主要為出行時長[8]. 而職工受工作時間的限制，除考慮出行時長外，還需考慮職工因乘坐班車產(chǎn)生的額外等待時間. 職工的額外等待時長由上班職工提前于開始工作時刻到達的等待時長和下班職工晚于結(jié)束工作時刻離開的等待時長2部分構(gòu)成，分別可表示為式(3)(4)，式(3)為上班職工提前于開始工作時刻到達的等待時長：

(3)

同理，可得到下班職工晚于結(jié)束工作時刻離開的額外等待時長，如式(4).

(4)

3 多線路換乘路徑優(yōu)化方法

由于本文研究的多線路換乘路徑優(yōu)化問題網(wǎng)絡規(guī)模較大，精確解法在有限時間內(nèi)無法得到最優(yōu)解，因此本文設計了一種分階段啟發(fā)式算法(如圖2)求解該問題的近似最優(yōu)解. 該算法主要分為可行線路集合生成、可行時刻表生成、客流加載3個階段，從靜態(tài)到動態(tài)逐階段細化求解，并以最終的客流加載結(jié)果作為評價指標，動態(tài)對時刻表進行再調(diào)整優(yōu)化. 該算法可降低各階段問題的求解難度，快速得到近似優(yōu)化方案，其具體計算過程見圖2.

圖2 分階段啟發(fā)式算法流程圖

步驟1 基于路網(wǎng)拓撲信息和各班組職工的需求OD矩陣，考慮節(jié)點流量約束、班車車隊規(guī)模、車輛行駛時長等約束，結(jié)合動態(tài)規(guī)劃與標號設置算法，對不滿足約束的路段和線路進行動態(tài)剪枝，從而生成可行的線路方案集；

步驟3 基于已經(jīng)確定的帶時刻表的線路方案和職工需求，從待服務需求集中按照一定的概率抽取需求并進行加載. 對每次迭代中抽取順序靠后的需求賦予更大的抽取概率，各需求的抽取概率由歷史抽取概率累積作比得到并在每次迭代中更新；

步驟4 判斷可行路徑集合是否為空，若為空，跳至步驟5，若非空, 在可行路徑集合中進行客流加載，構(gòu)造k短路矩陣，找到各個節(jié)點的有向邊及對應的權(quán)值. 基于鄰接點的路段連接情況及對應的權(quán)重，調(diào)用Dijkstra算法計算各條通路的權(quán)值，并對各路徑權(quán)重進行比較，找到需求對應的最短可行路徑及次短可行路徑；將需求加載至可行路徑后，更新各班車的區(qū)間載客人數(shù)，判斷是否超出車輛容量限制，若未超出，加載客流并執(zhí)行步驟5，若超出容量限制，將超容路段剔除重新執(zhí)行步驟4后將剔除路段重新置入備選集；

步驟5 從待服務需求集中剔除當前需求，并根據(jù)服務情況取zn值. 判斷職工待服務需求集是否為空，若為空集，更新綜合評分. 分別計算該方案下的班車服務率、職工出行時長及職工額外等待時長，根據(jù)決策者的需要對指標加權(quán)求和得到該方案下的綜合評分，若高出當前評分，更新執(zhí)行路徑及時刻表集和綜合評分；若非空，返回步驟3；

步驟6 判斷迭代次數(shù)是否到達預設值，若未達到預設迭代次數(shù)，將需求全部重置入待服務集后，返回步驟3；若達到迭代次數(shù)，結(jié)束迭代，得到優(yōu)化后的班車行駛線路及運行方案.

4 算例設計與結(jié)果分析

4.1 濮鶴管理處班車運行概況

本文以濮鶴管理處現(xiàn)運行的8條職工通勤班車線路為例進行優(yōu)化. 各線路以管理處為中心呈放射狀分別發(fā)往濮陽、安陽、鶴壁、新鄉(xiāng)、鄭州五市，服務于1 004名職工，其任務是在上班前將職工送抵工作地，下班后送回居住地. 由于服務覆蓋區(qū)域面積廣、職工數(shù)量較多且需求分布較為分散，傳統(tǒng)的班車線路方案不能較好地滿足職工出行需求，存在職工整體在途時間較長、班車資源浪費等問題. 為了提高班車服務水平，采用本文提出的多線路換乘路徑優(yōu)化方法對其班車運行方案進行優(yōu)化.

4.2 數(shù)據(jù)預處理

基于站點屬性、站點鄰接關系、站間距離等站點信息，可得到路網(wǎng)拓撲信息和基于站點的OD需求，連同車輛容量、車隊規(guī)模等車輛信息作為模型的輸入. 濮鶴管理處的排班實行“五班兩運轉(zhuǎn)”，即4個班組輪流承擔白班和夜班，1個班組固定上白班. 其中白班值班時間為8:00—19:00；夜班值班時間為19:00—次日8:00. 模型輸入的OD矩陣會隨班組的變化而發(fā)生變化，因此需要按照班組信息對需求數(shù)據(jù)預處理，在每1次調(diào)度中，將相同時間窗內(nèi)有相同通勤需求的職工合并到同一組需求. 預處理后的部分OD需求見表1.

表1 按班組的通勤需求

4.3 優(yōu)化結(jié)果分析

本文以第1組職工下班、第3組和第5組職工上班的交接為例進行結(jié)果展示，其中優(yōu)化過程設定的迭代次數(shù)為10 000次. 在綜合評分中的目標賦予相同權(quán)重時，將考慮多線路換乘的班車優(yōu)化方案下的評價指標與未考慮換乘方案的評價指標比較，對比如圖3. 考慮多線路換乘的班車優(yōu)化方案服務率得到顯著提高，雖然平均出行時間有少量增加，但涵蓋了職工換乘時的周轉(zhuǎn)時間，實際乘車時長也有所縮短. 此外，由于需求較為分散，服務率的提高會對時間成本產(chǎn)生較大的影響. 由此可見，考慮多線路換乘的班車運行優(yōu)化方案在服務率和職工乘車時長方面均具有一定優(yōu)化作用.

圖3 優(yōu)化方案與原方案指標對比

圖4 優(yōu)化后的班車行駛線路圖

基于不同線路方案的客流加載結(jié)果，可根據(jù)決策者的不同偏好對綜合評分中的目標權(quán)值進行調(diào)整. 通過對參數(shù)調(diào)整，分別得到了職工時間成本較小、班車服務率較高和兼顧時間與服務率的3種滿意解. 各方案下的班車行駛線路示意圖如圖4，不同顏色分別代表不同車輛的行駛線路.

根據(jù)班車服務率、職工平均出行時長、職工平均額外等待時長等評價指標，可對優(yōu)化方案進行初步評估與分析. 各方案下對應的服務率、職工平均出行時長和職工平均額外等待時長見圖5.

通過調(diào)整方案評分體系中各權(quán)重的大小發(fā)現(xiàn)，兼顧多目標方案下，職工的消耗時間和服務率同等重要. 以此為參照，在職工時間成本較小的方案下，職工平均出行時長具有顯著的優(yōu)勢，但服務率較其他2個方案低；班車服務率較高方案下，服務率有較為顯著的優(yōu)勢，但職工平均乘車時間和職工平均額外消耗時間均有一定幅度的增加.

這里考慮兼顧時間成本和服務率方案下，職工平均額外消耗時間較前兩種方案有顯著降低的原因是：在該方案下，職工的時間成本和班車服務率同等重要，相較服務率較高的方案，會降低對服務率的要求，通過舍棄少量偏遠的服務需求，減少班車的繞行現(xiàn)象，進而使得職工無需提早較長時間到達工作地點或在結(jié)束工作后能盡快獲得班車服務，減少了職工的平均額外消耗時長；相較職工時間成本較小的方案，兼顧多目標的方案會對班車服務率有一定的提高，會一定程度提高服務網(wǎng)絡的連通性，也會有助于職工平均額外消耗時長的降低.

5 結(jié)論

本文致力于提高班車的服務水平，建立了多線路換乘路徑優(yōu)化模型，設計了多線路換乘路徑優(yōu)化方法，并用濮鶴管理處的實例進行驗證得到以下結(jié)論和展望：

圖5 優(yōu)化后的班車服務水平

1)采用該多線路換乘優(yōu)化方法可有效提高班車的服務率和降低職工的乘車時長，可為企業(yè)班車的線路優(yōu)化問題提供一定的理論依據(jù)；

2)本文設計的多線路換乘路徑優(yōu)化方法，可大大提高求解效率，對于大規(guī)模的實際問題有較好的適應性；

3)基于本文的研究方法，決策者可根據(jù)目標的需求及成本差異，有針對性地提高服務質(zhì)量.