基于集對(duì)分析的隨機(jī)需求接駁公交調(diào)度模型*

孫 博 楊春風(fēng) 魏 明 陳 浩

(1.河北工業(yè)大學(xué)土木與交通學(xué)院 天津 300401;2.南通大學(xué)交通學(xué)院 江蘇 南通 226019)

0 引 言

若要發(fā)揮軌道交通在城市客運(yùn)交通系統(tǒng)的主干道作用，必須將客運(yùn)交通的主體客流吸引到軌道交通上來(lái)，接駁公交是滿足市民出行“最后一公里”需求的一種重要補(bǔ)充公共交通方式。目前，其運(yùn)營(yíng)管理模式多數(shù)與地面常規(guī)公交相似，以客流需求時(shí)空分布為基礎(chǔ)，按固定線路、固定時(shí)間運(yùn)營(yíng)將乘客疏散至軌道站點(diǎn)，存在問(wèn)題包括沒(méi)法提供“門到門”服務(wù)、實(shí)現(xiàn)居民的零等待、按需求發(fā)車等。借助互聯(lián)網(wǎng)技術(shù)，需求響應(yīng)型接駁公交(demand-responsive feeder transit services，DRFTS)是一種以滿足乘客需求為導(dǎo)向的非固定線路靈活公交，可以彌補(bǔ)傳統(tǒng)接駁公交的缺陷，吸引了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注[1-5]。

目前，需求響應(yīng)型接駁公交研究剛剛起步[6-7]，與具有傳統(tǒng)的固定線路、固定運(yùn)營(yíng)時(shí)間的傳統(tǒng)接駁公交差別較大，屬于車輛路徑問(wèn)題研究范疇，均需考慮車輛的額定載客量、乘客的出行時(shí)間窗等約束，安排多輛車遍歷所有客戶，主要差異在于車輛路徑問(wèn)題無(wú)須太關(guān)注乘客對(duì)乘坐軌道站點(diǎn)時(shí)間的要求影響、車輛路徑及其行車計(jì)劃生成過(guò)程，可以借鑒其研究思路和方法，主要成果歸納如下：Pan等[8]提出一種設(shè)計(jì)需求響應(yīng)型交通覆蓋區(qū)域形狀的混合整數(shù)規(guī)劃模型；Li等[9]提出一個(gè)解析模型揭示最佳服務(wù)區(qū)域數(shù)量、客戶的服務(wù)水平和運(yùn)營(yíng)成本之間關(guān)系，在此基礎(chǔ)上,進(jìn)一步提出解析和仿真模型分析居民如何選擇固定線路和需求相應(yīng)交通出行服務(wù)；Chandra等[11]提出一種解析模型識(shí)別和定位需求響應(yīng)型交通網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)；Cremers等[12]提出了考慮提前預(yù)約的需求響應(yīng)式公交的兩階段調(diào)度模型;Braekers[13]研究了多車場(chǎng)需求響應(yīng)式公交調(diào)度模型;Schilde等[14]研究了考慮不同時(shí)間行駛速度變化的需求響應(yīng)式公交調(diào)度模型和算法;Kirchler等[15]利用禁忌搜索算法求解帶時(shí)間窗的多目標(biāo)靜態(tài)DAR問(wèn)題;楊海軍[16]建立了基于快速需求響應(yīng)的單一、多車型全程車調(diào)度方法;Qiu等[17]研究提出了可同時(shí)處理預(yù)約需求和實(shí)時(shí)需求的兩階段車輛調(diào)度模型;Sun等[18-19]研究提出了考慮乘客滿意度、軌道同步換乘的DRT問(wèn)題。由上可知，現(xiàn)有研究主要不足包括：①忽略乘客對(duì)乘坐軌道站點(diǎn)時(shí)間的要求，即乘客除了要求接駁車輛在規(guī)定時(shí)間范圍內(nèi)到達(dá)出發(fā)點(diǎn)，還要求車輛在其要求時(shí)間內(nèi)到達(dá)軌道站點(diǎn)(最大容忍在車時(shí)間)，這影響車輛訪問(wèn)乘客的順序；②忽略部分需求點(diǎn)的居民出行隨機(jī)需求對(duì)其調(diào)度方案的影響，雖然可借鑒不確定的物流配送研究，其研究思路分為等價(jià)確定性模型和計(jì)算機(jī)模擬，其處理過(guò)程極其復(fù)雜，不利于大規(guī)模推廣應(yīng)用。

集對(duì)分析是我國(guó)學(xué)者趙克勤[15]提出的一種處理系統(tǒng)確定性與不確定性相互作用的數(shù)學(xué)理論，其核心是利用聯(lián)系數(shù)描述集合的同一性、對(duì)立性、差異性等。研究表明，正態(tài)分布變量ξ=(φ,δ)的隨機(jī)點(diǎn)x∈ξ落入x=[x-,x+]=[φ-3δ,φ+3δ]的區(qū)間的概率達(dá)99%以上。基于集對(duì)分析，將該不確定變量可以轉(zhuǎn)化為二元聯(lián)系數(shù)q=A+λB=μ-3σ+6σλ，其中：A=x-=μ-3σ為其確定部分，B=x+-x-=6σ為其不確定部分，聯(lián)系數(shù)λ∈[0,1]為其不確定程度。顯然地，集對(duì)分析可以完美刻畫隨機(jī)正態(tài)分布，具有線性簡(jiǎn)單處理等優(yōu)點(diǎn)。綜上所述，筆者研究隨機(jī)正態(tài)分布客流需求的需求響應(yīng)型接駁公交調(diào)度問(wèn)題，考慮乘客的最大容忍在車時(shí)間對(duì)車輛路徑構(gòu)建的影響，針對(duì)帶隨機(jī)參數(shù)的機(jī)會(huì)數(shù)學(xué)規(guī)劃模型求解復(fù)雜缺點(diǎn)，基于集對(duì)分析理論，利用二元聯(lián)系數(shù)刻畫隨機(jī)客流的確定和不確定部分，將其轉(zhuǎn)化為帶聯(lián)系數(shù)的確定性混合整數(shù)線性規(guī)劃模型。以南京商貿(mào)中心地鐵站為例，給出了最佳接駁公交調(diào)度方案，分析了客流的不確定程度對(duì)調(diào)度結(jié)果的影響，并進(jìn)行了參數(shù)的靈敏度分析，從而驗(yàn)證模型的正確性。

1 需求響應(yīng)型接駁公交調(diào)度的隨機(jī)線性規(guī)劃模型

1.1 隨機(jī)需求的需求響應(yīng)型接駁公交調(diào)度模型

該問(wèn)題為安排車輛從調(diào)度中心出發(fā)，將乘客從需求點(diǎn)運(yùn)輸至軌道站點(diǎn)，追求總里程最少。乘客需求信息通過(guò)手機(jī)APP下達(dá)出行訂單獲取，包括出行起訖點(diǎn)、上車時(shí)間窗、最大容忍在車時(shí)間等。利用百度或谷歌等Open GIS平臺(tái)可以精確計(jì)算需求點(diǎn)、軌道站點(diǎn)和調(diào)度中心之間實(shí)際出行距離和時(shí)間?？紤]乘客可以新增、修改和取消訂單，每個(gè)需求點(diǎn)的乘客需求不確定，假設(shè)服從正態(tài)分布，通過(guò)歷史數(shù)據(jù)可以獲取其平均值和偏差。根據(jù)上述描述，建立該問(wèn)題的隨機(jī)線性規(guī)劃模型，見(jiàn)式(1)～(12)。

(1)

(2)

(3)

(4)

(5)

?i,j∈I∪Ms?k∈K

(6)

?i,j∈I∪Ms?k∈K

(7a)

?i,j∈I∪Ms?k∈K

(7b)

(8)

(9)

(10)

(11)

(12)

在上述模型中，式(1)為問(wèn)題的目標(biāo)函數(shù)，即總運(yùn)輸里程最少。式(2)～(12)為約束條件，其中：式(2)為每輛車至少有1個(gè)需求點(diǎn)；式(3)確保每個(gè)需求點(diǎn)只乘坐一輛車；式(4)為1個(gè)需求點(diǎn)只屬于1個(gè)線路，1個(gè)線路不能同時(shí)訪問(wèn)2個(gè)需求點(diǎn)；式(5)為保證車輛從軌道站點(diǎn)出發(fā)并返回；式(6)為避免線路出現(xiàn)子回路；式(7)為車輛k到達(dá)相鄰需求點(diǎn)i和j之間時(shí)間關(guān)系；式(8)為車輛k到達(dá)需求點(diǎn)i的時(shí)間滿足其出行時(shí)間窗；式(9)為保證需求點(diǎn)i的在車時(shí)間不超過(guò)其容忍上限；式(10)為車輛k的隨機(jī)載客量不超過(guò)其額定載客量；式(11)為表示車輛k的行程里程不超過(guò)其上限；式(12)為車輛k的行程時(shí)間不低于其下限。

1.2 基于集對(duì)分析的線性等價(jià)確定性模型

minf

(13)

(14)

其他約束與上相同。

顯然地，根據(jù)約束(8)，將該問(wèn)題分為帶時(shí)間窗的DRFTS(DRFTS with Time Windows, DRFTSTW)和不帶時(shí)間窗的DRFTS(DRFTS with No Time Windows, DRFTSNTW)；根據(jù)約束(9)，將該問(wèn)題分為帶容忍在車時(shí)間的DRFTS(DRFTS with Tolerance in Car Time, DRFTSTCT)和不帶容忍在車時(shí)間的DRFTS(DRFTS with No Tolerance in Car Time, DRFTSNTCT)。

2 算例分析

以南京商貿(mào)中心地鐵站(M)周邊的接駁公交調(diào)度為例說(shuō)明，總共15個(gè)需求點(diǎn)，它們的位置、出行時(shí)間和人數(shù)見(jiàn)表1，已知：公交車輛的額定載客量為30人、最大行程里程為9 km、最小行駛時(shí)間為3 min。

利用C#編程實(shí)現(xiàn)基于GIS和Cplex的求解框架調(diào)度平臺(tái)，當(dāng)車輛數(shù)為3，4和5時(shí)，在分析客流的各個(gè)不確定程度基礎(chǔ)上，比較有無(wú)時(shí)間窗、最大容忍實(shí)際對(duì)車輛路徑的影響，計(jì)算結(jié)果見(jiàn)表2和表3，得到以下4個(gè)結(jié)論。

1) 隨著車輛數(shù)增加，雖然直達(dá)疏散乘客節(jié)省里程，但是車輛從需求點(diǎn)出發(fā)和返回增加更多無(wú)效空駛里程，總行駛里程變化趨勢(shì)與節(jié)省里程與增加無(wú)效空駛里程相關(guān)。除了表2的DRFTSNTW在λ=1時(shí)4輛車的總里程比3輛車略少，其它均是車輛數(shù)與里程成正比，增幅在0%～15%。

表1 客戶點(diǎn)的基本信息Tab.1 Basic information of customer points

2) 當(dāng)客流的不確定程度λ由0變1時(shí)，各個(gè)需求點(diǎn)的上車人數(shù)增加，雖然受車輛的額定載客量限制，但是需求點(diǎn)的客流量不影響車輛路徑，因而總行駛里程沒(méi)有發(fā)生變化。若當(dāng)前車輛路徑無(wú)法承載需求點(diǎn)的客流量，這些車輛可能偏好距離較遠(yuǎn)但不超過(guò)其額定載客量的需求點(diǎn)，因而總行駛里程變大。例如，DRFTSNTCT和DRFTSTCT模型的5輛車對(duì)不同λ保持總行駛里程沒(méi)有變化，其他情況增幅在2%～14%。

3) 與DRFTSNTW相比，DRFTSTW的總行駛里程保持不變或逐漸變大，這是因?yàn)槌丝偷臅r(shí)間窗可能改變車輛路徑，強(qiáng)制車輛偏好較遠(yuǎn)距離但是上車時(shí)間窗緊迫的需求點(diǎn)。雖然DRFTSNTW比DRFTSNTCT的總行駛里程多，但是滿足乘客的個(gè)性化出行時(shí)間窗，從而可以將乘客從私家車吸引至軌道交通出行。除了4輛車和λ=0.5時(shí)保持不變之外，DRFTSTW與DRFTSNTW偏差在0%～10%。

4) 同上，DRFTSTCT與DRFTSNTCT相比，其總行駛里程保持不變或變大，即：考慮乘客的最長(zhǎng)容忍在車時(shí)間后，若車輛偏好最近的需求點(diǎn)可以不滿足在車時(shí)間約束。當(dāng)車輛數(shù)增加一定程度時(shí)，由于每輛車僅負(fù)責(zé)少數(shù)乘客的疏散任務(wù)，客戶的時(shí)間窗約束條件較寬松，因而該約束對(duì)目標(biāo)函數(shù)幾乎沒(méi)有影響。 一般情況下， DRFTSTW與DRFTSNTW偏差在0%～4%。

表2 不同車輛數(shù)的有無(wú)時(shí)間窗調(diào)度方案比較Tab.2 Comparison of scheduling schemes for different number of vehicles having and not having time window

表3 有無(wú)考慮乘客的最大在車時(shí)間對(duì)目標(biāo)函數(shù)的影響Tab.3 The influence of maximum time in the car on the objective function considering passengers or not

3 結(jié)束語(yǔ)

針對(duì)已有需求響應(yīng)型接駁公交調(diào)度未涉及個(gè)性化出行時(shí)間、隨機(jī)客流出行對(duì)其接駁線路設(shè)計(jì)的影響，建立了一類隨機(jī)混合整數(shù)線性規(guī)劃模型，揭示需求點(diǎn)的客流不確定程度、時(shí)間窗、容忍在車時(shí)間與調(diào)度方案之間耦合關(guān)系?；诩瘜?duì)分析，將該隨機(jī)模型轉(zhuǎn)化為一個(gè)非常簡(jiǎn)單、易處理的線性確定性模型，容易分析客流的確定性部分和不確定部分對(duì)調(diào)度結(jié)果的影響。通過(guò)Cplex對(duì)一個(gè)算例求解表明：①隨著車輛數(shù)增加，若節(jié)省里程小于無(wú)效里程的增加量，總行駛里程保持增長(zhǎng)趨勢(shì)，增幅在0%～15%。②隨著客流的不確定程度增加，若當(dāng)前車輛路徑無(wú)法承載需求點(diǎn)的客流量，總行駛里程變大，增幅在2%～14%。③與DRFTSNTW相比，DRFTSTW的總行駛里程保持不變或逐漸變大，偏差在0%～10%；同理，DRFTSTCT與DRFTSNTCT相比，其總行駛里程也保持不變或變大，偏差在0%～4%。

本模型的研究不足在于：①忽略了不同需求點(diǎn)之間的不確定客流部分差異性；②沒(méi)有考慮接駁公交和軌道交通聯(lián)動(dòng)對(duì)車輛路徑的影響；③Cplex無(wú)法求解大規(guī)模問(wèn)題，亟待尋求求解該問(wèn)題的啟發(fā)式算法，如：蟻群算法、遺傳算法等。