Maximizing Revenues for On-Line Dial-a-Ride

DOI10.1007/978-3-319-12691-3_38MaRDI QIDQ2942425zbMATH OpenOpenAlexFDO

Authors William Forcier, Ananya D. Christman

Publication date 11 September 2015

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

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

zbMATH Keywords

graphsonline algorithmscompetitive analysisdial-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)

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.

Recommendations

• From theory to practice: maximizing revenues for on-line dial-a-ride
• New Bounds for Maximizing Revenue in Online Dial-a-Ride
• Improved bounds for revenue maximization in time-limited online dial-a-ride
• An improved algorithm for open online dial-a-ride
• Competitive analysis of the online dial-a-ride problem
• scientific article; zbMATH DE number 1629851
• scientific article; zbMATH DE number 1947431
• On-line dial-a-ride problems under a restricted information model
• scientific article; zbMATH DE number 1629830
• Optimal pricing for ride-sourcing platforms

Cited in

(8)

• Maximizing the number of rides served for dial-a-ride
• Serving rides of equal importance for time-limited dial-a-ride
• Revenue maximization in transportation networks
• scientific article; zbMATH DE number 1629851 (Why is no real title available?)
• Revenue maximization in online dial-a-ride
• Improved bounds for revenue maximization in time-limited online dial-a-ride
• New Bounds for Maximizing Revenue in Online Dial-a-Ride
• From theory to practice: maximizing revenues for on-line dial-a-ride

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)