The Clustered Dial-a-Ride Problem
The Clustered Dial-a-Ride Problem
No Thumbnail Available
Files
There are no files associated with this item.
Date
2019
Authors
Feitsch, Fabian
Editors
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
International patent number
Link to the license
oops
EU project number
Project
Open Access publication
Collections
Title in another language
Publication type
Contribution to a conference collection
Publication status
Published
Published in
Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling / Benton, J. et al. (ed.). - Palo Alto, CA : AAAI Press, 2019. - pp. 510-518. - eISSN 2334-0843
Abstract
We study a variant of the classical dial-a-ride problem, with an application to public transport planning in rural areas. In the classical dial-a-ride problem, n users each specify a pickup and a delivery location, and the aim is to plan the least cost route to cater all requests. This can be modeled as a traveling salesmen problem in a complete graph with precedence constraints (pick-ups need to happen before deliveries). In this paper, we consider the clustered dial-a-ride problem, where we do not operate on a complete graph but on a graph composed of serially numbered cliques where each clique is connected to the next one via a single edge. This setting is inspired by door-to-door transportation for people from remote villages who want to get to another village or the next city by a bus which operates on demand. We argue that in case the optimal route exhibits certain structural properties, it can be computed significantly faster. To make use of this observation, we devise a classification algorithm which can decide whether the optimal route exhibits these structural properties before computing it. Extensive experiments on artificial and real-world instances reveal that the majority of optimal routes indeed have the desired properties and that our classifier is an efficient tool to recognize the respective instances.
Summary in another language
Subject (DDC)
004 Computer Science
Keywords
Conference
Twenty-Ninth International Conference on Automated Planning and Scheduling : 2019 ICAPS conference, Jul 11, 2019 - Jul 15, 2019, Berkeley
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690
FEITSCH, Fabian, Sabine STORANDT, 2019. The Clustered Dial-a-Ride Problem. Twenty-Ninth International Conference on Automated Planning and Scheduling : 2019 ICAPS conference. Berkeley, Jul 11, 2019 - Jul 15, 2019. In: BENTON, J., ed. and others. Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling. Palo Alto, CA:AAAI Press, pp. 510-518. eISSN 2334-0843BibTex
@inproceedings{Feitsch2019Clust-46269, year={2019}, title={The Clustered Dial-a-Ride Problem}, url={https://wvvw.aaai.org/ojs/index.php/ICAPS/article/view/3516}, publisher={AAAI Press}, address={Palo Alto, CA}, booktitle={Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling}, pages={510--518}, editor={Benton, J.}, author={Feitsch, Fabian and Storandt, Sabine} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/46269"> <dc:contributor>Feitsch, Fabian</dc:contributor> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Storandt, Sabine</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-07-09T14:04:34Z</dc:date> <dcterms:abstract xml:lang="eng">We study a variant of the classical dial-a-ride problem, with an application to public transport planning in rural areas. In the classical dial-a-ride problem, n users each specify a pickup and a delivery location, and the aim is to plan the least cost route to cater all requests. This can be modeled as a traveling salesmen problem in a complete graph with precedence constraints (pick-ups need to happen before deliveries). In this paper, we consider the clustered dial-a-ride problem, where we do not operate on a complete graph but on a graph composed of serially numbered cliques where each clique is connected to the next one via a single edge. This setting is inspired by door-to-door transportation for people from remote villages who want to get to another village or the next city by a bus which operates on demand. We argue that in case the optimal route exhibits certain structural properties, it can be computed significantly faster. To make use of this observation, we devise a classification algorithm which can decide whether the optimal route exhibits these structural properties before computing it. Extensive experiments on artificial and real-world instances reveal that the majority of optimal routes indeed have the desired properties and that our classifier is an efficient tool to recognize the respective instances.</dcterms:abstract> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Feitsch, Fabian</dc:creator> <dcterms:issued>2019</dcterms:issued> <dc:contributor>Storandt, Sabine</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-07-09T14:04:34Z</dcterms:available> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/46269"/> <dcterms:title>The Clustered Dial-a-Ride Problem</dcterms:title> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:language>eng</dc:language> <foaf:homepage rdf:resource="http://localhost:8080/"/> </rdf:Description> </rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
URL of original publication
Test date of URL
2019-07-09
Examination date of dissertation
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
Yes