VEHICLE ROUTING AND SCHEDULING WITH TIME WINDOW CONSTRAINTS: MODELS AND ALGORITHMS (HEURISTICS)

The effective and efficient management of the distribution of goods or services is becoming increasingly important in both the private and public sectors. A key element of many distribution systems is the routing and scheduling of vehicles through a set of customers. This thesis is concerned with the design and analysis of models and algorithms for the vehicle routing and scheduling problem with time window constraints. These allowable service time constraints arise naturally in problems faced by business organizations which work on fixed time schedules. Given the intrinsic difficulty of this problem class, approximation methods seem to offer the most promise for practical size problems. After describing a variety of heuristics, an extensive computational study of their performance is conducted. The problem set includes routing and scheduling environments which differ in terms of the type of data being used to generate the problems, the percentage of time windows, their tightness and positioning, and the sechduling horizon. Our results indicate that heuristics are very effective and efficient in solving a wide range of large-scale problems. Several heuristics performed well in different problem environments; among them, the behavior of one heuristic was consistently very good. A parametric analysis of the best heuristic is conducted, and the effect of factors, such as time windows\u27 density, tightness, and positioning, on the behavior of heuristics is analyzed and found to be very strong. Analytical results concerning the behavior of approximation methods are then derived through worst-case analysis. For a variety of heuristics, it is shown that their worst-case behavior on n customer problems is (OMEGA)(n), for the number of vehicles used and the total distance traveled. Time window constraints alter the computational complexity of even easy problems involving routing components. It is shown that the spanning tree problem with time windows is NP-hard. We then analyze alternative model formulations and present new possibilities for developing branch and bound algorithms which exploit the structure of the time window constraints for this and more general problems with time windows. Approximate methods are also presented, and their performance is assessed theoretically