A multi-objective optimization approach for the capacitated vehicle routing problem with time windows (CVRPTW)

Wissam Marrouche*, Haidar Harmanani, Janka Chlebikova

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Investigating complex combinatorial optimization problems such as the capacitated vehicle routing problem with time windows (CVRPTW) commonly benefits the advancement of logistic systems and telecommunications fields. CVRPTW is a elaborate strain of the well studied capacitated vehicle routing problem (CVRP) with a time window framework as an added constraint. As the problems are known to be NP-hard, meta-heuristics proficiently explore the search space to obtain near optimal solutions. In this manuscript, we explore the strength Pareto evolutionary algorithm SPEA2 hybridized with a hill climbing method as a local search, which yields a very sophisticated yet promising population based meta-heuristic algorithm. The novelty of our approach is in the AQ1 selection of multi objective evolutionary algorithm namely SPEA2, its proposed evolutionary operators, and the optimization for three targets: the total distance traveled, the number of routes, and the average time per route - a newly introduced objective -, which offers an interesting trade-off opportunity scenarios for practitioners or supply chain managers. Based on our experimental results, such multiple objective optimization can guide the search toward favorable reduction of the total distance as well as offering a margin of compromise in the selection of the objectives of the final solution in general. The presented algorithm is a Python implementation tested extensively on the Solomon's instances benchmark. Encouraging results are recorded (sometimes reaching the best
known in literature) and hints for further refinement are proposed for future research.
Original languageEnglish
Title of host publicationComputational Intelligence
EditorsJonathan Garibaldi, Christian Wagner, Thomas Bäck, Hak-Keung Lam, Marie Cottrell, Kurosh Madani, Kevin Warwick
Number of pages23
ISBN (Electronic)9783031462214
ISBN (Print)9783031462207, 9783031475542
Publication statusPublished - 2 Nov 2023
EventIJCCI 2021 : 13th International Joint Conference on Computational Intelligence - Valletta, Malta
Duration: 25 Oct 202127 Oct 2021

Publication series

NameStudies in Computational Intelligence
ISSN (Print)1860-949X
ISSN (Electronic)1860-9503


ConferenceIJCCI 2021 : 13th International Joint Conference on Computational Intelligence


  • capacitated vehicle routing problem with time windows
  • strength pareto evolutionary algorithm
  • hill climbing
  • multi objective optimization
  • evolutionary operators
  • meta-heuristics

Cite this