This paper tackles the Green Vehicle Routing Problem (GVRP), where vehicles with limited driving range must visit customers while recharging at Alternative Fuel Stations (AFSs). We propose a Multi-Start Tabu Search with Set Partitioning (MSTS-SP) approach structured in two phases. In the first phase, MSTS-SP uses a new constructive heuristic, Randomized Sectoring with Repair, to generate diverse initial solutions, which are then improved through multiple independent tabu search runs. The high-quality routes found during these runs are collected into a global pool. In the second phase, an exact set partitioning model is applied to this pool to select the best combination of routes. Computational experiments on 52 GVRP benchmark instances show that MSTS-SP matches 46 known best solutions (88%) and improves upon the best known solution for one large instance. These results demonstrate that MSTS-SP offers a competitive balance between solution quality and computational efficiency compared to state-of-the-art methods.

This paper addresses the Green Vehicle Routing Problem (GVRP) which is a variant of the VRP that uses alternative fuel vehicles (AFVs) to perform routes. Since AFVs have limited fuel tank capacity, refueling among the routes at alternative fuel stations (AFSs) is considered. To solve the problem, we propose an improved version of the tabu search metaheuristic. The proposed algorithm relies on two main components: a local search component and a perturbation component. Computational results show that our approach is highly effective in terms of solution quality and CPU time.