Journal of Applied Mathematics and Physics
Vol.05 No.09(2017), Article ID:79084,8 pages
10.4236/jamp.2017.59140
A Dynamic Programming Algorithm for the Ridersharing Problem Restricted with Unique Destination and Zero Detour on Trees
Yiming Li1, Huiqiang Lu2, Zhiqian Ye3, Xiao Zhou4
1Wenzhou University, Wenzhou, China
2Zhejiang University of Technology, Hangzhou, China
3Zhejiang University, Hangzhou, China
4Tohoku University, Sendai, Japan
Received: August 7, 2017; Accepted: September 12, 2017; Published: September 15, 2017
ABSTRACT
We deal with the problem of sharing vehicles by individuals with similar itineraries which is to find the minimum number of drivers, each of which has a vehicle capacity and a detour to realize all trips. Recently, Gu et al. showed that the problem is NP-hard even for star graphs restricted with unique destination, and gave a polynomial-time algorithm to solve the problem for paths restricted with unique destination and zero detour. In this paper we will give a dynamic programming algorithm to solve the problem in polynomial time for trees restricted with unique destination and zero detour. In our best knowledge it is a first polynomial-time algorithm for trees.
Keywords:
Dynamic Programming Algorithm, Rideshare, Tree
1. Introduction
There are many previous researches for assigning passengers to drivers [1]-[7]. In this paper we deal with a more general ridesharing problem, introduced by Gu et al. [8], 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,
A ridesharing f of G with R is optimal if is minimum among all ridesharings f. The ridesharing problem is to find an optimal ridesharing f for a given graph G and a ridesharing information R.
Recently, Gu et al. showed that the problem is NP-hard even for star graphs restricted with unique destination, and gave a polynomial-time algorithm to solve the problem for paths restricted with unique destination and zero detour [8]. In this paper we will give a dynamic programming algorithm to solve the problem for trees T restricted with unique destination and zero detour. Our algorithm runs in time , where k is the number of the trips and n is the number of the vertices in T. In our best knowledge it is a first polynomial-time algorithm for trees.
2. A Dynamic Programming Algorithm
The ridesharing problem is NP-hard even for star graphs restricted with unique destination if some detours are not zero [8]. However, in this section, we have the following theorem for the problem of trees restricted with unique destination and zero detour.
The ridesharing problem of trees T can be solved in time if the destinations of all the k trips are same and the detour of each driver is zero, where n is the number of the vertices in T.
In the remainder of this section we give an algorithm to solve the ridesharing problem for trees in polynomial time as a proof of Theorem 2. Let k be a positive integer and let R be a set of the k trips , , as an instance of the ridesharing problem of T. Since we deal with the problem restricted with unique destination and zero detours, let r be the unique destination. Then for each i, , we have and , and is the unique path in T. For the sake of notational convenience we redefine the ridesharing information , and let be an instance of the ridesharing problem of T with the ridesharing information R and the unique destination r in the remainder of this paper.
Since the destinations of all trips are same, we choose the destination r as the root of a given tree T, and regard T as rooted tree. For each vertex v of T, we denote by the subtree of T which is rooted at v and is induced by all descendants of v in T. For each edge such that v is the parent of in T, we denote by the subtree of T which is rooted at v and is induced by v, and the descendants of in T. For a subtree of T rooted at v, let
For each , , we denote by the maximum number of additional trips which can be served after serving all trips in using at most drivers, that is,
where the maximum is taken over all ridesharings f with the instance satisfying and
Let if drivers can not serve all trips in with the unique destination v. The main step of our algorithm is to compute the table of the functions from leaves to the root r of T by dynamic programming. From the table on the root r, it is obvious that the minimum satisfying is the minimum number of drivers to serve all the trips. Although we give a dynamic programming algorithm to compute the minimum number of drivers to serve all the trips, the algorithm can be easily modified to actually find an optimal ridesharing f. We thus show how to compute such all the tables on vertices v from leaves to the root in the remainder of this section.
2.1. The Vertex v Is a Leaf in T
In this case, since v is a leaf in T, there is no trips from v's descendants in . Therefore, by the definition of , we trivially have the following lemma.
Let v be an arbitrary leaf of T. Then for each .
2.2. The Vertex v Is an Internal Vertex in T
In this case v is an internal vertex in T. Let be the children of v ordered arbitrarily, and let , , be the edge joining v to , as illustrated in Figure 1. The subtree , , of T is rooted at and is induced by all descendants of in T. We denote by the subtree of T which consists of the vertex v, the edges and the subtrees . is indicated by a dotted line in Figure 1. Obviousely .
Figure 1. Subtrees , and rooted at v.
We first compute the function for all and , and , as in the following lemma 1, where is the subtree obtained from by adding the edge , indicated by a dotted thick line in Figure 1.
Let be the subset of R such that the start location is at , and let
(1)
Then
(2)
Furthermore, all , , can be computed from all , , in time .
Proof. We first prove
(3)
If , then Equation (3) 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 since f is a ridesharing of and is a subtree of . Let , then by the definition of , we have . Let
Then the drivers in f consists of the drivers from start locations in and the drivers from start locations at , and hence . Therefore, we have and
verified Equation (3).
We next prove that
(4)
if . By Equation (1) m choose and such that , , and
(5)
Since , we have , and hence there is a ridesharing with the instance such that and . One can obtain a ridesharing with the instance from using drivers in plus the new drivers having the trip indices in . By Equation (5) we have , and by the definition , and hence we have , verified Equation (4) .
By Equations (3) and (4) m Equation (2) holds true. We finally show that for each , , , can be computed from all , , in time as follows.
By Equation (1) for a given , clearly is the set of the indices such that is at least largest among all , . One can sorted all , ), in non-increasing order, and compute all prefix sum of . This can be done in time . Then, for any given pair of and , ,
can be computed in time. One thus can compute in time for each since , and hence for all , , can be computed from all in time . ,
We finally compute the function for all and , and , as in the following lemma.
For each , ,
Furthermore, all , , can be computed from all and in time .
Proof. We first prove
(6)
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
(7)
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 . ,
2.3. Algorithm
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.
3. Conclusion
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.
Funding
This work is partially supported by JSPS KAKENHI Grant Number JP16K00003 (X. Zhou).
Cite this paper
Li, Y.M., Lu, H.Q., Ye, Z.Q. and Zhou, X. (2017) A Dynamic Programming Algorithm for the Ridersharing Problem Restricted with Unique Destination and Zero Detour on Trees. Journal of Applied Mathematics and Physics, 5, 1678-1685. https://doi.org/10.4236/jamp.2017.59140
References
- 1. Agatz, N., Erera, A., Savelsbergh, M. and Wang, X. (2011) Dynamic Ride-Sharing: A Simulation Study in Metro Atlanta. Transp. Res. Part B, 45, 1540-1564. https://doi.org/10.1016/j.trb.2011.05.017
- 2. Agatz, N., Erera, A., Savelsbergh, M. and Wang, X. (2012) Optimization for Dynamic Ride-Sharing: A Review. European Journal of Operational Research, 223, 295-303. https://doi.org/10.1016/j.ejor.2012.05.028
- 3. Baldacci, R., Maniezzo, V. and Mingozzi, A. (2004) An Exact Method for the Car Pooling Problem Based on La-grangean Column Generation. Oper. Res., 52, 422-439. https://doi.org/10.1287/opre.1030.0106
- 4. Brucker, P. and Nordmann, L. (1994) The k-Track Assignment Problem. Computing, 54, 97-122. https://doi.org/10.1007/BF02238071
- 5. Chan, N.D. and Shaheen, S.A. (2012) Ridesharing in North America: Past, Present, and Future. Transp. Rev., 32, 93-112. https://doi.org/10.1080/01441647.2011.621557
- 6. Cordeau, J.-F. and Laporte, G. (2007) The Dial-a-Ride Problem: Models and Algorithms. Annals of Operations Re-search, 153, 29-46. https://doi.org/10.1007/s10479-007-0170-8
- 7. Ghoseiri, K., Haghani, A. and Hamedi, M. (1979) Real-Time Ridesharing Matching Problem. Final Report of UMD-2009-05. U.S. Department of Transportation.
- 8. Gu, Q.-P., Liang, L. and Zhang, G. (2016) Algorithmic Analysis for Ridesharing of Personal Vehicles. Proc. of COCOA 2016, LNCS 10043, 438-452. https://doi.org/10.1007/978-3-319-48749-6_32