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