There are many previous researches for assigning passengers to drivers -. In this paper we deal with a more general ridesharing problem, introduced by Gu et al. , in which each individual is a driver or passenger. Let G be a connected and edge-weighted graph with vertex set and edge set . Let k be a positive integer, and let a ridesharing infomation R be a set of k trips , , where
• and are the source (start location) and the destination, respectively, of the i-th trip;
• is the number of seats (capacity) of the i-th driver available for passengers including the driver;
• is the detour distance limit which the i-th driver can tolerate for offering ridesharing services; and
• is the preferred path of the i-th trip from to in G.
Let be the set of the indices of all trips in R which should be served, that is, . A ridesharing of a graph G with R is a mapping such that, for each , if then , and there is a trip (walk) P satisfying for each and the distance of P is at most plus the distance of , where , that is, is the set of the indices of trips served by the i-th driver. Let be the number of drivers of a ridesharing f, that is,
Furthermore, all , , can be computed from all and in time .
Proof. We first prove
If , then Equation (6) trivially holds. We thus assume that , that is, there is a ridesharing f with the instance such that and . Let be a mapping from to such that for each . Then clearly is a ridesharing of with the instance . Let . By the definition of we have . Similarly, let be a mapping from to such that for each . Then clearly is a ridesharing of with the instance . Let . By the definition of we have . Furthermore, and , and hence . We thus have
verified Equation (6).
We next prove
Choose and such that , and
We may assume and ; otherwise Equation (7) trivially holds.
Since , there is a ridesharing with the instance such that . Similarly, since , there is a ridesharing with the instance such that . Let be a mapping such that for each
Then clearly is a ridesharing of with the instance such that and . By the definition of , we have
verified Equation (7).
Furthermore, clearly for all and , , can be computed in time from all and . ,
From Lemmas 2.1―1 one can obtain the following algorithm to compute all , and .
Algorithm Alg( ) begin if is a leaf in , then for all , , by Lemm 2.1; else if is an internal vertex in , then begin let be the children of ordered arbitrarily, and let , , be the edge joining to ; for each , , compute all , , from all m , by Lemma 1; for each , , compute all , , from all , , and all , , by Lemma 1; let for all , ; end end
Clearly it runs in time since T has the n vertices. This completes to prove Theorem 2.
In this paper we gave a dynamic programming algorithm to solve the ridesharing problem for trees restricted with unique destination and zero detour. Our algorithm runs in polynomial time. However, it is still open whether or not there is a polynomial-time algorithm to solve the problem restricted with unique destination and zero detour for series-parallel graphs and graphs with bounded treewidth.
This work is partially supported by JSPS KAKENHI Grant Number JP16K00003 (X. Zhou).