Scoring Based Heuristic for a Platoon Formation Planning Problem with Charging Capacity

This study focuses on scheduling electric connected and autonomous vehicles (CAVs) in platoons on highways, using a tree-like network that includes charging stations with limited capacity. The aim is to reduce overall energy consumption and travel time while meeting vehicle deadlines and charging capacities. The problem can be formulated by an MILP, however, this is only feasible for small instances. To reduce the size of the MILP, we propose to select possible platoon members and leaders based on a heuristic that takes into account the specific characteristics of the vehicles. Our numerical experiments indicate that this heuristic is 36 times faster than the original MILP.