Maximizing Revenues for On-Line Dial-a-Ride

DOI10.1007/978-3-319-12691-3_38zbMATH Open1431.90014arXiv1310.7232OpenAlexW272757062MaRDI QIDQ2942425FDOQ2942425

William Forcier, Ananya D. Christman

Publication date: 11 September 2015

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1310.7232

zbMATH Keywords

graphs online algorithms competitive analysis dial-a-ride

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Transportation, logistics and supply chain management (90B06)

Cited In (3)

   Recommendations

This page was built for publication: Maximizing Revenues for On-Line Dial-a-Ride

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942425)