Heuristic search and its transit applications.

Abstract

This dissertation is concerned with the development, analysis, and application of solution techniques for any discrete optimization problem that can be represented by a locally finite graph. These solution techniques are based on heuristic search procedures from the artificial intelligence (AI) literature. Application is made to the problem of scheduling and routing paratransit vehicles in an intermodal itinerary selection problem involving fixed-route buses. Relevant background on heuristic search theory is presented. We then investigate a multiobjective generalization of AO*, an important AI-based AND/OR graph search algorithm. Similar to AO*, this generalization is found to be complete and admissible under appropriately adjusted assumptions. Other relevant properties of this generalization that are considered include termination, comparison of heuristics, and efficiency. We also develop two new OR graph search algorithms, BA* and DA*, which are both extensions of A*. Under reasonable conditions, these two algorithms find a minimum cost path from the start node to a finite goal node set in a directed OR graph, assuming that estimates of the optimal costs from each node to the goal node set are given, estimates of all arc costs are given, but that actual arc costs require determination. Characteristics of these two algorithms and results concerning the comparison of these two algorithms are presented. A complex vehicle routing and scheduling problem, called the multimodal dial-a-ride problem, is defined in this dissertation. A multimodal dial-a-ride problem is a dial-a-ride problem that involves both paratransit vehicles and fixed route buses. We develop a solution procedure for the multimodal dial-a-ride problem by integrating heuristic search techniques with simulated annealing, a solution technique for combinatorial optimization problems. Computational experience with simulated data and real data is provided. Finally, some extensions to the work reported in this dissertation and possible directions for future research are discussed.