Publikation:

The Clustered Dial-a-Ride Problem

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2019

Autor:innen

Feitsch, Fabian

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

BENTON, J., ed. and others. Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling. Palo Alto, CA: AAAI Press, 2019, pp. 510-518. eISSN 2334-0843

Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Twenty-Ninth International Conference on Automated Planning and Scheduling : 2019 ICAPS conference, 11. Juli 2019 - 15. Juli 2019, Berkeley
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690FEITSCH, Fabian, Sabine STORANDT, 2019. The Clustered Dial-a-Ride Problem. Twenty-Ninth International Conference on Automated Planning and Scheduling : 2019 ICAPS conference. Berkeley, 11. Juli 2019 - 15. Juli 2019. In: BENTON, J., ed. and others. Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling. Palo Alto, CA: AAAI Press, 2019, pp. 510-518. eISSN 2334-0843
BibTex
@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>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt

Prüfdatum der URL

2019-07-09

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen