Heuristics and Performance Metamodels for the Dynamic Dial-a-Ride Problem

Abstract

Explicit performance models of a transit system are often very useful in facilitating system design, optimization, alternative comparison, and gaining insights into the system relations. In this dissertation, three performance metamodels have been developed using the response surface metamodeling approach for the dynamic many-to-many dial-a-ride problem. The models predict, respectively, the minimum vehicle fleet size requirement, the average passenger time deviation from desired time, and the average passenger ride time ratio. The metamodeling approach incorporates in its simulation experiments a detailed vehicle routing algorithm and passenger time constraints, which are oversimplified or omitted by analytical approaches.

A new rejected-reinsertion heuristic has been developed for the static dial-a-ride problem. The heuristic achieves vehicle reductions of up to 17% over the parallel insertion heuristic and of up to 12% over the regret insertion heuristic. The static heuristic has been extended to two online heuristics for the dynamic large-scale dial-a-ride problem, the immediate-insertion online heuristic and the rolling horizon online heuristic. The rolling horizon heuristic outperforms the immediate insertion heuristic by up to 10% vehicle reduction for demand scenario in which different demand lead times exist. Their computational efficiency makes them usable in real dynamic applications. The rolling horizon heuristic with an improvement procedure is employed in the simulation experiments upon which the metamodels are based. It is simple in concept, and it does not involve complex algorithm parameter calibration.

The response surface methodology models the functional relation between an output of a process and its input factors through well designed experiments and statistical analysis. A face-centered central composite design is used in this study to determine the design points. Models are based on data collected from the simulation experiments and fitted using SPSS's linear regression function. The metamodels are validated using an additional set of randomly generated data. The resulting models are relatively simple in structure, inexpensive to use and fairly robust. The applications of the performance models are illustrated through the parametric analysis and optimization of a dial-a-ride service considering the tradeoff between operator cost and user cost.