A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph

David S.W. Lai, Ozgun Caliskan Demirag, Janny M.Y. Leung

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We study a time-constrained heterogeneous vehicle routing problem on a multigraph where parallel arcs between pairs of vertices represent different travel options based on criteria such as time, cost, and distance. We formulate the problem as a mixed-integer linear programming model and develop a tabu search heuristic that efficiently addresses computational challenges due to parallel arcs. Numerical experiments show that the heuristic is highly effective and that freight operators can achieve advantages in cost and customer service by considering alternative paths, especially when route duration limits are restrictive and/or when vehicles of smaller capacity are dispatched to serve remote customers.

LanguageEnglish
Pages32-52
Number of pages21
JournalTransportation Research Part E: Logistics and Transportation Review
Volume86
DOIs
StatePublished - 2016

Fingerprint

tabu
Vehicle routing
Tabu search
heuristics
customer
costs
Linear programming
Costs
programming
travel
experiment
Experiments
time
Vehicle routing problem
Heuristics
Operator
Mixed integer linear programming
Customer service
Freight
Time costs

Keywords

  • Fixed sequence arc selection
  • Heterogeneous fleet
  • HVRP
  • Multigraph
  • Tabu search
  • Vehicle routing

Cite this

@article{9239d3ada5b842d1a3072d961ebad748,
title = "A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph",
abstract = "We study a time-constrained heterogeneous vehicle routing problem on a multigraph where parallel arcs between pairs of vertices represent different travel options based on criteria such as time, cost, and distance. We formulate the problem as a mixed-integer linear programming model and develop a tabu search heuristic that efficiently addresses computational challenges due to parallel arcs. Numerical experiments show that the heuristic is highly effective and that freight operators can achieve advantages in cost and customer service by considering alternative paths, especially when route duration limits are restrictive and/or when vehicles of smaller capacity are dispatched to serve remote customers.",
keywords = "Fixed sequence arc selection, Heterogeneous fleet, HVRP, Multigraph, Tabu search, Vehicle routing",
author = "Lai, {David S.W.} and {Caliskan Demirag}, Ozgun and Leung, {Janny M.Y.}",
year = "2016",
doi = "10.1016/j.tre.2015.12.001",
language = "English",
volume = "86",
pages = "32--52",
journal = "Transportation Research Part E: Logistics and Transportation Review",
issn = "1366-5545",
publisher = "Elsevier Limited",

}

A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. / Lai, David S.W.; Caliskan Demirag, Ozgun; Leung, Janny M.Y.

In: Transportation Research Part E: Logistics and Transportation Review, Vol. 86, 2016, p. 32-52.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph

AU - Lai,David S.W.

AU - Caliskan Demirag,Ozgun

AU - Leung,Janny M.Y.

PY - 2016

Y1 - 2016

N2 - We study a time-constrained heterogeneous vehicle routing problem on a multigraph where parallel arcs between pairs of vertices represent different travel options based on criteria such as time, cost, and distance. We formulate the problem as a mixed-integer linear programming model and develop a tabu search heuristic that efficiently addresses computational challenges due to parallel arcs. Numerical experiments show that the heuristic is highly effective and that freight operators can achieve advantages in cost and customer service by considering alternative paths, especially when route duration limits are restrictive and/or when vehicles of smaller capacity are dispatched to serve remote customers.

AB - We study a time-constrained heterogeneous vehicle routing problem on a multigraph where parallel arcs between pairs of vertices represent different travel options based on criteria such as time, cost, and distance. We formulate the problem as a mixed-integer linear programming model and develop a tabu search heuristic that efficiently addresses computational challenges due to parallel arcs. Numerical experiments show that the heuristic is highly effective and that freight operators can achieve advantages in cost and customer service by considering alternative paths, especially when route duration limits are restrictive and/or when vehicles of smaller capacity are dispatched to serve remote customers.

KW - Fixed sequence arc selection

KW - Heterogeneous fleet

KW - HVRP

KW - Multigraph

KW - Tabu search

KW - Vehicle routing

UR - http://www.scopus.com/inward/record.url?scp=84953807312&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84953807312&partnerID=8YFLogxK

U2 - 10.1016/j.tre.2015.12.001

DO - 10.1016/j.tre.2015.12.001

M3 - Article

VL - 86

SP - 32

EP - 52

JO - Transportation Research Part E: Logistics and Transportation Review

T2 - Transportation Research Part E: Logistics and Transportation Review

JF - Transportation Research Part E: Logistics and Transportation Review

SN - 1366-5545

ER -