By the same authors

A multi-arm bandit neighbourhood search for routing and scheduling problems

Research output: Contribution to conferencePaper

Full text download(s)

Author(s)

Department/unit(s)

Publication details

DatePublished - 2016
Number of pages33
Original languageEnglish

Abstract

Abstract Local search based meta-heuristics such as variable neighbourhood
search have achieved remarkable success in solving complex combinatorial
problems. Local search techniques are becoming increasingly popular and are
used in a wide variety of meta-heuristics, such as genetic algorithms. Typically,
local search iteratively improves a solution by making a series of small moves.
Traditionally these methods do not employ any learning mechanism.
We treat the selection of a local search neighbourhood as a dynamic multi-
armed bandit (D-MAB) problem where learning techniques for solving the
D-MAB can be used to guide the local search process. We present a D-MAB
neighbourhood search (D-MABNS) which can be embedded within any meta-
heuristic or hyperheuristic framework. Given a set of neighbourhoods, the aim
of D-MABNS is to adapt the search sequence, testing promising solutions
rst. We demonstrate the eectiveness of D-MABNS on two vehicle routing
and scheduling problems, the real-world geographically distributed mainte-
nance problem (GDMP) and the periodic vehicle routing problem (PVRP).
We present comparisons to benchmark instances and give a detailed analysis
of parameters, performance and behaviour.
Keywords Meta-heuristic Local search Vehicle routing

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations