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

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

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

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

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

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

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

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

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

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

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

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

設(shè)P={1,2，…,n}為接客點(diǎn)集合，D={n+1,n+2，…,2n}為送客點(diǎn)集合，接送客節(jié)點(diǎn)并非物理意義上的接送客站點(diǎn)，而是構(gòu)成出行需求的接送客節(jié)點(diǎn)，同時(shí)有A=P∪D.每個(gè)出行需求采用(i,n+i)表示，均由一個(gè)或多個(gè)時(shí)間窗相同、接送節(jié)點(diǎn)相同的觀賽人群在場(chǎng)館間的出行構(gòu)成.設(shè)K為賽事公交車輛集合.設(shè)0-1決策變量xi,j,k判斷賽事公交k是否經(jīng)過有向弧(i,j)，Ti,k和Li,k分別表示賽事公交k到達(dá)節(jié)點(diǎn)i的時(shí)間和服務(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問題，計(jì)算求解難度較高，首先利用數(shù)學(xué)規(guī)劃優(yōu)化器Gurobi實(shí)現(xiàn)對(duì)模型的基本精確計(jì)算，得到最優(yōu)解.然后引入有效不等式方法在基本精確計(jì)算的基礎(chǔ)上進(jìn)一步提高計(jì)算效率，實(shí)現(xiàn)模型求解.最后將上述兩種求解算法與禁忌搜索算法和基于最優(yōu)時(shí)差插入法的遺傳算法進(jìn)行對(duì)比，判斷不同求解策略在計(jì)算效率和求解精度上的優(yōu)化幅度，進(jìn)而分析基于最優(yōu)時(shí)差插入法的遺傳算法求解的準(zhǔn)確性和高效性.

2.1 有效不等式方法

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

(16)

(17)

2.2 禁忌搜索算法

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

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

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

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

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

2.2.3 閾值更新規(guī)則

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

2.2.4 搜索策略

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

2.3 遺傳算法

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

2.3.1 插入算子

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

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

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 交叉算子

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

圖2 染色體隨機(jī)交叉示意圖

2.3.3 突變算子

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

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

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

3 案例分析

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

圖4 2022年北京冬季奧運(yùn)會(huì)賽事場(chǎng)館分布圖

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

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

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

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

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

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

4 結(jié)論

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

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

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