New Bounds for Maximizing Revenue in Online Dial-a-Ride

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 prove that no non-preemptive deterministic online algorithm for OLDARP can be guaranteed to earn more than half the revenue earned by [Formula: see text]. We then investigate the segmented best path ([Formula: see text]) algorithm of [8] for the general case of weighted graphs. The previously-established lower and upper bounds for the competitive ratio of [Formula: see text] 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). We also prove that when revenues are uniform, [Formula: see text] has competitive ratio 4. Finally, we provide a competitive analysis of [Formula: see text] on complete bipartite graphs.