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

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