賽事公交車輛路徑優(yōu)化研究
——以2022年北京冬奧為例

官云林，王 云，閆學(xué)東，郭浩楠

(北京交通大學(xué) a.交通運輸學(xué)院, b.綜合交通運輸大數(shù)據(jù)應(yīng)用技術(shù)交通運輸應(yīng)用技術(shù)交通運輸行業(yè)重點實驗室，北京 100044)

國際重大賽事活動會吸引百萬級游客和全球媒體的關(guān)注[1].在2012年倫敦奧運會期間，有1 000萬觀賽人群現(xiàn)場觀看了由29個比賽場館舉行的各類賽事項目，日高峰觀眾人數(shù)超過80萬[2].海量的國內(nèi)外觀賽人群在短短幾周的賽事活動期間內(nèi)聚集在舉辦城市中，隨之激增的觀賽出行需求加大了常規(guī)交通系統(tǒng)的服務(wù)壓力，導(dǎo)致出現(xiàn)道路交通安全隱患、出行服務(wù)水平低、賽事觀眾出行效率低等問題[3-5].

國內(nèi)外的許多學(xué)者從調(diào)整賽事舉辦城市的全域綜合交通系統(tǒng)規(guī)劃、限制日常交通出行、加強交通基礎(chǔ)設(shè)施建設(shè)等方面展開研究.Currie等[6]總結(jié)了2012倫敦奧運期間通過大規(guī)模的交通需求管理調(diào)整居民的日常交通出行方式，提出城市交通規(guī)劃管理策略以適應(yīng)賽事人群激增的出行需求.面對觀賽出行的壓力，Kassens-Noor[7]分析2024年波士頓奧運會交通規(guī)劃方案發(fā)現(xiàn)其計劃增加了決策成本，同時大量交通發(fā)展空間被壓縮.除了減少日常出行需求外，許多城市還將大型活動視為交通發(fā)展的巨大機遇.通過建設(shè)鐵路、高速公路、地鐵線路等增加交通資源以服務(wù)新增觀賽出行需求[8-9].北京市在籌備2008年奧運會期間，投資了超過200億美元用于交通相關(guān)項目，地鐵網(wǎng)絡(luò)從3線擴展到7線系統(tǒng)，其中包括機場專用鐵路[10].然而調(diào)整城市總體交通規(guī)劃對當(dāng)?shù)鼐用竦娜粘３鲂杏绊懢薮螅黾咏煌ɑA(chǔ)設(shè)施建設(shè)的時間和經(jīng)濟成本也極其高昂，同時上述方法難以適應(yīng)場館之間觀賽人群靈活的出行需求，提出補充場館間交通方式是十分有必要的.

考慮到2022年北京冬季奧運會是世界首次開展的多賽區(qū)多場館奧運會，會在北京城區(qū)、延慶、張家口賽區(qū)之間及內(nèi)部的場館間新增大量出行需求.本文作者提出以觀賽人群出行需求為導(dǎo)向的賽事公交服務(wù)來緩解常規(guī)交通系統(tǒng)壓力，并保證場館間交通出行效率和服務(wù)質(zhì)量.基于車輛路徑問題(Vehicle Routing Problem，VRP)[11-13]，著重考慮時間窗、載量約束，以運營車輛使用、開行成本最小為目標(biāo)構(gòu)建優(yōu)化模型，并通過兩種有效不等式和基于最優(yōu)時差插入法的遺傳算法實現(xiàn)不同規(guī)模算例的求解.

1 賽事公交車輛路徑優(yōu)化模型

基于帶時間窗和載量約束的車輛路徑問題(Vehicle Routing Problem with Pickup and Delivery and Time Window, VRPPDTW)構(gòu)建賽事公交車輛路徑優(yōu)化模型，具體問題假設(shè)條件如下：

1)每個出行需求接送客節(jié)點、乘客數(shù)量和時間窗信息已知.兩場賽事間出行乘客時間窗相同，且所包含的乘客數(shù)量小于賽事公交載客能力.

2)任意出行需求均需在時間窗內(nèi)有且僅被服務(wù)一次，且同一出行需求由一輛賽事公交完成接送服務(wù).

3)任意出行需求的接送客最大時間間隔均大于或等于賽事公交在對應(yīng)接送節(jié)點間開行時間.

4)車庫僅有一個且位置固定不變，所有賽事公交從車庫出發(fā)，最后返回車庫.

5)賽事公交車輛同質(zhì)，在時間窗約束和載量約束條件下可進行混合搭載.

設(shè)P={1,2，…,n}為接客點集合，D={n+1,n+2，…,2n}為送客點集合，接送客節(jié)點并非物理意義上的接送客站點，而是構(gòu)成出行需求的接送客節(jié)點，同時有A=P∪D.每個出行需求采用(i,n+i)表示，均由一個或多個時間窗相同、接送節(jié)點相同的觀賽人群在場館間的出行構(gòu)成.設(shè)K為賽事公交車輛集合.設(shè)0-1決策變量xi,j,k判斷賽事公交k是否經(jīng)過有向弧(i,j)，Ti,k和Li,k分別表示賽事公交k到達節(jié)點i的時間和服務(wù)后的載量狀態(tài).構(gòu)建賽事公交車輛路徑優(yōu)化模型為

(1)

(2)

(3)

(4)

?j∈A,?k∈K

(5)

?i∈P,?k∈K

(6)

ai≤Ti,k≤bi?i∈A,?k∈K

(7)

Ti,k+Si+ti,j,k≤Tj,k+M(1-xi,j,k)

?i∈A,?j∈A,?k∈K

(8)

Ti,k+Si+ti,n+i,k≤Tn+i,k

(9)

Li,k+lj,k≤Lj,k+M(1-xi,j,k)

?i∈A,?j∈P,?k∈K

(10)

Li,k-lj,k≤Lj,k+M(1-xi,j,k)

?i∈A,?j∈D,?k∈K

(11)

li,k≤Li,k≤Ck?i∈P,?k∈K

(12)

0 ≤Li,k≤Ck-li,ki∈D,?k∈K

(13)

Lo,k=0 ?k∈K

(14)

xi,j,kbinary ?k∈K,(i,j)∈A

(15)

2 求解算法

考慮到車輛路徑優(yōu)化屬于典型的NP-hard問題，計算求解難度較高，首先利用數(shù)學(xué)規(guī)劃優(yōu)化器Gurobi實現(xiàn)對模型的基本精確計算，得到最優(yōu)解.然后引入有效不等式方法在基本精確計算的基礎(chǔ)上進一步提高計算效率，實現(xiàn)模型求解.最后將上述兩種求解算法與禁忌搜索算法和基于最優(yōu)時差插入法的遺傳算法進行對比，判斷不同求解策略在計算效率和求解精度上的優(yōu)化幅度，進而分析基于最優(yōu)時差插入法的遺傳算法求解的準(zhǔn)確性和高效性.

2.1 有效不等式方法

基于子路徑消除約束和2-path不等式[14]提出與賽事公交接送客服務(wù)特征相適應(yīng)的有效不等式.令集合S表示接乘集合中的任意子集S?P，|S|為集合S內(nèi)元素個數(shù).k(S)為在車輛載客容量約束條件下，可滿足集合S內(nèi)乘客接乘服務(wù)的最小用車數(shù).

(16)

(17)

2.2 禁忌搜索算法

利用一種帶閾值的禁忌算法對賽事公交車輛路徑優(yōu)化模型進行求解.禁忌算法是目前應(yīng)用于車輛路徑問題最為廣泛的啟發(fā)式算法，其核心是以禁忌列表的形式保存計算遍歷過的部分求解信息，進而減少鄰域算子搜索過程中陷入循環(huán)的情況.

2.2.1 鄰域結(jié)構(gòu)

以兩條路徑間點的插入作為鄰域操作策略.隨機選擇兩條路徑r1，r2，分別隨機任取[0,2]個出行需求，在時間窗及載量約束等條件下將出行需求對應(yīng)的接送客節(jié)點隨機插入對方路徑中，嘗試n次若插入方案均無法滿足約束則重新選擇兩條路徑重復(fù)鄰域操作.同時，因兩條路徑上的出行需求是在區(qū)間[0,2]中隨機選擇，故本節(jié)中點的插入實際上包含了出行需求的轉(zhuǎn)移和互換兩種操作.

2.2.2 禁忌和特赦規(guī)則

為增加搜索多樣性并防止求解循環(huán)，引入禁忌列表來儲存禁忌對象，用于記錄最近接受的移動.定義禁忌周期為Tabu_len，在本文中設(shè)定禁忌周期固定不變.同時，考慮到苛刻的禁忌原則使得一些較優(yōu)解被放棄不利于算法的搜索，設(shè)定移動后得到的解優(yōu)于禁忌列表中對應(yīng)解時則特赦允許禁忌的移動.

2.2.3 閾值更新規(guī)則

最初設(shè)置閾值t為0來保障求解質(zhì)量.當(dāng)且僅當(dāng)計算陷入局部最優(yōu)時，調(diào)整閾值t為[0,Tmax]間的隨機數(shù)以提高求解多樣性，其中Tmax為程序閾值的最大值.若得到的解更新了最優(yōu)可行解，則將閾值t重置為0以增加搜索深度.

2.2.4 搜索策略

通過first_accept搜索策略實現(xiàn)在增加求解多樣性的同時降低搜索時間的目標(biāo).當(dāng)鄰域算子變換后的解不在禁忌列表中或者滿足特赦規(guī)則，且解的目標(biāo)函數(shù)值變化小于閾值t時，替換當(dāng)前最優(yōu)可行解.

2.3 遺傳算法

遺傳算法是一種不依賴于梯度，具有隨機與高度并行特征的自適應(yīng)全局域優(yōu)化概率搜索算法.在遺傳算法求解過程中考慮了基于插入前檢測的最優(yōu)時差插入法和隨機匹配交叉方法以提高算法求解效率.

2.3.1 插入算子

基于最優(yōu)時差插入法[15]構(gòu)建插入算子.如圖1所示，插入算子核心在于計算新節(jié)點插入位置后面節(jié)點實際到達服務(wù)時間，并判斷是否仍在相應(yīng)的時間窗范圍內(nèi).以可行路徑Rk(0,i,j,…,i+1,…,j+1,0)為例，具體公式為

圖1 基于插入前檢測的最優(yōu)時差插入過程示意圖

wj=max{0,aj-(Ti,k+si+ti,j,k)}

?(i,j)∈Rk,?k∈K

(18)

?(i,j)∈Rk,?k∈K

(19)

(20)

?(i,j)∈Rk,?k∈K

(21)

(22)

(23)

?(i,j)∈Rk,?l∈Sk?k∈K

(24)

2.3.2 交叉算子

考慮到染色體片段交叉后仍需滿足先接后送原則，同時要符合載量約束和時間窗約束，因此交叉算子以路徑作為染色體片段交換的最小單位.采用隨機不等交叉算子增加算法搜索步長，如圖2所示，在[0,1]范圍內(nèi)隨機生成兩位小數(shù)，若小于交叉概率Pc(Pc≥0)則觸發(fā)交叉算子計算，從兩個父代染色體中分別隨機任取一至兩條路徑完成交換.刪除重復(fù)需求節(jié)點并根據(jù)插入算子補全染色體缺失需求點.若現(xiàn)有路徑均插入不可行，則在染色體末尾生成一條新路徑插入該出行需求.

圖2 染色體隨機交叉示意圖

2.3.3 突變算子

突變算子以出行需求作為突變的最小單位，仍需確保每個出行需求先接后送的原則，同時滿足載量約束和時間窗約束.圖3中，設(shè)突變概率Pm在[0,1]范圍內(nèi)隨機生成兩位小數(shù)，若小于突變概率則從父代染色體中隨機選取一個路徑中的出行需求并將其從該位置刪除，在染色體中搜索最優(yōu)插入位置，根據(jù)插入算子確定最終方案.若現(xiàn)有路徑插入不可行，則在染色體末尾再生成一條新路徑并插入該出行需求.

圖3 染色體變異過程示意圖

突變后形成新的子代染色體種群池，計算每個染色體目標(biāo)函數(shù)值，進行適應(yīng)度映射后得到染色體適應(yīng)度，適應(yīng)度函數(shù)為目標(biāo)函數(shù)的倒數(shù).種群池中染色體兩兩一組選擇適應(yīng)度高的染色體遺傳至下一代，進行種群規(guī)模次選擇形成新的父代染色體種群池重復(fù)交叉、突變算子直至滿足迭代次數(shù)條件.

3 案例分析

以2022年北京冬季奧運會為例進行分析.作為世界首次開展的多賽區(qū)冬奧會，2022年北京冬季奧運會包括北京城區(qū)、延慶、張家口賽區(qū)，共涵蓋12個比賽場館，見圖4.為優(yōu)先對使用車隊規(guī)模進行優(yōu)化，可采用設(shè)置高于車輛行駛費用數(shù)量級的車輛固定使用費用[16]，考慮到北京冬奧賽區(qū)間及內(nèi)部道路網(wǎng)絡(luò)上車輛實際行駛費用范圍，設(shè)車輛固定使用費用為1 000元，車輛行駛費用單位為1元/min，同時根據(jù)實際賽事活動安排組織足夠的賽事公交車隊開展服務(wù)，車載容量為40人，在接、送客站點停泊時間為5 min.

圖4 2022年北京冬季奧運會賽事場館分布圖

設(shè)置2022年2月8日內(nèi)的13個觀賽出行需求，數(shù)據(jù)格式如表1所示，其中各出行需求乘客數(shù)之和為184人.利用現(xiàn)有商業(yè)化數(shù)學(xué)規(guī)劃優(yōu)化器Gurobi實現(xiàn)對算例的基本精確求解，并與本文有效不等式、禁忌搜索算法和遺傳算法計算結(jié)果進行比較分析.如表2所示，利用有效不等式能夠合理縮小最優(yōu)解搜索范圍，計算效率提升57.3%，并能在可接受計算時間內(nèi)得到精確結(jié)果.而禁忌搜索算法在n=400、Tabu_len=20、Tmax=100，迭代次數(shù)為2 000次時，可在34.9 s計算后得到優(yōu)化目標(biāo)值誤差在8%的可行解，求解精度較高.而采用基于最優(yōu)時差插入法的遺傳算法，設(shè)置500種群規(guī)模、交叉因子為0.8、突變因子為0.15，共迭代2 000次，能夠進一步提高99.4%的計算效率且得到理想的優(yōu)化結(jié)果.分析遺傳算法計算結(jié)果的產(chǎn)生原因為，模型優(yōu)先最小化車輛使用成本，優(yōu)化車輛開行成本的搜索空間受到最小車隊規(guī)模限制，因此在小規(guī)模算例中更易得到理想優(yōu)化結(jié)果，計算表明禁忌搜索算法、遺傳算法均具備在有限計算能力和時間條件下完成更大規(guī)模計算任務(wù)的能力，且后者計算精度更高.

表1 觀賽人群出行需求數(shù)據(jù)格式表

表2 有效不等式和遺傳算法計算結(jié)果分析

設(shè)置2022年2月16日比賽日內(nèi)的122個出行需求，總乘客數(shù)量為1 809人.該算例規(guī)模條件下已無法通過有效不等式方法在有限計算條件下獲得優(yōu)化結(jié)果.故采用禁忌搜索算法和遺傳算法實現(xiàn)優(yōu)化計算，其中禁忌搜索算法在n=400、Tabu_len=40、Tmax=1 000，迭代次數(shù)為200 000次時，可在2 648秒計算后得到目標(biāo)值為81 353的可行解.同時利用基于最優(yōu)時差插入法的遺傳算法，根據(jù)不同種群條件下的交叉、突變概率參數(shù)組合可以得到優(yōu)化目標(biāo)函數(shù)值及相應(yīng)方案計算時間見表3.由表3可知，在相同種群規(guī)模條件下，交叉、突變概率變化對計算的影響主要表現(xiàn)在求解效率上：隨著交叉突變概率的提高，觸發(fā)交叉、突變算子運算的情況更加頻繁，從而導(dǎo)致計算時間不斷增長.

表3 不同交叉、突變參數(shù)及種群數(shù)量組合計算結(jié)果對比

由表3可知，種群規(guī)模較小時，計算時間相對較短但求解質(zhì)量普遍不高，在500種群規(guī)模下交叉因子設(shè)置為0.7，突變因子為0.1時，求解時間最短，共用時922 s.在2 000種群規(guī)模下，設(shè)置交叉概率為0.9，突變概率為0.3時，求解時間最長，共用時5 152 s，求解時間相差近5.59倍.與禁忌搜索算法相比，基于最優(yōu)時差插入法的遺傳算法在1 000種群規(guī)模下，交叉因子為0.8，突變因子為0.1時，能夠在更少的計算時間內(nèi)求解得到目標(biāo)值為69 373的較優(yōu)解.

4 結(jié)論

1)面向觀賽人群提供需求響應(yīng)式移動服務(wù)滿足乘客觀看多場賽事活動的出行需求.為乘客減少了出行決策難度與長時候車、車上無座等問題.同時作為公共交通系統(tǒng)的補充，提高了公共交通服務(wù)水平和應(yīng)對靈活觀賽出行需求的適應(yīng)能力.

2)針對觀賽人群單比賽日內(nèi)為觀看多場賽事活動而在比賽場館間產(chǎn)生的出行需求，本文基于對多出行需求、混合搭載和帶有時間窗和載量約束的考慮，以最小化賽事公交使用、開行成本為目標(biāo)構(gòu)建了賽事公交車輛路徑優(yōu)化模型.

3)求解算法中利用兩種有效不等式，提高57.3%的精確求解計算效率，采用帶閾值的禁忌搜索算法能夠在可接受的計算誤差范圍內(nèi)，以較高的計算效率得到優(yōu)化結(jié)果.而基于最優(yōu)時差插入法的遺傳算法則能夠更好地實現(xiàn)賽事公交車輛路徑優(yōu)化模型求解，相較于基本精確求解計算效率能夠提升99.4%，并可得到不同規(guī)模條件下算例的車輛路徑優(yōu)化方案，以期為推動2022年北京冬季奧運會交通發(fā)展提供規(guī)劃參考.