Approximate ridesharing of personal vehicles problem

DOI10.1016/J.TCS.2021.04.009MaRDI QIDQ5918279zbMATH OpenOpenAlexFDO

Authors Qian-Ping Gu, Jiajian Leo Liang, Guochuan Zhang

Publication date 8 June 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic analysisapproximation algorithmsoptimization problemsridesharing problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06) Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35)

Abstract: The ridesharing problem is that given a set of trips, each trip consists of an individual, a vehicle of the individual and some requirements, select a subset of trips and use the vehicles of selected trips to deliver all individuals to their destinations satisfying the requirements. Requirements of trips are specified by parameters including source, destination, vehicle capacity, preferred paths of a driver, detour distance and number of stops a driver is willing to make, and time constraints. We analyze the relations between the time complexity and parameters for two optimization problems: minimizing the number of selected vehicles and minimizing total travel distance of the vehicles. We consider the following conditions: (1) all trips have the same source or same destination, (2) no detour is allowed, (3) each participant has one preferred path, (4) no limit on the number of stops, and (5) all trips have the same departure and same arrival time. It is known that both minimization problems are NP-hard if one of Conditions (1), (2) and (3) is not satisfied. We prove that both problems are NP-hard and further show that it is NP-hard to approximate both problems within a constant factor if Conditions (4) or (5) is not satisfied. We give $fracK+22$-approximation algorithms for minimizing the number of selected vehicles when condition (4) is not satisfied, where $K$ is the largest capacity of all vehicles.

Recommendations

• Efficient algorithms for ridesharing of personal vehicles
• Efficient algorithms for ridesharing of personal vehicles
• Algorithmic Analysis for Ridesharing of Personal Vehicles
• Algorithmic analysis for ridesharing of personal vehicles
• Ride Sharing with a Vehicle of Unlimited Capacity.

Cites work

• Algorithmic analysis for ridesharing of personal vehicles
• Approximate ridesharing of personal vehicles problem
• Efficient algorithms for ridesharing of personal vehicles
• Enhancing urban mobility: integrating ride-sharing and public transit
• Local search algorithms for the maximum carpool matching problem
• Optimization for dynamic ride-sharing: a review
• Typology and literature review for dial-a-ride problems

Cited in

(19)

• Algorithmic analysis for ridesharing of personal vehicles
• Taxi-sharing: parameterized complexity and approximability of the dial-a-ride problem with money as an incentive
• Modeling and solving the multimodal car- and ride-sharing problem
• Local search algorithms for the maximum carpool matching problem
• Approximation algorithms for the maximum carpool matching problem
• Interrelated trips in the rural dial-a-ride problem with autonomous vehicles
• Trip-vehicle assignment algorithms for ride-sharing
• Fast detour computation for ride sharing
• Algorithmic Analysis for Ridesharing of Personal Vehicles
• Ride Sharing with a Vehicle of Unlimited Capacity.
• Local search algorithms for the maximum carpool matching problem
• Meeting Locations in Real-Time Ridesharing Problem: A Buckets Approach
• Real-time ride-sharing substitution service in multi-modal public transport using buckets
• Efficient algorithms for ridesharing of personal vehicles
• Efficient algorithms for ridesharing of personal vehicles
• Approximate ridesharing of personal vehicles problem
• Algorithms and computational study on a transportation system integrating public transit and ridesharing of personal vehicles
• On the shared transportation problem: computational hardness and exact approach
• The flexible and real-time commute trip sharing problems

Describes a project that uses

Uses Software

• PoliUniPool

This page was built for publication: Approximate ridesharing of personal vehicles problem

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