公交線路配車問題的不確定雙層規(guī)劃模型

薛運強(qiáng)，郭 俊，安 靜，薛邏維，桑 梓

(1.華東交通大學(xué)交通運輸與物流學(xué)院，南昌330013；2.東南大學(xué)交通學(xué)院，南京210096；3.江西省高鐵區(qū)域發(fā)展研究中心，南昌330013)

0 引言

公共交通因其安全、高效、便捷、環(huán)保，成為緩解城市交通問題的有效交通方式，優(yōu)先發(fā)展公共交通已成為普遍共識[1-2].常規(guī)公交線路的開辟和車輛配置問題，不僅關(guān)系企業(yè)的成本和收益，還與公交的服務(wù)水平、乘客的乘車滿意度有重要關(guān)系[2].如何確定合理的配車數(shù)量，在保證公交運營者基本收益的同時使公交服務(wù)的社會效益最優(yōu)是值得探討的問題.

國內(nèi)外眾多學(xué)者對公交線路配車優(yōu)化問題做了深入研究，考慮公交運營者和出行者兩個群體權(quán)益的雙層規(guī)劃模型使用較多.趙淑芝[2]以公交運營者的成本和公交服務(wù)水平加權(quán)和為目標(biāo)，建立多車型公交線路配車優(yōu)化模型.邸振[3]以公交企業(yè)收益作為上層目標(biāo)，乘客出行的時間和費用加權(quán)總成本最小為下層目標(biāo)，政府行為作為約束條件，建立公交線路車輛配置雙層規(guī)劃模型.Liu Tao[4]構(gòu)建雙目標(biāo)雙層優(yōu)化模型，上層模型的兩個目標(biāo)是從公交運營者角度使總運營成本最小，乘客出行總時間成本最??；下層模型是基于發(fā)車時刻考慮車輛容量約束的交通分配問題.Filipe Monnerat等[5]考慮車隊管理問題，建立車輛和駕駛員的分配模型，目標(biāo)是總成本最小.然而，公交在運行中往往會出現(xiàn)許多不確定因素，不同站點的服務(wù)時間窗口和乘客需求量都是無法準(zhǔn)確估計的.在公交線路開辟和車輛配置過程中，往往根據(jù)歷史數(shù)據(jù)或者經(jīng)驗對這些變量進(jìn)行估計，對需要解決的問題進(jìn)行預(yù)測，得出一個相對可靠的結(jié)果，這樣會有一個較大誤差.為了盡量降低誤差，劉寶碇[6]提出了不確定理論，不斷完善使其形成規(guī)范的公理化數(shù)學(xué)體系.Liu[6]在考慮規(guī)劃問題時引入了不確定變量，首次提出了不確定規(guī)劃.以不確定規(guī)劃為代表的不確定理論在交通、物流、金融領(lǐng)域得到廣泛和成功的應(yīng)用[7]，交通方面的應(yīng)用主要包括車輛調(diào)度問題、關(guān)鍵路問題等[7].焦登婭[8]在劉寶碇研究的基礎(chǔ)上構(gòu)建不確定規(guī)劃模型解決含有不確定因素的物流車輛調(diào)度問題，不確定因素考慮了送貨點對貨物需求量的不確定性和行程時間的不確定性.張鳳嬌[9]利用劉寶碇提出的不確定時間測度模型，研究車輛路徑問題，用混合智能算法求出最優(yōu)解.柳伍生[10]利用公交IC卡數(shù)據(jù)分析公交站點的客流不確定性，提出概率推導(dǎo)模型及算法，沒有繼續(xù)應(yīng)用到公交配車、運營調(diào)度等問題.

綜上可知，利用不確定理論研究公交線路配車問題的成果較少，本文考慮公交站臺乘客數(shù)量的不確定性，同時考慮公交運營者的成本收益、公交乘客的時間和費用成本，構(gòu)建公交線路配車問題的不確定雙層規(guī)劃模型，以期為公交線路配車問題提供理論支持.

1 不確定理論

一段時間內(nèi)(如一個發(fā)車間隔)每個公交站點到達(dá)的人數(shù)都是不確定的，它是在一個范圍內(nèi)波動的不確定變量.下面給出不確定理論的相關(guān)概念.

1.1 不確定測度和不確定空間

定義1[6]設(shè)L是非空集合Γ上的一個σ-代數(shù)，則集合函數(shù)Μ：L→[0,1]稱為一個不確定測度，如果Μ：L→[0,1]滿足如下3條公理：

公理1(規(guī)范性)對于全集Γ，Μ{Γ}=1.

公理2(自對偶性)對任意事件Λ，Μ{Λ}+Μ{ΛC}=1，ΛC是Λ的補集.

公理 3(次可加性)對可數(shù)個事件Λ1,Λ2,…,

定義2[6]由上述非空集合Γ，Γ上的σ-代數(shù)L，不確定測度Μ組成的三元組(Γ,L,Μ)稱為不確定空間.

1.2 不確定變量和不確定分布

定義3[6]稱ξ是一個不確定變量，如果ξ是從不確定空間(Γ,L,Μ)到實數(shù)集R的可測函數(shù).也就是說對實數(shù)集中任意的Borel集B，集合{ξ∈B}={γ∈Γ|ξ(γ)∈B} 是一個事件，其中，γ是非空集合Γ中的元素值.

定義4[6]稱不確定變量ξ為線性的，如果它服從下列線性不確定分布Φ(s)，該分布記為L(a,b)，其中，a,b為常數(shù)值，為不確定變量ξ取值范圍的邊界值，且滿足a＜b.

以南昌市210路公交為例進(jìn)行調(diào)查分析，獲得該線路2019年3月25～31日一個星期早高峰(07:00-08:00)的IC卡數(shù)據(jù)和線路全天票款數(shù)據(jù)，如表1和表2所示.各個站點和時間段刷卡乘客數(shù)量和投幣乘客數(shù)量的比例大體一致，根據(jù)早高峰IC卡刷卡量占全天刷卡量的比例，近似得到早高峰投幣的乘客數(shù)量.通過一個星期的調(diào)查數(shù)據(jù)可知，每個站點到達(dá)的人數(shù)是在一個范圍內(nèi)波動的不確定變量.對現(xiàn)狀一個星期的各公交站點到達(dá)人數(shù)進(jìn)行擬合，進(jìn)行卡方檢驗可知(見3.1節(jié)卡方檢驗表3)，站點乘客到達(dá)的不確定變量符合線性不確定分布.

表 1 210路早高峰(07：00-08：00)刷卡量和發(fā)車數(shù)(2019年3月25～31日)Table 1 Cards volume and number of vehicles in 07：00-08：00 AM from Mar.25～31,2019 for bus line 210

表 2 210路早高峰(07：00-08：00)各站點上下車人數(shù)(2019年3月29日)Table 2 Number of passengers of line 210 getting on and off at each station during 07：00-08：00 AM on Mar.29,2019

2 公交線路配車的不確定雙層規(guī)劃模型

2.1 模型建立

從公交企業(yè)利益和乘客利益兩個角度考慮，在相關(guān)約束條件下分別建立上層公交收益和下層乘客收益兩層目標(biāo)函數(shù).

模型構(gòu)建基于如下模型假設(shè)：①公交線路確定后再進(jìn)行線路公交車配置；②公交車輛車速由歷史運行數(shù)據(jù)取均值得到；③上車規(guī)則是先到先上車；④若乘客等到第1趟公交車未能上車，算作留客，影響公交服務(wù)滿意度.乘客的到達(dá)服從線性不確定分布(案例分析中給出驗證該分布的卡方檢驗過程).

(1)目標(biāo)函數(shù).

考慮公交企業(yè)收益的上層目標(biāo)函數(shù)為

式中：Uij為公交車j到達(dá)公交站i時的上車人數(shù)，，其中，Wij為公交車j到達(dá)站點i時站臺候車乘客數(shù)，qij為可乘車人數(shù)，qij=C-Vij+Dij，C為車內(nèi)最大容量，Vij為公交車j從始發(fā)站到站i之間的乘客數(shù)，Dij為公交車j到站i時下車的乘客數(shù)；C1為平均每輛公交車運營成本；C2為一輛公交車分?jǐn)偟墓潭ǔ杀?；x為時間段[T1,T2]內(nèi)配置的車輛數(shù)；n為[T1,T2]內(nèi)運行的車輛數(shù)；m為站點數(shù)；ρ1為公交票價.

乘客出行時間和費用成本加權(quán)和最小的下層目標(biāo)函數(shù)為

式中：α，β為加權(quán)系數(shù)；ρ2為乘客改乘其他交通方式的費用；y為發(fā)車時間間隔.

(2)約束條件.

從政府角度考慮，乘客的乘車率應(yīng)不小于某一值δ；高峰時段，應(yīng)有一個最大的發(fā)車間隔限制；公交線路的長度、公交車行駛速度、配置車輛數(shù)、時間間隔應(yīng)該滿足

式中：t1，t2分別為發(fā)車間隔的最小值與最大值；L為公交線路長度；v為公交車在研究時段的歷史車速均值.

2.2 求解思路

首先，對原始數(shù)據(jù)進(jìn)行處理，確定各站點不確定分布參數(shù)a,b的值；然后，通過具體的a,b值擬合現(xiàn)狀的OD出行量，利用MATLAB來對模型進(jìn)行求解；最后，得出各站點乘客需求量不確定情況下的最優(yōu)發(fā)車間隔.

各站點的乘客到達(dá)服從參數(shù)為a,b的線性不確定分布(案例分析中給出驗證該分布的卡方檢驗過程)，利用調(diào)查得到的各站點乘客到達(dá)量的均值和方差，得出各站點到達(dá)人數(shù)符合相應(yīng)線性不確定分布的到達(dá)人數(shù)，再在現(xiàn)狀調(diào)查的基礎(chǔ)上反推出各站點的OD出行量.

對現(xiàn)行不確定分布函數(shù)關(guān)于x求導(dǎo)，得到其概率密度函數(shù)為

式(8)和式(9)為均值、方差的計算公式.利用反推得出的OD出行量，對模型中的相關(guān)參數(shù)進(jìn)行取值，其依據(jù)主要是查閱相關(guān)資料和咨詢公交公司的運營管理人員，最后得出的一個相對比較合理的參考值.

由式(4)～式(6)決定的下層目標(biāo)函數(shù)的解是有限的.通過分析可知，模型的下層目標(biāo)函數(shù)是一個關(guān)于發(fā)車間隔y的單調(diào)遞增函數(shù)，且配車數(shù)為整數(shù)，可以快速縮小搜尋范圍，如最優(yōu)解只能出現(xiàn)在圖1中AB,EI,FJ,GL,HK,DC上.

結(jié)合上文所述，最優(yōu)配車數(shù)應(yīng)該在A，E，F(xiàn)，G，H，D點上；帶入式(4)進(jìn)行檢驗，刪除不滿足條件的點，將滿足條件的點帶入上層目標(biāo)函數(shù)，使上層目標(biāo)函數(shù)取值最大的點就是最優(yōu)的配車數(shù).

圖1 配車數(shù)—發(fā)車間隔示意圖Fig.1 Relationship of number of vehicles and departure intervals

3 案例分析

3.1 案例介紹

本文以南昌市210路公交線為例進(jìn)行公交線路配車優(yōu)化.南昌210路公交線，全長20 km，設(shè)站26處，線路雙向配車51輛，駕駛員63人.早高峰(07:00-08:00)刷卡量約為2 000，發(fā)車班次為16班.

圖2 210路公交走向和站點分布圖Fig.2 Stops and route distribution of bus line 210 in Nanchang City

對現(xiàn)狀一個星期的各公交站點到達(dá)人數(shù)進(jìn)行擬合卡方檢驗可知，站點乘客到達(dá)的不確定變量符合線性不確定分布.表3是以線路一個星期刷卡量為不確定變量，驗證乘客數(shù)量作為不確定變量服從線性不確定分布(參數(shù)擬合值取a=100,b=2 000，即滿足卡方檢驗).樣本分組數(shù)為g=7，線性不確定分布中有兩個參數(shù)a,b，參數(shù)個數(shù)l=2，故卡方統(tǒng)計量的自由度χDF=g-1-l=7-1-2=4 (DF 是 Degrees of Freedom的簡寫，表示統(tǒng)計量的自由度).查卡方分布分位數(shù)表，=7.779＞3.31，因此有99%的概率不能拒絕乘客數(shù)量服從線性不確定分布.每個站點公交乘客數(shù)量服從線性不確定分布的卡方檢驗類似.

表 3 早高峰乘客數(shù)量服從線性不確定分布的卡方檢驗統(tǒng)計表Table 3 Chi-square test statistics for passenger numbers in morning peak hour satisfying linear uncertainty distributions

3.2 模型求解及分析

模型中相關(guān)參數(shù)取值如下：210路公交線路長度為20 km，車輛全程的平均速度為15 km/h，時間為晚高峰(17:00-18:00)；乘車率不低于80%，各站臺乘客的到達(dá)率相互獨立，服從參數(shù)為a,b的不確定分布；時間成本與經(jīng)濟(jì)成本的加權(quán)系數(shù)都取1，公交票價分為兩種，刷卡和不刷卡分別取2元和1.4元，公交車的運營成本取80元/次，配車成本取100元/輛.

根據(jù)建立的雙層優(yōu)化模型，利用MATLAB編寫程序計算得到不同配車數(shù)量下的運營指標(biāo)，如表4所示.

表 4 不同配車數(shù)量下運營指標(biāo)計算結(jié)果Table 4 Calculation results of operation indicators under different number of vehicles

表4中配車數(shù)為20,18,16輛的乘車率均小于80%，不滿足最小乘車率要求，故不是最優(yōu)配車數(shù)；根據(jù)上文解題思路可知，在滿足乘車率的要求下，使企業(yè)利潤最大的配車數(shù)就是該線路下行方向的最優(yōu)配車數(shù)，由表4可知，當(dāng)配車數(shù)為23輛時，企業(yè)利潤最大，故最優(yōu)配車數(shù)為23輛.

210路公交上行方向現(xiàn)狀配置的車輛數(shù)是26輛，本文模型計算的最優(yōu)配車數(shù)是23輛，減少11.5%.從數(shù)據(jù)上看，優(yōu)化結(jié)果比較接近現(xiàn)狀，在一定程度上反映出該模型具有一定的實用性.從表5優(yōu)化前后數(shù)據(jù)看：優(yōu)化后高峰時乘客總加權(quán)成本相比于優(yōu)化前小幅增加0.5%，基本持平；高峰時該線路的利潤比優(yōu)化前增加了112元，增加29.6%；綜上，早高峰線路配車優(yōu)化效果明顯.

模型上層決策變量取值為整數(shù)，比一般雙層規(guī)劃模型求解更加方便；上層規(guī)劃模型能夠比較直觀地反映公交公司、乘客、政府三者間相互影響、相互制約關(guān)系；將優(yōu)化結(jié)果與實際情況比較，模型結(jié)果比較接近實際情況.

表 5 線路配車優(yōu)化前后指標(biāo)對比Table 5 Comparison of indicators before and after vehicle allocation optimization for bus line

4 結(jié)論

本文考慮公交站點乘客數(shù)量的不確定性，以公交企業(yè)收益和乘客出行總成本為目標(biāo)，構(gòu)建不確定雙層規(guī)劃模型，對公交線路進(jìn)行車輛配置優(yōu)化.以南昌市210路公交為例，對早高峰配車數(shù)進(jìn)行優(yōu)化.分析結(jié)果顯示，本文不確定雙層規(guī)模型的優(yōu)化效果明顯；模型變量取整數(shù)有利于模型求解，提高了模型的實用性.本文為公交運營者優(yōu)化線路配車提供了理論支持.

乘客選擇公交車輛時，模型假設(shè)公交車只要沒有達(dá)到荷載人數(shù)，乘客就會上車，沒有考慮車內(nèi)擁擠程度對乘客選擇的影響，在一定程度上影響了模型計算結(jié)果的可靠性.本文只研究了站點乘客數(shù)量這一不確定變量下的配車問題，公交線路配人、行車時刻表，構(gòu)成行車作業(yè)計劃、公交網(wǎng)絡(luò)的優(yōu)化，以及區(qū)域調(diào)度等問題在線路運行時間、公交站點乘客數(shù)量等多重不確定因素下的優(yōu)化問題有待進(jìn)一步討論.