A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem

Harilaos N. Psaraftis
Additional contact information
Harilaos N. Psaraftis: Massachusetts Institute of Technology, Cambridge, Massachusetts

Transportation Science, 1980, vol. 14, issue 2, 130-154

Abstract: An investigation of the single-vehicle, many-to-many, immediate-request dial-a-ride problem is developed in two parts (I and II). Part I focuses on the “static” case of the problem. In this case, intermediate requests that may appear during the execution of the route are not considered. A generalized objective function is examined, the minimization of a weighted combination of the time to service all customers and of the total degree of “dissatisfaction” experienced by them while waiting for service. This dissatisfaction is assumed to be a linear function of the waiting and riding times of each customer. Vehicle capacity constraints and special priority rules are part of the problem. A Dynamic Programming approach is developed. The algorithm exhibits a computational effort which, although an exponential function of the size of the problem, is asymptotically lower than the corresponding effort of the classical Dynamic Programming algorithm applied to a Traveling Salesman Problem of the same size. Part II extends this approach to solving the equivalent “dynamic” case. In this case, new customer requests are automatically eligible for consideration at the time they occur. The procedure is an open-ended sequence of updates, each following every new customer request. The algorithm optimizes only over known inputs and does not anticipate future customer requests. Indefinite deferment of a customer’s request is prevented by the priority rules introduced in Part I. Examples in both “static” and “dynamic” cases are presented.

Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (91)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.14.2.130 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:14:y:1980:i:2:p:130-154

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().