  The problem of how to coordinate a large fleet of trucks with given itinerary
to enable fuel-efficient platooning is considered. Platooning is a promising
technology that enables trucks to save significant amounts of fuel by driving
close together and thus reducing air drag. A setting is considered in which
each truck in a fleet is provided with a start location, a destination, a
departure time, and an arrival deadline from a higher planning level.
Fuel-efficient plans should be computed. The plans consist of routes and speed
profiles that allow trucks to arrive by their arrival deadlines. Hereby, trucks
can meet on common parts of their routes and form platoons, resulting in
decreased fuel consumption.
  We formulate a combinatorial optimization problem that combines plans
involving only two vehicles. We show that this problem is hard to solve for
large problem instances. Hence a heuristic algorithm is proposed. The resulting
plans are further optimized using convex optimization techniques. The method is
evaluated with Monte Carlo simulations in a realistic setting. We demonstrate
that the proposed algorithm can compute plans for thousands of trucks and that
significant fuel savings can be achieved.
