2025

Conférence

2025 11th International Conference on Control, Decision and Information Technologies (CoDIT)

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.

@INPROCEEDINGS{11321705,
  author={Dridi, Atef and Tayachi, Dalila and Moukrim, Aziz and Said, Lamjed Ben},
  booktitle={2025 11th International Conference on Control, Decision and Information Technologies (CoDIT)}, 
  title={A Multi-Start Tabu Search with Set Partitioning for the Green VRP}, 
  year={2025},
  volume={1},
  number={},
  pages={2828-2833},
  keywords={Runtime;Computational modeling;Vehicle routing;Machine learning;Maintenance engineering;Search problems;Computational efficiency;Fuels;Information technology;Optimization;Green VRP;set partitioning;combinatorial optimization},
  doi={10.1109/CoDIT66093.2025.11321705}}