Knowledge that Transforms

This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints. 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, we conduct an extensive computational study of their performance. The problem set includes routing and scheduling environments that differ in terms of the type of data used to generate the problems, the percentage of customers with time windows, their tightness and positioning, and the scheduling horizon. We found that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.

In this paper we analyze an optimization problem that arises in the overhaul of a gas turbine engine. This problem involves the placement of nozzle guide vanes in the nozzle of the engine. The objective of the vane placement is to attain “uniform” flow (equalized distribution of hot fuel gases) about the circumference of the engine nozzle. We show that this placement problem is equivalent to a traveling salesman problem (TSP) whose cost matrix is a product matrix. Exploiting properties of the special form of the cost matrix, we give a heuristic algorithm for solving the problem, and derive a posteriori lower bounds for the heuristic. We show that the heuristic performs extremely well on both real and simulated data. Finally, we present and develop the theoretical results that are the foundation of the proposed heuristic.