應用於自動駕駛車輛車道合併與車道變換排程問題之最佳化方法

Optimization Approaches for Scheduling Problems of Lane Merging and Lane Changing of Connected and Autonomous Vehicles

林尚謙(Shang-Chien Lin)

指導教授 ： 江蕙如

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202001065

摘要

車道合併和車道變換是導致交通堵塞和延遲的主要來源。隨著自動駕駛技術的發展，我們可以借助車對車或車與基礎設施間的通信，來緩解車道合併和車道變換帶來的堵塞和延遲。在這篇論文中，我們先提出一個兩車道合併的情景，並發表一種動態規劃演算法來找到最佳解。接著，我們將問題延伸為一個連續車道合併的情景，我們分析了應用相同動態規劃演算法來處理此連續車道合併問題的困難處，並提出了改進的版本來解決它。實驗結果顯示，與先前研究使用的貪婪演算法相比，我們的動態規劃演算法可以有效地降低所有車輛通過合併點所需的時間，並減少所有車輛的平均延遲。第二部分，我們提出一個強制性車道變換的情景，並使用混合整數線性規劃（MILP）來找到最佳解，我們還提出了一種基於遞增窗口的MILP演算法，來減少所需的計算時間。實驗結果顯示與原本的MILP相比，遞增窗口的MILP可以花費更少的時間來獲得幾乎相同的表現。

關鍵字

自動駕駛車輛 ； 車聯網 ； 智慧運輸系統 ； 車道合併 ； 車道變換 ； 排程演算法

並列摘要

Lane merging and lane changing are the major sources causing traffic congestion and delay. With the help of vehicle-to-vehicle or vehicle-to-infrastructure communication and autonomous driving technology, there are opportunities to alleviate congestion and delay resulting from lane merging and lane changing. In this thesis, we first formulate and propose a dynamic programming algorithm to find the optimal solution for a two-lane merging scenario. We also extend the problem to a consecutive lane-merging scenario. We show the difficulty to apply the original dynamic programming to the consecutive lane-merging scenario and propose an improved version to solve it. Experimental results show that our dynamic programming algorithm can efficiently minimize the time needed for all vehicles to go through the merging point and reduce the average delay of all vehicles, compared with some greedy methods. Then, We formulate a mandatory lane changing scenario and propose a mixed-integer linear programming (MILP) to find the optimal solution. We also propose an incremental-window-based MILP algorithm to reduce the computation time. Experimental results show that our incremental-window-based MILP algorithm can take much less time to achieve almost the same solution quality, compared with the original MILP.

並列關鍵字

Autonomous Vehicle ； Internet of Vehicle ； Intelligent Transportation System ； Lane Merging ； Lane Changing ； Scheduling Algorithms

參考文獻

[1] J. B. Kenney, “Dedicated short-range communications (DSRC) standards in the united states,” Proceedings of the IEEE, vol. 99, pp. 1162–1182, July 2011.

[2] A. Uno, T. Sakaguchi, and S. Tsugawa, “A merging control algorithm based on inter-vehicle communication,” in IEEE International Conference on Intelligent Transportation Systems (ITSC), pp. 783-787, October 1999.

[3] J. Rios-Torres and A. A. Malikopoulos, “A survey on the coordination of connected and automated vehicles at intersections and merging at highway on-ramps,” IEEE Transactions on Intelligent Transportation Systems (T-ITS), vol. 18, pp. 1066-1077, May 2017.

[4] V. Milanes, J. Godoy, J. Villagra, and J. Perez, “Automated on-ramp merging system for congested traffic situations,” IEEE Transactions on Intelligent Transportation Systems (T-ITS), vol. 12, pp. 500-508, June 2011.

[5] Y. Wang, W. E, W. Tang, D. Tian, G. Lu, and G. Yu, “Automated on-ramp merging control algorithm based on internet-connected vehicles,” IET Intelligent Transport Systems, vol. 7, pp. 371-379, December 2013.