Ride Sharing with a Vehicle of Unlimited Capacity.

DOI10.4230/LIPICS.MFCS.2016.36zbMATH Open1398.90024arXiv1507.02414OpenAlexW2964351530MaRDI QIDQ4608596FDOQ4608596

Angelo Fanelli, Greco Gianluigi

Publication date: 21 March 2018

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$.

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

zbMATH Keywords

vehicle routingride sharingpick up and delivery problem

Mathematics Subject Classification ID

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

Cited In (2)

• Car-sharing between two locations: online scheduling with flexible advance bookings
• A cooperative game-theoretic approach to the social ridesharing problem

   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 👍 👎

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)