A Dynamic Programming Algorithm for the Ridersharing Problem Restricted with Unique Destination and Zero Detour on Trees
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.

1. Introduction

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 $V\left(G\right)$ and edge set $E\left(G\right)$ . Let k be a positive integer, and let a ridesharing infomation R be a set of k trips $\left(i,{s}_{i},{t}_{i},{c}_{i},{d}_{i},{P}_{i}\right)$ , $1\le i\le k$ , where

${s}_{i}$ and ${t}_{i}$ are the source (start location) and the destination, respectively, of the i-th trip;

${c}_{i}$ is the number of seats (capacity) of the i-th driver available for passengers including the driver;

${d}_{i}$ is the detour distance limit which the i-th driver can tolerate for offering ridesharing services; and

${P}_{i}$ is the preferred path of the i-th trip from ${s}_{i}$ to ${t}_{i}$ in G.

Let $I\left(R\right)$ be the set of the indices of all trips in R which should be served, that is, $I\left(R\right)=\left\{i|\left(i,{s}_{i},{t}_{i},{c}_{i},{d}_{i},{P}_{i}\right)\in R\right\}$ . A ridesharing of a graph G with R is a mapping $f:I\left(R\right)\to I\left(R\right)$ such that, for each $i\in I\left(R\right)$ , if ${f}^{-1}\left(i\right)\overline{)=}\varnothing$ then $i\in {f}^{-1}\left(i\right)$ , $|{f}^{-1}\left(i\right)|\le {c}_{i}$ and there is a trip (walk) P satisfying ${P}_{j}\subseteq P$ for each $j\in {f}^{-1}\left(i\right)$ and the distance of P is at most ${d}_{i}$ plus the distance of ${P}_{i}$ , where ${f}^{-1}\left(i\right)=\left\{j|f\left(j\right)=i\right\}$ , that is, ${f}^{-1}\left(i\right)$ is the set of the indices of trips served by the i-th driver. Let $driver\left(f\right)$ be the number of drivers of a ridesharing f, that is,

$driver\left(f\right)=|\right)+cap\left({T}_{{e}_{j}},v,{\alpha }_{2}\right)\right\}.$

Furthermore, all $cap\left({T}_{v}^{j},v,\alpha \right)$ , $0\le \alpha \le k$ , can be computed from all $cap\left({T}_{v}^{j-1},v,{\alpha }_{1}\right)$ and $cap\left({T}_{{v}_{j}},{v}_{j},{\alpha }_{2}\right)$ in time $O\left({k}^{2}\right)$ .

Proof. We first prove

$cap\left({T}_{v}^{j},v,\alpha \right)\le \underset{0\le {\alpha }_{1},{\alpha }_{2}\le \alpha ,\text{\hspace{0.17em}}{\alpha }_{1}+{\alpha }_{2}=\alpha }{max}\left\{cap\left({T}_{v}^{j-1},v,{\alpha }_{1}\right)+cap\left({T}_{{e}_{j}},v,{\alpha }_{2}\right)\right\}.$ (6)

If $cap\left({T}_{v}^{j},v,\alpha \right)=-\infty$ , then Equation (6) trivially holds. We thus assume that $cap\left({T}_{v}^{j},v,\alpha \right)\overline{)=}-\infty$ , that is, there is a ridesharing f with the instance $\left({T}_{v}^{j},R\left({T}_{v}^{j},v\right),v\right)$ such that $driver\left(f\right)\le \alpha$ and $cap\left({T}_{v}^{j},v,\alpha \right)=cap\left(f\right)$ . Let ${f}_{1}$ be a mapping from $I\left(R\left({T}_{v}^{j-1},v\right)\right)$ to $I\left(R\left({T}_{v}^{j-1},v\right)\right)$ such that ${f}_{1}\left(i\right)=f\left(i\right)$ for each $i\in I\left(R\left({T}_{v}^{j-1},v\right)\right)$ . Then clearly ${f}_{1}$ is a ridesharing of ${T}_{v}^{j-1}$ with the instance $\left({T}_{v}^{j-1},R\left({T}_{v}^{j-1},v\right),v\right)$ . Let ${\alpha }_{1}=driver\left({f}_{1}\right)$ . By the definition of $cap\left({T}_{v}^{j-1},v,{\alpha }_{1}\right)$ we have $cap\left({f}_{1}\right)\le cap\left({T}_{v}^{j-1},v,{\alpha }_{1}\right)$ . Similarly, let ${f}_{2}$ be a mapping from $I\left(R\left({T}_{{e}_{j}},v\right)\right)$ to $I\left(R\left({T}_{{e}_{j}},v\right)\right)$ such that ${f}_{2}\left(i\right)=f\left(i\right)$ for each $i\in I\left(R\left({T}_{{e}_{j}},v\right)\right)$ . Then clearly ${f}_{2}$ is a ridesharing of ${T}_{{e}_{j}}$ with the instance $\left({T}_{{e}_{j}},R\left({T}_{{e}_{j}},v\right),v\right)$ . Let ${\alpha }_{2}=driver\left({f}_{2}\right)$ . By the definition of $cap\left({T}_{{e}_{j}},v,{\alpha }_{2}\right)$ we have $cap\left({f}_{2}\right)\le cap\left({T}_{{e}_{j}},v,{\alpha }_{2}\right)$ . Furthermore, $cap\left(f\right)=cap\left({f}_{1}\right)+cap\left({f}_{2}\right)$ and $driver\left(f\right)=driver\left({f}_{1}\right)+driver\left({f}_{2}\right)$ , and hence $\alpha ={\alpha }_{1}+{\alpha }_{2}$ . We thus have

$\begin{array}{c}cap\left({T}_{v}^{j},v,\alpha \right)=cap\left(f\right)=cap\left({f}_{1}\right)+cap\left({f}_{2}\right)\\ \le cap\left({T}_{v}^{j-1},v,{\alpha }_{1}\right)+cap\left({T}_{{e}_{j}},v,{\alpha }_{2}\right),\end{array}$

verified Equation (6).

We next prove

$cap\left({T}_{v}^{j},v,\alpha \right)\ge \underset{0\le {\alpha }_{1},{\alpha }_{2}\le \alpha ,\text{\hspace{0.17em}}{\alpha }_{1}+{\alpha }_{2}=\alpha }{max}\left\{cap\left({T}_{v}^{j-1},v,{\alpha }_{1}\right)+cap\left({T}_{{e}_{j}},v,{\alpha }_{2}\right)\right\}.$ (7)

Choose ${{\alpha }^{\prime }}_{1}$ and ${{\alpha }^{\prime }}_{2}$ such that $0\le {{\alpha }^{\prime }}_{1},{{\alpha }^{\prime }}_{2}\le \alpha$ , ${{\alpha }^{\prime }}_{1}+{{\alpha }^{\prime }}_{2}=\alpha$ and

$cap\left({T}_{v}^{j-1},v,{\alpha }_{{1}^{\prime }}\right)+cap\left({T}_{{e}_{j}},v,{\alpha }_{{2}^{\prime }}\right)=\underset{0\le {\alpha }_{1},{\alpha }_{2}\le \alpha ,\text{\hspace{0.17em}}{\alpha }_{1}+{\alpha }_{2}=\alpha }{\mathrm{max}}\left\{cap\left({T}_{v}^{j-1},v,{\alpha }_{1}\right)+cap\left({T}_{{e}_{j}},v,{\alpha }_{2}\right)\right\}.$

We may assume $cap\left({T}_{v}^{j-1},v,{{\alpha }^{\prime }}_{1}\right)\overline{)=}-\infty$ and $cap\left({T}_{{e}_{j}},v,{{\alpha }^{\prime }}_{2}\right)\overline{)=}-\infty$ ; otherwise Equation (7) trivially holds.

Since $cap\left({T}_{v}^{j-1},v,{{\alpha }^{\prime }}_{1}\right)\overline{)=}\infty$ , there is a ridesharing ${f}_{1}$ with the instance $\left({T}_{v}^{j-1},R\left({T}_{v}^{j-1},v\right),v\right)$ such that $cap\left({f}_{1}\right)=cap\left({T}_{v}^{j-1},v,{{\alpha }^{\prime }}_{1}\right)$ . Similarly, since $cap\left({T}_{{e}_{j}},v,{{\alpha }^{\prime }}_{2}\right)\overline{)=}-\infty$ , there is a ridesharing ${f}_{2}$ with the instance $\left({T}_{{e}_{j}},R\left({T}_{{e}_{j}},v\right),v\right)$ such that $cap\left({f}_{2}\right)=cap\left({T}_{{e}_{j}},v,{{\alpha }^{\prime }}_{2}\right)$ . Let $f$ be a mapping such that for each $i\in I\left(R\left({T}_{v}^{j},v\right)\right)$

$f\left(i\right)=\left\{\begin{array}{ll}{f}_{1}\left(i\right)\hfill & \text{ }if\text{\hspace{0.17em}}i\in \text{\hspace{0.17em}}I\left(R\left({T}_{v}^{j-1},v\right)\right),\text{ }\hfill \\ {f}_{2}\left(i\right)\hfill & \text{ }otherwise,\text{\hspace{0.17em}}that\text{\hspace{0.17em}}is,\text{\hspace{0.17em}}i\in \text{\hspace{0.17em}}I\left(R\left({T}_{{e}_{j}},v\right)\right).\text{ }\hfill \end{array}$

Then clearly $f$ is a ridesharing of ${T}_{v}^{j}$ with the instance $\left({T}_{v}^{j},R\left({T}_{v}^{j},v\right),v\right)$ such that $cap\left(f\right)=cap\left({f}_{1}\right)+cap\left({f}_{2}\right)$ and $driver\left(f\right)=driver\left({f}_{1}\right)+driver\left({f}_{2}\right)$ . By the definition of $cap\left({T}_{v}^{j},v,\alpha \right)$ , we have

$\begin{array}{c}cap\left({T}_{v}^{j},v,\alpha \right)\ge cap\left(f\right)=cap\left({f}_{1}\right)+cap\left({f}_{2}\right)\\ =cap\left({T}_{v}^{j-1},v,{{\alpha }^{\prime }}_{1}\right)+cap\left({T}_{{e}_{j}},v,{{\alpha }^{\prime }}_{2}\right)\\ =\underset{0\le {\alpha }_{1},{\alpha }_{2}\le \alpha ,\text{\hspace{0.17em}}{\alpha }_{1}+{\alpha }_{2}=\alpha }{\mathrm{max}}\left\{cap\left({T}_{v}^{j-1},v,{\alpha }_{1}\right)+cap\left({T}_{{e}_{j}},v,{\alpha }_{2}\right)\right\},\end{array}$

verified Equation (7).

Furthermore, clearly $cap\left({T}_{v}^{j},v,\alpha \right)$ for all $\alpha$ and $j$ , $0\le \alpha \le k$ , can be computed in time $O\left({k}^{2}\right)$ from all $cap\left({T}_{v}^{j-1},v,{\alpha }_{1}\right)$ and $cap\left({T}_{{e}_{j}},v,{\alpha }_{2}\right)$ . ,

2.3. Algorithm

From Lemmas 2.1―1 one can obtain the following algorithm to compute all $cap\left({T}_{v},v,\alpha \right)$ , $v\in V\left(T\right)$ and $0\le \alpha \le k$ .

Algorithm Alg( ${T}_{v},R,v,cap$ ) begin if $v$ is a leaf in $T$ , then $cap\left({T}_{v},v,\alpha \right)=0$ for all $\alpha$ , $0\le \alpha \le k$ , by Lemm 2.1; else if $v$ is an internal vertex in $T$ , then begin let ${v}_{1},{v}_{2},\cdots ,{v}_{l}$ be the children of $v$ ordered arbitrarily, and let ${e}_{j}$ , $1\le j\le l$ , be the edge joining $v$ to ${v}_{j}$ ; for each $j$ , $1\le j\le l$ , compute all $cap\left({T}_{{e}_{j}},v,\alpha \right)$ , $0\le \alpha \le k$ , from all $cap\left({T}_{{v}_{j}},{v}_{j},{\alpha }_{1}\right)$ m $0\le {\alpha }_{1}\le k$ , by Lemma 1; for each $j$ , $1\le j\le l$ , compute all $cap\left({T}_{v}^{j},v,\alpha \right)$ , $0\le \alpha \le k$ , from all $cap\left({T}_{v}^{j-1},v,{\alpha }_{1}\right)$ , $0\le {\alpha }_{1}\le k$ , and all $cap\left({T}_{{e}_{j}},v,{\alpha }_{2}\right)$ , $0\le {\alpha }_{2}\le k$ , by Lemma 1; let $cap\left({T}_{v},v,\alpha \right)=cap\left({T}_{v}^{l},v,\alpha \right)$ for all $\alpha$ , $0\le \alpha \le k$ ; end end

Clearly it runs in time $O\left({k}^{2}n\right)$ 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. , Lu, H. , Ye, Z. 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. doi: 10.4236/jamp.2017.59140.
References
   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

   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

   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

   Brucker, P. and Nordmann, L. (1994) The k-Track Assignment Problem. Computing, 54, 97-122. https://doi.org/10.1007/BF02238071

   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

   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

   Ghoseiri, K., Haghani, A. and Hamedi, M. (1979) Real-Time Ridesharing Matching Problem. Final Report of UMD-2009-05. U.S. Department of Transportation.

   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

Top