The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristic - Plante, Robert D.; Lowe, Timothy J.; Chandrasekaran, R. (Operations Research, 1987)
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.