聯網自駕車線道合併與擴增之通過順序決策

Abstract

車道合併是導致交通擁堵的主要原因之一，因為車道數目減少， 而其他車輛的行為通常是不可預測的。通過利用車輛對車輛和車輛對 基礎設施的通信，以及自動駕駛車輛的特點，車輛可以以較低的時間 成本達成共識，從而緩解交通擁堵。本文旨在對在兩對一車道合併情 景下車輛的通過順序進行調度，其中每對車輛之間的等待時間不同。 首先，我們對問題進行了形式化，提出了一種無車道變換的基於動態 規劃的算法，用全局視角對所有車輛進行調度。此外，我們引入了一 種考慮車道變換的基於動態規劃的算法，進一步縮短了最後一輛車的 預定進入時間。受到車道合併問題的啟發，我們提出了在M-N車道擴 展情景下的負載平衡調度問題。負載平衡的重要性在於，如果車道上 的負載不平衡，維護不僅會變得昂貴，而且會耗費時間。因此，我們 對問題進行了形式化，並首先提出了一種處理每輛車輛出車道決策的 混合整數線性規劃（MILP）方法。然後，我們提出了一種啟發式方法，提高了所有車輛的通過效率。車道合併的實驗結果表明，相比於 無車道變換的先來先服務（FCFS）、有車道變換的FCFS以及無車道變 換的基於動態規劃的算法，考慮車道變換的基於動態規劃的算法找到 了更優的解決方案。負載平衡問題的實驗結果表明，雖然我們的啟發 式方法可能無法找到最優解，但它仍然比FCFS方法提供了更優的解決 方案。

Lane merging is a major reason causing traffic congestion because the number of lanes decreases and the behavior of other vehicles is usually unpredictable. By taking advantage of vehicle-to-vehicle and vehicle-to-infrastructure communication, as well as the characteristics of autonomous vehicles, vehicles can reach a consensus with low time cost, and traffic congestion can be alleviated. In this thesis, we aim to schedule the passing order of vehicles in a two-to-one lane-merging scenario where the waiting times between each pair of vehicles are different. We first formulate the problem and come up with a dynamic programming (DP)-based algorithm that schedules all vehicles with a global perspective. Moreover, we introduce a DP-based algorithm that takes lane changing into consideration, further reducing the scheduled entering time of the last vehicle. Inspired by the lane-merging problem, we come up with a load-balancing scheduling problem under M-N lane-expanding scenarios. The significance of load balancing is that if the load on lanes is unbalanced, maintenance will not only be expensive but also time-consuming. Therefore, we formulate the problem and first propose a Mixed-Integer Linear Programming (MILP) approach that handles the decision of outgoing lanes for each vehicle. Then, we present a heuristic approach that reduces the scheduled entering time of the last vehicle. Experimental results for lane merging show that the DP-Based Algorithm with Lane Changing finds a better solution compared to First Come First Serve (FCFS) without Lane Changing, FCFS with Lane Changing, and the DP-Based Algorithm without Lane Changing. Experimental results for the load-balancing problem demonstrate that our heuristic approach, although it may not find the optimal solution, still provides a better solution than FCFS