The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristic

Robert D. Plante, Timothy J. Lowe and R. Chandrasekaran
Additional contact information
Robert D. Plante: Purdue University, West Lafayette, Indiana
Timothy J. Lowe: Purdue University, West Lafayette, Indiana
R. Chandrasekaran: The University of Texas at Dallas, Richardson, Texas

Operations Research, 1987, vol. 35, issue 5, 772-783

Abstract: 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.

Keywords: 490 overhauling gas turbine engines; 628 combinatorial optimization; 634 heuristic solution procedure (search for similar items in EconPapers)
Date: 1987
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.35.5.772 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:35:y:1987:i:5:p:772-783

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().