Centralized vehicle trajectory planning on general platoon sorting problem with multi-vehicle lane changing

Platooning of connected and autonomous vehicles has been extensively researched for its potential benefits in energy consumption, safety, comfort, traffic flow, and capacity. However, little attention has been given to the general platoon sorting problem of how to regulate the platoon to a desired formation and order. The problem poses a challenge as it involves multiple vehicles changing lanes in various directions, which makes them vulnerable to conflicts. This paper proposes a centralized trajectory planning method to address this problem. We construct a time-space-velocity network and formulate the problem as a multi-commodity flow model. To handle the large-scale network, we decompose the proposed model into several time-dependent least-cost path sub-problems using Lagrangian relaxation- and ADMM-based decomposition algorithms. Our method was tested through a series of experiments, which demonstrated its superiority in facilitating a faster and safer platoon sorting process compared to the existing method and achieving significant travel time savings at high traffic volumes compared to the simulations with SUMO.