Article citationsMore>>

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

has been cited by the following article:

• 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.