考慮擁堵道路停車懲罰的定制公交調(diào)度研究

程仁輝，賈順平

(北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044)

定制公交(customized bus，CB)是一種介于價(jià)格實(shí)惠的常規(guī)公交和舒適快捷的網(wǎng)約車之間的一種公交服務(wù)模式，服務(wù)于特定人群，為處于相同區(qū)域、有相近出行時(shí)間和相似出行需求的乘客群體量身定制[1]。定制公交有著比常規(guī)公交更加復(fù)雜且精細(xì)的運(yùn)作流程。首先必須進(jìn)行需求分析，制定基本的線路開行方案；然后設(shè)計(jì)產(chǎn)品方案，包括乘客端、司機(jī)端和調(diào)度端等終端設(shè)計(jì)；最后招募乘客，編制最終的行車計(jì)劃和人員排班計(jì)劃[2]。由于乘客的出行需求是動(dòng)態(tài)變化的，定制公交需要對(duì)實(shí)時(shí)產(chǎn)生的乘客請(qǐng)求進(jìn)行決策響應(yīng)和調(diào)度安排[3]。

對(duì)網(wǎng)約公交的研究是從理論設(shè)想逐漸深入實(shí)際的。Liu等[4]全面考察了定制公交的背景及其在中國的時(shí)空分布，分析了CB的運(yùn)營規(guī)劃過程。Tong等[5]從時(shí)空網(wǎng)絡(luò)建模的角度出發(fā)，提出了一種基于多商品網(wǎng)絡(luò)流的優(yōu)化模型和基于時(shí)空棱鏡的算法，在滿足通過時(shí)空窗定義的個(gè)性化需求的同時(shí)，優(yōu)化車輛容量的利用率。Lyu等[6]提出了一種面向定制公交系統(tǒng)的公交線路規(guī)劃框架CB-Planner，并利用中國南京市的出租車軌跡數(shù)據(jù)驗(yàn)證了優(yōu)化模型。

對(duì)公交車輛調(diào)度和路徑規(guī)劃等優(yōu)化問題，專家學(xué)者采用了多種方法來進(jìn)行模擬求解。對(duì)于突尼斯的校車路徑規(guī)劃，Euchi等[7]采用元啟發(fā)式方法和改進(jìn)混合人工蟻群算法求解，以使得校車總行駛距離最小化。邵文等[8]考慮混合車型聯(lián)合調(diào)度和乘客滿意度對(duì)接駁公交路徑優(yōu)化的影響，建立了靈活型接駁公交路徑協(xié)同優(yōu)化模型。鄭漢等[9]提出使用混合車型的需求響應(yīng)服務(wù)定制方法，構(gòu)建了需求響應(yīng)公交服務(wù)定制等價(jià)分解模型。趙偉忠[10]以乘客在站等待時(shí)間、乘客在車等待時(shí)間、車輛運(yùn)行效益為優(yōu)化目標(biāo)，建立了實(shí)時(shí)公交線路生成模型，從可靠性和舒適性兩方面來研究需求響應(yīng)式定制公交線路設(shè)計(jì)。

目前對(duì)定制公交的研究主要集中于路徑規(guī)劃、政策選擇、服務(wù)水平評(píng)價(jià)等方面，但是大多數(shù)的研究都比較理想化，簡單地以總路徑最短或者運(yùn)營成本最小為最優(yōu)目標(biāo)，而很少考慮實(shí)際條件下道路擁堵條件和乘客對(duì)等待時(shí)間和費(fèi)用的接受程度。本文以企業(yè)密集的城市產(chǎn)業(yè)園區(qū)乘客通勤問題為背景，在乘車需求集中區(qū)域，研究單一首發(fā)站和終點(diǎn)站的定制公交決策安排和車輛調(diào)度?？紤]到定制公交在擁堵道路停車載客對(duì)道路交通的影響，構(gòu)造合適的擁堵道路停車懲罰函數(shù)，以定制公交及乘客的最優(yōu)成本為目標(biāo)建立了實(shí)時(shí)需求響應(yīng)的定制公交調(diào)度決策模型，并采用改進(jìn)遺傳算法和插入算法求解模型。

1 懲罰函數(shù)和調(diào)度規(guī)則

1.1 擁堵道路停車懲罰函數(shù)

大城市很多產(chǎn)業(yè)園區(qū)接近城市邊緣，這些區(qū)域公共交通覆蓋密度低，其服務(wù)難以滿足乘客個(gè)性化需求，園區(qū)內(nèi)主要道路飽和度過高且服務(wù)水平低下。推動(dòng)定制公交替代私人交通出行，可以有效緩解道路擁堵情況。但是定制公交車輛在擁堵道路上多次停車載客會(huì)讓乘客產(chǎn)生厭煩心理，同時(shí)由于道路等級(jí)低還會(huì)嚴(yán)重阻礙道路交通順暢?？紤]乘客心理和道路交通的影響，對(duì)定制公交給予一定的擁堵道路停車載客懲罰。通過停車載客懲罰成本約束定制公交對(duì)乘客需求的響應(yīng)，減少在某些擁堵道路上的停車載客次數(shù)，而盡量在負(fù)荷度小的道路上進(jìn)行響應(yīng)載客，使定制公交能夠連續(xù)行駛且減少對(duì)高負(fù)荷道路的壓力，維持路網(wǎng)的通暢。

本文考慮公交車輛在不同等級(jí)及不同擁堵程度道路上，由于停車次數(shù)和人數(shù)造成的占用道路構(gòu)造了式(1)停車懲罰成本函數(shù)。

(1)

式中，F(xiàn)road為擁堵道路停車懲罰成本，N為道路R上累計(jì)停車載客的人數(shù)，LR為道路等級(jí)修正系數(shù)(本文對(duì)次干路和支路分別取1.2和0.9)，C為道路負(fù)荷度，p為停車次數(shù)，m、n為參數(shù)。從式(1)可以看出，停車懲罰成本和載客人數(shù)成正比關(guān)系，與停車次數(shù)呈指數(shù)關(guān)系。

1.2 乘客時(shí)間窗成本懲罰函數(shù)

在實(shí)際情況下，乘客對(duì)等待公交車輛的時(shí)長具有一定的忍耐程度，但隨著等待時(shí)間的增加，乘客的不滿意度會(huì)急劇上升?？紤]用時(shí)間成本函數(shù)來對(duì)車輛違反乘客時(shí)間窗進(jìn)行懲罰，懲罰成本會(huì)隨著違反時(shí)間的增加呈指數(shù)趨勢(shì)增長。式(2)為乘客時(shí)間窗的時(shí)間成本懲罰函數(shù)[11]。

(2)

1.3 調(diào)度規(guī)則

定制公交開行方案由兩方面的乘客需求確定，一是提前預(yù)約的乘客靜態(tài)需求，二是實(shí)時(shí)網(wǎng)約的乘客動(dòng)態(tài)請(qǐng)求，定制公交需要對(duì)車輛進(jìn)行調(diào)度和響應(yīng)決策來滿足乘客的預(yù)約和網(wǎng)約需求。主要有以下幾個(gè)原則：

(1)乘客靜態(tài)需求的優(yōu)先級(jí)高于乘客動(dòng)態(tài)需求，即一個(gè)調(diào)度周期內(nèi)應(yīng)首先根據(jù)提前預(yù)約的客流需求制定調(diào)度計(jì)劃，其次實(shí)行動(dòng)態(tài)調(diào)整。

(2)對(duì)于提前預(yù)約的乘客，需要滿足其時(shí)間窗要求；對(duì)于臨時(shí)網(wǎng)約的乘客，如果響應(yīng)則應(yīng)盡量減少其等待時(shí)間，并告知乘客需要等待的時(shí)間。

(3)假設(shè)乘客在其預(yù)約時(shí)間點(diǎn)上到達(dá)服務(wù)點(diǎn)，等車忍耐時(shí)長為5 min。

(4)為減少使用的車輛數(shù)，制定的車輛調(diào)度周期在滿足乘客時(shí)間窗的前提下應(yīng)有冗余時(shí)間循環(huán)服務(wù)。

(5)通過對(duì)車等人、人等車的時(shí)間成本懲罰，避免車輛長時(shí)間的停靠等待和掉頭接客，避免乘客等車時(shí)間過長。

根據(jù)調(diào)度規(guī)則，制定了如圖1所示的一個(gè)周期定制公交靜、動(dòng)態(tài)兩階段調(diào)度流程。第一階段為帶時(shí)間窗的靜態(tài)車輛路徑問題(SVRP)，首先根據(jù)預(yù)定需求制定靜態(tài)開行方案，并對(duì)實(shí)時(shí)產(chǎn)生的網(wǎng)約請(qǐng)求進(jìn)行判斷。第二階段為動(dòng)態(tài)車輛路徑問題(DVRP)，通過路徑插入，對(duì)局部成本變動(dòng)進(jìn)行比較后作出決策，若當(dāng)前班次選擇響應(yīng)實(shí)時(shí)請(qǐng)求，則形成新的路徑，若選擇不進(jìn)行響應(yīng)，則繼續(xù)原來的開行方案。

圖1 定制公交基本調(diào)度流程圖

2 定制公交調(diào)度模型

2.1 問題描述

研究的某區(qū)域內(nèi)，定制公交有唯一起終點(diǎn)和多個(gè)沿途公交服務(wù)點(diǎn)，起點(diǎn)首發(fā)站停車場(chǎng)和終點(diǎn)位置均已確定，沿途公交服務(wù)站點(diǎn)則根據(jù)乘客需求進(jìn)行決策確定。預(yù)先確定公交發(fā)車周期以及基準(zhǔn)線路，對(duì)提前預(yù)約和實(shí)時(shí)網(wǎng)約的乘客進(jìn)行定制服務(wù)。一個(gè)運(yùn)行周期具有一定的松弛時(shí)間，公交可以在約束條件下偏離基準(zhǔn)線路響應(yīng)實(shí)時(shí)需求載客，通過其靈活可變的時(shí)空范圍來更好地完成車輛的調(diào)度計(jì)劃。

2.2 模型假設(shè)

建立的模型需要滿足乘客的軟時(shí)間窗要求，減少乘客等待時(shí)間，并在調(diào)度車輛的服務(wù)路徑中考慮停車懲罰，盡量減少在飽和度過高道路上的停車載客次數(shù)。為方便建立模型，本文給出以下的假設(shè)。

(1)在服務(wù)范圍內(nèi)，乘客動(dòng)態(tài)請(qǐng)求是隨機(jī)的，且符合空間和時(shí)間上的均勻分布。將服務(wù)站點(diǎn)乘客上下車的時(shí)間成本考慮進(jìn)擁堵道路停車懲罰成本中計(jì)算。

(2)定制公交在行程中基本勻速行駛，不受交通條件和道路條件的限制。

(3)公交車輛采用單方向行駛，即每個(gè)站點(diǎn)只經(jīng)過一次，基準(zhǔn)路線上不允許掉頭和下客。

(4)定制公交?？奎c(diǎn)設(shè)為始發(fā)點(diǎn)，開行前公交車輛都在始發(fā)站點(diǎn)處等待，公交終點(diǎn)為某一固定的地鐵站，但是沿途服務(wù)點(diǎn)為服務(wù)區(qū)域范圍內(nèi)自由選擇。

(5)車內(nèi)乘客數(shù)量不超過規(guī)定公交車型的額定座位數(shù)。

2.3 模型建立

模型參數(shù)及其含義如表1所示。

表1 模型參數(shù)及其含義

本文綜合考慮乘客需求、公交車輛運(yùn)行成本和擁堵道路停車成本及乘客時(shí)間窗懲罰成本，以系統(tǒng)總成本最小建立了定制公交車輛調(diào)度模型，如式(3)所示。

(3)

(4)

(5)

(6)

(7)

(8)

(9)

模型目標(biāo)函數(shù)Z，包含的4個(gè)目標(biāo)分別為乘客在車時(shí)間成本、車輛運(yùn)行時(shí)間成本、違反乘客時(shí)間窗懲罰成本和擁堵道路停車懲罰成本，綜合以求得最小的系統(tǒng)廣義總成本。式(4)表示公交車輛一定會(huì)經(jīng)過線路上的某一服務(wù)點(diǎn)；式(5)表示車輛經(jīng)過某一站點(diǎn)后會(huì)離開此站點(diǎn)；式(6)為起點(diǎn)約束，服務(wù)點(diǎn)O為起始站點(diǎn)；式(7)為終點(diǎn)約束，服務(wù)點(diǎn)n為終點(diǎn)站；式(8)為車輛運(yùn)行周期時(shí)間約束，不超過乘客可容忍的最大的乘車時(shí)間；式(9)為載客量約束，不超過車輛額定載客量。

式(3)是根據(jù)預(yù)約乘客的需求信息建立的SVRP調(diào)度模型，而實(shí)時(shí)網(wǎng)約的乘客動(dòng)態(tài)請(qǐng)求，則是一個(gè)DVRP調(diào)度問題。是否實(shí)時(shí)響應(yīng)產(chǎn)生的動(dòng)態(tài)請(qǐng)求r需要考慮定制公交荷載量約束以及改變?cè)ň€路后的成本變化。本文采用插入式算法，采用式(10)成本變動(dòng)函數(shù)進(jìn)行決策判斷。對(duì)動(dòng)態(tài)請(qǐng)求僅考慮局部費(fèi)用，即增加的乘客時(shí)間窗懲罰成本和停車載客成本，在去除車票價(jià)格fr后，選擇最小成本變動(dòng)者進(jìn)行響應(yīng)，將動(dòng)態(tài)請(qǐng)求插入到現(xiàn)有線路中，車輛及時(shí)作出調(diào)整，規(guī)劃新的載客方案，而將不滿足的請(qǐng)求傳給下一班次的車輛進(jìn)行調(diào)度安排。每一車次都會(huì)不斷地對(duì)實(shí)時(shí)產(chǎn)生的r=r+1個(gè)需求進(jìn)行成本計(jì)算和決定是否響應(yīng)此請(qǐng)求，并及時(shí)更新線路，直到到達(dá)終點(diǎn)。

min ΔZ=ΔF(t)+ΔFroad-fr。

(10)

2.4 求解方法

因?yàn)槎ㄖ乒宦窂揭?guī)劃問題是多目標(biāo)優(yōu)化難題，隨著數(shù)據(jù)規(guī)模的擴(kuò)大，計(jì)算量將呈指數(shù)增大，傳統(tǒng)方法難以在較短時(shí)間內(nèi)解決。本文采用搜索能力較強(qiáng)的改進(jìn)遺傳算法和插入精確求解法來求解建立的模型，對(duì)交叉和變異的概率大小采用自適應(yīng)化處理，計(jì)算公式如下：

(11)

式中，Po為交叉概率，Pv為變異概率,fmax為種群中最大適應(yīng)值,favg為種群平均適應(yīng)值,f′為交叉的兩個(gè)體適應(yīng)度值較大者,f為個(gè)體適應(yīng)度值,k1、k2、k3、k4為常數(shù)。

求解步驟如下：

Step 1：采用實(shí)數(shù)編碼，0表示定制公交出發(fā)點(diǎn)，從1開始的自然數(shù)表示靜態(tài)需求點(diǎn)。隨機(jī)生成染色體創(chuàng)建定制公交調(diào)度路徑初始種群initpop，經(jīng)過荷載約束判斷后，根據(jù)模型計(jì)算出每條車輛路徑目標(biāo)函數(shù)值，經(jīng)過函數(shù)值變換f=1/f成為最大化問題，得出每條染色體的適應(yīng)度值。

Step 2：遺傳算法的選擇、交叉和變異操作。根據(jù)染色體的適應(yīng)度值，采取精英保留策略保存最佳個(gè)體后，再使用輪盤賭方式選擇優(yōu)化個(gè)體遺傳下一代。采用保留精英個(gè)體的部分映射交叉和基本位變異算子來產(chǎn)生新的種群newpop。

Step 3：終止條件判斷。如果迭代次數(shù)(iteration)大于最大進(jìn)化代數(shù)(maxiter)，則終止運(yùn)算，否則返回Step 2繼續(xù)迭代。

Step 4：對(duì)新增的動(dòng)態(tài)需求r，根據(jù)荷載約束條件，插入當(dāng)前路徑求出最小的成本變化ΔZ,來判斷是否響應(yīng)請(qǐng)求。如果響應(yīng)，則對(duì)r=r+1請(qǐng)求繼續(xù)進(jìn)行決策，反之，給下一班次進(jìn)行調(diào)度。

3 案例分析

3.1 背景介紹

本文以北京市海淀區(qū)軟件園為研究背景，驗(yàn)證提出的模型適用性和開通定制公交的可行性。園區(qū)乘客由于職住分離，多數(shù)人以附近西二旗和新開通的清河地鐵站為換乘點(diǎn)，并且員工因?yàn)閺椥怨ぷ髦?，可以為定制公交帶來足夠的差異化乘客。軟件園區(qū)道路情況和定制公交OD位置如圖2所示。

圖2 園區(qū)路網(wǎng)和定制公交車場(chǎng)位置圖

園區(qū)內(nèi)路網(wǎng)較為密集，多為低等級(jí)次干路和支路，以軟件園南街為基準(zhǔn)路線。園區(qū)西側(cè)為公交起點(diǎn)，終點(diǎn)為東側(cè)軌道交通站點(diǎn)。經(jīng)調(diào)研發(fā)現(xiàn)，園區(qū)各道路面臨交通壓力區(qū)別較大，軟件園南街高峰小時(shí)負(fù)荷度達(dá)0.8，部分路段甚至超過了1，高峰時(shí)段擁堵相當(dāng)嚴(yán)重，而其他道路則為0.5左右。

3.2 參數(shù)標(biāo)定

對(duì)案例的主要參數(shù)標(biāo)定如表2所示，其中車輛最大的行駛時(shí)間為45 min，公交最大載客量為16人。定制公交需要制定合理的發(fā)車計(jì)劃，本文案例設(shè)固定發(fā)車周期為15 min，使用3輛車來對(duì)乘客需求進(jìn)行載客調(diào)度安排。

表2 案例主要參數(shù)標(biāo)定

擁堵停車懲罰函數(shù)參數(shù)取值為：

乘客時(shí)間窗約束懲罰函數(shù)參數(shù)標(biāo)定為：

站點(diǎn)的預(yù)約人數(shù)和預(yù)約時(shí)刻見表3，這里將時(shí)刻表簡單化成從0 min開始，站點(diǎn)之間的行駛時(shí)間見表4。

表3 各站點(diǎn)的預(yù)約人數(shù)和預(yù)約時(shí)間

表4 各站點(diǎn)間旅行時(shí)間矩陣表

除了提前預(yù)約站點(diǎn)外，在實(shí)際運(yùn)行過程中，定制公交還需要對(duì)實(shí)時(shí)的動(dòng)態(tài)需求進(jìn)行處理。假設(shè)時(shí)間在30 min時(shí)，公交系統(tǒng)收到5個(gè)動(dòng)態(tài)需求r1,r2,…,r5，每個(gè)需求的人數(shù)均為1，通過采用SVRP調(diào)度階段改進(jìn)遺傳算法和DVRP調(diào)度階段插入式方法進(jìn)行計(jì)算求解，定制公交做出響應(yīng)決策和調(diào)度安排。

3.3 運(yùn)行結(jié)果及分析

對(duì)文章案例的計(jì)算是在Win10系統(tǒng)電腦上，使用Python語言進(jìn)行編碼求解。在模型約束條件下，遺傳算法運(yùn)行結(jié)果如圖3所示，目標(biāo)函數(shù)大約在400代達(dá)到收斂，運(yùn)行時(shí)間為8.9 s，得出的靜態(tài)最優(yōu)解染色體編碼為[0, 2, 5, 6, 8, 11, 13, 15, 0, 1,3, 4, 7, 9, 10, 12, 14]，表示2—5—6—8—11—13—15和1—3—4—7—9—10—12—14兩條定制公交車輛調(diào)度路徑。

圖3 目標(biāo)函數(shù)求解進(jìn)化趨勢(shì)

定制公交在對(duì)靜態(tài)需求進(jìn)行車輛調(diào)度和路徑規(guī)劃之后，對(duì)實(shí)時(shí)產(chǎn)生的乘客需求進(jìn)行插入計(jì)算，進(jìn)而做出響應(yīng)決策并動(dòng)態(tài)調(diào)整車輛調(diào)度。根據(jù)計(jì)算結(jié)果，在不考慮擁堵道路停車載客懲罰情況下，定制公交將對(duì)5個(gè)動(dòng)態(tài)需求均進(jìn)行響應(yīng)，這種結(jié)果導(dǎo)致車輛在南街停車次數(shù)過多及增加旅行時(shí)間，會(huì)加大南街的交通壓力，對(duì)乘客產(chǎn)生負(fù)面效果。

而在考慮停車載客懲罰情況下，定制公交根據(jù)最優(yōu)成本做出響應(yīng)的決策，得出車輛路徑圖見圖4，最終結(jié)果見表5。

圖4 車輛調(diào)度路徑圖

表5 考慮停車懲罰后定制公交調(diào)度結(jié)果

定制公交對(duì)動(dòng)態(tài)需求中4個(gè)請(qǐng)求進(jìn)行了響應(yīng)，車輛1和車輛2分別響應(yīng)了1個(gè)和2個(gè)請(qǐng)求，同時(shí)將請(qǐng)求r4和9插入進(jìn)后續(xù)第3輛車的可能路徑中，系統(tǒng)出于滿載和懲罰約束以及最優(yōu)成本原因拒絕了在南街上的r2請(qǐng)求點(diǎn)。

從表5中可以看出，兩輛車的行駛時(shí)間分別為33和32 min，小于最大的行駛周期45 min，因此車輛有一定的松弛時(shí)間。所有乘客平均等待時(shí)間分別為2.3和5.8 min，在乘客可接受的時(shí)長范圍內(nèi)。滿載率分別為93.7%和100.0%，車輛容量利用率較高。目標(biāo)函數(shù)成本為144.8元，擁堵道路停車懲罰的總成本為28.3元，成本控制較好。

從案例靜態(tài)需求和動(dòng)態(tài)需求的最終調(diào)度結(jié)果看，此次調(diào)度能夠基本滿足要求。在采用本文建立的定制公交調(diào)度模型和求解算法下，定制公交的成本控制、班次時(shí)長、滿載率以及擁堵停車懲罰等目標(biāo)均比較滿意，系統(tǒng)的運(yùn)營調(diào)度是比較合理的。

4 結(jié)論

本文對(duì)響應(yīng)乘客實(shí)時(shí)需求的定制公交進(jìn)行了系統(tǒng)分析和調(diào)度研究，在考慮實(shí)際的路網(wǎng)擁堵條件和乘客候車時(shí)長忍耐程度下，標(biāo)定了擁堵道路停車懲罰成本函數(shù)和乘客時(shí)間窗懲罰成本函數(shù)，建立了考慮擁堵道路停車懲罰的定制公交路徑調(diào)度最小成本模型。對(duì)實(shí)例的求解結(jié)果表明，提出的定制公交可以在較短時(shí)間內(nèi)做出合理的決策和車輛調(diào)度安排，既能解決乘客的出行需求，又能有效降低道路通行壓力。

本文建立的懲罰函數(shù)和目標(biāo)模型的各參數(shù)需要結(jié)合實(shí)際路網(wǎng)和城市經(jīng)濟(jì)情況進(jìn)行修正，在某一個(gè)更大的城市區(qū)域內(nèi)對(duì)較大數(shù)量的乘客需求進(jìn)行分析計(jì)算，可以有效地對(duì)車輛進(jìn)行調(diào)度優(yōu)化和緩解道路擁堵問題。