A Coevolutionary Algorithm for Cooperative Platoon Formation of Connected and Automated Vehicles

This paper proposes a coevolutionary algorithm to optimize longitudinal trajectories of multiple vehicles with an energy-aware non-linear objective during the cooperative platoon formation process. In this work, an adaptive encoding scheme is adopted to represent trajectories as knot vectors of parametric cubic splines, and therefore the original problem is reformulated into a constrained numerical optimization version. The number of knots can be adjusted to trade-off between the shape flexibility and computation efficiency. Further, the proposed coevolutionary algorithm decomposes the initially high-dimensional problem into smaller subproblems, significantly reducing the complexity. A hybrid evolutionary algorithm is developed as an optimizer for subproblems. Additionally, a branch-and-bound strategy and a Tabu search component are integrated into the steepest ascent hill-climbing algorithm to speed up convergences within the local exploitation phase. Numerical experiments are conducted on extensive scenarios with different platooning sizes and initial separations. Experimental results indicate the superiority of the proposed approach in optimality and stability with reasonable sub-second computation time for real-life applications.