The Green Vehicle Routing Problem with Capacitated Alternative Fuel Stations

This work addresses the problem of efficiently routing a set of Alternative Fuel Vehicles (AFVs), considering that, during their trips, some stops at Alternative Fuel Stations (AFSs) have to be planned. Every AFV leaves from a common depot and returns to it, after serving a subset of customers. Due to some forms of contract with the drivers, an upper bound is usually imposed on the duration of each route. The aim is to dene the optimal routing of the AFVs in order to minimize the total traveled distance. This problem is known in the literature as the Green Vehicle Routing Problem (G-VRP). Several Mixed Integer Linear Programming (MILP) formulations have been already presented to model it. The G-VRP assumes that an unlimited number of vehicles may be simultaneously refueled at the same AFS. This hypothesis is not realistic, since AFSs typically have a very small number of refueling locations. To manage this issue, we propose an extension of the G-VRP that models the more realistic situation where a capacity is associated with every AFS, bounding the number of vehicles that can simultaneously refuel. The capacity constraint makes more challenging the scheduling of the stops at the AFSs, since now the AFSs become a shared resource of the problem. For this new version of the GVRP, we propose a MILP formulation and a heuristic approach. Preliminary numerical results have been carried out on some benchmark instances, properly adapted to this extension of the G-VRP.