TITLE:
A Dynamic Programming Algorithm for the Ridersharing Problem Restricted with Unique Destination and Zero Detour on Trees
AUTHORS:
Yiming Li, Huiqiang Lu, Zhiqian Ye, Xiao Zhou
KEYWORDS:
Dynamic Programming Algorithm, Rideshare, Tree
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.5 No.9,
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.