We introduce the Green Vehicle Routing Problem with Capacitated Alternative Fuel Stations (GVRP-CAFS) aimed at routing Alternative Fuel Vehicles (AFVs), serving all customers at minimum total travel distance. A route starts/ends from/to a common depot where the AFVs are based at, serving a sub-set of customers, with possible intermediate stops at stations for being refueled. Unlike the GVRP, in the GVRP-CAFS, at most ƞ AFVs can be simultaneously refueled at each station, being ƞ the number of its refueling pumps. We consider both the scenario in which stations are owned by the transportation company and that one where they are public. In the latter case, refueling pumps can be reserved in advance for preventing unpredictable waiting times at stations during the routes.

We propose both an Arc and a Path-based Mixed Integer Linear Programming (MILP) models where the latter is defined on only feasible non-dominated paths. Both are extended to model also multiple time windows associated with stations in the public scenario. We propose also two Cutting Plane approaches where the relaxations are obtained dropping the stations capacity constraints and the cuts are obtained in two different ways. In the first approach, at each iteration, we add a single cut that consists in restoring the capacity constraint violated by the current solution. In the second one, we add a pull of cuts consisting in capacity constraints that can be luckily violated in the next iterations. The solutions of both MILP models are compared with those of the Cutting Plane approaches.