A Dynamic Programming Algorithm for the Ridersharing Problem Restricted with Unique Destination and Zero Detour on Trees

Yiming Li¹, Huiqiang Lu², Zhiqian Ye³, Xiao Zhou⁴

¹Wenzhou University, Wenzhou, China.
²Zhejiang University of Technology, Hangzhou, China.
³Zhejiang University, Hangzhou, China.
⁴Tohoku University, Sendai, Japan.

DOI: 10.4236/jamp.2017.59140                

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 $V\mathrm{<mo\; stretchy="false">\; (\; </mo>}G\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ and edge set $E\mathrm{<mo\; stretchy="false">\; (\; </mo>}G\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Let k be a positive integer, and let a ridesharing infomation R be a set of k trips $\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{,}{s}_i\mathrm{,}{t}_i\mathrm{,}{c}_i\mathrm{,}{d}_i\mathrm{,}{P}_i\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $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\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ be the set of the indices of all trips in R which should be served, that is, $I(R)=\left\{i\right|(i,s_i,t_i,c_i,d_i,P_i)\in R\}$ . A ridesharing of a graph G with R is a mapping $f\mathrm{<mo>\; :\; </mo>}I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; )\; </mo>}\to I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ such that, for each $i\in I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , if $f^{-1}(i)\cancel{=}\varnothing$ then $i\in f^{-1}\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $\mathrm{<mo>\; |\; </mo>}{f}^{-1}\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; |\; </mo>}\le c_i$ and there is a trip (walk) P satisfying $P_j\subseteq P$ for each $j\in f^{-1}\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ and the distance of P is at most $d_i$ plus the distance of $P_i$ , where $f^{-1}(i)=\left\{j\right|f(j)=i\}$ , that is, $f^{-1}\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ is the set of the indices of trips served by the i-th driver. Let $driver\mathrm{<mo\; stretchy="false">\; (\; </mo>}f\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ be the number of drivers of a ridesharing f, that is,

$driver(f)=\left|\left\{i|f^{-1}(i)\cancel{=}\varnothing \right\}\right|.$

A ridesharing f of G with R is optimal if $driver\mathrm{<mo\; stretchy="false">\; (\; </mo>}f\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ 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 $O\mathrm{<mo\; stretchy="false">\; (\; </mo>}{k}^{2}n\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , 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 $O\mathrm{<mo\; stretchy="false">\; (\; </mo>}{k}^{2}n\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ 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 $\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{,}{s}_i\mathrm{,}{t}_i\mathrm{,}{c}_i\mathrm{,}{d}_i\mathrm{,}{P}_i\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $1\le i\le k$ , 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, $1\le i\le k$ , we have $t_i=r$ and $d_i=0$ , and $P_i$ is the unique path in T. For the sake of notational convenience we redefine the ridesharing information $R=\{(i,s_i,c_i)|1\le i\le k\}$ , and let $\mathrm{<mo\; stretchy="false">\; (\; </mo>}T\mathrm{,}R\mathrm{,}r\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ 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 $T_v$ the subtree of T which is rooted at v and is induced by all descendants of v in T. For each edge $e\mathrm{<mo>\; =\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}v\mathrm{,}{v}^{\prime }\mathrm{<mo\; stretchy="false">\; )\; </mo>}\in E\mathrm{<mo\; stretchy="false">\; (\; </mo>}T\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ such that v is the parent of $v^{\prime }$ in T, we denote by $T_e$ the subtree of T which is rooted at v and is induced by v, $v^{\prime }$ and the descendants of $v^{\prime }$ in T. For a subtree $T^{\prime }$ of T rooted at v, let

$R(T^{\prime },v)=\{(i,s_i,c_i)\in R|s_i\in V(T^{\prime })\backslash \left\{v\right\}\}.$

For each $\alpha$ , $0\le \alpha \le k$ , we denote by $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}^{\prime }\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ the maximum number of additional trips which can be served after serving all trips in $R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}^{\prime }\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ using at most $\alpha$ drivers, that is,

$cap(T^{\prime },v,\alpha )=\underset{f}{\max }cap(f)$

where the maximum is taken over all ridesharings f with the instance $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}^{\prime }\mathrm{,}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}^{\prime }\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ satisfying $driver\mathrm{<mo\; stretchy="false">\; (\; </mo>}f\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le \alpha$ and

$cap(f)={\displaystyle \underset{i\in I(R(T^{\prime },v)),f^{-1}(i)\cancel{=}\varnothing }{\sum }}{c}_i-\left|R(T^{\prime },v)\right|.$

Let $cap(T^{\prime },v,\alpha )=-\infty$ if $\alpha$ drivers can not serve all trips in $R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}^{\prime }\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ with the unique destination v. The main step of our algorithm is to compute the table of the functions $cap$ from leaves to the root r of T by dynamic programming. From the table on the root r, it is obvious that the minimum $\alpha$ satisfying $cap(T_r,r,\alpha )\cancel{=}-\infty$ 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 $T_v$ . Therefore, by the definition of $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , we trivially have the following lemma.

Let v be an arbitrary leaf of T. Then $cap(T_v,v,\alpha )=0$ for each $\alpha \ge 0$ .

2.2. The Vertex v Is an Internal Vertex in T

In this case v is an internal vertex in T. Let $v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{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$ , as illustrated in Figure 1. The subtree $T_{v_j}$ , $1\le j\le l$ , of T is rooted at $v_j$ and is induced by all descendants of $v_j$ in T. We denote by $T_v^j$ the subtree of T which consists of the vertex v, the edges $e_1\mathrm{,}{e}_2\mathrm{,}\cdots \mathrm{,}{e}_j$ and the subtrees $T_{v_1},T_{v_2},\cdots ,T_{v_j}$ . $T_v^{j-1}$ is indicated by a dotted line in Figure 1. Obviousely $T_v=T_v^l$ .

Figure 1. Subtrees $T_v$ , $T_v^{j-1}$ and $T_{e_j}$ rooted at v.

We first compute the function $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ for all $\alpha$ and $j$ , $0\le \alpha \le k$ and $1\le j\le l$ , as in the following lemma 1, where $T_{e_j}$ is the subtree obtained from $T_{v_j}$ by adding the edge $e_j$ , indicated by a dotted thick line in Figure 1.

Let $R(v_j)=\{(i,s_i,c_i)\in R|s_i=v_j\}$ be the subset of R such that the start location is at $v_j$ , and let

$\gamma (T_{e_j},v,\alpha )=\underset{0\le {\alpha }_1\le \alpha }{\max }\left\{cap(T_{v_j},v_j,{\alpha }_1)+\underset{I^{\prime }\subseteq I(R(v_j)),\left|I^{\prime }\right|=\alpha -{\alpha }_1}{\max }{\displaystyle \underset{i\in I^{\prime }}{\sum }}{c}_i-|R(v_j)|\right\}.$ (1)

Then

$cap(T_{e_j},v,\alpha )=\{\begin{array}{ll}\gamma (T_{e_j},v,\alpha )\hfill & \text{if}\gamma (T_{e_j},v,\alpha )\ge 0;\hfill \\ -\infty \hfill & \text{otherwise}\text{.}\hfill \end{array}$ (2)

Furthermore, all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $0\le \alpha \le k$ , can be computed from all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $0\le {\alpha }_1\le k$ , in time $O\mathrm{<mo\; stretchy="false">\; (\; </mo>}{k}^2\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ .

Proof. We first prove

$cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le \gamma \mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>.}$ (3)

If $cap(T_{e_j},v,\alpha )=-\infty$ , then Equation (3) trivially holds. We thus assume that $cap(T_{e_j},v,\alpha )\cancel{=}-\infty$ , that is, there is a ridesharing f with the instance $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ such that $driver\mathrm{<mo\; stretchy="false">\; (\; </mo>}f\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le \alpha$ and $cap(T_{e_j},v,\alpha )=cap(f)$ . Let $f^{\prime }$ be a mapping from $I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ to $I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ such that $f^{\prime }(i)=f(i)$ for each $i\in I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ . Then clearly $f^{\prime }$ is a ridesharing of $T_{v_j}$ with the instance $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>,}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ since f is a ridesharing of $T_{e_j}$ and $T_{v_j}$ is a subtree of $T_{e_j}$ . Let ${\alpha }_1=driver(f^{\prime })$ , then by the definition of $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , we have $cap(f^{\prime })\le cap(T_{v_j},v_j,{\alpha }_1)$ . Let

$I^{\prime }=\{i\in I(R(v_j))|f^{-1}(i)\cancel{=}\varnothing \}.$

Then the $driver\mathrm{<mo\; stretchy="false">\; (\; </mo>}f\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ drivers in f consists of the $driver\mathrm{<mo\; stretchy="false">\; (\; </mo>}{f}^{\prime }\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ drivers from start locations in $T_{v_j}$ and the $\mathrm{<mo>\; |\; </mo>}{I}^{\prime }\mathrm{<mo>\; |\; </mo>}$ drivers from start locations at $v_j$ , and hence $driver(f)=driver(f^{\prime })+\left|I^{\prime }\right|$ . Therefore, we have $\alpha ={\alpha }_1+\left|I^{\prime }\right|$ and

$\begin{array}{c}cap(T_{e_j},v,\alpha )=cap(f)={\displaystyle \underset{i\in I(R(T_{e_j},v)),f^{-1}(i)\cancel{=}\varnothing }{\sum }}{c}_i-\left|R(T_{e_j},v)\right|\\ ={\displaystyle \underset{i\in I(R(T_{v_j},v_j)),f^{-1}(i)\cancel{=}\varnothing }{\sum }}{c}_i+{\displaystyle \underset{i\in I(R(v_j)),f^{-1}(i)\cancel{=}\varnothing }{\sum }}{c}_i-\left|R(T_{v_j},v_j)\right|-\left|R(v_j)\right|\\ =cap(f^{\prime })+{\displaystyle \underset{i\in I^{\prime }}{\sum }}{c}_i-|R(v_j)|\le cap(T_{v_j},v_j,{\alpha }_1)+{\displaystyle \underset{i\in I^{\prime }}{\sum }}{c}_i-|R(v_j)|\\ \le \gamma (T_{e_j},v,\alpha ),\end{array}$

verified Equation (3).

We next prove that

$cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge \gamma \mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ (4)

if $\gamma \mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge 0$ . By Equation (1) m choose ${\alpha }_1$ and $I^{\prime }$ such that $0\le {\alpha }_1\le \alpha$ , $I^{\prime }\subseteq I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ , $\left|I^{\prime }\right|=\alpha -{\alpha }_1$ and

$\gamma (T_{e_j},v,\alpha )=cap(T_{v_j},v_j,{\alpha }_1)+{\displaystyle \underset{i\in I^{\prime }}{\sum }}{c}_i-|R(v_j)|.$ (5)

Since $\gamma \mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge 0$ , we have $cap(T_{v_j},v_j,{\alpha }_1)\cancel{=}-\infty$ , and hence there is a ridesharing $f^{\prime }$ with the instance $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>,}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ such that $driver\mathrm{<mo\; stretchy="false">\; (\; </mo>}{f}^{\prime }\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le {\alpha }_1$ and $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{f}^{\prime }\mathrm{<mo\; stretchy="false">\; )\; </mo>}=cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . One can obtain a ridesharing $f$ with the instance $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ from $f^{\prime }$ using ${\alpha }_1$ drivers in $f^{\prime }$ plus the new $\mathrm{<mo>\; |\; </mo>}{I}^{\prime }\mathrm{<mo>\; |\; </mo>}$ drivers having the trip indices in $I^{\prime }$ . By Equation (5) we have $cap(f)=\gamma (T_{e_j},v,\alpha )$ , and by the definition $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}f\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , and hence we have $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge \gamma \mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , verified Equation (4) .

By Equations (3) and (4) m Equation (2) holds true. We finally show that for each $\alpha$ , $0\le \alpha \le k$ , $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , can be computed from all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $0\le {\alpha }_1\le k$ , in time $O\mathrm{<mo\; stretchy="false">\; (\; </mo>}{k}^2\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ as follows.

By Equation (1) for a given ${\alpha }_1$ , clearly $I^{\prime }$ is the set of the $\alpha -{\alpha }_1$ indices $i\in I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ such that $c_i$ is at least $\alpha -{\alpha }_1$ largest among all $c_{i^{\prime }}$ , $i^{\prime }\in I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ . One can sorted all $c_i$ , $i\in I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ ), in non-increasing order, and compute all prefix sum of $c_i$ . This can be done in time $O\mathrm{<mo\; stretchy="false">\; (\; </mo>}klogk\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Then, for any given pair of $\alpha$ and ${\alpha }_1$ , $0\le {\alpha }_1\le \alpha \le k$ ,

$\underset{I^{\prime }\subseteq I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{v}_j\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>,}\mathrm{<mo>\; |\; </mo>}{I}^{\prime }\mathrm{<mo>\; |\; </mo>\; <mo>\; =\; </mo>}\alpha -{\alpha }_1}{max}{\displaystyle \underset{i\in I^{\prime }}{\sum }}{c}_i$

can be computed in $O\mathrm{<mo\; stretchy="false">\; (\; </mo>1\; <mo\; stretchy="false">\; )\; </mo>}$ time. One thus can compute $\gamma \mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ in time $O\mathrm{<mo\; stretchy="false">\; (\; </mo>}k\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ for each $\alpha$ since ${\alpha }_1\le \alpha \le k$ , and hence $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ for all $\alpha$ , $0\le \alpha \le k$ , can be computed from all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ in time $O\mathrm{<mo\; stretchy="false">\; (\; </mo>}{k}^2\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . ,

We finally compute the function $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ for all $\alpha$ and $j$ , $0\le \alpha \le k$ and $1\le j\le l$ , as in the following lemma.

For each $\alpha$ , $0\le \alpha \le k$ ,

$cap(T_v^j,v,\alpha )=\underset{0\le {\alpha }_1,{\alpha }_2\le \alpha ,{\alpha }_1+{\alpha }_2=\alpha }{\max }\left\{cap(T_v^{j-1},v,{\alpha }_1)+cap(T_{e_j},v,{\alpha }_2)\right\}.$

Furthermore, all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $0\le \alpha \le k$ , can be computed from all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ and $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{,}{\alpha }_2\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ in time $O\mathrm{<mo\; stretchy="false">\; (\; </mo>}{k}^2\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ .

Proof. We first prove

$cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}\le \underset{0\le {\alpha }_1\mathrm{,}{\alpha }_2\le \alpha \mathrm{,}{\alpha }_1+{\alpha }_2\mathrm{<mo>\; =\; </mo>}\alpha }{max}\left\{cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}+cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}{\alpha }_2\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right\}\mathrm{.}$ (6)

If $cap(T_v^j,v,\alpha )=-\infty$ , then Equation (6) trivially holds. We thus assume that $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{,}\alpha )\cancel{=}-\infty$ , that is, there is a ridesharing f with the instance $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ such that $driver\mathrm{<mo\; stretchy="false">\; (\; </mo>}f\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le \alpha$ and $cap(T_v^j,v,\alpha )=cap(f)$ . Let $f_1$ be a mapping from $I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ to $I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ such that $f_1(i)=f(i)$ for each $i\in I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ . Then clearly $f_1$ is a ridesharing of $T_v^{j-1}$ with the instance $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Let ${\alpha }_1=driver(f_1)$ . By the definition of $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ we have $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{f}_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Similarly, let $f_2$ be a mapping from $I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ to $I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ such that $f_2(i)=f(i)$ for each $i\in I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$ . Then clearly $f_2$ is a ridesharing of $T_{e_j}$ with the instance $(T_{e_j},R(T_{e_j},v),v)$ . Let ${\alpha }_2=driver(f_2)$ . By the definition of $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}{\alpha }_2\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ we have $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{f}_2\mathrm{<mo\; stretchy="false">\; )\; </mo>}\le cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}{\alpha }_2\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Furthermore, $cap(f)=cap(f_1)+cap(f_2)$ and $driver(f)=driver(f_1)+driver(f_2)$ , and hence $\alpha ={\alpha }_1+{\alpha }_2$ . We thus have

$\begin{array}{c}cap(T_v^j,v,\alpha )=cap(f)=cap(f_1)+cap(f_2)\\ \le cap(T_v^{j-1},v,{\alpha }_1)+cap(T_{e_j},v,{\alpha }_2),\end{array}$

verified Equation (6).

We next prove

$cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}\ge \underset{0\le {\alpha }_1\mathrm{,}{\alpha }_2\le \alpha \mathrm{,}{\alpha }_1+{\alpha }_2\mathrm{<mo>\; =\; </mo>}\alpha }{max}\left\{cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}+cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}{\alpha }_2\mathrm{<mo\; stretchy="false">\; )\; </mo>}\right\}\mathrm{.}$ (7)

Choose ${{\alpha }^{\prime }}_1$ and ${{\alpha }^{\prime }}_2$ such that $0\le {{\alpha }^{\prime }}_1\mathrm{,}{{\alpha }^{\prime }}_2\le \alpha$ , ${{\alpha }^{\prime }}_1+{{\alpha }^{\prime }}_2=\alpha$ and

$cap(T_v^{j-1},v,{\alpha }_{1^{\prime }})+cap(T_{e_j},v,{\alpha }_{2^{\prime }})=\underset{0\le {\alpha }_1,{\alpha }_2\le \alpha ,{\alpha }_1+{\alpha }_2=\alpha }{\max }\left\{cap(T_v^{j-1},v,{\alpha }_1)+cap(T_{e_j},v,{\alpha }_2)\right\}.$

We may assume $cap(T_v^{j-1},v,{{\alpha }^{\prime }}_1)\cancel{=}-\infty$ and $cap(T_{e_j},v,{{\alpha }^{\prime }}_2)\cancel{=}-\infty$ ; otherwise Equation (7) trivially holds.

Since $cap(T_v^{j-1},v,{{\alpha }^{\prime }}_1)\cancel{=}\infty$ , there is a ridesharing $f_1$ with the instance $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ such that $cap(f_1)=cap(T_v^{j-1},v,{{\alpha }^{\prime }}_1)$ . Similarly, since $cap(T_{e_j},v,{{\alpha }^{\prime }}_2)\cancel{=}-\infty$ , there is a ridesharing $f_2$ with the instance $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ such that $cap(f_2)=cap(T_{e_j},v,{{\alpha }^{\prime }}_2)$ . Let $f$ be a mapping such that for each $i\in I\mathrm{<mo\; stretchy="false">\; (\; </mo>}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; )\; </mo>}$

$f(i)=\{\begin{array}{ll}{f}_1(i)\hfill & ifi\in I(R(T_v^{j-1},v)),\hfill \\ f_2(i)\hfill & otherwise,thatis,i\in I(R(T_{e_j},v)).\hfill \end{array}$

Then clearly $f$ is a ridesharing of $T_v^j$ with the instance $\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}R\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>,}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ such that $cap(f)=cap(f_1)+cap(f_2)$ and $driver(f)=driver(f_1)+driver(f_2)$ . By the definition of $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , we have

$\begin{array}{c}cap(T_v^j,v,\alpha )\ge cap(f)=cap(f_1)+cap(f_2)\\ =cap(T_v^{j-1},v,{{\alpha }^{\prime }}_1)+cap(T_{e_j},v,{{\alpha }^{\prime }}_2)\\ =\underset{0\le {\alpha }_1,{\alpha }_2\le \alpha ,{\alpha }_1+{\alpha }_2=\alpha }{\max }\left\{cap(T_v^{j-1},v,{\alpha }_1)+cap(T_{e_j},v,{\alpha }_2)\right\},\end{array}$

verified Equation (7).

Furthermore, clearly $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ for all $\alpha$ and $j$ , $0\le \alpha \le k$ , can be computed in time $O\mathrm{<mo\; stretchy="false">\; (\; </mo>}{k}^2\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ from all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ and $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}{\alpha }_2\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . ,

2.3. Algorithm

From Lemmas 2.1―1 one can obtain the following algorithm to compute all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $v\in V\mathrm{<mo\; stretchy="false">\; (\; </mo>}T\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ and $0\le \alpha \le k$ .

Algorithm Alg( $T_v\mathrm{,}R\mathrm{,}v\mathrm{,}cap$ ) begin if $v$ is a leaf in $T$ , then $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; =\; </mo>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\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{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\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $0\le \alpha \le k$ , from all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{v_j}\mathrm{,}{v}_j\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ m $0\le {\alpha }_1\le k$ , by Lemma 1; for each $j$ , $1\le j\le l$ , compute all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^j\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $0\le \alpha \le k$ , from all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^{j-1}\mathrm{,}v\mathrm{,}{\alpha }_1\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $0\le {\alpha }_1\le k$ , and all $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_{e_j}\mathrm{,}v\mathrm{,}{\alpha }_2\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $0\le {\alpha }_2\le k$ , by Lemma 1; let $cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; =\; </mo>}cap\mathrm{<mo\; stretchy="false">\; (\; </mo>}{T}_v^l\mathrm{,}v\mathrm{,}\alpha \mathrm{<mo\; stretchy="false">\; )\; </mo>}$ for all $\alpha$ , $0\le \alpha \le k$ ; end end

Clearly it runs in time $O\mathrm{<mo\; stretchy="false">\; (\; </mo>}{k}^{2}n\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ 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).

Conflicts of Interest

The authors declare no conflicts of interest.

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