基于雙層規(guī)劃的自動(dòng)卡車運(yùn)輸專用網(wǎng)絡(luò)設(shè)計(jì)優(yōu)化

　　摘 要: 為保障交通系統(tǒng)安全性和卡車貨運(yùn)自動(dòng)化的發(fā)展, 有必要對(duì)自動(dòng)卡車貨物運(yùn)輸專用網(wǎng)絡(luò)進(jìn)行科學(xué)規(guī)劃與布局. 考慮自動(dòng)卡車專用道會(huì)減少普通車輛的路權(quán), 對(duì)普通車輛的出行路徑選擇行為造成影響. 首先, 從路網(wǎng)整體出發(fā), 以系統(tǒng)出行時(shí)間最小為目標(biāo), 充分考慮路網(wǎng)普通車輛的出行路徑選擇行為, 構(gòu)建了一種新的自動(dòng)卡車專用運(yùn)輸網(wǎng)絡(luò)設(shè)計(jì)的雙層規(guī)劃模型. 其次, 提出了一種基于實(shí)數(shù)編碼的改進(jìn)差分進(jìn)化算法求解建立的雙層規(guī)劃模型, 不僅保證解的可行性，還避免了復(fù)雜的不可行解修復(fù)過程. 最后, 通過 Sioux Falls 基準(zhǔn)網(wǎng)絡(luò)實(shí)例和大量隨機(jī)算例對(duì)比測(cè)試結(jié)果驗(yàn)證了模型和算法的有效性.

　　關(guān)鍵詞: 自動(dòng)卡車;專用道網(wǎng)絡(luò);路徑規(guī)劃;雙層規(guī)劃;自適應(yīng)差分進(jìn)化算法

　　引 言

　　近年來,5G 技術(shù)和人工智能的迅速發(fā)展加快了智能化社會(huì)的進(jìn)程.5G 技術(shù)和人工智能的普及應(yīng)用將很大程度推進(jìn)車聯(lián)網(wǎng)的快速構(gòu)建和自動(dòng)駕駛的實(shí)現(xiàn)與成熟, 在智能交通領(lǐng)域體現(xiàn)得尤為明顯[1]. 自動(dòng)駕駛發(fā)展的重要組成部分之一是自動(dòng)卡車. 在旺盛的物流需求背景下, 自動(dòng)卡車貨物運(yùn)輸具有相對(duì)固定的運(yùn)輸路線與需求剛性的特點(diǎn), 相對(duì)于自動(dòng)駕駛承運(yùn)車具有更加容易落地與商業(yè)化的優(yōu)勢(shì), 如圖森未來公司已在美國實(shí)現(xiàn)了自動(dòng)駕駛貨運(yùn)服務(wù)[2,3]. 另一方面, 在完全實(shí)現(xiàn)自動(dòng)駕駛之前, 人工駕駛車輛與自動(dòng)駕駛車輛混行的過渡階段將長期存在, 如何在該階段安全、高效地管理混合交通流成為保障高質(zhì)量交通發(fā)展的重要現(xiàn)實(shí)問題[4].

　　因此, 在未來復(fù)雜的混行道路環(huán)境中, 首先為自動(dòng)卡車貨運(yùn)規(guī)劃專用運(yùn)輸網(wǎng)絡(luò)是保障道路安全、運(yùn)輸效率并促進(jìn)自動(dòng)駕駛技術(shù)發(fā)展的有效舉措, 具有重要的現(xiàn)實(shí)意義.專用道策略是一種提供與其他車輛分離道路的經(jīng)濟(jì)、有效的方法, 具體是指在現(xiàn)有城市交通網(wǎng)絡(luò)中選擇部分路段的車道設(shè)置成為僅供特定車輛使用的專用車道, 為其提供相對(duì)安全暢通的道路條件提高運(yùn)輸效率. 然而, 在城市化進(jìn)程不斷加快的時(shí)代,為自動(dòng)卡車設(shè)置專用車道會(huì)使普通車輛可使用的道路空間減小, 很可能使原本的交通狀況更加糟糕, 對(duì)整個(gè)系統(tǒng)的普通車輛造成負(fù)面影響. 如何科學(xué)合理規(guī)劃自動(dòng)卡車運(yùn)輸專用道網(wǎng)絡(luò), 有效分配路網(wǎng)資源,保障自動(dòng)卡車運(yùn)輸任務(wù)效率與專用車道造成的負(fù)面影響之間的權(quán)衡至關(guān)重要. 因此, 本文將在 5G、人工智能不斷推進(jìn)自動(dòng)駕駛發(fā)展的背景下, 重點(diǎn)研究未來自動(dòng)卡車運(yùn)輸專用網(wǎng)絡(luò)的設(shè)計(jì)優(yōu)化問題.

　　目前, 專用道設(shè)置規(guī)劃問題 (Lane ReservationProblem, LRP) 得到了國內(nèi)外研究學(xué)者的廣泛關(guān)注. 研究應(yīng)用場(chǎng)景主要可分為特殊事件的臨時(shí)專用道設(shè)置規(guī)劃、危險(xiǎn)品運(yùn)輸?shù)膶Ｓ玫涝O(shè)置規(guī)劃、自動(dòng)卡車專用道設(shè)置規(guī)劃以及公交專用道的設(shè)置規(guī)劃等方面. 絕大多數(shù)研究集中于公交專用道優(yōu)化. 如,Zhao 等[5] 提出一種動(dòng)態(tài)公交專用道設(shè)置策略,以交叉口平均延誤最小化為目標(biāo)建立混合整數(shù)非線性規(guī)劃. Han 等[6] 針對(duì)部分路段旅行時(shí)間信息, 研究隨機(jī)公交車專用道優(yōu)化問題, 提出面向服務(wù)的分布式魯棒優(yōu)化模型. 少部分研究了特殊事件的臨時(shí)專用道和危險(xiǎn)品專用道設(shè)置規(guī)劃.

　　如,Li 等[7] 研究運(yùn)輸任務(wù)合并下的大型運(yùn)動(dòng)會(huì)專用道設(shè)置問題, 建立整數(shù)線性規(guī)劃. Wu 等[8] 同時(shí)考慮剩余容量和預(yù)算限制建立雙目標(biāo)整數(shù)規(guī)劃模型, 并提出新的松弛優(yōu)化求解算法. 張圣忠等[9] 以總體出行成本最小、專用道影響最小、專用道利用率最大建立雙層規(guī)劃模型,并采用 NSGA-Ⅱ 算法求解. 自動(dòng)卡車運(yùn)輸專用道優(yōu)化問題研究很少, 然而在 5G、人工智能技術(shù)背景下自動(dòng)駕駛的成熟實(shí)現(xiàn)勢(shì)不可擋, 很有必要提前為自動(dòng)卡車規(guī)劃專用運(yùn)輸網(wǎng)絡(luò), 為未來混行交通狀態(tài)提供理論和實(shí)踐參考.

　　在微觀層面,Xun 等[10] 為精確評(píng)估大規(guī)模路網(wǎng)引入自動(dòng)貨車車道引起的交通流變化提出一種微觀 -中觀交通仿真器, 結(jié)果表明為自動(dòng)貨車提供專用道會(huì)導(dǎo)致廣泛的道路網(wǎng)絡(luò)交通流變化. 在宏觀層面,Fang 等[11] 首次將專用道策略引入自動(dòng)卡車貨物運(yùn)輸研究中, 優(yōu)化專用道路段選擇并為自動(dòng)卡車運(yùn)輸任務(wù)規(guī)劃專用道路徑, 提出整數(shù)線性規(guī)劃模型并驗(yàn)證了問題的 NP 難特性. 隨后,Wu 等[12]在文獻(xiàn)[11] 的基礎(chǔ)上提出有效不等式建立了新的整數(shù)線性規(guī)劃并提出求解大規(guī)模問題的兩階段精確算法.上述成果一定程度上豐富了專用道設(shè)置規(guī)劃研究, 但還存在以下不足：

　　1) 現(xiàn)有文獻(xiàn)對(duì)于路段上存在車道被設(shè)置為專用道后, 將原本在該車道上行駛的普通車輛直接移至該路段上剩余的普通車道上,而不考慮部分車輛可能的重新路徑選擇, 不能很好的反映自動(dòng)卡車專用道規(guī)劃后對(duì)系統(tǒng)的影響. 2) 現(xiàn)有文獻(xiàn)考慮普通車輛路徑選擇行為后, 大多用于求解小規(guī)模算例, 如何開發(fā)適合中大規(guī)模算例的求解算法值得進(jìn)一步思考. 因此, 本文將針對(duì)上述研究問題與挑戰(zhàn), 進(jìn)一步分析自動(dòng)卡車專用車道和普通車輛之間的動(dòng)態(tài)相互影響關(guān)系, 建立一類新的關(guān)于自動(dòng)卡車專用運(yùn)輸網(wǎng)絡(luò)優(yōu)化的雙層規(guī)劃模型, 同時(shí)針對(duì)自動(dòng)卡車專用運(yùn)輸網(wǎng)絡(luò)規(guī)劃的問題特性開發(fā)了基于實(shí)數(shù)編碼改進(jìn)差分進(jìn)化算法 (Improved DifferentialEvolutionary Algorithm, IDEA), 利用不同規(guī)模的案例驗(yàn)證算法與模型的有效性.

　　1 問題描述及符號(hào)定義

　　1.1 問題描述

　　本文采用有向圖 G(N, A) 表示城市交通網(wǎng)絡(luò);其中 N 代表網(wǎng)絡(luò)節(jié)點(diǎn)的集合, 每個(gè)節(jié)點(diǎn)表示實(shí)際交通網(wǎng)絡(luò)的交叉路口;A 表示城市交通網(wǎng)絡(luò)的弧集合,每條弧表示實(shí)際道路路段. K 表示自動(dòng)卡車運(yùn)輸任務(wù)集合,O、D 分別表示任務(wù)的起點(diǎn)集合與終點(diǎn)集合,每個(gè)運(yùn)輸任務(wù)都有對(duì)應(yīng)的起訖點(diǎn) (OD) 以及嚴(yán)格的時(shí)間限制. 為保障運(yùn)輸任務(wù)的準(zhǔn)時(shí)完成, 需要將部分車道轉(zhuǎn)化為僅供自動(dòng)卡車運(yùn)輸任務(wù)行駛的專用車道,以提高自動(dòng)卡車運(yùn)輸任務(wù)的效率和安全性. 此外, 為促進(jìn)自動(dòng)駕駛的不斷成熟以及安全性, 要求自動(dòng)卡車運(yùn)輸任務(wù)所經(jīng)過的路徑均設(shè)置專用道.

　　但是, 一旦某些路段上設(shè)置了專用道, 將會(huì)對(duì)該路段上的普通車輛產(chǎn)生負(fù)面影響, 使該路段上普通車輛可使用的道路容量降低, 造成道路擁擠, 行駛時(shí)間增大. 與此同時(shí), 城市網(wǎng)絡(luò)的交通狀態(tài)也將改變, 專用道路段上原本的普通車輛可能重新進(jìn)行路徑規(guī)劃, 導(dǎo)致網(wǎng)絡(luò)中的普通車輛流量重新分配. 而普通車輛的路徑規(guī)劃結(jié)果反過來又將直接決定路網(wǎng)整體行駛時(shí)間, 影響了專用道布局方案. 因此, 本文從系統(tǒng)的角度出發(fā),充分考慮專用道與普通車輛之間的相互影響, 以專用道負(fù)面影響最小為目標(biāo), 確定能夠保證運(yùn)輸任務(wù)都能準(zhǔn)時(shí)完成的專用道優(yōu)化設(shè)置方案.

　　1.2 假設(shè)條件

　　1)每條路段至少 2 車道, 確保設(shè)置專用道后普通車輛還可以在當(dāng)前路段行駛. 2) 每條路段至多有 1個(gè)車道為專用道. 3) 每個(gè)任務(wù)從其起點(diǎn)到訖點(diǎn)之間存在可行路徑.

　　2 模型建立

　　上層規(guī)劃模型描述從整個(gè)系統(tǒng)角度如何確定自動(dòng)卡車專用運(yùn)輸網(wǎng)絡(luò)方案, 使得在保證所有任務(wù)能夠準(zhǔn)時(shí)完成的情況下對(duì)普通車輛影響最小.下層規(guī)劃模型采用 Beckmann 等價(jià)模型描述在對(duì)應(yīng)專用道方案下, 普通車輛的路徑選擇行為. 所有普通車輛都以力圖最小化各自最短出行成本為目的,最終將達(dá)到一種用戶均衡狀態(tài). 在用戶均衡狀態(tài)下,連接每個(gè)出行 OD 對(duì)的所有被使用的路徑有相同的旅行時(shí)間, 且小于等于任何未被使用過的路徑旅行時(shí)間[13].

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

　　雙層規(guī)劃模型是 NP 難問題[15]. 由于本文建立的雙層規(guī)劃模型是非線性模型并且很難將問題轉(zhuǎn)化為線性模型, 不具備良好的問題特性, 本文選用差分進(jìn)化算法 (Differential Evolutionary Algorithm, DEA)內(nèi)嵌 FrankWolfe 算法[16] 對(duì)雙層規(guī)劃模型進(jìn)行求解.傳統(tǒng)求解專用道優(yōu)化問題, 通常用 0-1 編碼來表示專用道的設(shè)置與否. 一旦道路網(wǎng)絡(luò)規(guī)模增大, 該編碼方式將造成過度冗長的個(gè)體, 搜索空間極度增大. 此外, 自動(dòng)卡車專用道設(shè)置問題要求每個(gè)任務(wù)路徑的專用道是連續(xù)的, 對(duì)解的要求嚴(yán)苛, 不易生成可行解, 通常需要伴隨復(fù)雜的解修復(fù)過程. 為此, 本文提出一種基于實(shí)數(shù)編碼的 IDEA 解決考慮普通車輛路徑選擇的自動(dòng)卡車專用運(yùn)輸網(wǎng)絡(luò)優(yōu)化問題.

　　3.1 預(yù)處理令交通網(wǎng)絡(luò)中所有路段都有一條車道作為自動(dòng)卡車專用道, 可得一個(gè)完全專用道網(wǎng)絡(luò), 并將其命名為 G′. 在 G′ 中可以為每個(gè)任務(wù)規(guī)劃運(yùn)輸路徑, 計(jì)算任務(wù)路徑旅行時(shí)間. 在 G′ 中每個(gè)任務(wù)滿足其時(shí)間限制的路徑數(shù)量是有限的, 是可以枚舉的. 可以發(fā)現(xiàn),只要從每個(gè)任務(wù)滿足時(shí)間限制的可行路徑集合中隨機(jī)選擇一條路徑進(jìn)行組合而得到的路段集合就是一個(gè)可行的專用道方案. 此外,Yen 的 K 最短路徑算法[17] 是用于枚舉任意起訖點(diǎn)間所有無環(huán)路徑的有效方法. 所以, 本文將該方法應(yīng)用于所有滿足任務(wù)時(shí)間限制的無環(huán)路徑以及對(duì)應(yīng)完成時(shí)間的枚舉.

　　4 案例分析

　　為了驗(yàn)證本文構(gòu)建的模型和改進(jìn)算法的有效性,以 Sioux Falls 為案例, 與不同場(chǎng)景下求解的專用道方案進(jìn)行效果對(duì)比分析, 對(duì)應(yīng)的場(chǎng)景描述見表 2. 此外,為驗(yàn)證 IDEA 中預(yù)處理與實(shí)數(shù)編碼結(jié)合的有效性, 隨機(jī)生成仿真算例進(jìn)行測(cè)試, 與傳統(tǒng) 0-1 編碼的差分進(jìn)化算法 (BDEA) 進(jìn)行對(duì)比.

　　4.1 參數(shù)敏感性分析

　　DEA 的控制參數(shù)主要包括 NP、F、CR, 選取合適的控制參數(shù)對(duì)于算法的性能至關(guān)重要. 由于算法不同階段對(duì)控制參數(shù)的要求不盡相同, 固定的控制參數(shù)存在一定的缺陷, 本文對(duì) F、CR 采用自適應(yīng)形式, 在不同進(jìn)化階段動(dòng)態(tài)的調(diào)整, 以改善算法性能. 由于 CR 的自適應(yīng)規(guī)則需要選定 CRmin 以及CRmax, 不易以參數(shù)敏感性分析的方法來確定, 則以通常的經(jīng)驗(yàn)規(guī)則令 CRmin=0.2,CRmax=0.9. 而對(duì)于NP、M axIter、F 以敏感性分析來確定相對(duì)合適的參數(shù)值, 以保證算法相對(duì)優(yōu)良的求解質(zhì)量和效率.

　　4.2 實(shí)例分析

　　本文考慮了普通車輛的路徑選擇, 并采用用戶均衡原則描述了交通網(wǎng)絡(luò)中普通車輛路徑選擇的流量分布情況. 在有出行需求的交通網(wǎng)絡(luò)中, 無論是否設(shè)置專用車道出行者都會(huì)進(jìn)行路徑選擇, 為了檢驗(yàn)本文提出的雙層規(guī)劃模型的效果, 以 Sioux Falls 網(wǎng)絡(luò)為實(shí)例, 在表 2 中所描述的網(wǎng)絡(luò)場(chǎng)景中, 分別考慮普通車輛的路徑選擇行為進(jìn)行用戶均衡交通分配,比較這三種場(chǎng)景下的系統(tǒng)總時(shí)間.

　　5 結(jié)論

　　(1) 本文在未來自動(dòng)駕駛與人工駕駛混行背景下, 基于自動(dòng)卡車專用道對(duì)普通車輛出行路徑選擇的影響分析, 構(gòu)建了一個(gè)新的雙層規(guī)劃模型以表示自動(dòng)卡車專用網(wǎng)絡(luò)布局方案和普通車輛出行路徑選擇結(jié)果之間的動(dòng)態(tài)相互影響關(guān)系, 對(duì)自動(dòng)卡車專用運(yùn)輸網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)問題進(jìn)行研究.(2) 針對(duì)自動(dòng)卡車專用運(yùn)輸網(wǎng)絡(luò)設(shè)計(jì)問題的特征，設(shè)計(jì)了一個(gè)基于實(shí)數(shù)編碼的 IDEA 對(duì)模型進(jìn)行求解，具體包括考慮問題特性的預(yù)處理策略、高效的實(shí)數(shù)編碼規(guī)則以及自適應(yīng)交叉算子和縮放因子,不僅保證了解的可行性, 同時(shí)還避免了復(fù)雜的不可行解修復(fù)過程以及算法的早熟收斂.

　　(3) 以 Sioux Falls 基準(zhǔn)算例, 分別在文中三種場(chǎng)景的交通網(wǎng)絡(luò)狀態(tài)進(jìn)行優(yōu)化結(jié)果對(duì)比. 結(jié)果表明, 建立的雙層規(guī)劃模型能夠得到較優(yōu)的自動(dòng)卡車專用網(wǎng)絡(luò)布局方案, 有效減小自動(dòng)卡車專用道對(duì)交通系統(tǒng)的影響, 改善系統(tǒng)運(yùn)行效率. 而且專用道設(shè)置并不會(huì)絕對(duì)增加系統(tǒng)影響, 在某些關(guān)鍵路段設(shè)置自動(dòng)卡車專用道還能夠改善交通網(wǎng)絡(luò)效率, 達(dá)到較好的效果.

　　(4) 通過對(duì)不同規(guī)模的隨機(jī)算例測(cè)試發(fā)現(xiàn), 隨著自動(dòng)卡車任務(wù)的增加 IDEA 顯著優(yōu)于 BDEA, 隨著普通車輛出行需求的增加,IDEA 與 BDEA 差距相對(duì)較小. 表明 IDEA 對(duì)能夠更好的解決運(yùn)輸任務(wù)較多的自動(dòng)卡車專用道設(shè)計(jì)問題, 為大規(guī)模網(wǎng)絡(luò)的專用道設(shè)計(jì)問題提供一定的理論參考.(5) 本文對(duì)于普通車輛出行路徑選擇行為的描述是基于靜態(tài)交通分配原理. 在未來的研究中可以進(jìn)一步以動(dòng)態(tài)的方式描述普通車輛的出行路徑選擇,以便更加準(zhǔn)確的衡量專用道的影響以及設(shè)置效果.

　　參考文獻(xiàn) (References)

　　[1] 郭戈, 許陽光, 徐濤, 等. 網(wǎng)聯(lián)共享車路協(xié)同智能交通系統(tǒng)綜述 [J]. 控制與決策, 2019, 34(11): 2375-2389.(Guo G, Xu Y G, Xu T, et al. A survey ofconnected shared vehicle-road cooperative intelligenttransportation systems[J]. Control and Decision, 2019,34(11): 2375-2389.)

　　[2] 田野. 干線物流: 進(jìn)擊的高速自動(dòng)駕駛卡車 [J]. 智能網(wǎng)聯(lián)汽車, 2021, (05): 29-31.(Tian Y. Trunk logistics: aggressive high-speedautonomous trucks[J]. Intelligent Connected Vehicles,2021, (05): 29-31.)

　　[3] Roldan S, Jallais C, Hoedemaeker M, et al. Preparingfor Safe and Successful Truck Platooning on PublicRoads: Collaboration between the United States andthe European Union[J]. Institute of TransportationEngineers. 2021, 91(11): 35-40.

　　[4] 姚志洪, 顧秋凡, 徐桃讓, 等. 考慮時(shí)延的智能網(wǎng)聯(lián)汽車混合交通流穩(wěn)定性分析 [J/OL]. 控制與決策:1-8[2022-04-09].(Yao Z H, Gu Q F, Xu T R, et al. Stability ofMixed Traffic Flow with Intelligent Connected VehiclesConsidering Time Delay[J/OL]. Control and Decision:1-8[2022-04-09].)

　　作者：吳 鵬†, 顏寶卿

轉(zhuǎn)載請(qǐng)注明來自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///jjlw/30214.html