Maximizing Revenues for On-Line Dial-a-Ride

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

Authors: 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

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

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)

Cited In (6)

• Serving rides of equal importance for time-limited 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
• Revenue maximization in transportation networks
• Improved bounds for revenue maximization in time-limited online dial-a-ride
• Title not available (Why is that?)

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)