A Hyperheuristic for the Dial-a-Ride Problem with Time Windows. (11th January 2015)

• Record Type: Journal Article
• Authors: Urra, Enrique; Cubillos, Claudio; Cabrera-Paniagua, Daniel
• Other Names: Peng Haipeng Academic Editor.
• Is Part Of: Mathematical problems in engineering. Volume 2015(2015)
• Publication Date: 2015-01-11
• Subjects: Engineering mathematics -- Periodicals; 510.2462
• DOI: 10.1155/2015/707056
• Languages: English
• ISSNs: 1024-123X

Abstract

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.