Vehicle Platooning
2026-08-10 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study how to arrange groups of vehicles driving closely together (called platoons) to save energy. They focus on two goals: using the least total energy overall and reducing the highest energy used by any single vehicle. They classify which versions of this problem can be solved quickly and which are very hard, and they create smart methods to find nearly best solutions when exact answers are too complex. They also handle cases with limited information and situations where only small changes in the order of vehicles are allowed, providing practical ways to improve energy efficiency in vehicle platooning.
vehicle platooningenergy consumptionsequencing problemresequencingpolynomial-time algorithmscomputational complexityapproximation schemesheuristicsroad networksenergy efficiency
Authors
Zhi-Long Chen, Nicholas G. Hall
Abstract
Vehicle platooning offers significant benefits, including reduced energy consumption, lower emissions, improved road utilization, enhanced safety, and reduced driver fatigue. As intelligent driving technologies continue to advance, platoon sizes are expected to increase substantially, making the efficient sequencing and resequencing of vehicles increasingly important. We study the vehicle platoon sequencing and resequencing problem on road networks with varying segment lengths under two fundamental objectives: minimizing total energy consumption and minimizing the maximum energy consumption of any vehicle. For the typically encountered combinations of vehicle and road characteristics, we provide a complete computational complexity classification, either developing polynomial-time algorithms or proving computational intractability. For several intractable cases, we design fully polynomial-time approximation schemes and polynomial-time heuristics with provable performance guarantees. A computational study demonstrates that the proposed heuristics achieve average solutions within 1\% of optimal. We also consider settings in which only limited information about position-dependent energy savings is available and develop a heuristic with bounded worst-case performance. In addition, we present an efficient algorithm for on-road vehicle resequencing when only limited position changes are permitted. Together, these results provide a comprehensive algorithmic framework for energy-efficient vehicle platoon sequencing and resequencing.