A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem

Somayeh Allahyari, Majid Salari, Daniele Vigo

Research output: Contribution to journalArticlepeer-review

75 Citations (SciVal)


We propose a generalization of themulti-depot capacitated vehicle routing problem where the assumption of visiting each customer does not hold. In this problem, called the Multi-Depot Covering Tour Vehicle Routing Problem (MDCTVRP), the demand of each customer could be satisfied in two different ways: either by visiting the customer along the tour or by "covering" it. When a customer is visited, the corresponding demand is delivered at its location. A customer is instead covered when it is located within an acceptable distance from at least one visited customer from which it can receive its demand. For this problem we develop two mixed integer programming formulations and a hybrid metaheuristic combining GRASP, iterated local search and simulated annealing. Extensive computational tests on this problem and some of its variants clearly indicate the effectiveness of the developed solution methods.

Original languageEnglish
Pages (from-to)756-768
Number of pages13
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 1 May 2015

Bibliographical note

Publisher Copyright:
© 2014 Elsevier B.V. All rights reserved.


  • Hybrid metaheuristic
  • Multi-depot capacitated covering tour vehicle routing problem
  • Simulated annealing
  • Vehicle routing

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem'. Together they form a unique fingerprint.

Cite this