We will discuss the vehicle routing problem with energy constraints, motivated by the significant role of charging in batterypowered vehicles (Electric Vehicles, mobile robots, etc.) We seek to minimize the total elapsed time for vehicles to reach their destinations by determining routes as well as recharging amounts when the vehicles do not have adequate energy for the entire journey. For a single vehicle, we formulate a mixedinteger nonlinear programming (MINLP) problem and derive properties of the optimal solution
allowing it to be decomposed into two simpler linear programming (LP) problems which we subsequently solve. For a multivehicle problem, where traffic congestion effects are included, we use a similar approach by grouping vehicles into “subflows.” We also provide an alternative flow optimization formulation where the MINLP problem is relaxed, leading to a computationally simpler problem solution.
