Itinerary Planning for Cooperative Truck Platooning

A cooperative truck platoon is a set of virtually linked trucks driving with a small intra-vehicle gap enabled by connected and automated vehicle technologies. One of the primary benefits of truck platooning is energy savings due to the reduction of aerodynamic drag on the platooned vehicles. The focus of this paper is on scheduling travel itineraries of a given set of trucks to maximize platooning opportunities and the corresponding energy savings. By constructing a time-expanded network, we formulate the problem as a minimum concave-cost network flow problem, and devise a number of solution methodologies to find the optimal or high-quality solutions. The solution methodologies include an outer approximation algorithm for solving a mixed-integer convex minimization reformulation of the problem, a dynamic-programming-based heuristic scalable to large-scale instances, and a fast approximation algorithm with guaranteed performance for a restrictive version of the problem. All the proposed algorithms are examined and benchmarked on medium to large networks under various test scenarios. The numerical results demonstrate the efficiency of the proposed methods and their applicability in real-world settings.