基于混合車型的靈活型接駁公交路徑協同優化研究

邵文，賈順平，曹文娟

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

目前，我國城市公共交通系統以軌道交通為骨干，常規公交為主體，由于二者“定點”與“定線”的特性，乘客出行需要一定距離的繞行，無法滿足非高峰時段居民出行需求。相比固定線路公交，靈活型接駁公交作為介于常規公交與出租車之間的新興公交服務模式，具有更優的機動性、便捷性和舒適性，可提高居民出行直達性，是完善城市交通資源優化配置的有效方法。該系統多適用于城市邊緣地帶、高科技園區、新型居民區等客流密度中等偏低的地區，是聯系周邊交通小區與主線公交的紐帶，其調度方案和停靠站位置可根據乘客需求調整，能有效滿足低出行密度區域多樣化、個性化的居民出行需求。

國外關于靈活型接駁公交系統的研究要早于國內，有較為充分的理論成果并得以應用。Cole[1]提出的7種交通運營模式之一的Dial-a-Bus系統作為靈活型接駁公交系統的雛形，旨在解決低密度人口區域居民出行難的問題。Flussberg[2]提出了根據乘客出行需求在特定區域提供靈活型接駁服務的Merrill-Go-Round系統，并進行了實例應用研究。現有的針對靈活型接駁公交線路調度優化的研究多是關于可變線路式的服務系統(mobility allowance shuttle transit，MAST)，即車輛圍繞一條由若干站點組成的基準線路運行，車輛可在兩固定站點間允許的松弛時間內一定程度地偏離基準線路。針對MAST系統的線路設計、車輛調度等優化問題，Malucelli等[3]建立了離線優化模型，Quadrifoglio等[4-5]建立了混合整數規劃模型，并提出插入式啟發算法求解[6-7]，但均未充分考慮接駁公交與主線公交時刻表的協同優化。國內學者對于該系統的研究起步較晚，但也取得了一些研究成果。熊杰等[8]綜合考慮路徑出行時間和圈點線路約束，以路徑需求潛力最大化為優化目標，建立地鐵接駁線路的路徑優化模型，并提出基于路段交叉變異的遺傳算法求解模型。潘述亮等[9]兼顧出行者和運營者雙方利益，就接駁系統線路規劃和車輛協同問題，建立路徑優化和協調調度整數規劃模型，并設計了一種基于新型重模型的啟發式算法進行求解。劉心雨等[10]研究了保障乘客在期望時間及可接受延誤時間范圍內到達換乘中心的前提下，基于乘客不同出行目的的接駁公交線路調度優化方案。目前，國內外關于靈活型接駁公交服務系統的研究多側重于減少系統出行成本，而忽略了公交服務滿意度這一關鍵因素。將公交服務滿意度納入系統優化目標將有助于提高公交服務水平，增強客流吸引力[11]。

本文考慮乘客滿意度這一影響因素，將其轉化為接駁公交與主線公交時刻表的協同優化，兼顧混合車型對靈活型公交接駁系統運營成本的影響，針對靈活型接駁公交的路徑優化及協同調度問題展開研究。以單個換乘站點為研究對象，同一個固定換乘點作為接駁公交的起訖點，依據乘客預約出行需求和各需求點車輛到達時間動態優化接駁車輛的運行線路和調度方案，最終生成多條車輛行駛路徑，即在給定預約需求和車隊規模的前提下，以最大化乘客滿意度和最小化企業運營成本為優化目標，建立基于混合車型的靈活型接駁公交路徑協同優化模型，并使用遺傳算法對該模型進行求解。

1 研究問題描述

本文所研究的靈活型接駁公交可定義為依托于互聯網平臺，運營方根據乘客預約的出行申請設計車輛行駛線路，完成招募乘客、預訂座位、在線支付等一系列公交服務[12]。

為研究車輛路徑優化問題，現進行詳細描述：在服務區域內有1個固定換乘站點和n個需求點，換乘點內有mp輛不同類型容量為Qp的接駁車輛供其調配，輸出結果為多條車輛行駛的有向路徑。以車輛把乘客從需求點送達換乘站的過程為例，車輛一次接駁服務可定義為：車輛從換乘站點出發，基于乘客預約的確定性需求依次對需求響應站點服務后，最終返回原換乘站點，即完成“多對一”條件下的接駁車輛路徑優化和調度方案設計。如圖1所示，圖中有3條接駁線路，線路1采用車型a服務，線路2和線路3均采用車型b服務。

圖1 基于混合車型的接駁車輛行駛路線示意圖Fig.1 Schematic of the flexible shuttle transit routing based on various vehicle types

2 靈活型接駁公交路徑協同優化模型

2.1 模型假設

定義編號0為換乘站，編號1,2,3,…,n為乘客需求點。在建模過程中，進行如下假設：

(1)服務區域內有1個換乘站點和n個需求響應站點，各站點位置已知；

(2)接駁車輛保持一定的速度在各站點間勻速行駛，忽略特殊交通狀況和乘客上下車對車速的影響，不考慮延時和等待；

(3)換乘站點和各需求點間均互相通達，每兩個站點間的行程時間固定且已知；

(4)換乘站所能提供接駁服務的車隊規模已知；

(5)服務區域內不存在拒絕服務乘客的情況，所有有預約申請的乘客均被服務；

(6)乘客提交預約申請時，明確出行需求，包括需求點位置、出發時刻、期望和可容忍服務時間窗，只能將換乘點和需求點作為出行起訖點，起訖點不能均是需求點；

(7)接駁公交系統只服務于有預約申請的乘客，所有申請均在車輛出發前完成，行駛過程中不存在乘客需求變動的情況。

2.2 模型構建

模型中的主要參數和決策變量的含義如表1所示。

表1 模型參數

2.2.1 目標函數

靈活型接駁公交屬于城市公共交通的類別，其運營一般需要兼顧乘客和企業雙方利益，在保證乘客滿意度水平的同時降低企業運營成本。基于此，本文將以企業運營成本最小和乘客滿意度最大兩部分作為目標函數建立模型。

(1)最小化企業運營成本

參考已有研究，公交企業運營成本主要包括車輛損耗成本和車輛油耗成本[13]。車輛損耗成本為每次啟動車輛時所產生的折舊損耗費用，與發車次數相關；車輛油耗成本與車輛類型和行駛里程有關，不同類型車輛的油耗成本與行駛里程成正比例關系。

所以公交企業運營成本可表示為：

(1)

(2)最大化乘客滿意度

(2)

圖2 軟時間窗約束下乘客滿意度函數圖Fig.2 Passenger satisfaction function with soft time window constraints

(3)

圖3 硬時間窗約束下乘客滿意度函數圖Fig.3 Passenger satisfaction function with hard time window constraints

因此，乘客滿意度函數可整理如公式4所示，乘客滿意度最大的目標函數如公式5所示。

(4)

maxZ2=fsat。

(5)

2.2.2 模型綜合表述

s.t.

(6)

(7)

(8)

(9)

,?k∈D，

(10)

(11)

(12)

(13)

(14)

(15)

式(6)、(7)表示接駁車輛行駛過程中各需求點僅有1條行駛路徑；式(8)表示車上乘客數不超過p車型的額定載客量；式(9)表示調度過程中所使用的各車型車輛數不可超出換乘站總配備車輛數；式(10)表示車輛從換乘站點出發，最終返回原換乘站完成接駁服務；式(11)表示一次接駁服務行程中，每輛車不得超過最大允許行駛距離；式(12)表示需求點i乘客滿意度函數的軟時間窗約束；式(13)表示第k輛車返回換乘站的乘客滿意度函數的硬時間窗約束；式(14)、(15)表示接駁車輛到達需求點i的時間約束。

3 模型求解

本文研究的基于混合車型的靈活型接駁公交路徑協同優化模型帶有乘客滿意度的時間窗約束，屬于典型的帶有時間窗約束的開放式車輛路徑問題(vehicle routing problem，VRP)。車輛路徑問題的求解方法可分為精確算法和啟發式算法，精確算法包括分支定界法和列生成法等，啟發式算法包括蟻群算法、模擬退火算法和遺傳算法等。

蟻群算法是一種基于種群的進化算法，具有很強的發現較好解的能力和魯棒性，易于與多種啟發式算法結合，在解決一些小規模的旅行商問題(travelling salesman problem，TSP)時表現較好，但隨著問題規模的增大，難以在可接受的循環次數內找到最優解。模擬退火算法能夠以較大概率求得較優解，具有較強的魯棒性、全局收斂性以及隱含并行性，通用性強，易于實現，但是該算法缺乏歷史搜索信息，每次能保留一個解，對整個搜索空間的搜索能力不強。遺傳算法提供了一種求解非線性、多模型、多目標等復雜系統優化問題的通用框架，具有較強的全局搜索能力和隱含并行搜索特性，按照一定概率的變遷規則來指導搜索方向，具有較強的自組織和自適應的能力，是一種實用、高效、魯棒性強的優化技術。因此，本文利用遺傳算法求解該路徑優化模型。

3.1 染色體編碼及種群初始化

本文采用自然數編碼策略求解車輛調度模型，將染色體編碼成長度為n+k+1的個體，1，2，3，…，n為各需求點的編號，n+1～n+k為k輛接駁公交的編號。由于需求點位置在車輛出發前已確定，對車輛進行編碼，0代表不使用，1代表使用。個體向量的第1個分量代表第1輛車服務的第1個乘客，接著尋找滿足時間窗和車容量約束的乘客加入到當前路徑中，直至不滿足約束條件時停止，最終得到該車輛的行駛路徑。例如，若確定車輛1、4、7投入使用，基于車輛編碼結果確定乘客編碼，對于乘客1隨機生成1～3的數字。若輸出數字2，表示車輛4對乘客1進行服務。

本文采取隨機排列策略生成初始種群，以保證種群多樣性的最大化，將所有乘客的出行需求隨機排列，形成初始個體向量并設置種群規模。

3.2 適應度函數

3.2.1 統一求解方向

該模型的優化目標包括最小化企業運營成本和最大化乘客滿意度兩部分，屬于是多目標問題優化，由于目標函數求解方向不同，需要統一求解方向，將乘客滿意度極大值轉換為不滿意度極小值進行求解。

minZ3=min(1-fsat)。

(16)

3.2.2 歸一化處理

因企業運營成本和乘客滿意度量綱不同，且乘客滿意度取值范圍為0～1，需對運營成本進行歸一化處理，處理結果為：

G*=Gm/Gmax，

(17)

H*=Hm/Hmax，

(18)

其中，G*和H*分別表示未歸一化后的車輛損耗成本和油耗成本，Gm和Hm分別表示個體cm中實際的損耗成本和油耗成本，Gmax和Hmax分別表示當前種群個體中的損耗成本和油耗成本的最大值。

3.2.3 多目標函數處理

為將多目標優化模型轉變為單目標優化問題，可將目標函數變為求企業運營成本和平均乘客不滿意度之和的最小值。本文依據運營成本和乘客滿意度對系統的影響程度賦予不同的權重值，并且取兩者之和的倒數，構造適應度函數如式(19)所示。個體適應度函數值越大，表明其適應度越強。

g(cm)=1/[w1G*+w2H*+w3(1-fsat)]。

(20)

3.2.4 遺傳操作

基因選擇采用輪盤賭的方法，將各染色體適應度與所有染色體適應度和的比值作為該染色體的被選概率進行選擇。假設各染色體的被選概率為Pi，Si為染色體i隨機產生一個數，取值在0～1內。若Si

交叉操作采用多點交叉的方式，先隨機確定多個交叉位置，然后交換相應的子串，從而產生新的個體。

變異操作采用單點變異法，即遍歷種群中每個個體的編碼位置，每次產生一個隨機數τ。若τ小于變異概率，則對該位置進行變異操作；反之，則重新選擇變異位置。

4 案例分析

為驗證上述模型的有效性和可行性，構造一個小型網絡進行案例分析，該模型所需的已知條件如表2～4所示。表2中給出了一些常變量的輸入參數，車輛到達換乘站的時間窗約束范圍為主線公交出發前2 min。表3 列出了服務區域內各需求站點的乘客預約信息。以需求點1的乘客預約信息為例進行解釋，在需求點1共有2名乘客提出預約申請，他們的期望服務時間窗分別為9:03—9:05和9:23—9:25，可容忍服務時間窗分別為9:00—9:10和9:18—9:30。表4列出了服務區域內換乘站與需求點以及各需求點之間的出行時間矩陣，其中編號1～15為需求點，編號0為換乘站，各站點間的平均出行時間為在實際路網中的最短距離與車輛平均行駛速度的比值。

表2 案例中的常變量

表3 各需求點的預約信息統計表

表4 案例網絡的旅行時間矩陣

運用建立的路徑優化模型和設計的遺傳算法，通過PYTHON軟件編程對該案例進行求解，同時對比單純使用8座車型和15座車型的輸出結果進行分析，如表5所示。

表5 接駁公交行駛路線表

表5的結果表明，算例1使用了4輛車，包括3輛8座車和1輛15座車，算例2使用了5輛8座車，算例3使用了4輛15座車，其中算例1的最優適應度值最高為1.086 7。通過對比可發現，綜合考慮企業運營成本最低和平均乘客滿意度最高，同樣的出行需求下，混合車型的路徑規劃結果更優，其供需匹配更為合理。采用混合車型路徑優化方案與僅使用單一車型相比，其優勢在于：在不超出車容量和線路長度的前提下，乘客出行需求少且距離換乘站遠的需求點宜使用運營成本低的小型接駁車輛，乘客出行需求多且位置分布較集中的需求點宜使用可服務更多乘客的大容量接駁車輛，從而達到系統最優的效果。

4 結論

本文探討了靈活型接駁公交的路徑優化問題，重點考慮混合車型聯合調度對接駁車輛路徑優化的影響，以企業運營成本最小和乘客滿意度最大為優化目標，兼顧路徑規劃和車輛協調調度，建立了基于混合車型的靈活型接駁公交路徑協同優化模型，同時設計了遺傳算法求解模型。算例結果表明，該模型適用于采用多車型的靈活型接駁公交系統，能在合理時間內求解出車輛調度方案和最優行駛路徑，具有一定的實際運用價值。本文建立的模型適用于小規模的主線公交換乘點的接駁公交線路設計及調度方案優化，作為一類典型的NP-hard問題，當乘客需求數較大時，算法的運算效率有待提高，后續需要進一步設計算法，提高實時在線的計算速度。