Accelerating the Miller–Tucker–Zemlin model for the asymmetric traveling salesman problem. (15th June 2020)

• Record Type: Journal Article
• Authors: Campuzano, Giovanni; Obreque, Carlos; Aguayo, Maichel M.
• Is Part Of: Expert systems with applications. Volume 148(2020)
• Publication Date: 2020-06-15
• Subjects: Traveling salesman -- Asymmetric traveling salesman problem (ATSP) -- Miller–Tucker–Zemlin (MTZ) -- Subtour elimination constraints (SECs); Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2020.113229
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: Valid inequalities accelerate the performance of the Miller–Tucker–Zemlin model. Valid inequalities improve the performance of the Desrochers and Laporte model. The enhanced Miller–Tucker–Zemlin model outperforms the most effective formulations. The proposed approach may be useful to solve other routing problems. Abstract: In this article, we present an easy to implement algorithmic approach that improves the computational performance of the Miller–Tucker–Zemlin (MTZ) model for the asymmetric traveling salesman problem (ATSP) by efficiently generating valid inequalities from fractional solutions. Computational experiments show that the proposed approach enhances considerably the performance of MTZ-based formulations reported in the literature. By adding facet-defining inequalities of the underline ATSP-polytope, the number of nodes in the branch-and-bound tree is drastically reduced, and the convergence of the MTZ-type formulations is accelerated. We also extend this idea to solve the multiple asymmetric traveling salesman problem (mATSP). This approach can help practitioners to solve real-life problems to near optimality using a standard optimization solver and may be useful to solve a variety of routing problems that use MTZ-type of subtour elimination constraints.