考慮擁堵道路停車懲罰的定制公交調度研究

程仁輝，賈順平

(北京交通大學 交通運輸學院，北京 100044)

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

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

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

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

1 懲罰函數和調度規則

1.1 擁堵道路停車懲罰函數

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

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

(1)

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

1.2 乘客時間窗成本懲罰函數

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

(2)

1.3 調度規則

定制公交開行方案由兩方面的乘客需求確定，一是提前預約的乘客靜態需求，二是實時網約的乘客動態請求，定制公交需要對車輛進行調度和響應決策來滿足乘客的預約和網約需求。主要有以下幾個原則：

(1)乘客靜態需求的優先級高于乘客動態需求，即一個調度周期內應首先根據提前預約的客流需求制定調度計劃，其次實行動態調整。

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

(3)假設乘客在其預約時間點上到達服務點，等車忍耐時長為5 min。

(4)為減少使用的車輛數，制定的車輛調度周期在滿足乘客時間窗的前提下應有冗余時間循環服務。

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

根據調度規則，制定了如圖1所示的一個周期定制公交靜、動態兩階段調度流程。第一階段為帶時間窗的靜態車輛路徑問題(SVRP)，首先根據預定需求制定靜態開行方案，并對實時產生的網約請求進行判斷。第二階段為動態車輛路徑問題(DVRP)，通過路徑插入，對局部成本變動進行比較后作出決策，若當前班次選擇響應實時請求，則形成新的路徑，若選擇不進行響應，則繼續原來的開行方案。

圖1 定制公交基本調度流程圖

2 定制公交調度模型

2.1 問題描述

研究的某區域內，定制公交有唯一起終點和多個沿途公交服務點，起點首發站停車場和終點位置均已確定，沿途公交服務站點則根據乘客需求進行決策確定。預先確定公交發車周期以及基準線路，對提前預約和實時網約的乘客進行定制服務。一個運行周期具有一定的松弛時間，公交可以在約束條件下偏離基準線路響應實時需求載客，通過其靈活可變的時空范圍來更好地完成車輛的調度計劃。

2.2 模型假設

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

(1)在服務范圍內，乘客動態請求是隨機的，且符合空間和時間上的均勻分布。將服務站點乘客上下車的時間成本考慮進擁堵道路停車懲罰成本中計算。

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

(3)公交車輛采用單方向行駛，即每個站點只經過一次，基準路線上不允許掉頭和下客。

(4)定制公交停靠點設為始發點，開行前公交車輛都在始發站點處等待，公交終點為某一固定的地鐵站，但是沿途服務點為服務區域范圍內自由選擇。

(5)車內乘客數量不超過規定公交車型的額定座位數。

2.3 模型建立

模型參數及其含義如表1所示。

表1 模型參數及其含義

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

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

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

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

(10)

2.4 求解方法

因為定制公交路徑規劃問題是多目標優化難題，隨著數據規模的擴大，計算量將呈指數增大，傳統方法難以在較短時間內解決。本文采用搜索能力較強的改進遺傳算法和插入精確求解法來求解建立的模型，對交叉和變異的概率大小采用自適應化處理，計算公式如下：

(11)

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

求解步驟如下：

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

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

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

Step 4：對新增的動態需求r，根據荷載約束條件，插入當前路徑求出最小的成本變化ΔZ,來判斷是否響應請求。如果響應，則對r=r+1請求繼續進行決策，反之，給下一班次進行調度。

3 案例分析

3.1 背景介紹

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

圖2 園區路網和定制公交車場位置圖

園區內路網較為密集，多為低等級次干路和支路，以軟件園南街為基準路線。園區西側為公交起點，終點為東側軌道交通站點。經調研發現，園區各道路面臨交通壓力區別較大，軟件園南街高峰小時負荷度達0.8，部分路段甚至超過了1，高峰時段擁堵相當嚴重，而其他道路則為0.5左右。

3.2 參數標定

對案例的主要參數標定如表2所示，其中車輛最大的行駛時間為45 min，公交最大載客量為16人。定制公交需要制定合理的發車計劃，本文案例設固定發車周期為15 min，使用3輛車來對乘客需求進行載客調度安排。

表2 案例主要參數標定

擁堵停車懲罰函數參數取值為：

乘客時間窗約束懲罰函數參數標定為：

站點的預約人數和預約時刻見表3，這里將時刻表簡單化成從0 min開始，站點之間的行駛時間見表4。

表3 各站點的預約人數和預約時間

表4 各站點間旅行時間矩陣表

除了提前預約站點外，在實際運行過程中，定制公交還需要對實時的動態需求進行處理。假設時間在30 min時，公交系統收到5個動態需求r1,r2,…,r5，每個需求的人數均為1，通過采用SVRP調度階段改進遺傳算法和DVRP調度階段插入式方法進行計算求解，定制公交做出響應決策和調度安排。

3.3 運行結果及分析

對文章案例的計算是在Win10系統電腦上，使用Python語言進行編碼求解。在模型約束條件下，遺傳算法運行結果如圖3所示，目標函數大約在400代達到收斂，運行時間為8.9 s，得出的靜態最優解染色體編碼為[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兩條定制公交車輛調度路徑。

圖3 目標函數求解進化趨勢

定制公交在對靜態需求進行車輛調度和路徑規劃之后，對實時產生的乘客需求進行插入計算，進而做出響應決策并動態調整車輛調度。根據計算結果，在不考慮擁堵道路停車載客懲罰情況下，定制公交將對5個動態需求均進行響應，這種結果導致車輛在南街停車次數過多及增加旅行時間，會加大南街的交通壓力，對乘客產生負面效果。

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

圖4 車輛調度路徑圖

表5 考慮停車懲罰后定制公交調度結果

定制公交對動態需求中4個請求進行了響應，車輛1和車輛2分別響應了1個和2個請求，同時將請求r4和9插入進后續第3輛車的可能路徑中，系統出于滿載和懲罰約束以及最優成本原因拒絕了在南街上的r2請求點。

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

從案例靜態需求和動態需求的最終調度結果看，此次調度能夠基本滿足要求。在采用本文建立的定制公交調度模型和求解算法下，定制公交的成本控制、班次時長、滿載率以及擁堵停車懲罰等目標均比較滿意，系統的運營調度是比較合理的。

4 結論

本文對響應乘客實時需求的定制公交進行了系統分析和調度研究，在考慮實際的路網擁堵條件和乘客候車時長忍耐程度下，標定了擁堵道路停車懲罰成本函數和乘客時間窗懲罰成本函數，建立了考慮擁堵道路停車懲罰的定制公交路徑調度最小成本模型。對實例的求解結果表明，提出的定制公交可以在較短時間內做出合理的決策和車輛調度安排，既能解決乘客的出行需求，又能有效降低道路通行壓力。

本文建立的懲罰函數和目標模型的各參數需要結合實際路網和城市經濟情況進行修正，在某一個更大的城市區域內對較大數量的乘客需求進行分析計算，可以有效地對車輛進行調度優化和緩解道路擁堵問題。