A multi-space sampling heuristic for the green vehicle routing problem

The green vehicle routing problem (Green VRP) is an extension of the VRP in which routes are performed using alternative fuel vehicles (AFVs). AFVs have limited tank capacity, so routes may visit alternative fuel stations (AFSs) en-route. We propose a simple yet effective two-phase heuristic to tackle the Green VRP. In the first phase our heuristic builds a pool of routes via a set of randomized route-first cluster-second heuristics with an optimal AFSs insertion procedure. In the second phase our approach assembles a Green VRP solution by solving a set partitioning formulation over the columns (routes) stored in the pool. To test our approach, we performed experiments on a set of 52 instances from the literature. The results show that our heuristic is competitive with state-of-the-art methods. Our heuristic unveiled 8 new best-known solutions, matched another 40, and delivered solutions with an average gap of 0.14% for the 4 remaining instances.