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.

The multi-objective Time-Dependent Green Vehicle Routing Problem (MOTDGVRP) is examinated in this study. A mathematical model for the MOTDGVRP where distance, transportation time and fuel consumption are minimized is formulated. Calculation methods for the travel time and the fuel consumption across time periods with time-dependent speeds are presented. In the Time-dependent fuel consumption calculation function, distance, load, and time-dependent speed are considered simultaneously. We propose an approximate heuristic based on the Iterated Local Search (ILS) to generate the Pareto solutions. This heuristic is tested on a real-world case and the results show that the proposed heuristic can scientifically plan driving route for each vehicle, effectively reduce the total distribution costs, the vehicle fuel consumption and protect the environment.