The cooperative sorting strategy for connected and automated vehicle platoons

Abstract This paper presents a “cooperative vehicle sorting” strategy that seeks to optimally sort connected and automated vehicles (CAVs) in a multi-lane platoon to reach an ideally organized platoon. In the proposed method, a CAV platoon is firstly discretized into a grid system, where a CAV moves from one cell to another in discrete time-space domain. Then, the cooperative sorting problem is modeled as a path-finding problem in the graphic domain. The problem is solved by the deterministic A* algorithm with a stepwise strategy, where only one vehicle can move within a movement step. The resultant shortest path is further optimized with an integer linear programming algorithm to minimize the sorting time by allowing multiple movements within a step. To improve the algorithm running time and address multiple shortest paths, a distributed stochastic A* algorithm (DSA*) is developed by introducing random disturbances to the edge costs to break uniform paths (with equal path cost). Numerical experiments are conducted to demonstrate the effectiveness of the proposed DSA* method. The results report shorter sorting time and significantly improved algorithm running time due to the use of DSA*. In addition, we find that the optimization performance can be further improved by increasing the number of processes in the distributed computing system.