The undirected m-peripatetic salesman problem:: Polyhedral results and new algorithms
成果类型：
Article
署名作者：
Duchenne, Eric; Laporte, Gilbert; Semet, Frederic
署名单位：
Centre National de la Recherche Scientifique (CNRS); Universite Polytechnique Hauts-de-France; Universite de Montreal; HEC Montreal
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1070.0387
发表日期：
2007
页码：
949-965
关键词：
摘要：
In the m-peripatetic salesman problem (m-PSP), the aim is to determine m edge disjoint Hamiltonian cycles of minimum total cost on a graph. This article introduces new valid inequalities and polyhedral results for the m-PSP. An improved 2-index branch-and-cut algorithm is developed. Tests performed on randomly generated and TSPLIB Euclidean instances indicate that this algorithm can solve instances with more than double the size of what was previously achievable.