Application of genetic algorithms for the DARPTW problem

Claudio Cubillos, Enrique Urra, NIBALDO RODRIGUEZ AGURTO

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

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.

Original languageEnglish
Pages (from-to)127-136
Number of pages10
JournalInternational Journal of Computers, Communications and Control
Volume4
Issue number2
DOIs
StatePublished - 1 Jan 2009

Keywords

  • DARPTW
  • Dial-a-ride
  • Heuristic
  • Passenger transportation
  • Scheduling

Fingerprint Dive into the research topics of 'Application of genetic algorithms for the DARPTW problem'. Together they form a unique fingerprint.

Cite this