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

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

doi:10.1016/j.tre.2015.12.001

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

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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

124 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	32-52
Aantal pagina's	21
Tijdschrift	Transportation Research. Part E: Logistics and Transportation Review
Volume	86
DOI's	https://doi.org/10.1016/j.tre.2015.12.001
Status	Gepubliceerd - 1 feb. 2016
Extern gepubliceerd	Ja

Financiering

The authors thank Editor Prof. Jiuh-Biing Sheu and four anonymous referees for their constructive suggestions, which helped improve the content and presentation of this article. They also thank Prof. W.E.H. Dullaert for his valuable comments and feedback. The work of the third author is partially supported by GRF grant CUHK414313 from the Hong Kong Research Grants Council.

Toegang tot document

10.1016/j.tre.2015.12.001

Andere bestanden en links

Link to publication in Scopus

Citeer dit

@article{a623342cca424272a3b13377e496b6e3,

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",

month = feb,

day = "1",

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",

}

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/2/1

Y1 - 2016/2/1

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 - https://www.scopus.com/pages/publications/84953807312

U2 - 10.1016/j.tre.2015.12.001

DO - 10.1016/j.tre.2015.12.001

M3 - Article

AN - SCOPUS:84953807312

SN - 1366-5545

VL - 86

SP - 32

EP - 52

JO - Transportation Research. Part E: Logistics and Transportation Review

JF - Transportation Research. Part E: Logistics and Transportation Review

ER -

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

Samenvatting

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit