A Criteria-Based Approach to the Traveling Salesman Problem (TSP)

The “traveling salesman problem (TSP)” is a classic minimum cost network flow problem in mathematical programming and graph theory that can be formulated in multiple configurations. The fundamental question, however, is: “what is a cost”? The original “traveling salesman problem (TSP)” defines distance as the cost and the objective is to minimize distance traveled. This paper proposes other “cost” criteria to the original problem and also proposes a maximum revenue network flow as a variant to improve managerial decision-making. The proposed decision table methodology can be applied to problems that involve multiple locations or multiple tasks to complete.