Dynamic vehicle relocation and assignment for an intelligent vehicle platooning transit system

An emerging on-demand urban transit system, namely, Intelligent Vehicle Platooning Transit (IVPT), promises to provide rapid, flexible, comfortable and affordable passenger mobility services. IVPT features direct station-to-station transit services by utilizing dynamically formed platoons possibly composed of different types of vehicles running on exclusive traffic lanes and through intersections controlled by transit signal priority. This paper defines, formulates, and solves a dynamic vehicle relocation and assignment problem for the daily operations of an IVPT system. The focus is on the modeling and solution methods for the system’s real-time vehicle relocation and assignment decisions, which primarily include two parts: 1) Optimal relocation of service vehicles from low-demand stations to high-demand stations so as to mitigate the supply-demand imbalance; 2) optimal assignment of vehicles to carry matched passengers from their boarding stations to alighting stations. With its implementation in the rolling horizon framework, a mixed integer linear programming model is formulated, and both an exact and a heuristic algorithm are designed and tested. The exact method is powered by Lagrangian relaxation, embedding a dynamic programming algorithm for solving its decomposed relaxed Lagrangian subproblems and a tailored vehicle-removing-and-reloading algorithm for finding feasible solutions. The heuristic method relies on adaptive large neighborhood search, integrating several problem-specific destroy and repair subheuristics to effectively explore the solution space and enhance search diversity. A few illustrative numerical examples and a real-world case study are employed to validate the advantages of this new demand-responsive, platoon-based transit system, along with the efficacy and performance of the proposed solution methods for real-time vehicle relocation and assignment.