多車型MAST的調度優化及關鍵參數分析

王正武，趙振于，何 煦

(長沙理工大學 交通運輸工程學院，湖南 長沙 410114)

機動式輔助客運(mobility allowance shuttle transit，簡稱為MAST)是一種典型的需求響應型公交(demand responsive transit，簡稱為DRT)，其車輛圍繞控制點確定的基準路線運行，并在可逆距離內偏離基準路線行駛，在乘客需求點上、下客(如圖1所示)。MAST兼具DRT的靈活性和常規公交(固定線路、固定站點)的低成本性[1]，國外有些城市已經采用了這種公交運營模式[2]。

圖1 多車型MAST公交運行模式Fig.1 Operation mode of the multi-class vehicle MAST system

目前，一些學者對MAST進行了研究。云亮[3]等人闡述了MAST 研究的相關進展。陳堅[4-5]等人提出了基于MAST智慧公交的系統構架。劉慧君[6]對多車輛MAST的調度問題并進行了仿真研究。林葉倩[7]等人構建了單車型MAST的混合整數規劃模型。邱豐[8]等人提出了MAST的兩階段調度模型,處理靜態和動態需求問題。Quadrifoglio[9-10]等人分析了雙車型MAST的運行車速邊界值問題，并構建了單車型MAST的插入式調度模型。Zhao[11]等人研究了單車型MAST系統的服務能力問題。Yangsheng[12]等人提出了雙向多車輛MAST調度模型。現有研究主要是以單車型MAST為研究對象，但因單車型MAST的車輛容量單一，比較適應于乘客預約需求量穩定的情形；當需求量變化較大時，容易造成滿載率低或滯站乘客多，因此，應根據乘客需求量選擇合適的車型。在MAST調度優化中，車輛運行成本是以時間成本來計算的，無法分車型計算運行成本。而實際上，不同車型的運行成本是不同的，而且缺少可逆距離等參數對運行成本的影響分析。最大可逆距離對乘客的坐乘時間、乘客到停靠點的步行時間等有較大的影響。可逆距離的取值不同，系統的總成本就會不同。作者擬構建不同車型的運行成本函數，研究多車型MAST的調度優化模型，并確定在一定需求水平下使總成本最小的最大可逆距離。

1 多車型MAST系統的調度優化模型

1.1 模型假設

設服務區域長度為L，寬度為W，控制點(含首末站)共S(S≥2)個，車輛必須經過所有控制點，并在規定時間從控制點發車，控制點S的發車時間為TS，最大可逆距離為dback。乘客分為4類：Ⅰ類乘客上、下車地點均在基準線外的停靠點；Ⅱ類乘客上車點、下車點分別在基準線上和基準線外的停靠點；Ⅲ類乘客上車點、下車點分別在基準線外和基準線上的停靠點；Ⅳ類乘客上、下車點均在基準線上的站點。發車班次和發車時間已知，但發出車型未定。站點乘客已事先獲得公交到達時間，無需在站點上等車。

1.2 出行費用函數的構建

系統中既有公交公司的運營成本，也有乘客的出行成本，二者之和即系統總成本F。設系統共有k種類型的車，則有：

(1)

式中：μ1,μ2,μ3和μ4均為權值；NⅠ,NⅡ,NⅢ和NⅣ分別為第Ⅰ～Ⅳ類乘客的數量(NⅠ∪NⅡ∪NⅢ∪NⅣ=N)；MⅠ,MⅡ,MⅢ和MⅣ分別為第Ⅰ～Ⅳ類站點的數量(MⅠ∪MⅡ∪MⅢ∪MⅣ=M)；Air為r班次車(發出了k種類型的車) 到i站的時間；Sir，Xir分別為i停靠點上和下r班次車的人數(i停靠點對應的乘客為m類)；yi為i站點縱坐標；Yi為到i站點乘客的縱坐標；ξi為乘客到i站的時刻；ζir為乘客在i站上r班次車的時刻；dback為車輛最大逆行距離，m；τk為k種類型的車的每公里耗費，元/km；cm為m類乘客的票價，元/人；L為基準線路長度，m；α1為距離與時間的轉換系數，s/m；α2為費用與時間的轉換系數，s/元。

式(1)中，右邊第一項為乘客乘車時間，為車輛路段行駛時間與車上乘客數之積。第二項為乘客候車時間，為乘客平均等待時間與上車乘客數之積。第三項為乘客步行時間，為平均步行距離與乘客數之積，若Yi>dback，則yi=dback；否則，yi=Yi。第四項為公交公司的凈費用，也即運營成本與票價收入之差。

1.3 模型的構建

設車輛單程最大運行時間為Tmax，有r班次，從首站的發車時刻為Tr。通過計算，確定r-1(r>1)班次車發出后服務區域內剩余乘客數與r班次車發出后在Tmax內預約乘客量的和。根據該和值，初步確定r班次的發出車型(若車型最大容量小于該和值的1/n，則同時派出n輛最大容量車型的車，對n輛車按發車前、后重新排班；否則，派出車型的容量大于且最接近該和值)。然后，根據初選的r班次派出車型，優化運行路徑。最后，根據優化結果，計算r班次上的最大乘客數，選定容量大于且最接近最大乘客數的車型作為r班次的派出車型。車型初選后，車輛運行路線的優化模型為：

minF

(2)

(3)

ei≤ζir≤li。

(4)

ζir≥ξi。

(5)

Tir≥ζir。

(6)

Tir>tir。

(7)

QCir≤Ck。

(8)

(9)

QCir=QCi-1,r+Sir-Xir。

(10)

|yi|≤dback。

(11)

式中：Tir和tir分別為r班次車離開和到達i站的時刻；tird為r班次車到達i站(若i為控制站)的規定時刻；QWir為r班次車到i站時站上的等待乘客數；QDir為班次r-1～班次r間隔內到i站的乘客數；QCir為r班次車到i站時的車上人數；li和ei分別為i站乘客上車時間窗的上、下界；Ck為k型車的額定載客數量，人/輛。

式(3)表示車輛到達控制站的時刻不晚于事先規定的時刻；式(4)表示乘客上車時刻滿足時間窗要求；式(5)表示乘客到i站時刻應早于上車時刻；式(6)表示乘客上車時刻要早于車輛離開時刻；式(7)表示車輛離開時刻要晚于到達時刻；式(8)表示車上乘客數不能高于車輛容量；式(9)表示r班次車在i停靠點的上車人數；式(10)表示車上乘客數；式(11)表示車輛逆行距離約束。

2 求解算法設計

在調度模型中，車輛是否途經某站點是整型變量，車輛的到達時刻、出發時刻及可逆距離等是非整型變量，因此，該規劃問題是混合整數規劃(NP-Hard)問題。本研究基于遺傳算法設計求解算法[13]，算法流程如圖2所示。

在圖2中，采用0和1編碼途經站點，編碼長度是站點總數。如：染色體為0 1 1 0 1 0 0 1 … 1，從左到右每個數表示一個站點，第一個“0”表示不經過第一個站點，第一個“1”表示經過第二個站點，以此類推)。適應度函數為系統總成本F的倒數。按文獻[13]的方法進行選擇、交叉及變異運算。采用最近插入法，獲得初始解[13]。先由第1和第2個固定點生成一個初始路徑，然后，根據車輛時間窗限制、松弛時間限制及容量限制等約束條件，不斷判斷控制站外的停靠點i是否具有插入路徑中的可能，從而尋找到若干初始可行解。

圖2 遺傳算法流程Fig.2 Genetic algorithm flow chart

3 算例分析

通過不同車型組合MAST與常規公交進行對比，表明多車型MAST的有效性和經濟性。

3.1 乘客需求及相關參數

設發車間隔為10 min，研究時段為8∶00-9∶00，L=16 km、W=1.6 km，S=3，行駛速度v=40 km/h，票價分別為m(NI)=3元，m(NⅡ)=m(NⅢ)=2元，m(NⅣ)=1元，乘客步行速度為4.8 km/h，u1=0.2，u2=0.1，u3=0.4，u4=0.2，Tmax=40 min。對7座、12座及22座的車型，τk分別為0.6,1.2和2.0 元/km。α1=1 min/km，α2=2 min/元。低需求水平下乘客量為ρ=10人/h，中等需求水平下的乘客量為ρ=15人/h，高雪球水平下的乘客量為ρ=25人/h，最大迭代數為200，交叉和變異概率分別為0.4和0.1。車輛最大可逆距離會導致乘客類型的變化，不同可逆距離下的乘客類型比例見表1。不同需求水平下的乘客分布見表2。

表1 不同可逆距離下的乘客類型比例Table 1 Proportion of passenger categories at different reversible distances

表2 不同需求水平下的乘客分布Table 2 Passenger distribution under different demand levels

3.2 實驗設計

1) 實驗一：不同需求水平、不同可逆距離及不同發出車型的比較實驗

在低、中、高3種需求水平下，分3種情形(Q1為7座車；Q2為12座車；Q3為22座車)分析最大可逆距離分別為0.12，0.22，0.32，0.42和0.52 km時經過路徑優化后系統的總成本，見表3。

從表3中可以看出：①最大可逆距離為0.32km時，各種需求水平下，各發出車型的系統成本均最小。其原因是：當可逆距離小時，乘客步行時間顯著增加；當可逆距離較大時，乘客乘車時間和公交公司運行費用顯著增加。②發出不同車型適應的需求水平不同。當需求量水平一定時，存在相應最適應的發車車型使系統總成本最小。如：當可逆距離0.12 km、低需求水平時，最佳車型為12座車。

表3 不同可逆距離下系統的總成本Table 3 System costs of different reversible distances

2) 實驗二：不同車型組合下系統的總費用

常規公交是定點、定線的運營模式，乘客被允許在固定站點上、下車。常規公交站點間距為0.8 km，即在基準線路上可以布設21個公交站點。MAST中，最大可逆距離為0.32 km，仍考慮3種需求水平，分6種情形(Q1為7座車，Q2為12座車，Q3為22座車，Q4為7座和12座的組合型，Q5為7座、12座及22座的組合，Q6為常規公交)進行仿真，其結果見表4。

表4 MAST系統與常規公交仿真結果對比Table 4 The MAST system and conventional bus simulation results

從表4中可以看出：①需求水平較低時(ρ=10人/h)，與常規公交相比，多車型MAST系統能有效降低系統成本。其原因是：在低需求水平下，使用多車型MAST系統，雖然公交公司運營費用等增加了，但乘客的步行時間減少得很多。②需求水平高時(ρ=25人/h)，使用常規公交能降低系統總成本，因為在高需求水平下使用常規公交時，乘客步行時間等增加了，但車輛運營費用減少得很多。③在低需求量(ρ=10人/h)水平和中等需求量(ρ=15人/h)水平下，多車型MAST和單車型MAST系統均能有效降低系統總費用。其原因是單車型MAST系統和多車型MAST系統均能有效降低運營成本和乘客等待時間，提高了公交車輛的利用率。

4 結論

在分析公交公司運營成本和乘客出行費用的基礎上，綜合考慮乘客在車內時間、等待時間、步行時間及車輛運行時間，構建了多車型MAST的調度優化模型。由算例分析證實了該模型的經濟性、有效性和適用性。為完善該模型，以后還需要研究預約型和實時申請型的混合需求MAST的調度優化問題。

參考文獻(References)：

[1] Bruun E C,Marx E.Omnilink:Case study of successful flex-route-capable intelligent transportation system implementation[J].Transporation Research Record,2006,1971:91-98.

[2] Koffman D.Operational experiences with flexible transit services:A synthesis of transit practice,TCRP Report 53[R].Washington,D C:Transportation Research Board of the National Academies,2004.

[3] 云亮,蔣陽升,宋雪梅.機動式輔助客運系統(MAST)及其研究進展綜述[J].交通運輸工程與信息學報,2009,7(4):79-83,123.(YUN Liang,JIANG Yang-sheng,SONG Xue-mei.Introduction of mobility allowance shuttle transit system(MAST) and the summary of its research progress[J].Journal of Transportation Engineering and Information,2009,7(4):79-83,123.(in Chinese))

[4] 陳堅,李武,吳丹,等.基于MAST的智慧公交系統調度優化模型[J].重慶交通大學學報:自然科學版, 2016,35(5):140-145.(CHEN Jian,LI Wu,WU Dan,et al.Scheduling optimization model of intelligent public transport system based on MAST[J].Journal of Chongqing Jiaotong University:Natural Science,2016,35(5):140-145.(in Chinese))

[5] 陳茂林,龐明寶,張寧.基于MAST的城市郊區智慧公交調度發車計劃研究[J].河北工業大學學報,2016,45(4):80-85.(CHEN Mao-lin,PANG Ming-bao,ZHANG Ning.Study on the departure plan of intelligent public transport scheduling for urban suburbs based on MAST[J].Journal of Hebei University of Technology,2016,45(4):80-85.(in Chinese))

[6] 劉慧君.多車輛機動式輔助客運系統配置仿真研究[D].成都:西南交通大學,2012.(LIU Hui-jun.Simulation study on the configuration of the multi-vehicle mobility allowance shuttle transit service system[D].Chengdou:Southwest Jiaotong University,2012.(in Chinese))

[7] 林葉倩，李文權，邱豐，等．可變線路式公交車輛調度優化模型[J].交通信息與安全，2012，30(5):14-18.(LIN Ye-qian,LI Wen-quan,QIU Feng,et al.Optimization model of variable line bus scheduling[J].Journal of Transport Information and Safety,2012,30(5):14-18,33.(in Chinese))

[8] 邱豐,李文權,沈金星.可變線路式公交的兩階段車輛調度模型[J].東南大學學報:自然科學版,2014,44(5):1078-1084.(QIU Feng,LI Wen-quan,SHEN Jin-xing.Two-stage model for flex-route transit scheduling[J].Journal of Southeast University:Natural Science Edition,2014,44(5):1078-1084.(in Chinese))

[9] Quadrifoglio L,Hall R W,Dessouky M M.Performance and design of mobility allowance shuttle transit services:Bounds on the maximum longitudinal velocity[J].Transportation Science,2006,40(3):351-363.

[10] Quadrifoglio L,Dessouky M M,Palmer K.An insertion heuristic for scheduling mobility allowance shuttle transit(MAST) services[J].Journal of Scheduling,2007,10(1):25-40.

[11] Zhao J,Dessouky M.Service capacity design problems for mobility allowance shuttle transit systems[J].Transportation Research Part B,2008,42(2):135-146．

[12] Yangsheng J,Liang Y,Huijun L,et al.Multi-vehicle system design for mobility allowance shuttle transit service[A].International Conference on Mechanic Automation and Control Engineering[C].Wuhan:[s.n.],2010:2858-2862.

[13] 任昊南.用遺傳算法求解TSP問題[D].濟南:山東大學,2008.(REN Hao-nan.Research on genetic algorithm for solving traveling salesman problem[D].Jinan:Shandong University,2008.(in Chinese))