邵文，賈順平，曹文娟

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

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

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

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

1 研究問題描述

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

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

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

2 靈活型接駁公交路徑協(xié)同優(yōu)化模型

2.1 模型假設(shè)

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

(1)服務(wù)區(qū)域內(nèi)有1個換乘站點和n個需求響應(yīng)站點，各站點位置已知；

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

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

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

(5)服務(wù)區(qū)域內(nèi)不存在拒絕服務(wù)乘客的情況，所有有預(yù)約申請的乘客均被服務(wù)；

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

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

2.2 模型構(gòu)建

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

表1 模型參數(shù)

2.2.1 目標(biāo)函數(shù)

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

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

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

所以公交企業(yè)運營成本可表示為：

(1)

(2)最大化乘客滿意度

(2)

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

(3)

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

因此，乘客滿意度函數(shù)可整理如公式4所示，乘客滿意度最大的目標(biāo)函數(shù)如公式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)表示車上乘客數(shù)不超過p車型的額定載客量；式(9)表示調(diào)度過程中所使用的各車型車輛數(shù)不可超出換乘站總配備車輛數(shù)；式(10)表示車輛從換乘站點出發(fā)，最終返回原換乘站完成接駁服務(wù)；式(11)表示一次接駁服務(wù)行程中，每輛車不得超過最大允許行駛距離；式(12)表示需求點i乘客滿意度函數(shù)的軟時間窗約束；式(13)表示第k輛車返回?fù)Q乘站的乘客滿意度函數(shù)的硬時間窗約束；式(14)、(15)表示接駁車輛到達(dá)需求點i的時間約束。

3 模型求解

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

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

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

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

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

3.2 適應(yīng)度函數(shù)

3.2.1 統(tǒng)一求解方向

該模型的優(yōu)化目標(biāo)包括最小化企業(yè)運營成本和最大化乘客滿意度兩部分，屬于是多目標(biāo)問題優(yōu)化，由于目標(biāo)函數(shù)求解方向不同，需要統(tǒng)一求解方向，將乘客滿意度極大值轉(zhuǎn)換為不滿意度極小值進(jìn)行求解。

minZ3=min(1-fsat)。

(16)

3.2.2 歸一化處理

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

G*=Gm/Gmax，

(17)

H*=Hm/Hmax，

(18)

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

3.2.3 多目標(biāo)函數(shù)處理

為將多目標(biāo)優(yōu)化模型轉(zhuǎn)變?yōu)閱文繕?biāo)優(yōu)化問題，可將目標(biāo)函數(shù)變?yōu)榍笃髽I(yè)運營成本和平均乘客不滿意度之和的最小值。本文依據(jù)運營成本和乘客滿意度對系統(tǒng)的影響程度賦予不同的權(quán)重值，并且取兩者之和的倒數(shù)，構(gòu)造適應(yīng)度函數(shù)如式(19)所示。個體適應(yīng)度函數(shù)值越大，表明其適應(yīng)度越強。

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

(20)

3.2.4 遺傳操作

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

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

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

4 案例分析

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

表2 案例中的常變量

表3 各需求點的預(yù)約信息統(tǒng)計表

表4 案例網(wǎng)絡(luò)的旅行時間矩陣

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

表5 接駁公交行駛路線表

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

4 結(jié)論

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