The Green Vehicle Routing Problem with Reserved Capacitated

The Green Vehicle Routing Problem (G-VRP) aims at routing Alternative Fuel Vehicles (AFVs), based at a common depot, for serving a set of customers. Each route starts and ends from/at the depot, serving a subset of customers. Due to its limited driving range, an AFV may stop at Alternative Fuel Stations (AFSs) along its route. While in the literature the AFS capacity is assumed unlimited, we address the extension of the G-VRP with Capacitated AFSs where at most η AFVs can be simultaneously refueled at an AFS with η fueling pumps. We model it by both Arc and Path based Mixed Integer Linear Programming. The latter model (P-MILP) considers only feasible nondominated paths. We also design two efficient slightly different P-MILP based Cutting Planes methods where in the relaxations, the AFS capacity constraints are dropped. Moreover, at each iteration, in the former, a cut is added for restoring the capacity constraint violated by the current solution while, in the latter, a set of cuts are included for restoring the capacity constraints that may be luckily violated later. For preventing possible queues at AFSs, the possibility of reserving them is considered. Then, our approaches are extended introducing time windows at AFSs for modelling their availability. Results, on both benchmark and realistic instances, are compared in scenarios with and without AFS reservation.