TY - JOUR

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

AU - Urra, Enrique

AU - Cubillos, Claudio

AU - Cabrera-Paniagua, Daniel

N1 - Publisher Copyright:
© 2015 Enrique Urra et al.

PY - 2015/1/11

Y1 - 2015/1/11

N2 - 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.

AB - 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.

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

U2 - 10.1155/2015/707056

DO - 10.1155/2015/707056

M3 - Article

AN - SCOPUS:84947650211

VL - 2015

JO - Mathematical Problems in Engineering

JF - Mathematical Problems in Engineering

SN - 1024-123X

M1 - 707056

ER -