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

HTML  XML Download Download as PDF (Size: 423KB)  PP. 1678-1685  
DOI: 10.4236/jamp.2017.59140    679 Downloads   1,371 Views  

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.

Share and Cite:

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.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.