zbMATH — the first resource for mathematics

The product matrix traveling salesman problem: an application and solution heuristic. (English) Zbl 0635.90096
Summary: 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.

90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
90C90 Applications of mathematical programming
90B25 Reliability, availability, maintenance, inspection in operations research
Full Text: DOI