The Recharging Vehicle Routing Problem

This research introduces the recharging vehicle routing problem (RVRP), a new variant of the well-known vehicle routing problem (VRP) where vehicles with limited range are allowed to recharge at customer locations mid-tour. The problem has potential practical applications in real-world routing problems where electric vehicles with fast recharging capabilities may be used for less-than-truckload (LTL) deliveries in urban areas. The general problem is introduced as a capacitated problem (CRVRP) and a capacitated problem with customer time window constraints (CRVRP-TW). A problem statement is formulated and experimental results along with derived solution bounds are presented. Intuitive results are observed when the vehicle range is constrained and when recharging time is lengthy. It is also shown that the average tour length highly correlates with derived solution bounds. Estimations of the average tour length can be used in planning application to estimate energy costs and consumption as a function of vehicle and customer characteristics.