Improved Bounds for Revenue Maximization in Time-Limited Online Dial-a-Ride

Ananya D. Christman (), Christine Chung, Nicholas Jaczko, Tianzhi Li, Scott Westvold, Xinyue Xu and David Yuen
Additional contact information
Ananya D. Christman: Middlebury College
Christine Chung: Connecticut College
Nicholas Jaczko: Middlebury College
Tianzhi Li: Middlebury College
Scott Westvold: Middlebury College
Xinyue Xu: Middlebury College

SN Operations Research Forum, 2021, vol. 2, issue 3, 1-38

Abstract: Abstract In the Online Dial-a-Ride Problem (OLDARP), a server travels to serve requests for rides. We consider a variant where each request specifies a source, destination, release time, and revenue that is earned for serving the request. The goal is to maximize the total revenue earned within a given time limit. We first prove that no non-preemptive deterministic online algorithm can be guaranteed to earn more than half the revenue earned by opt. We then investigate the segmented best path (sbp) algorithm of [1]. The previously established lower and upper bounds for the competitive ratio of sbp are 4 and 6, respectively, under reasonable assumptions about the input instance. We eliminate the gap by proving that the competitive ratio is 5 (under the same assumptions) and also prove that this bound is tight. When revenues are uniform, we prove that sbp has competitive ratio 4. Next we provide a competitive analysis of sbp on complete bipartite graphs. We then consider this problem on the uniform metric and revisit the bp algorithm of [1]; we provide an instance where the algorithm's competitive ratio is unbounded. We conclude with experimental results that suggest that sbp would be effective if applied in practice.

Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-021-00076-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:2:y:2021:i:3:d:10.1007_s43069-021-00076-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-021-00076-x

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().