A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem

Research output: Contribution to journalJournal articleResearchpeer-review

1162 Downloads (Pure)

Abstract

When considering the static 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, and extended 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 dates, each following every new customer request. The algorithm optimizes only over known inputs and does not anticipate future customer requests.
Original languageEnglish
JournalTransportation Science
Volume14
Issue number2
Pages (from-to)130-154
Number of pages25
DOIs
Publication statusPublished - 1980
Externally publishedYes

Fingerprint

Dive into the research topics of 'A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem'. Together they form a unique fingerprint.

Cite this