Optimization of routes for a fleet of plug-in hybrid vehicles Mathematical modeling and solution procedures

Abstract

We have developed mathematical models and optimization methods for the problem of routing a fleet of plug-in hybrid vehicles. This problem is referred to as the hybrid vehicle routing problem (hybrid VRP) and it is a generalization of the traditional VRP, which regards only one type of propellant. The most cost-efficient routes for hybrid vehicles may differ substantially from corresponding routes for other types of vehicles. Our models consider a homogeneous fleet of plug-in hybrid vehicles, constrained by both load capacity limits and time windows for delivery. Recharging of the vehicle’s battery is optional, and can be done only at special recharging sites (nodes). We consider the recharging times being either constant or dependent on the battery charge level at arrival at the recharging node. The hybrid VRP has not yet been studied to a large degree. To the best of our knowledge, there is no successful implementation of a mathematical solution procedure for the hybrid VRP including separate customer and recharging nodes. The hybrid VRPs considered are modeled as mixed integer linear programs and solved using column generation, which separates each problem into a set covering master problem, and a shortest path subproblem. Our tests show that the hybrid VRPs are time-consuming to solve exactly using conventional branch-and-cut methods. Our column generation approach combined with the dominance criteria reduces, however, the solution times considerably.