University of California Transportation Center

The last several years has witnessed a sharp increase in interest in stochastic and dynamic routing and scheduling. Because many systems contain inherently stochastic factors, decisions must often be made before all necessary information is available. To a certain degree, algorithm development has lagged behind implementation. In order to fully leverage advances in information technologies, algorithms which explicitly consider dynamic and stochastic factors should be examined. Or, if static algorithms are to be applied in these dynamic environments, proper attention should be given to examining the conditions under which these perform well. This is the primary theme of this research.

This dissertation examines several key dynamic and stochastic routing and scheduling problems: the probabilistic traveling salesman problem, the dynamic traveling salesman problem and the dynamic traveling repair problem. In addition, as part of our research on the dynamic traveling salesman problem, we examine a related M/G/l queuing problem with switching costs. These problems arise in pickup and and delivery options, repair fleet operations, and emergency vehicle and policy operations in addition to many computing, telecommunications and manufacturing applications.

As part of our research, we demonstrate that heuristics which rely on partitioning the service region into smaller regions can be very effective for dynamic routing problems. Using a partitioning scheme we show that if a constant guarantee algorithm exists for the k- capacitated median problem, then a constant guarantee algorithm exists for the probabilistic traveling salesman problem. For the DTRP, we show that a partitioning algorithm is asymptotically optimal when the traffic intensity is high.

We show that robust a priori algorithms can be developed for dynamic routing problems. For the M/G/l with switchover cost, we show that an a priori cyclic polling algorithm works very well using both theoretical and simulation analysis. Cyclic polling algorithm also works well for dynamic traveling salesman problem. For these both problems, we identify certain conditions under which the a priori (cyclic polluting) solution is close to optimal. We demonstrate that the existence of the connection between the static and dynamic vehicle routing and scheduling problem that have been observed by earlier researchers.