Maximizing the Number of Rides Served for Dial-a-Ride

Medientyp: E-Artikel; Elektronischer Konferenzbericht; Sonstige Veröffentlichung

Titel: Maximizing the Number of Rides Served for Dial-a-Ride

Beteiligte: Anthony, Barbara M. [VerfasserIn]; Birnbaum, Ricky [VerfasserIn]; Boyd, Sara [VerfasserIn]; Christman, Ananya [VerfasserIn]; Chung, Christine [VerfasserIn]; Davis, Patrick [VerfasserIn]; Dhimar, Jigar [VerfasserIn]; Yuen, David [VerfasserIn]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019

Sprache: Englisch

DOI: https://doi.org/10.4230/OASIcs.ATMOS.2019.11

Schlagwörter: dial-a-ride ; vehicle routing ; revenue maximization ; approximation algorithm

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: We study a variation of offline Dial-a-Ride, where each request has not only a source and destination, but also a revenue that is earned for serving the request. We investigate this problem for the uniform metric space with uniform revenues. While we present a study on a simplified setting of the problem that has limited practical applications, this work provides the theoretical foundation for analyzing the more general forms of the problem. Since revenues are uniform the problem is equivalent to maximizing the number of served requests. We show that the problem is NP-hard and present a 2/3 approximation algorithm. We also show that a natural generalization of this algorithm has an approximation ratio at most 7/9.

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: