Why to climb if one can jump: a hill jumping algorithm for the vehicle routing problem with time windows

David Mester, Olli Bräysy, Wout Dullaert

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

The most common approaches to solve the variants of the well-known vehicle routing problem are based on metaheuristic hill-climbing search. The deficiency of these methods is slow local search based hill climbing that often is restricted to limited local neighborhood. In this paper we suggest a novel new two-phase metaheuristic that escapes the local minima with jumps of varying size, instead of step by step local hill climbing. The initial solution is first generated with a powerful ejection pool heuristic. The key idea of the improvement phase is to combine large neighborhood search with standard guided local search metaheuristic in a novel way, allowing improved search diversification and escape from local minima in more efficient way through jumps. The algorithm has been tested on the standard Gehring and Homberger benchmarks for the vehicle routing problem with time windows and the results indicate very competitive performance. We found 12 new and 43 matched best-known solutions and the best overall results for all problem sizes at comparable computation times.

LanguageEnglish
Title of host publicationComputational Methods and Models for Transport
Subtitle of host publicationNew Challenges for the Greening of Transport Systems
PublisherSpringer International Publishing
Chapter6
Pages87-96
Number of pages10
ISBN (Electronic)9783319544908
ISBN (Print)9783319544892 , 9783319854052
DOIs
StatePublished - 2018

Publication series

NameComputational Methods in Applied Sciences
Volume45
ISSN (Print)1871-3033

Fingerprint

Vehicle Routing Problem with Time Windows
Hill Climbing
Vehicle routing
Metaheuristics
Jump
Local Minima
Guided Local Search
Neighborhood Search
Diversification
Vehicle Routing Problem
Local Search
Heuristics
Benchmark
Standards

Keywords

  • Heuristics
  • Metaheuristic
  • Time windows
  • Vehicle routing

Cite this

Mester, D., Bräysy, O., & Dullaert, W. (2018). Why to climb if one can jump: a hill jumping algorithm for the vehicle routing problem with time windows. In Computational Methods and Models for Transport : New Challenges for the Greening of Transport Systems (pp. 87-96). (Computational Methods in Applied Sciences; Vol. 45). Springer International Publishing. DOI: 10.1007/978-3-319-54490-8_6
Mester, David ; Bräysy, Olli ; Dullaert, Wout. / Why to climb if one can jump : a hill jumping algorithm for the vehicle routing problem with time windows. Computational Methods and Models for Transport : New Challenges for the Greening of Transport Systems. Springer International Publishing, 2018. pp. 87-96 (Computational Methods in Applied Sciences).
@inbook{edd316ffbdb949f087d2a855ee9dac5a,
title = "Why to climb if one can jump: a hill jumping algorithm for the vehicle routing problem with time windows",
abstract = "The most common approaches to solve the variants of the well-known vehicle routing problem are based on metaheuristic hill-climbing search. The deficiency of these methods is slow local search based hill climbing that often is restricted to limited local neighborhood. In this paper we suggest a novel new two-phase metaheuristic that escapes the local minima with jumps of varying size, instead of step by step local hill climbing. The initial solution is first generated with a powerful ejection pool heuristic. The key idea of the improvement phase is to combine large neighborhood search with standard guided local search metaheuristic in a novel way, allowing improved search diversification and escape from local minima in more efficient way through jumps. The algorithm has been tested on the standard Gehring and Homberger benchmarks for the vehicle routing problem with time windows and the results indicate very competitive performance. We found 12 new and 43 matched best-known solutions and the best overall results for all problem sizes at comparable computation times.",
keywords = "Heuristics, Metaheuristic, Time windows, Vehicle routing",
author = "David Mester and Olli Br{\"a}ysy and Wout Dullaert",
year = "2018",
doi = "10.1007/978-3-319-54490-8_6",
language = "English",
isbn = "9783319544892",
series = "Computational Methods in Applied Sciences",
publisher = "Springer International Publishing",
pages = "87--96",
booktitle = "Computational Methods and Models for Transport",

}

Mester, D, Bräysy, O & Dullaert, W 2018, Why to climb if one can jump: a hill jumping algorithm for the vehicle routing problem with time windows. in Computational Methods and Models for Transport : New Challenges for the Greening of Transport Systems. Computational Methods in Applied Sciences, vol. 45, Springer International Publishing, pp. 87-96. DOI: 10.1007/978-3-319-54490-8_6

Why to climb if one can jump : a hill jumping algorithm for the vehicle routing problem with time windows. / Mester, David; Bräysy, Olli; Dullaert, Wout.

Computational Methods and Models for Transport : New Challenges for the Greening of Transport Systems. Springer International Publishing, 2018. p. 87-96 (Computational Methods in Applied Sciences; Vol. 45).

Research output: Chapter in Book/Report/Conference proceedingChapter

TY - CHAP

T1 - Why to climb if one can jump

T2 - a hill jumping algorithm for the vehicle routing problem with time windows

AU - Mester,David

AU - Bräysy,Olli

AU - Dullaert,Wout

PY - 2018

Y1 - 2018

N2 - The most common approaches to solve the variants of the well-known vehicle routing problem are based on metaheuristic hill-climbing search. The deficiency of these methods is slow local search based hill climbing that often is restricted to limited local neighborhood. In this paper we suggest a novel new two-phase metaheuristic that escapes the local minima with jumps of varying size, instead of step by step local hill climbing. The initial solution is first generated with a powerful ejection pool heuristic. The key idea of the improvement phase is to combine large neighborhood search with standard guided local search metaheuristic in a novel way, allowing improved search diversification and escape from local minima in more efficient way through jumps. The algorithm has been tested on the standard Gehring and Homberger benchmarks for the vehicle routing problem with time windows and the results indicate very competitive performance. We found 12 new and 43 matched best-known solutions and the best overall results for all problem sizes at comparable computation times.

AB - The most common approaches to solve the variants of the well-known vehicle routing problem are based on metaheuristic hill-climbing search. The deficiency of these methods is slow local search based hill climbing that often is restricted to limited local neighborhood. In this paper we suggest a novel new two-phase metaheuristic that escapes the local minima with jumps of varying size, instead of step by step local hill climbing. The initial solution is first generated with a powerful ejection pool heuristic. The key idea of the improvement phase is to combine large neighborhood search with standard guided local search metaheuristic in a novel way, allowing improved search diversification and escape from local minima in more efficient way through jumps. The algorithm has been tested on the standard Gehring and Homberger benchmarks for the vehicle routing problem with time windows and the results indicate very competitive performance. We found 12 new and 43 matched best-known solutions and the best overall results for all problem sizes at comparable computation times.

KW - Heuristics

KW - Metaheuristic

KW - Time windows

KW - Vehicle routing

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

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

UR - https://www.springerprofessional.de/en/computational-methods-and-models-for-transport/12491840

U2 - 10.1007/978-3-319-54490-8_6

DO - 10.1007/978-3-319-54490-8_6

M3 - Chapter

SN - 9783319544892

SN - 9783319854052

T3 - Computational Methods in Applied Sciences

SP - 87

EP - 96

BT - Computational Methods and Models for Transport

PB - Springer International Publishing

ER -

Mester D, Bräysy O, Dullaert W. Why to climb if one can jump: a hill jumping algorithm for the vehicle routing problem with time windows. In Computational Methods and Models for Transport : New Challenges for the Greening of Transport Systems. Springer International Publishing. 2018. p. 87-96. (Computational Methods in Applied Sciences). Available from, DOI: 10.1007/978-3-319-54490-8_6