On-line dial-a-ride problems under a restricted information model

Maarten Lipmann, X. Lu, Willem E. de Paepe, Rene A. Sitters, Leen Stougie

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


In on-line dial-a-ride problems, servers are traveling in some metric space to serve requests for rides which are presented over time. Each ride is characterized by two points in the metric space, a source, the starting point of the ride, and a destination, the end point of the ride. Usually it is assumed that at the release of such a request complete information about the ride is known. We diverge from this by assuming that at the release of such a ride only information about the source is given. At visiting the source, the information about the destination will be made available to the servers. For many practical problems, our model is closer to reality. However, we feel that the lack of information is often a choice, rather than inherent to the problem: additional information can be obtained, but this requires investments in information systems. In this paper we give mathematical evidence that for the problem under study it pays to invest. timizer.

Original languageEnglish
Title of host publicationAlgorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
Number of pages12
ISBN (Electronic)3540441808, 9783540441809
Publication statusPublished - 2002
Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
Duration: 17 Sept 200221 Sept 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


Conference10th Annual European Symposium on Algorithms, ESA 2002


Dive into the research topics of 'On-line dial-a-ride problems under a restricted information model'. Together they form a unique fingerprint.

Cite this