Solving the Green Vehicle Routing Problem with Capacitated Alternative Fuel Stations

The Green Vehicle Routing Problem (GVRP) aims to efficiently route a fleet of Alternative Fuel Vehicles (AFVs), in order to serve a set of customers, minimizing the total travel distance. Each AFV leaves from a common depot, serves a subset of customers and returns to the depot, without exceeding a maximum duration. Due to their limited driving range, the AFVs may need to refuel one or more times at the Alternative Fuel Stations (AFSs), along their route. In this work, we introduce the GVRP with Capacitated AFSs (GVRP-CAFS) in which only a limited number of AFVs can refuel at the same time at each AFS to account for their limited capacity. In order to solve the GVRP-CAFS, we propose an exact approach in which a route is the composition of paths, each handling a subset of customers without intermediate stops at AFSs. Firstly, all feasible non-dominated paths are generated. Secondly, via a path-based Mixed Integer Programming model, the paths are selected and properly combined each other to generate the routes of the optimal GVRP-CAFS solution. To reduce the computational times, a relaxed version of the path-based model is solved and then, the violated constraints are iteratively added. Some preliminary results are also discussed.