基于雙層規劃的自動卡車運輸專用網絡設計優化

　　摘 要: 為保障交通系統安全性和卡車貨運自動化的發展, 有必要對自動卡車貨物運輸專用網絡進行科學規劃與布局. 考慮自動卡車專用道會減少普通車輛的路權, 對普通車輛的出行路徑選擇行為造成影響. 首先, 從路網整體出發, 以系統出行時間最小為目標, 充分考慮路網普通車輛的出行路徑選擇行為, 構建了一種新的自動卡車專用運輸網絡設計的雙層規劃模型. 其次, 提出了一種基于實數編碼的改進差分進化算法求解建立的雙層規劃模型, 不僅保證解的可行性，還避免了復雜的不可行解修復過程. 最后, 通過 Sioux Falls 基準網絡實例和大量隨機算例對比測試結果驗證了模型和算法的有效性.

　　關鍵詞: 自動卡車;專用道網絡;路徑規劃;雙層規劃;自適應差分進化算法

　　引 言

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

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

　　目前, 專用道設置規劃問題 (Lane ReservationProblem, LRP) 得到了國內外研究學者的廣泛關注. 研究應用場景主要可分為特殊事件的臨時專用道設置規劃、危險品運輸的專用道設置規劃、自動卡車專用道設置規劃以及公交專用道的設置規劃等方面. 絕大多數研究集中于公交專用道優化. 如,Zhao 等[5] 提出一種動態公交專用道設置策略,以交叉口平均延誤最小化為目標建立混合整數非線性規劃. Han 等[6] 針對部分路段旅行時間信息, 研究隨機公交車專用道優化問題, 提出面向服務的分布式魯棒優化模型. 少部分研究了特殊事件的臨時專用道和危險品專用道設置規劃.

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

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

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

　　1 問題描述及符號定義

　　1.1 問題描述

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

　　但是, 一旦某些路段上設置了專用道, 將會對該路段上的普通車輛產生負面影響, 使該路段上普通車輛可使用的道路容量降低, 造成道路擁擠, 行駛時間增大. 與此同時, 城市網絡的交通狀態也將改變, 專用道路段上原本的普通車輛可能重新進行路徑規劃, 導致網絡中的普通車輛流量重新分配. 而普通車輛的路徑規劃結果反過來又將直接決定路網整體行駛時間, 影響了專用道布局方案. 因此, 本文從系統的角度出發,充分考慮專用道與普通車輛之間的相互影響, 以專用道負面影響最小為目標, 確定能夠保證運輸任務都能準時完成的專用道優化設置方案.

　　1.2 假設條件

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

　　2 模型建立

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

　　3 算法設計

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

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

　　4 案例分析

　　為了驗證本文構建的模型和改進算法的有效性,以 Sioux Falls 為案例, 與不同場景下求解的專用道方案進行效果對比分析, 對應的場景描述見表 2. 此外,為驗證 IDEA 中預處理與實數編碼結合的有效性, 隨機生成仿真算例進行測試, 與傳統 0-1 編碼的差分進化算法 (BDEA) 進行對比.

　　4.1 參數敏感性分析

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

　　4.2 實例分析

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

　　5 結論

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

　　(3) 以 Sioux Falls 基準算例, 分別在文中三種場景的交通網絡狀態進行優化結果對比. 結果表明, 建立的雙層規劃模型能夠得到較優的自動卡車專用網絡布局方案, 有效減小自動卡車專用道對交通系統的影響, 改善系統運行效率. 而且專用道設置并不會絕對增加系統影響, 在某些關鍵路段設置自動卡車專用道還能夠改善交通網絡效率, 達到較好的效果.

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

　　參考文獻 (References)

　　[1] 郭戈, 許陽光, 徐濤, 等. 網聯共享車路協同智能交通系統綜述 [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]. 智能網聯汽車, 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] 姚志洪, 顧秋凡, 徐桃讓, 等. 考慮時延的智能網聯汽車混合交通流穩定性分析 [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].)

　　作者：吳 鵬†, 顏寶卿

轉載請注明來自發表學術論文網：http://www.cnzjbx.cn/jjlw/30214.html