區(qū)間阻抗下無人駕駛接駁出租車合乘路徑優(yōu)化

劉津洋

(長沙理工大學(xué) 交通運(yùn)輸工程學(xué)院， 湖南 長沙 410114)

實(shí)際交通網(wǎng)絡(luò)中行程時(shí)間包含很多不確定性。基于不確定條件對交通網(wǎng)絡(luò)的路徑優(yōu)化研究主要分為兩類：一是基于概率分布的期望時(shí)間，研究路徑的行程時(shí)間概率分布；二是基于區(qū)間數(shù)據(jù)表達(dá)，用區(qū)間數(shù)據(jù)表示路網(wǎng)中的種種不確定性因素。現(xiàn)實(shí)生活中難以獲取較精確的數(shù)據(jù)，而通過概率分布選取的最佳路徑與數(shù)學(xué)模型的期望值成相關(guān)關(guān)系，但不能稱之為最可靠路徑。可見，更適合采用區(qū)間數(shù)據(jù)表達(dá)路網(wǎng)的不確定性。

2020年是中國無人駕駛車輛落地試運(yùn)營的開局之年，全國各地多城市陸續(xù)開展了試運(yùn)營相關(guān)測試。現(xiàn)階段無人駕駛出租車不可隨意切換路徑，乘客必須在指定位置上下車。該文將多輛無人駕駛接駁出租車和合乘問題相結(jié)合，建立基于區(qū)間阻抗的最短路徑優(yōu)化模型。

1 問題描述

區(qū)間阻抗下無人駕駛接駁出租車合乘路徑優(yōu)化是以原始最短路模型為基礎(chǔ)，考慮路網(wǎng)間阻抗的不確定因素，結(jié)合決策者的區(qū)間分析方法，形成對應(yīng)約束條件，建立在區(qū)間阻抗數(shù)據(jù)背景下的最短路優(yōu)化模型。模型可運(yùn)用于出行者的路徑方案選擇決策，根據(jù)所求結(jié)果選擇最佳出行路徑方案。將路網(wǎng)詳細(xì)描述成有向網(wǎng)絡(luò)圖G=(V，A)，其中V表示路網(wǎng)圖中所有節(jié)點(diǎn)集合，A表示路網(wǎng)圖中所有邊的集合。起點(diǎn)、終點(diǎn)r,t∈V，(i,j)∈A表示路網(wǎng)內(nèi)任意一條邊，賦予邊的區(qū)間阻抗為[lij,uij]，共有n輛車，每輛車的最大載客為Q人。路網(wǎng)中每個需求點(diǎn)有對應(yīng)的上車需求人數(shù)，同時(shí)規(guī)定車輛行駛最大時(shí)間Tmax，目標(biāo)是滿足所有上車需求點(diǎn)且在規(guī)定時(shí)間內(nèi)調(diào)度方案的魯棒成本最小。

在區(qū)間阻抗背景下，兩兩區(qū)間值因?yàn)榉N種不確定因素不能進(jìn)行直接比較，應(yīng)考慮魯棒偏差，即考慮出行者所選路徑與當(dāng)前情景下最短路的差值。某種情景用s表示，魯棒偏差是在某種情景下與之相對應(yīng)的網(wǎng)絡(luò)整體狀態(tài)。如從起點(diǎn)r到終點(diǎn)t的路徑方案p，其魯棒偏差為：

魯棒偏差的大小可反映出行者選擇該路徑的后悔程度。因此，可根據(jù)所有情景下的魯棒偏差，找到魯棒偏差的最大值，再根據(jù)魯棒優(yōu)化的極小化極大值準(zhǔn)則尋找魯棒偏差的最小值路徑即魯棒最短路徑。這里的路徑魯棒性是在當(dāng)前情景選定路徑與最壞情景最短路徑之間的差值，出行者作出決策選擇魯棒最短路方案后，即使在所有不確定因素全部發(fā)生的條件下，也可保證當(dāng)前的魯棒最短路方案與實(shí)際最短路徑差值最小。對交通樞紐接駁車輛、特殊工種車輛、災(zāi)區(qū)應(yīng)急物流等有硬時(shí)間窗約束或?qū)r(shí)間可靠性要求高的路徑方案進(jìn)行決策時(shí)，路徑魯棒性可作為關(guān)鍵評價(jià)指標(biāo)。

2 模型構(gòu)建

基于以上分析，構(gòu)建魯棒最短路混合整數(shù)規(guī)劃模型。定義Xij、Wij為所選路網(wǎng)路徑?jīng)Q策變量，當(dāng)邊(i,j)在魯棒最短路徑上時(shí)，Xij、Wij取1,否則取零。定義Y為車輛c所選路徑?jīng)Q策變量，經(jīng)過點(diǎn)i時(shí)取1，否則取零。以pickupi表示點(diǎn)i的乘車人數(shù)，passnodes表示上車需求點(diǎn)集合(這里討論的情況為需求點(diǎn)全部滿足)。邊(i,j)的路徑行程時(shí)間Cij可表示為lbij+(ubij-lbij)Xij(lbij為路段ij的下界值；ubij為路段ij的上界值)。xt表示當(dāng)前情形下起點(diǎn)s到終點(diǎn)t的最短路徑時(shí)間，是一個隨變量Xijc取值而定的變量。混合整數(shù)規(guī)劃模型如下：

(1)

約束條件如下：

xj≤xi+lij+(ubij-lb)Xij;?(i,j)∈E

(2)

(3)

(4)

c∈1,…,n

(5)

(6)

Xijc+Xjic≤1,?i,j∈E,c∈1,…,n

(7)

c∈1,…,n

(8)

(9)

c∈1,…,n

(10)

(11)

(12)

式中：E為路網(wǎng)中所有i、j點(diǎn)的集合。

式(1)中xt可描述為：

Xijc)]Wijc

(13)

對于Wijc，有：

(14)

式(1)為目標(biāo)函數(shù)模型，表示求最小魯棒成本下最優(yōu)路徑；式(2)為當(dāng)前情景下最短路徑約束；式(3)、式(4)為參照傳統(tǒng)最短路徑的所有選擇路徑的起點(diǎn)、終點(diǎn)約束；式(5)為路網(wǎng)各節(jié)點(diǎn)流量約束；式(6)表示上車需求點(diǎn)(必經(jīng)節(jié)點(diǎn))需全部滿足；式(7)為避免兩點(diǎn)間出現(xiàn)路徑成環(huán)現(xiàn)象的約束；式(8)為各車輛行駛最大時(shí)間約束；式(9)表示每一個上車需求點(diǎn)(必經(jīng)節(jié)點(diǎn))只能被一輛車服務(wù)；式(10)表示上車需求點(diǎn)(必經(jīng)節(jié)點(diǎn))被車輛c服務(wù)，與經(jīng)過當(dāng)前節(jié)點(diǎn)的車輛c為同一輛；式(11)為車輛c的最大載客量約束；式(12)為其余變量取值范圍。

3 算法設(shè)計(jì)

Benders分解算法在解決較大規(guī)模混合整數(shù)規(guī)劃、隨機(jī)規(guī)劃等問題方面應(yīng)用廣泛。運(yùn)用割平面的思想，將復(fù)雜變量固定后不斷迭代求解產(chǎn)生新的約束，產(chǎn)生新的約束后主問題的約束增加產(chǎn)生新解，通過不斷迭代計(jì)算求得最優(yōu)解。該文研究的魯棒成本，首先固定車輛路徑，再計(jì)算在該情形下的最短路徑，與Benders分解算法有異曲同工之處。因此，采用Benders分解算法對最小魯棒成本下最優(yōu)路徑模型進(jìn)行求解。步驟如下：

(2) 將路網(wǎng)中車輛經(jīng)過的所有路徑取區(qū)間阻抗的上界值，未經(jīng)過路徑取區(qū)間阻抗的下界值，求解子模型，獲得新的最優(yōu)解Wijc、Yic。如果目標(biāo)函數(shù)值小于上界UB值，則更新UB。

(3) 將Wijc代入主模型，形成式(15)所示新的約束條件，得到新的解Xijc、Yic。如目標(biāo)值z大于下界LB值，則更新LB。

lbij(1-Xijc)]Wijc

(15)

(4) 若UB=LB，目標(biāo)模型得到最優(yōu)解，停止計(jì)算。否則，進(jìn)入下一步。

4 算例分析

采用圖1所示交通仿真網(wǎng)絡(luò)，對上述模型和算法進(jìn)行論證。該路網(wǎng)由26個節(jié)點(diǎn)、61條路段組成，兩點(diǎn)之間的區(qū)間阻抗值均作標(biāo)記。在AMPL中編寫B(tài)enders算法，寫出對應(yīng)主問題、子問題，并調(diào)用Gurobi求解器進(jìn)行求解。

圖1 路網(wǎng)測試圖

車輛數(shù)設(shè)定為3臺；需求點(diǎn)設(shè)置為7個,分別為路網(wǎng)中節(jié)點(diǎn)4、6、9、15、19、22、23，各點(diǎn)上車需求人數(shù)見表1；最大載客量設(shè)定為4，最大行駛時(shí)間設(shè)定為15 min。表1為車輛所滿足的各個需求點(diǎn)，因設(shè)定最大載客量為4，需求點(diǎn)需求量的不同會對路徑產(chǎn)生不同約束。

表1 上車需求點(diǎn)分配

3輛車魯棒最短路徑見表2，總魯棒成本為26.7，路徑形成見圖2。

表2 魯棒最短路徑

圖2 魯棒優(yōu)化路徑

表3為傳統(tǒng)下界最短路的車輛行駛路徑方案。雖然在3臺車的行程時(shí)間區(qū)間中，下界值均比表2中魯棒最短路徑的下界時(shí)間小，但總體魯棒成本大于表2中成本。魯棒成本越大，則行程時(shí)間的不穩(wěn)定性增加。說明所建立的基于區(qū)間阻抗的最短路徑優(yōu)化模型和算法可行，所得最短路徑相較于傳統(tǒng)最短路徑具有更強(qiáng)的魯棒性。

表3 下界最短路徑

5 結(jié)語

結(jié)合無人駕駛路徑研究熱點(diǎn)，將多輛無人駕駛接駁出租車和合乘問題相結(jié)合，以總體魯棒為目標(biāo)成本，在滿足乘客需求下，將車輛資源、環(huán)境資源、時(shí)間資源等做到最大整合，最大限度滿足乘客需求和出行時(shí)間的穩(wěn)定性要求。考慮到出行者在路網(wǎng)中選擇出行路徑方案時(shí)間的不確定性，建立基于區(qū)間阻抗的最短路徑優(yōu)化模型，模型經(jīng)由CPLEX搭建并驗(yàn)證，驗(yàn)證過程中為避免非線性因素采用對偶模型,并設(shè)計(jì)Benders算法通過固定復(fù)雜變量進(jìn)行求解。算例驗(yàn)證結(jié)果表明該魯棒最短路徑相較于傳統(tǒng)最短路徑具有更強(qiáng)的魯棒性和穩(wěn)定性，對于接駁運(yùn)輸、應(yīng)急物流等均具有應(yīng)用價(jià)值。