Application of Genetic Algorithms for the DARPTW Problem

• DOI: 10.15837/ijccc.2009.2.2420
• Publication Date: 2016-01-23T09:22:58Z
• Authors: Claudio Cubillos; Enrique Urra; Nibaldo Rodríguez
• Keywords: 0211 other engineering and technologies; 02 engineering and technology

On the Dial-a-Ride with time windows (DARPTW) customer transportation problem, there is a set of requests from customers to be transported from an origin place to a delivery place through a locations network, under several constraints like the time windows. The problem complexity (NP-Hard) forces the use of heuristics on its resolution. In this context, the application of Genetic Algorithms (GA) on DARPTW was not largely considered, with the exception of a few researches. In this work, under a restrictive scenario, a GA model for the problem was developed based on the adaptation of a generic GA model from literature. Our solution applies data pre-processing techniques to reduce the search space to points that are feasible regarding time windows constraints. Tests show competitive results on Cordeau & Laporte benchmark datasets while improving processing times.