×

zbMATH — the first resource for mathematics

The travelling salesman problem with neighbourhoods: MINLP solution. (English) Zbl 1270.90055
Summary: The travelling salesman problem (TSP) with neighbourhoods extends the TSP to the case where each vertex of the tour is allowed to move in a given region. This NP-hard optimization problem has recently received increasing attention in several technical fields such as robotics, unmanned aerial vehicles, or utility management. In this paper, the problem is formulated as a non-convex mixed-integer nonlinear programme (MINLP) having the property that fixing all the integer variables to any integer values yields a convex nonlinear program. This property is used to modify the global MINLP optimizer Couenne, improving by orders of magnitude its performance and allowing the exact solution of instances large enough to be useful in applications. Computational results are presented where neighbourhoods are either polyhedra or ellipsoids in \(\mathbb R^2\) or \(\mathbb R^3\) and with the Euclidean norm as distance metric.

MSC:
90C27 Combinatorial optimization
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Applegate D., The Traveling Salesman Problem: A Computational Study (2006) · Zbl 1130.90036
[2] DOI: 10.1016/0166-218X(94)90008-6 · Zbl 0819.90115
[3] DOI: 10.1080/10556780903087124 · Zbl 1179.90237
[4] DOI: 10.1016/j.disopt.2006.10.011 · Zbl 1151.90028
[5] COIN-OR . ” Computational infrastructure for operations researchproject” . Available at http://www.coin-or.org/.
[6] CPLEX . 2011 . Available at http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/.
[7] DOI: 10.1007/978-0-387-48793-9_10 · Zbl 1278.90335
[8] DOI: 10.1142/S0218195909002897 · Zbl 1172.65028
[9] Fourer , R. , Gay , D. and Kernighan , B. 2003 . ” AMPL: A Modeling Language for Mathematical Programming ” . Pacific Grove, CA , USA : Brookes/Cole Publishing . · Zbl 0701.90062
[10] Gentilini I., STSPN Instances
[11] Gueta , L. , Chiba , R. , Ota , J. , Ueyama , T. and Arai , T. 2008 . Coordinated Motion Control of a Robot Arm and a Positioning Table With Arrangement of Multiple Goals . Proceedings of the 2008 IEEE International Conference on Robotics and Automation (ICRA 2008) . May 19–23 2008 , Pasadena , USA. pp. 2252 – 2258 .
[12] Gutin , G. and Punnen , A. 2002 . ” The Traveling Salesman Problem and Its Variations ” . Dordrecht : Kluwer Academic . · Zbl 0996.00026
[13] Hong , S. 1972 . ” A linear programming approach for the travelling salesman problem ” . Baltimore , MD : Johns Hopkins University . Ph.D. thesis
[14] LINDO, Solver Suite
[15] Mennell , W. 2009 . ” Heuristics for solving three routing problems: Close-enough traveling salesman problem, close-enough vehicle routing problem, sequence-dependent team orienteering problem ” . College Park : University of Maryland . Ph.D. thesis
[16] DOI: 10.1145/321043.321046 · Zbl 0100.15101
[17] DOI: 10.1007/3-540-36626-1_5 · Zbl 1183.90309
[18] DOI: 10.1137/1033004 · Zbl 0734.90060
[19] DOI: 10.1007/BF00138693 · Zbl 0856.90104
[20] Vásquez-Gómez , J. , López-Damian , E. and Sucar , L. 2009 . View planning for 3D object reconstruction . 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2009) . October 11–15 2009 , St. Louis , USA. pp. 4015 – 4020 .
[21] DOI: 10.1007/s10107-004-0559-y · Zbl 1134.90542
[22] Wang , P. , Krishnamurti , R. and Gupta , K. 2007 . View planning problem with combined view and traveling cost . 2007 IEEE International Conference on Robotics and Automation (ICRA 2007) . April 10–14 2007 , Roma , Italy. pp. 711 – 716 .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.