程仁輝，賈順平

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

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

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

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

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

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

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

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

(5)通過對車等人、人等車的時間成本懲罰，避免車輛長時間的?？康却偷纛^接客，避免乘客等車時間過長。

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

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

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

2.1 問題描述

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

2.2 模型假設(shè)

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

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

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

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

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

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

2.3 模型建立

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

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

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

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

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

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

(10)

2.4 求解方法

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

(11)

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

求解步驟如下：

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

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

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

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

3 案例分析

3.1 背景介紹

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

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

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

3.2 參數(shù)標定

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

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

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

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

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

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

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

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

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

對文章案例的計算是在Win10系統(tǒng)電腦上，使用Python語言進行編碼求解。在模型約束條件下，遺傳算法運行結(jié)果如圖3所示，目標函數(shù)大約在400代達到收斂，運行時間為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 目標函數(shù)求解進化趨勢

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

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

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

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

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

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

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

4 結(jié)論

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

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