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

S. Allahyari, M. Salari, D. Vigo

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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
JournalEuropean Journal of Operational Research
Volume242
Issue number3
Early online date31 Oct 2014
DOIs
Publication statusPublished - 2015

Fingerprint

Hybrid Metaheuristics
Vehicle routing
Vehicle Routing Problem
Covering
Customers
Integer programming
Simulated annealing
Iterated Local Search
Mixed Integer Programming
Simulated Annealing
Metaheuristics
Vehicle routing problem
Formulation
Demand
Local search (optimization)

Cite this

@article{bed13ff3f72b4c199ba3482284f51dde,
title = "A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem",
abstract = "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.",
author = "S. Allahyari and M. Salari and D. Vigo",
year = "2015",
doi = "10.1016/j.ejor.2014.10.048",
language = "English",
volume = "242",
pages = "756--768",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "3",

}

A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem. / Allahyari, S.; Salari, M.; Vigo, D.

In: European Journal of Operational Research, Vol. 242, No. 3, 2015, p. 756-768.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

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

AU - Allahyari, S.

AU - Salari, M.

AU - Vigo, D.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

U2 - 10.1016/j.ejor.2014.10.048

DO - 10.1016/j.ejor.2014.10.048

M3 - Article

VL - 242

SP - 756

EP - 768

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -