Application of genetic algorithms for the DARPTW problem
Abstract:
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. © 2006-2009 by CCC Publications.
Año de publicación:
2009
Keywords:
- scheduling
- Heuristic
- Dial-a-ride
- Passenger transportation
- DARPTW
Fuente:

Tipo de documento:
Article
Estado:
Acceso abierto
Áreas de conocimiento:
- Algoritmo
- Algoritmo
Áreas temáticas de Dewey:
- Métodos informáticos especiales

Objetivos de Desarrollo Sostenible:
- ODS 9: Industria, innovación e infraestructura
- ODS 11: Ciudades y comunidades sostenibles
- ODS 8: Trabajo decente y crecimiento económico
