Ride Sharing with a Vehicle of Unlimited Capacity.

DOI10.4230/LIPICS.MFCS.2016.36MaRDI QIDQ4608596zbMATH OpenOpenAlexFDO

Authors Angelo Fanelli, Greco Gianluigi

Publication date 21 March 2018

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

zbMATH Keywords

pick up and delivery problemride sharingvehicle routing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Transportation, logistics and supply chain management (90B06)

Abstract: A ride sharing problem is considered where we are given a graph, whose edges are equipped with a travel cost, plus a set of objects, each associated with a transportation request given by a pair of origin and destination nodes. A vehicle travels through the graph, carrying each object from its origin to its destination without any bound on the number of objects that can be simultaneously transported. The vehicle starts and terminates its ride at given nodes, and the goal is to compute a minimum-cost ride satisfying all requests. This ride sharing problem is shown to be tractable on paths by designing a $O(hlogh+n)$ algorithm, with $h$ being the number of distinct requests and with $n$ being the number of nodes in the path. The algorithm is then used as a subroutine to efficiently solve instances defined over cycles, hence covering all graphs with maximum degree $2$. This traces the frontier of tractability, since $$-hard instances are exhibited over trees whose maximum degree is $3$.

Recommendations

• A new <scp>ride‐sharing</scp> model incorporating the passengers' efforts
• Shared mobility systems
• Carpool services for ride‐sharing platforms: Price and welfare implications
• Ridesharing for emergency evacuation
• Approximate ridesharing of personal vehicles problem
• Approximate ridesharing of personal vehicles problem
• Dynamic matching for real-time ride sharing

Cited in

(9)

• 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
• A cooperative game-theoretic approach to the social ridesharing problem
• Trip-vehicle assignment algorithms for ride-sharing
• Car-sharing between two locations: online scheduling with flexible advance bookings
• Efficient algorithms for ridesharing of personal vehicles
• Approximate ridesharing of personal vehicles problem
• On the shared transportation problem: computational hardness and exact approach

This page was built for publication: Ride Sharing with a Vehicle of Unlimited Capacity.

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