Search Results

Documents authored by Chung, Christine

Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2024.8
New Bounds on the Performance of SBP for the Dial-a-Ride Problem with Revenues (Short Paper)

Authors: Barbara M. Anthony, Christine Chung, Ananya Das, and David Yuen

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
We revisit the Segmented Best Path (sbp) algorithm for online DARP in an offline setting with revenues and a time limit. The goal is to find a subset of the inputted ride requests that can be served within the time limit while maximizing the total revenue earned. sbp divides the time into segments and greedily chooses the highest-revenue path of requests to serve within each time segment. We show that sbp’s performance has an upper bound of 5. Further, while sbp is a tight 4-approximation in the uniform-revenue case, we find that with non-uniform revenues, the approximation ratio of sbp has a lower bound strictly greater than 4; in particular, we provide a lower bound of (√e + 1)/(√e - 1) ≈ 4.08299, which we show can be generalized to instances with ratio greater than 4.278.
Cite as

Barbara M. Anthony, Christine Chung, Ananya Das, and David Yuen. New Bounds on the Performance of SBP for the Dial-a-Ride Problem with Revenues (Short Paper). In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 8:1-8:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{anthony_et_al:OASIcs.ATMOS.2024.8,
  author =	{Anthony, Barbara M. and Chung, Christine and Das, Ananya and Yuen, David},
  title =	{{New Bounds on the Performance of SBP for the Dial-a-Ride Problem with Revenues}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{8:1--8:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.8},
  URN =		{urn:nbn:de:0030-drops-211964},
  doi =		{10.4230/OASIcs.ATMOS.2024.8},
  annote =	{Keywords: Dial-a-Ride problems, Lower bounds, Vehicle routing}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.11
Maximizing the Number of Rides Served for Dial-a-Ride

Authors: Barbara M. Anthony, Ricky Birnbaum, Sara Boyd, Ananya Christman, Christine Chung, Patrick Davis, Jigar Dhimar, and David Yuen

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
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.
Cite as

Barbara M. Anthony, Sara Boyd, Ricky Birnbaum, Ananya Christman, Christine Chung, Patrick Davis, Jigar Dhimar, and David Yuen. Maximizing the Number of Rides Served for Dial-a-Ride. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{anthony_et_al:OASIcs.ATMOS.2019.11,
  author =	{Anthony, Barbara M. and Birnbaum, Ricky and Boyd, Sara and Christman, Ananya and Chung, Christine and Davis, Patrick and Dhimar, Jigar and Yuen, David},
  title =	{{Maximizing the Number of Rides Served for Dial-a-Ride}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{11:1--11:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.11},
  URN =		{urn:nbn:de:0030-drops-114237},
  doi =		{10.4230/OASIcs.ATMOS.2019.11},
  annote =	{Keywords: dial-a-ride, revenue maximization, approximation algorithm, vehicle routing}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.1
Revenue Maximization in Online Dial-A-Ride

Authors: Ananya Christman, Christine Chung, Nicholas Jaczko, Marina Milan, Anna Vasilchenko, and Scott Westvold

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
We study a variation of the Online-Dial-a-Ride Problem where each request comes with not only a source, destination and release time, but also has an associated revenue. The server's goal is to maximize its total revenue within a given time limit, T. We show that the competitive ratio is unbounded for any deterministic online algorithm for the problem. We then provide a 3-competitive algorithm for the problem in a uniform metric space and a 6-competitive algorithm for the general case of weighted graphs (under reasonable assumptions about the input instance). We conclude with an experimental evaluation of our algorithm in simulated settings inspired by real-world Dial-a-Ride data. Experimental results show that our algorithm performs well when compared to an offline version of the algorithm and a greedy algorithm.
Cite as

Ananya Christman, Christine Chung, Nicholas Jaczko, Marina Milan, Anna Vasilchenko, and Scott Westvold. Revenue Maximization in Online Dial-A-Ride. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{christman_et_al:OASIcs.ATMOS.2017.1,
  author =	{Christman, Ananya and Chung, Christine and Jaczko, Nicholas and Milan, Marina and Vasilchenko, Anna and Westvold, Scott},
  title =	{{Revenue Maximization in Online Dial-A-Ride}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.1},
  URN =		{urn:nbn:de:0030-drops-78886},
  doi =		{10.4230/OASIcs.ATMOS.2017.1},
  annote =	{Keywords: online algorithms, dial-a-ride, competitive analysis, vehicle routing, metric space}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact