  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 the 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 Astar 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 Astar 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.
