期刊
COMPUTERS & OPERATIONS RESEARCH
卷 51, 期 -, 页码 64-89出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2014.05.014
关键词
Multiple asymmetric traveling salesmen; problem; Precedence constraints; Sequential ordering problem
类别
资金
- National Science Foundation [CMMI-0856270, CMMI-0969169]
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. (C) 2014 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据