A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows

Slim Belhaiza; Pierre Hansen; Gilbert Laporte

doi:10.1016/j.cor.2013.08.010

A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows

Slim Belhaiza, Pierre Hansen, Gilbert Laporte

Research output: Contribution to journal › Article › peer-review

78 Citations (SciVal)

Abstract

This paper presents a new hybrid variable neighborhood-tabu search heuristic for the Vehicle Routing Problem with Multiple Time windows. It also proposes a minimum backward time slack algorithm applicable to a multiple time windows environment. This algorithm records the minimum waiting time and the minimum delay during route generation and adjusts the arrival and departure times backward. The implementation of the proposed heuristic is compared to an ant colony heuristic on benchmark instances involving multiple time windows. Computational results on newly generated instances are provided.

Original language	English
Pages (from-to)	269-281
Number of pages	13
Journal	Computers and Operations Research
Volume	52
DOIs	https://doi.org/10.1016/j.cor.2013.08.010
Publication status	Published - 1 Dec 2014

Keywords

Multiple time windows
Tabu search
Variable neighborhood search
Vehicle routing problem

ASJC Scopus subject areas

Computer Science(all)
Modelling and Simulation
Management Science and Operations Research

Access to Document

10.1016/j.cor.2013.08.010

Cite this

@article{c0dc1e0902b346dbb9ee98b274ac2d3b,

title = "A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows",

abstract = "This paper presents a new hybrid variable neighborhood-tabu search heuristic for the Vehicle Routing Problem with Multiple Time windows. It also proposes a minimum backward time slack algorithm applicable to a multiple time windows environment. This algorithm records the minimum waiting time and the minimum delay during route generation and adjusts the arrival and departure times backward. The implementation of the proposed heuristic is compared to an ant colony heuristic on benchmark instances involving multiple time windows. Computational results on newly generated instances are provided.",

keywords = "Multiple time windows, Tabu search, Variable neighborhood search, Vehicle routing problem",

author = "Slim Belhaiza and Pierre Hansen and Gilbert Laporte",

year = "2014",

month = dec,

day = "1",

doi = "10.1016/j.cor.2013.08.010",

language = "English",

volume = "52",

pages = "269--281",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier",

}

TY - JOUR

T1 - A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows

AU - Belhaiza, Slim

AU - Hansen, Pierre

AU - Laporte, Gilbert

PY - 2014/12/1

Y1 - 2014/12/1

N2 - This paper presents a new hybrid variable neighborhood-tabu search heuristic for the Vehicle Routing Problem with Multiple Time windows. It also proposes a minimum backward time slack algorithm applicable to a multiple time windows environment. This algorithm records the minimum waiting time and the minimum delay during route generation and adjusts the arrival and departure times backward. The implementation of the proposed heuristic is compared to an ant colony heuristic on benchmark instances involving multiple time windows. Computational results on newly generated instances are provided.

AB - This paper presents a new hybrid variable neighborhood-tabu search heuristic for the Vehicle Routing Problem with Multiple Time windows. It also proposes a minimum backward time slack algorithm applicable to a multiple time windows environment. This algorithm records the minimum waiting time and the minimum delay during route generation and adjusts the arrival and departure times backward. The implementation of the proposed heuristic is compared to an ant colony heuristic on benchmark instances involving multiple time windows. Computational results on newly generated instances are provided.

KW - Multiple time windows

KW - Tabu search

KW - Variable neighborhood search

KW - Vehicle routing problem

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

U2 - 10.1016/j.cor.2013.08.010

DO - 10.1016/j.cor.2013.08.010

M3 - Article

AN - SCOPUS:84938787400

VL - 52

SP - 269

EP - 281

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -

A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this