The global warming phenomenon and other environmental concerns have motivated the use of zero emission vehicles (ZEV) in different transportation operations ranging from postal delivery to grocery distribution. The use of ZEV leads to new optimization problems. One of these problems is the green vehicle routing problem (Green-VRP): an extension of the well-known vehicle routing problem arising when a fleet of ZEV based at a central depot services the demand of a set of geographically-spread customers. The particular feature of the Green VRP comes from the limited autonomy of ZEV. Indeed, to assure the feasible completion of trips, alternative fuel stations (AFS) have to be visited en-route in order to refill the tank (or recharge the battery). Additionally, a maximum duration constraint is also imposed to the routes in a Green-VRP.

In this work we propose a route-first cluster-second metaheuristic that explores the space of giant tours (where all customers are visited ignoring the autonomy and maximum duration constraints) using a simulated annealing mechanism. To extract a Green-VRP solution from a given giant tour we use an optimal splitting procedure that solves a shortest path problem in an auxiliary graph which arcs represent feasible routes. Moreover, infeasible routes with respect to the autonomy constraint are repaired by inserting the visits to AFS using a heuristic procedure.

Computational experiments, on a set of standard instances, show that the proposed metaheuristic obtains competitive results when compared to state-of-the-art methods that include: a modified Clarke and Wright savings heuristic, a density-based clustering algorithm, and a hybrid variable neighborhood search/tabu search.