Two-commodity opposite direction network flow formulations for the travelling salesman problem

Abstract This paper considers the well-known Travelling Salesman Problem (TSP) in its symmetric and asymmetric versions. A distinctive feature of the symmetric version of the problem is the ability to formulate it as an undirected network optimization problem using $$n(n - 1)/2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> binary variables, where n is the number of locations involved in the problem. At the same time, formulating the asymmetric version of the problem generally requires the full set of $$n(n - 1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> binary variables. This paper presents a new approach to formulate the symmetric and asymmetric TSPs based on the flow of two commodities. Unlike traditional approaches formulating the problem with the flow of multiple commodities, the flow of two commodities considered in this paper is organized in opposite directions along a Hamiltonian cycle in the complete graph with n nodes. The proposed two-commodity network flow formulations are strictly stronger than their one-commodity flow counterparts in terms of the quality of their linear programming relaxations. This is a new result in the sense that the existing two-commodity network flow formulations of the TSP provide lower bounds that are no different from those of the corresponding one-commodity flow formulations. Moreover, the opposite direction flow of two commodities allows us to formulate the asymmetric TSP with only $$n(n - 1)/2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> binary variables, just as in the case of symmetric TSP. This result suggests that various classes of valid inequalities based upon the polyhedral structure of the symmetric problem are sufficient for designing branch-and-cut algorithms for the asymmetric problem. Finally, the proposed mathematical programming formulations are compared to the existing approaches analytically and using an extensive computational study.