Journal of Applied Mathematics and Physics

Volume 5, Issue 9 (September 2017)

ISSN Print: 2327-4352   ISSN Online: 2327-4379

Google-based Impact Factor: 0.61  Citations  

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    402 Downloads   674 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.

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.

Cited by

No relevant information.

Copyright © 2020 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.