Two-Commodity Opposite Direction Network Flow Formulations for the Travelling Salesman Problem

Research output: Contribution to journalJournal articleResearchpeer-review

10 Downloads (Pure)

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 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) 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 flow formulations are strictly stronger than their one-commodity 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 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.
Original languageEnglish
JournalComputational Optimization and Applications
ISSN0926-6003
DOIs
Publication statusAccepted/In press - Jan 2025

Fingerprint

Dive into the research topics of 'Two-Commodity Opposite Direction Network Flow Formulations for the Travelling Salesman Problem'. Together they form a unique fingerprint.

Cite this