A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation

In “A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation,” Luo and Larson propose a novel repeated route-then-schedule algorithmic framework to efficiently solve a complex vehicle routing and scheduling problem arising in the intelligent transportation system. The goal is to maximize the collective savings of a set of vehicles (especially heavy-duty vehicles) by utilizing the fact that platooning vehicles save energy due to reduced aerodynamic drag. In the algorithm, the original simultaneous route-and-schedule approach is decomposed into the routing stage and scheduling stage with a sophisticated learning-like feedback mechanism to update the presumed fuel cost for each vehicle traversing through each road segment. This leads to an iterative change of objective function in the routing problem and thereby changes the routes that are fed to the scheduling problem. This approach helps identify high-quality solution. The algorithmic framework leads to a very tight formulation of subproblems that can be solved in a timely manner.