A hyperheuristic for the dial-a-ride problem with time windows

Enrique Urra, CLAUDIO ALONSO CUBILLOS FIGUEROA, Daniel Cabrera-Paniagua

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

The dial-a-ride problem with time windows (DARPTW) is a combinatorial optimization problem related to transportation, in which a set of customers must be picked up from an origin location and they have to be delivered to a destination location. A transportation schedule must be constructed for a set of available vehicles, and several constraints have to be considered, particularly time windows, which define an upper and lower time bound for each customer request in which a vehicle must arrive to perform the service. Because of the complexity of DARPTW, a number of algorithms have been proposed for solving the problem, mainly based on metaheuristics such as Genetic Algorithms and Simulated Annealing. In this work, a different approach for solving DARPTW is proposed, designed, and evaluated: hyperheuristics, which are alternative heuristic methods that operate at a higher abstraction level than metaheuristics, because rather than searching in the problem space directly, they search in a space of low-level heuristics to find the best strategy through which good solutions can be found. Although the proposed hyperheuristic uses simple and easy-to-implement operators, the experimental results demonstrate efficient and competitive performance on DARPTW when compared to other metaheuristics from the literature.

Original languageEnglish
Article number707056
JournalMathematical Problems in Engineering
Volume2015
DOIs
StatePublished - 11 Jan 2015
Externally publishedYes

Fingerprint

Dive into the research topics of 'A hyperheuristic for the dial-a-ride problem with time windows'. Together they form a unique fingerprint.

Cite this