Passing-Order Decision for Three-to-Two Lane Merging of Connected and Autonomous Vehicles

Lane merging is a common cause of traffic congestion and delays. The advancement of connected and autonomous vehicles can address the problem and improve the traffic efficiency. In this paper, we aim to schedule the passing order of vehicles in a three-to-two lane-merging problem and minimize the time needed for all vehicles to pass the merging intersection. We propose a three-dimensional dynamic-programming-based algorithm to solve the problem. We introduce a groupingbased strategy to reduce the computational overhead. The experimental results and SUMO simulation show that the threedimensional dynamic-programming-based algorithm achieves a comparable solution quality in much less time than an optimal approach based on mixed integer linear programming. Besides, the grouping-based strategy makes the real-time computation applicable and achieves a balancing trade-off between computation time and solution quality. The dynamic-programming-based algorithm can be further generalized for solving any <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex>-to- <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(n-1)$</tex> lane-merging problem.