Multiple asymmetric traveling salesmen problem with and without precedence constraints: Performance comparison of alternative formulations

• Published in: Computers & operations research 2014-11, Vol.51, p.64-89
• Main Authors: Sarin, Subhash C., Sherali, Hanif D., Judd, Jason D., Tsai, Pei-Fang (Jennifer)
• Format: Article
• Language: English
• Subjects: Applied sciences; Cities; Comparative analysis; Exact sciences and technology; Flows in networks. Combinatorial problems; Job shops; Logistics; Mathematical models; Multiple asymmetric traveling salesmen problem; Operational research and scientific management; Operational research. Management science; Precedence constraints; Sequential ordering problem; Software; Studies; Traveling salesman problem
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2014.05.014

In this paper, we investigate the performances of 32 formulations for the multiple asymmetric traveling salesman problem (mATSP) from the viewpoint of their tightness and solvability using commercial software. These formulations are either new or are generalizations of those proposed in the literature for the ATSP, including a transformation of the mATSP to an equivalent ATSP formulation. In particular, our results based on the latter strategy reveal that the superiority of the original mATSP formulation over an equivalent transformed ATSP model depends upon the type of formulation used for conducting such a transformation. We also extend our study to the case where precedence relationships exist among the cities. We address two situations in this context. In the first case, a sequential processing order is enforced between a pair of cities only if they both lie on the tour of a particular salesman. The second case involves a more general precedence in which a sequential processing order between certain pairs of cities is enforced regardless of whether the designated pairs are visited by the same or by different salesmen. Our computational experiments demonstrate that the flow-based models afford the tightest LP relaxations. Additionally, the formulations that model the different variants of the mATSP directly, rather than by transforming them to equivalent ATSP problems, are generally faster to solve and are more robust.