2013/10/27 by Ananya Christman, Christman, Ananya, William Forcier +1
Computer Science · Engineering · #Optimization and Search Problems #Transportation and Mobility Innovations #Smart Parking Systems Research
paper · pdf · doi:10.48550/arxiv.1310.7232
In the classic Dial-a-Ride Problem, a server travels in some metric space to serve requests for rides. Each request has a source, destination, and release time. We study a variation of this problem where each request also has a revenue that is earned if the request is satisfied. The goal is to serve requests within a time limit such that the total revenue is maximized. We first prove that the version of this problem where edges in the input graph have varying weights is NP-complete. We also prove that no algorithm can be competitive for this problem. We therefore consider the version where edges in the graph have unit weight and develop a 2-competitive algorithm for this problem.