Solving the Dial-a-Ride problem using genetic algorithms

R M Jorgensen, J Larsen () and K B Bergvinsdottir
Additional contact information
R M Jorgensen: Technical University of Denmark
J Larsen: Technical University of Denmark
K B Bergvinsdottir: Technical University of Denmark

Journal of the Operational Research Society, 2007, vol. 58, issue 10, 1321-1331

Abstract: Abstract 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.

Keywords: Dial-a-Ride; heuristics; specialized transportation (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (27)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2602287 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:58:y:2007:i:10:d:10.1057_palgrave.jors.2602287

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2602287

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().