Solving the Dial-a-Ride Problem using Genetic Algorithms

Publication: Research - peer-reviewJournal article – Annual report year: 2007

View graph of relations

In the Dial-a-Ride problem (DARP), customers request transportation from an operator. A request consists of a specified pickup location and destination location along with a desired departure or arrival time and capacity demand. The aim of DARP is to minimize transportation cost while satisfying customer service level constraints (Quality of Service). In this paper, we present a genetic algorithm (GA) for solving the DARP. The algorithm is based on the classical cluster-first, route-second approach, where it alternates between assigning customers to vehicles using a GA and solving independent routing problems for the vehicles using a routing heuristic. The algorithm is implemented in Java and tested on publicly available data sets. The new solution method has achieved solutions comparable with the current state-of-the-art methods.
Original languageEnglish
JournalOperational Research Society. Journal
Publication date2007
Volume58
Issue10
Pages1321-1331
ISSN0160-5682
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 30

Keywords

  • Dial-a-Ride, Heuristics, Specialized transportation
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 3778326