可變線路式公交運(yùn)行服務(wù)能力優(yōu)化策略

鄭 樂， 高良鵬， 沈金星， 李文權(quán)

(1. 南京郵電大學(xué) 現(xiàn)代郵政學(xué)院，南京 210003；2. 福建工程學(xué)院 交通運(yùn)輸學(xué)院， 福州 350108；3. 河海大學(xué) 土木與交通學(xué)院，南京 210098；4. 東南大學(xué) 交通學(xué)院， 南京 210089)

近年來，隨著城市化進(jìn)程的加快，越來越多的城市新區(qū)逐步形成。這些地區(qū)由于尚未形成穩(wěn)定的客流走廊，其公交系統(tǒng)在成本效益和服務(wù)水平兩方面難以達(dá)到合理平衡。傳統(tǒng)的常規(guī)公交系統(tǒng)由于運(yùn)營線路固定且發(fā)車頻率較低，導(dǎo)致乘客的等車時(shí)間以及步行時(shí)間較長，因此運(yùn)營效率低下。需求響應(yīng)式公交[1]沒有嚴(yán)格的站點(diǎn)、線路及時(shí)刻表，可以為乘客提供門到門的出行服務(wù)，但運(yùn)營費(fèi)用高昂，通常僅局限于針對老年人和殘疾人的特殊公交服務(wù)。

靈活式公交融合了常規(guī)公交的高成本效益以及需求響應(yīng)式公交的靈活性，在北美的很多低人口密度區(qū)域應(yīng)用廣泛。文獻(xiàn)[2-3]的調(diào)查研究表明，可變線路式公交是目前使用最為廣泛的一種靈活式公交運(yùn)營方式。國外的實(shí)際運(yùn)營表明，可變線路式公交相比于需求響應(yīng)式公交更為經(jīng)濟(jì)高效[4]，相比于比常規(guī)公交乘客滿意度更高[5]。

到目前為止，可變線路式公交的研究大多集中在對其系統(tǒng)參數(shù)的設(shè)計(jì)及調(diào)度算法研究方面。文獻(xiàn)[6]對可變線路式公交沿基準(zhǔn)線路運(yùn)行速度的上下界進(jìn)行了評估。文獻(xiàn)[7-8]分別針對靜態(tài)預(yù)約需求和動(dòng)態(tài)實(shí)時(shí)需求了評估，分別提出了相應(yīng)的可變線路式公交調(diào)度算法。文獻(xiàn)[9]分析了可變線路式公交車運(yùn)行周期與服務(wù)區(qū)域的長、寬之間的關(guān)系。文獻(xiàn)[10]利用概率近似理論對可變線路式公交最優(yōu)服務(wù)周期進(jìn)行了估計(jì)。文獻(xiàn)[11]針對可變線路公交設(shè)計(jì)了一種可以同時(shí)處理靜態(tài)預(yù)約需求和實(shí)時(shí)動(dòng)態(tài)需求的兩階段車輛調(diào)度模型。文獻(xiàn)[12]考慮了可變線路式公交車型和車載容量的影響，構(gòu)建了多車型系統(tǒng)的優(yōu)化調(diào)度模型。

在以上研究以及可變線路式公交的實(shí)際運(yùn)行過程中，站點(diǎn)間額外分配用于服務(wù)乘客預(yù)約請求的松弛時(shí)間被視為定值，且乘客的上下車點(diǎn)必須為其所預(yù)約的位置。這些限制條件導(dǎo)致該服務(wù)在實(shí)際運(yùn)行過程中受乘客需求的波動(dòng)影響非常大[13]。當(dāng)松弛時(shí)間不足以滿足實(shí)際過高的乘客需求時(shí)，一些預(yù)約請求可能會(huì)被拒絕。而當(dāng)實(shí)際需求低于預(yù)期時(shí)，車內(nèi)乘客可能會(huì)在固定站點(diǎn)經(jīng)歷相當(dāng)長的空等時(shí)間。這兩種情況都會(huì)顯著降低可變線路式公交系統(tǒng)的服務(wù)水平，長此以往甚至?xí)?dǎo)致客流的流失。為了提高乘客需求波動(dòng)條件下系統(tǒng)的運(yùn)行服務(wù)能力，本文分別從時(shí)間以及空間維度出發(fā)，提出了可變線路式公交的動(dòng)態(tài)離站時(shí)間窗策略和待選站點(diǎn)策略。這兩種策略打破了原有運(yùn)行模式下的強(qiáng)制離站時(shí)間以及上下車位置的約束，可以在不影響服務(wù)周期且不增加任何運(yùn)營成本的情況下服務(wù)更多的乘客。

1 系統(tǒng)描述

1.1 服務(wù)區(qū)域及乘客分類

如圖1所示，假設(shè)可變線路式公交的服務(wù)區(qū)域?yàn)閷挾葹閃，長度為L的矩形。在服務(wù)區(qū)域內(nèi)有C個(gè)固定站點(diǎn)。每個(gè)服務(wù)班次，車輛從一個(gè)首末站出發(fā)，經(jīng)過所有的固定站點(diǎn)及可服務(wù)的預(yù)約站點(diǎn)，到達(dá)另一個(gè)首末站結(jié)束。每個(gè)固定站點(diǎn)都設(shè)有自身的固定離站時(shí)間。

圖1 可變線路式公交示意

根據(jù)乘客的上下車的位置是否在固定站點(diǎn)，乘客可分為4種類型：1)上車點(diǎn)和下車點(diǎn)都在固定站點(diǎn)，即第1類乘客；2)上車點(diǎn)在固定站點(diǎn)，下車點(diǎn)不在固定站點(diǎn)，即第2類乘客；3)上車點(diǎn)不在固定站點(diǎn)，下車點(diǎn)在固定站點(diǎn)，即第3類乘客；4)上車點(diǎn)和下車點(diǎn)都不在固定站點(diǎn)，即第4類乘客。每類乘客所占比例分別為η1，η2，η3，η4。

第1類乘客無需提前預(yù)定，在固定站點(diǎn)候車即可，視為常規(guī)乘客。其他3類乘客為需求響應(yīng)型乘客，出行前需要通過電話或網(wǎng)絡(luò)進(jìn)行預(yù)約。相鄰固定站點(diǎn)之間都分配有一定的松弛時(shí)間以服務(wù)需求響應(yīng)型乘客的需求，其值等于相鄰固定站點(diǎn)間時(shí)刻表所分配的運(yùn)行時(shí)間減去沿基準(zhǔn)線路的直接行駛時(shí)間。松弛時(shí)間的大小通常根據(jù)乘客的預(yù)期需求水平來確定，在松弛時(shí)間的限制范圍內(nèi)，服務(wù)車輛允許偏離基準(zhǔn)線路去接送預(yù)約的需求響應(yīng)型乘客。

1.2 運(yùn)行服務(wù)能力優(yōu)化策略

可變線路式公交的運(yùn)行服務(wù)能力定義為在一個(gè)運(yùn)行班次中服務(wù)乘客預(yù)約需求的能力，主要的衡量指標(biāo)是乘客預(yù)約需求被拒絕的比例。在實(shí)際運(yùn)行過程中，如何更加充分地利用站點(diǎn)間的松弛時(shí)間，減小由于乘客需求不確定性導(dǎo)致的部分乘客被拒絕現(xiàn)象，是當(dāng)前亟待解決的問題[14]。針對該問題，本節(jié)提出了動(dòng)態(tài)離站時(shí)間窗策略以及待選站點(diǎn)策略，兩種策略分別從時(shí)間以及空間維度出發(fā)，對原有的約束進(jìn)行了松弛，從而增加站點(diǎn)間松弛時(shí)間利用的靈活性。

1.2.1 動(dòng)態(tài)離站時(shí)間窗策略

動(dòng)態(tài)離站時(shí)間窗策略對固定站點(diǎn)的離站時(shí)間約束進(jìn)行了松弛，允許車輛在一定的時(shí)間窗范圍內(nèi)都可以離站。具體而言，假設(shè)車輛到達(dá)固定站點(diǎn)i的時(shí)間為t_arri，停站時(shí)間為t0，該站點(diǎn)的計(jì)劃離站時(shí)間為t_sdi。動(dòng)態(tài)離站時(shí)間窗策略放寬了在t_sdi時(shí)刻離站的約束，允許車輛在時(shí)間窗[t_sdi,t_sdi+ε]內(nèi)都可以離站。車輛的實(shí)際離站時(shí)間t_depi可根據(jù)下式進(jìn)行確定：

(1)

動(dòng)態(tài)離站時(shí)間窗策略通過動(dòng)態(tài)重新分配站點(diǎn)間的松弛時(shí)間，可以達(dá)到減少拒絕乘客數(shù)量以及車輛空等時(shí)間的目的。但同時(shí)也存在一定負(fù)面影響，如在固定站點(diǎn)等待上車的乘客可能會(huì)因?yàn)榈秸緯r(shí)間延誤而等待更長時(shí)間。此外在固定站點(diǎn)下車乘客的乘車時(shí)間也可能會(huì)被相應(yīng)地延長。在低出行密度區(qū)域，乘客相對更容易接受一個(gè)較小范圍內(nèi)的到站時(shí)間延誤，尤其是當(dāng)乘客被提前告知車輛的離站時(shí)間范圍以后。例如，若原先固定站點(diǎn)的計(jì)劃離站時(shí)間為t_sdi，當(dāng)分配2 min的時(shí)間窗寬度后，該站點(diǎn)等候的乘客知道車輛一定會(huì)在[t_sdi,t_sdi+2 min]內(nèi)離站，因此他們只需像往常一樣在t_sdi之前到達(dá)該站點(diǎn)，并經(jīng)歷至多2 min的等待時(shí)間。

1.2.2 待選站點(diǎn)策略

待選站點(diǎn)策略對乘客預(yù)約的上下車站點(diǎn)約束進(jìn)行了松弛。如圖2所示，實(shí)際應(yīng)用時(shí)運(yùn)營商需要提前在服務(wù)區(qū)域內(nèi)布設(shè)一定數(shù)量的待選站點(diǎn)，待選站點(diǎn)通常布設(shè)在方便車輛?？恳约八境讼嗷プR別的位置。乘客在預(yù)約時(shí)除了需要提供其理想的上下車點(diǎn)之外(預(yù)約站點(diǎn))，還需要提供其可接受步行距離。調(diào)度中心會(huì)根據(jù)每個(gè)班次的實(shí)際乘客需求規(guī)劃車輛的行車計(jì)劃。對乘客而言，實(shí)際的上下車點(diǎn)的位置既可能是其預(yù)約站點(diǎn)，也可能是其可接受步行范圍內(nèi)的待選站點(diǎn)。當(dāng)乘客接受到調(diào)度中心反饋的上下車點(diǎn)信息后，步行至相應(yīng)的待選站點(diǎn)即可。

待選站點(diǎn)策略的引入不僅可以將部分乘客分配到待選站點(diǎn)以減少車輛的繞行距離[15]，還可以在實(shí)際需求過高時(shí)，令多名乘客可以在同一待選站點(diǎn)上下車，從而減少車輛的停站次數(shù)，節(jié)省由于車輛加減速以及上下客所消耗的時(shí)間。待選站點(diǎn)策略通過動(dòng)態(tài)調(diào)整乘客的實(shí)際上下車點(diǎn)以降低需求波動(dòng)的影響，其代價(jià)是部分乘客需要步行少量的距離。

圖2 可變線路式公交待選站點(diǎn)策略示意

1.3 運(yùn)行方式及優(yōu)化目標(biāo)

如圖3所示，系統(tǒng)在處理接收到的預(yù)約請求時(shí)，會(huì)執(zhí)行一個(gè)兩階段的處理過程。在第1階段，當(dāng)調(diào)度中心接受到乘客的需求后，會(huì)立即反饋該乘客是否能被該班次服務(wù)，該判斷綜合考慮了在時(shí)間窗范圍內(nèi)車輛的延誤到達(dá)以及將部分乘客上下車點(diǎn)分配到待選站點(diǎn)的可能。為體現(xiàn)公平性，在第1階段采取先到先服務(wù)的原則，即較早預(yù)定的乘客被拒絕的可能性更低。

在預(yù)約截止時(shí)間之后，調(diào)度中心會(huì)對所有能夠被服務(wù)乘客的需求進(jìn)行全局優(yōu)化(第2階段)。該階段的主要任務(wù)是在能夠滿足所有乘客需求的基礎(chǔ)上，以最小化所有乘客的總出行時(shí)間(步行時(shí)間+等待時(shí)間+車內(nèi)時(shí)間)為目標(biāo)，生成車輛最優(yōu)的行車計(jì)劃方案。

該兩階段反饋過程可以視為一個(gè)字典序的兩階段的優(yōu)化問題，其首要目標(biāo)是盡可能多地滿足更多的乘客預(yù)約需求，次要目標(biāo)是最小化被接受乘客的總出行時(shí)間。

圖3 優(yōu)化策略應(yīng)用下的系統(tǒng)運(yùn)行方式示意圖

2 模型構(gòu)建

針對上述兩階段的優(yōu)化問題，本文采用混合整數(shù)規(guī)劃模型進(jìn)行建模，第1階段用于判斷乘客的預(yù)約能否被接受，第2階段用于構(gòu)建車輛的最優(yōu)行車計(jì)劃。這兩個(gè)階段的優(yōu)化問題除目標(biāo)函數(shù)不同外，模型結(jié)構(gòu)幾乎完全相同。因此，本節(jié)只討論所有被接受的乘客已確定后的最優(yōu)車輛路徑規(guī)劃問題。

對于任意預(yù)約站點(diǎn)i，定義站點(diǎn)群Si=Mi∪{i}用于表示所有可行的乘客上下車點(diǎn)。其中，Mi為預(yù)約站點(diǎn)i可接受步行距離內(nèi)的所有待選站點(diǎn)集合。定義有向圖G=(N,A,T)來表示車輛的路徑規(guī)劃網(wǎng)絡(luò)，其中N表示所有的可選站點(diǎn)集合，A=N2表示所有可選站點(diǎn)所構(gòu)成的邊集，T=(tij)為每條邊所對應(yīng)的車輛行程時(shí)間集合，可通過站點(diǎn)間距離以及車輛的平時(shí)行駛速度計(jì)算得到。該問題的目標(biāo)可以總結(jié)為：在不違反固定站點(diǎn)離站時(shí)間窗約束的條件下，確定一條通過所有站點(diǎn)群，且每個(gè)站點(diǎn)群只訪問其中一個(gè)站點(diǎn)的最優(yōu)路徑。

2.1 模型參數(shù)

模型中的參數(shù)定義如下：C為固定站點(diǎn)的數(shù)量；N0為固定站點(diǎn)集合，N0={1,2,…,C}；K為所有被接受的乘客需求集合，K=K1∪K2∪K3∪K4，其中K1～K4分別代表第1類到第4類被接受的乘客需求集合；TC為車輛需要訪問的站點(diǎn)總數(shù)，TC=C+|K2|+|K3|+2×|K4|；Nn為乘客預(yù)約的需求響應(yīng)型站點(diǎn)集合，Nn={C+1,…,TC}；MP為服務(wù)區(qū)域內(nèi)的待選站點(diǎn)集合；rMP為服務(wù)區(qū)域內(nèi)的待選站點(diǎn)總數(shù)，rMP=|MP|；Si為需求響應(yīng)型站點(diǎn)i所對應(yīng)的站點(diǎn)群；N為所有的可選站點(diǎn)集合，N=S1∪S2…STC，其中S1={ 1 }，…，SC={C}；r為所有可選站點(diǎn)總數(shù)，r=|N|；A為所有可選站點(diǎn)所構(gòu)成的邊集；t_sdi為固定站點(diǎn)i的計(jì)劃離站時(shí)間，?i∈N0；t_wki為站點(diǎn)i步行至對應(yīng)預(yù)約站點(diǎn)的時(shí)間，?i∈N；tij為站點(diǎn)i至站點(diǎn)j的車輛行駛時(shí)間，?i,j∈N；tn為車輛在需求響應(yīng)型站點(diǎn)的停站時(shí)間；t0為車輛在固定站點(diǎn)的停站時(shí)間；ps(k)為需求k所對應(yīng)的上車點(diǎn)；ds(k)為需求k所對應(yīng)的下車點(diǎn)；Dwalking為預(yù)約乘客的可接受步行距離；ε為固定站點(diǎn)的離站時(shí)間窗寬度。

模型中所有的決策變量定義如下：xij為0或1，若最優(yōu)路徑包含路段(i,j)，則為1，否則為0；yi為0或1，若最優(yōu)行駛路徑經(jīng)過站點(diǎn)i，則為1，否則為0；t_depi為站點(diǎn)群Si中所選站點(diǎn)的離站時(shí)間；t_arri為站點(diǎn)群Si中所選站點(diǎn)的到站時(shí)間；pk為需求k所對應(yīng)的上車時(shí)間；dk為需求k所對應(yīng)的下車時(shí)間。

2.2 模型建立

基于以上參數(shù)定義，該路徑優(yōu)化問題可以用以下的混合整數(shù)規(guī)劃模型來表示，其中ωVH，ωWK，ωWT分別為車內(nèi)時(shí)間、步行時(shí)間以及等待時(shí)間的權(quán)重。

(2)

s.t.:

(3)

(4)

(5)

(6)

xii=0，?i∈N

(7)

(8)

其中V?N,且滿足與至少1個(gè)至多TC-1個(gè)站點(diǎn)群的交集為空。

t_sdi≤t_depi≤t_sdi+ε，?i∈N0

(9)

i,j=1,2,…,TC

(10)

t_depi=t_arri+tn，i=C+1,…,TC

(11)

t_depi≥t_arri+t0， ?i∈N0/{1}

(12)

pk=t_depps(k)，?k∈K

(13)

dk=t_arrds(k)，?k∈K

(14)

dk>pk， ?k∈K

(15)

式(2)為目標(biāo)函數(shù)，優(yōu)化目標(biāo)是乘客的總出行時(shí)間Z最小，包括乘客的車內(nèi)時(shí)間、步行時(shí)間以及由于車輛延誤到達(dá)造成的第1及第2類乘客的等待時(shí)間。約束(3)表示對于任意一個(gè)站點(diǎn)群而言，車輛有且僅可以訪問其中的一個(gè)站點(diǎn)。約束(4)和(5)對首末站的特殊情形進(jìn)行了討論，對于首發(fā)站而言，入度為0，出度為1；對于終點(diǎn)站而言，入度為1，出度為0。對于除首末站外的任意一個(gè)中間站點(diǎn)，約束(6)確保了若站點(diǎn)為對應(yīng)站點(diǎn)群中的所選站點(diǎn)，其入度和出度均為1；否則，其入度和出度均為0。約束(7)保證了所有站點(diǎn)不會(huì)存在自連接的情況。約束(8)確保了在車輛路徑中不會(huì)出現(xiàn)回路的情況。約束(9)保證了車輛在固定站點(diǎn)的離站時(shí)間必須在離站時(shí)間窗的范圍內(nèi)。約束(10)為模型的核心約束，表示若兩個(gè)站點(diǎn)群之間存在連接(即先后被車輛服務(wù))，站點(diǎn)群j中所選站點(diǎn)的到達(dá)時(shí)間不會(huì)早于站點(diǎn)群i中所選站點(diǎn)的離站時(shí)間加上在兩個(gè)站點(diǎn)之間的行駛時(shí)間，當(dāng)兩個(gè)站點(diǎn)群之間不存在連接時(shí)，采用大M法令此約束無效。約束(11)保證了站點(diǎn)的離站時(shí)間等于車輛到達(dá)該站點(diǎn)的時(shí)間加上停站服務(wù)時(shí)間。由于車輛在固定站點(diǎn)可能存在部分空等時(shí)間，因此約束(12)保證了車輛在固定站點(diǎn)的離站時(shí)間要晚于車輛的到達(dá)該站點(diǎn)時(shí)間加上在停站服務(wù)時(shí)間。約束(13)為每個(gè)乘客需求的上車時(shí)間與其對應(yīng)站點(diǎn)的車輛離站時(shí)間之間建立了等式關(guān)系。同理，約束(14)為每個(gè)乘客需求的下車時(shí)間與其對應(yīng)站點(diǎn)的車輛到站時(shí)間之間建立了等式關(guān)系。約束(15)保證了乘客的下車時(shí)間要晚于其上車時(shí)間。

3 模型求解

上述問題可以看作是一類帶有時(shí)間窗約束的廣義旅行商問題(GTSP)，該問題是公認(rèn)的NP-hard問題。在問題規(guī)模較小的情況下，可以采用分支定界法或者割平面法等精確算法進(jìn)行求解[16]，但其求解復(fù)雜度會(huì)隨著問題規(guī)模的增大呈指數(shù)方式增長。本文所提的兩階段反饋過程都對求解時(shí)間有著較為嚴(yán)格的要求，因此精確算法難以適用。

鑒于此，采用文化基因算法對該模型進(jìn)行求解[17]。文化基因算法是一種混合型算法，該算法結(jié)合了遺傳算法和局部搜索算法的優(yōu)點(diǎn)，能夠在合理的計(jì)算時(shí)間內(nèi)得到高質(zhì)量的近似最優(yōu)解。具體的算法流程如圖4所示。

圖4 文化基因算法流程

3.1 染色體編碼

本文采用自然排列編碼的方式對車輛的行駛路徑進(jìn)行染色體編碼，染色體的生成必須滿足以下兩個(gè)條件：1)每個(gè)站點(diǎn)群只能選擇一個(gè)站點(diǎn)納入到染色體中；2)染色體的第一個(gè)和最后一個(gè)元素必須對應(yīng)可變線路式公交的首末站。

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

適應(yīng)度值由兩部分構(gòu)成，第1部分與混合整數(shù)規(guī)劃模型的目標(biāo)函數(shù)值相同，第2部分為懲罰值，用于表征可行解對固定站點(diǎn)的離站時(shí)間窗約束的遵守情況，可通過式(16)和式(17)計(jì)算得到。

(16)

(17)

其中：λ1為用于衡量超出離站時(shí)間窗上界部分的懲罰系數(shù)，λ2為固定懲罰系數(shù)。

對于第1階段的乘客預(yù)約請求的處理，可以通過查看最優(yōu)解是否存在懲罰值來判斷該需求能否得到滿足。如果懲罰值等于0，則該預(yù)約需求可以被服務(wù)；否則，拒絕該請求。

3.3 初始種群生成

初始種群由于包含了構(gòu)造最優(yōu)解所需的大部分信息，因此對于算法的性能影響極大。本研究中，初始種群的染色體數(shù)量設(shè)置為5TC。對于每條染色體，其初始點(diǎn)P1設(shè)為可變線路式公交的第1個(gè)固定站點(diǎn)。對于其后任意一個(gè)站點(diǎn)Pk，k∈{2,…,TC-1}，首先對其所在站點(diǎn)群進(jìn)行選擇，每個(gè)站點(diǎn)群被選擇的概率與其距離前一個(gè)站點(diǎn)的距離成反比(選擇乘客預(yù)約站點(diǎn)作為該站點(diǎn)群的代表用于計(jì)算距離)，然后再從該站點(diǎn)群中隨機(jī)選擇一個(gè)站點(diǎn)放入該條染色體中。染色中的最后一個(gè)點(diǎn)PTC設(shè)置為可變線路式公交的最后一個(gè)固定站點(diǎn)。

3.4 遺傳操作

在本研究中，40%的種群直接通過從上一代種群中選擇得到，40%的種群通過交叉產(chǎn)生，剩下的20%通過變異產(chǎn)生。這些遺傳操作的具體描述為：1)選擇操作，采用精英策略，將上一代種群中適應(yīng)度較高的一部分個(gè)體作為父代染色體；2)交叉操作，采用PMX交叉方法，通過交換父代部分染色體信息從而生成兩個(gè)子代染色體，隨機(jī)生成交換起點(diǎn)位置a以及交換長度l，最終染色體交換位置的區(qū)間可以表示為[a,a+l]；3)變異操作，作用于單個(gè)染色體，隨機(jī)將染色體的一部分移除，然后再將移除部分插入到剩余部分中的任意隨機(jī)位置中。移除部分的長度從2到TC/2不等。

3.5 局部搜索

遺傳算法是對種群進(jìn)行全局廣域搜索，而局部搜索是對種群中的個(gè)體進(jìn)行局部深度搜索，從而提高單個(gè)染色體的適應(yīng)度值。每當(dāng)生成一個(gè)新的染色體(初始種群或通過交叉、變異操作產(chǎn)生)，都會(huì)先后執(zhí)行 “插入”和“k鄰域交換”操作以提高單個(gè)染色體的質(zhì)量。

1)插入操作。首先將染色體中站點(diǎn)群Si對應(yīng)的節(jié)點(diǎn)刪除，然后通過枚舉的方式嘗試站點(diǎn)群Si中所有的站點(diǎn)和插入位置的組合，最后將適應(yīng)度值提高最多的新染色替換原來的染色體。對于每條染色體，共執(zhí)行TC-C次插入操作，以保證所有的待選站點(diǎn)在局部優(yōu)化時(shí)都得到了考慮。

2)k鄰域交換操作。首先選擇染色體中k個(gè)相鄰的節(jié)點(diǎn)，然后對這k個(gè)節(jié)點(diǎn)對應(yīng)站點(diǎn)群所有可能的全排列進(jìn)行逐個(gè)嘗試，最后將適應(yīng)度值最低的染色體替換當(dāng)前染色體。對于每條染色體，算法會(huì)隨機(jī)遍歷所有k個(gè)相鄰的節(jié)點(diǎn)的組合。為保證算法的精度，本文研究采用4鄰域交換操作。

3.6 終止條件

當(dāng)達(dá)到迭代次數(shù)Imax或者連續(xù)Idlemax次迭代最優(yōu)解的適應(yīng)度值未發(fā)生改變時(shí)，算法終止。終止條件可以根據(jù)具體問題的規(guī)模來設(shè)定，本研究中終止條件參數(shù)設(shè)置為Imax=30，Idlemax=5。

4 結(jié)果分析

4.1 系統(tǒng)參數(shù)設(shè)置

以美國洛杉磯646路公交為例進(jìn)行仿真案例研究。646路公交是一個(gè)典型的可變線路式公交系統(tǒng)并廣泛被國內(nèi)外學(xué)者用作案例分析[6-8,11,14]，其具體公交線路圖可參考文獻(xiàn)[18]。研究假設(shè)所有乘客的預(yù)約站點(diǎn)以及待選站點(diǎn)在服務(wù)區(qū)域內(nèi)服從均勻分布；公交車輛行駛規(guī)則采用方格路網(wǎng)，即先沿X方向行駛，再沿Y方向到達(dá)停靠點(diǎn)[19]。站點(diǎn)間的行駛時(shí)間以及乘客的步行時(shí)間可以通過車輛的平均行駛速度Vb以及乘客平均步行速度Vwk計(jì)算得到。

系統(tǒng)的參數(shù)取值設(shè)定如下：服務(wù)區(qū)域的長度L=16 km，寬度W=1.6 km；基準(zhǔn)線路上設(shè)有3個(gè)固定站點(diǎn)(C=3)；服務(wù)區(qū)域內(nèi)的待選站點(diǎn)總數(shù)rMP=80；乘客的可接受步行距離Dwalking=0.48 km；車輛的平均行駛速度Vb=40 km/h；乘客的平均步行速度Vwk=4.8 km/h；車輛在固定站點(diǎn)的停站時(shí)間t0=1 min；車輛在需求響應(yīng)型站點(diǎn)的停站時(shí)間tn=0.3 min；4類出行乘客比例設(shè)為η1=0.1，η2=0.4，η3=0.4，η4=0.1；懲罰系數(shù)λ1=10，λ2=50；車內(nèi)時(shí)間、步行時(shí)間以及等待時(shí)間的權(quán)重設(shè)為ωVH=ωWK=ωWT=1；固定站點(diǎn)的離站時(shí)間窗寬度ε=2 min；系統(tǒng)的預(yù)期乘客需求δ=12人/班次，根據(jù)文獻(xiàn)[20]所提出的理論模型，可以得到單程運(yùn)行時(shí)間Tr=40 min。

4.2 算法對比

為了驗(yàn)證所采用的啟發(fā)式算法的有效性，本文對比了不同乘客需求下文化基因算法以及采用CPLEX求解MIP模型的計(jì)算結(jié)果。對比指標(biāo)包括3項(xiàng)：1)第1階段系統(tǒng)最多能服務(wù)的乘客數(shù)量；2)第2階段系統(tǒng)的目標(biāo)函數(shù)值；3)算法的計(jì)算時(shí)間。由于可變線路式公交通常服務(wù)于低人口密度區(qū)域，因此假設(shè)乘客需求不超過25人/班次。從表1可以看出，采用CPLEX求解的計(jì)算時(shí)間隨著乘客需求的增加呈指數(shù)方式增長。當(dāng)乘客需求為25人/班次時(shí)，需要10 h以上的計(jì)算時(shí)間。因此，采用精確算法進(jìn)行求解難以滿足可變線路式公交在實(shí)際運(yùn)行中實(shí)時(shí)性的要求。相比之下，除了乘客需求為25人/班次之外，文化基因算法在所有需求場景下的計(jì)算結(jié)果都與最優(yōu)解相同，且計(jì)算時(shí)間相較精確算法大幅度縮短。這表明該啟發(fā)式算法無論在求解質(zhì)量還是計(jì)算時(shí)間方面都具有較好的性能，能夠滿足實(shí)際應(yīng)用的需要。因此，后續(xù)的仿真計(jì)算均采用文化基因算法進(jìn)行求解。

表1 文化基因算法與CPLEX計(jì)算結(jié)果對比

4.3 優(yōu)化策略的影響分析

本文通過仿真對比了4類運(yùn)行模式下的系統(tǒng)性能。分別為：1)傳統(tǒng)的可變線路式公交系統(tǒng)(下文中稱為Flex)；2)動(dòng)態(tài)離站時(shí)間窗策略下的系統(tǒng)(下文中稱為Flex-slack)；3)待選站點(diǎn)策略下的系統(tǒng)(下文中稱為Flex-MP)；4)兩種策略同時(shí)應(yīng)用下的系統(tǒng)(下文中稱為Flex-slack-MP)。為模擬實(shí)際運(yùn)行中乘客需求的波動(dòng)性，對不同乘客需求水平下的場景進(jìn)行仿真。對于每個(gè)場景，共進(jìn)行100個(gè)運(yùn)行班次的仿真以保證結(jié)果的可靠性。

系統(tǒng)性能的評估指標(biāo)包括：1)拒絕率Rej，即乘客預(yù)約請求被系統(tǒng)拒絕的比例；2)乘車時(shí)間RD，即乘客的平均乘車時(shí)間，包括車輛行駛時(shí)間以及站點(diǎn)的服務(wù)時(shí)間；3)空等時(shí)間ID，即車輛提前到達(dá)固定站點(diǎn)時(shí)，車上乘客在固定站點(diǎn)的平均等候時(shí)間；4)等車時(shí)間WT，即由于車輛延誤到達(dá)，乘客在固定站點(diǎn)的平均等待時(shí)間；5)步行時(shí)間WK，即乘客從出發(fā)點(diǎn)步行至待選站點(diǎn)以及從待選站點(diǎn)步行至目的地的平均步行時(shí)間。

圖5為不同需求水平下的拒絕率的變化趨勢。可以看出隨著實(shí)際出行需求的增加，傳統(tǒng)的可變線路式公交拒絕率增長迅速。動(dòng)態(tài)離站時(shí)間窗策略以及待選站點(diǎn)策略分別在時(shí)間和空間維度增加了車輛路徑規(guī)劃的靈活性，能夠顯著的降低系統(tǒng)的拒絕率。當(dāng)實(shí)際乘客需求較高時(shí)，由于待選站點(diǎn)策略可以通過將兩個(gè)甚至多個(gè)需求匹配到同一個(gè)站點(diǎn)完成上下車，因此對于拒絕率降低效果更為明顯。圖6為不同需求水平下Flex-MP運(yùn)行模式待選站點(diǎn)的使用情況，可以看出隨著乘客需求的增加，待選站點(diǎn)的使用比例以及多個(gè)需求匹配在同一站點(diǎn)的比例都會(huì)逐漸增加。

圖5 不同需求水平下的系統(tǒng)拒絕率

圖6 不同需求水平下待選站點(diǎn)需求匹配數(shù)量比例分布

Flex-slack-MP融合兩種策略的優(yōu)勢并在應(yīng)用過程中可以相互補(bǔ)充，因此在拒絕率控制方面相較于單一策略的使用效果更為顯著，從圖5可以看出，隨著實(shí)際乘客需求的增加，F(xiàn)lex-slack-MP系統(tǒng)對于拒絕率的抑制作用逐漸提升，至多可減少22%的系統(tǒng)的拒絕率。

圖7為不同需求水平下各類乘客出行時(shí)間的變化趨勢。隨著實(shí)際出行需求水平的增加，可以看出：1)在Flex-slack運(yùn)行模式下，乘客的乘車時(shí)間有所增加，但由于松弛時(shí)間利用率的提高，空等時(shí)間顯著減少，由于車輛存在晚于預(yù)計(jì)到達(dá)的情況，因此在固定站點(diǎn)候車乘客會(huì)存在少量等車時(shí)間；2)在Flex-MP運(yùn)行模式下，由于部分乘客需要步行至附近的待選站點(diǎn)完成上下車，因此存在一定的步行時(shí)間，并且平均步行時(shí)間會(huì)隨出行需求的增加而顯著增加；3)在Flex-slack-MP運(yùn)行模式下，部分乘客可能需要經(jīng)歷一定的等車時(shí)間及步行時(shí)間，當(dāng)乘客需求相對較少時(shí)，系統(tǒng)會(huì)優(yōu)先應(yīng)用離站時(shí)間窗策略來減少系統(tǒng)拒絕率，但隨著需求量的進(jìn)一步增加，待選站點(diǎn)策略應(yīng)用的比重會(huì)逐步增加。

圖7 不同需求水平下的乘客出行時(shí)間

總體而言，所提出的3種運(yùn)行模式能夠很好地提高需求不確定性下可變線路式公交的服務(wù)可靠性，減少乘客頻繁被拒絕以及在站點(diǎn)空等所造成的滿意度下降。盡管乘客的總出行時(shí)間會(huì)有所提高，但由于時(shí)間窗的寬度以及可接受的步行距離都存在上限，因此并不會(huì)造成單個(gè)乘客出行時(shí)間的大幅增加。就其適用環(huán)境而言，F(xiàn)lex-slack運(yùn)行模式適用于乘客對步行更加敏感而對車輛到站時(shí)間可靠性要求不高的情形，如步行環(huán)境較差，夜間環(huán)境等。而Flex-MP運(yùn)行模式更加適用于對到站時(shí)間可靠性關(guān)注度較高但能接受少量步行的情形，如需要在固定站點(diǎn)進(jìn)行換乘，步行環(huán)境較好等。Flex-slack-MP運(yùn)行模式則適用于乘客對步行以及到站時(shí)間可靠性均不敏感的情形。

4.4 靈敏度分析

本文對預(yù)期乘客需求下(δ=12人/班次)不同運(yùn)行模式的參數(shù)靈敏度進(jìn)行了分析。分析參數(shù)包括兩類：1)時(shí)間窗寬度ε；2)服務(wù)區(qū)域內(nèi)待選站點(diǎn)總數(shù)rMP。

從表2可以看出，在Flex-slack運(yùn)行模式下，隨著時(shí)間窗寬度ε的增加，系統(tǒng)的拒絕率從12.83%急劇下降至2.25%并呈現(xiàn)逐步放緩的趨勢，乘客的空等時(shí)間也有所減少。但與此同時(shí)，乘客的平均等待時(shí)間以及車內(nèi)乘客的乘車時(shí)間也有所提高。盡管時(shí)間窗寬度的增加能夠進(jìn)一步地增強(qiáng)路徑規(guī)劃的靈活性，但在實(shí)際應(yīng)用過程中，時(shí)間窗寬度的設(shè)置不宜過大，否則會(huì)降低車輛到站時(shí)間的穩(wěn)定性，造成客流流失。

在Flex-MP運(yùn)行模式下，隨著待選站點(diǎn)數(shù)量的增加，系統(tǒng)的拒絕率顯著降低，乘客的平均乘車時(shí)間以及空等時(shí)間也都有所減少。但由于待選站點(diǎn)使用比例的上升，乘客的平均步行時(shí)間也隨之增加。在實(shí)際應(yīng)用中，運(yùn)營商應(yīng)結(jié)合服務(wù)區(qū)域的實(shí)際土地利用特性以及路網(wǎng)條件盡可能多地布設(shè)更多的待選站點(diǎn)以增加路徑規(guī)劃的靈活性。

在Flex-slack-MP運(yùn)行模式下，拒絕率下降更為顯著，至多可將拒絕率降至0.33%。但同時(shí)乘客也不可避免地會(huì)經(jīng)歷一定的等待時(shí)間和步行時(shí)間。由于該種運(yùn)行模式能夠有效地抑制需求不確定性的影響，因此對于乘客需求時(shí)空波動(dòng)較大的區(qū)域應(yīng)優(yōu)先考慮實(shí)施。

表2 不同運(yùn)行優(yōu)化策略下的參數(shù)靈敏度分析

5 結(jié) 論

1)在當(dāng)前可變線路式公交運(yùn)行模式中，所有固定站點(diǎn)的離站時(shí)間是確定的，并且乘客的上下車點(diǎn)必須為其預(yù)約的位置，這種運(yùn)行模式在實(shí)際路徑規(guī)劃中由于缺乏一定的靈活性，在乘客需求波動(dòng)較大的情況下會(huì)造成乘客在固定站點(diǎn)空等以及部分乘客被拒絕的現(xiàn)象。針對此問題，分別從時(shí)間以及空間維度出發(fā)，提出了動(dòng)態(tài)離站時(shí)間窗策略和待選站點(diǎn)策略，用以提高乘客需求波動(dòng)情況下的可變線路式公交的運(yùn)行服務(wù)能力。并在此基礎(chǔ)上，建立了策略應(yīng)用背景下的兩階段混合整數(shù)規(guī)劃模型以及相應(yīng)的啟發(fā)式求解算法。

2)研究結(jié)果表明，這兩種策略的實(shí)施可以顯著地減少乘客被拒絕現(xiàn)象，使得松弛時(shí)間得到更加充分的利用，其代價(jià)是部分乘客可能需要經(jīng)歷少量的等待時(shí)間和步行時(shí)間。研究還發(fā)現(xiàn)，當(dāng)兩種策略聯(lián)合使用時(shí)能夠更好地控制系統(tǒng)的拒絕率，實(shí)現(xiàn)有效的互補(bǔ)。

3)在策略實(shí)際實(shí)施過程中，為了減少車輛的到站時(shí)間延誤以及步行至待選站點(diǎn)給乘客帶來的不便，運(yùn)營商可以開發(fā)具備顯示車輛實(shí)時(shí)位置以及步行導(dǎo)航功能的手機(jī)客戶端，以幫助用戶更快地適應(yīng)新策略的實(shí)施。另外，對于需要步行至待選站點(diǎn)的乘客，運(yùn)營商應(yīng)考慮在票價(jià)方面給予一定的補(bǔ)償以彌補(bǔ)其由于步行而產(chǎn)生的不便。最后，由于幾乎所有的靈活式公交服務(wù)都會(huì)受到站點(diǎn)間松弛時(shí)間以及乘客上下車位置的限制，因此所提出的動(dòng)態(tài)離站時(shí)間窗策略及待選站點(diǎn)策略除了可應(yīng)用于可變線路式公交之外，對于提升其他類型靈活式公交的運(yùn)行服務(wù)能力同樣可以發(fā)揮作用。