Top

Published in:

2020 | OriginalPaper | Chapter

PCGLNS: A Heuristic Solver for the Precedence Constrained Generalized Traveling Salesman Problem

Authors : Michael Khachay, Andrei Kudriavtsev, Alexander Petunin

Published in: Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) is a specialized version of the well-known Generalized Traveling Salesman Problem (GTSP) having a lot of valuable applications in operations research. Despite the practical significance, results in the field of design, implementation, and numerical evaluation the algorithms for this problem remain still rare. In this paper, to the best of our knowledge, we propose the first heuristic solver for this problem augmented by numerical evaluation results of its performance against the public test instances library PCGTSPLIB. Our algorithm is an extension of the recent Large Neighborhood Search (GLNS) heuristic GTSP solver designed to take into account additional precedence constraints. Similarly to GLNS, the source code of all our algorithms is open, and the executables are freely accessible, which ensures the reproducibility of the reported numerical results.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Nonlinear Least Squares Solver for Evaluating Canonical Tensor Decomposition

next chapter Simultaneous Detection and Discrimination of Subsequences Which Are Nonlinearly Extended Elements of the Given Sequences Alphabet in a Quasiperiodic Sequence

Indeed, in the case of the linear order, the instance becomes trivial.

To the best of our knowledge.

Balas, E.: New classes of efficiently solvable Generalized Traveling Salesman Problems. Ann. Oper. Res. 86, 529–558 (1999). https://doi.org/10.1023/A:1018939709890MathSciNetCrossRefMATH

Castelino, K., D’Souza, R., Wright, P.K.: Toolpath optimization for minimizing airtime during machining. J. Manuf. Syst. 22(3), 173–180 (2003). https://doi.org/10.1016/S0278-6125(03)90018-5CrossRef

Chentsov, A.G., Khachai, M.Y., Khachai, D.M.: An exact algorithm with linear complexity for a problem of visiting megalopolises. Proc. Steklov Inst. Math. 295(1), 38–46 (2016). https://doi.org/10.1134/S0081543816090054MathSciNetCrossRefMATH

Chentsov, A.: Problem of successive megalopolis traversal with the precedence conditions. Autom. Remote Control 75(4), 728–744 (2014). https://doi.org/10.1134/S0005117914040122MathSciNetCrossRefMATH

Chentsov, A., Khachay, M., Khachay, D.: Linear time algorithm for precedence constrained asymmetric Generalized Traveling Salesman Problem. IFAC-PapersOnLine 49(12), 651–655 (2016). https://doi.org/10.1016/j.ifacol.2016.07.767. 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016

Chentsov, A.G., Chentsov, P.A., Petunin, A.A., Sesekin, A.N.: Model of megalopolises in the tool path optimisation for CNC plate cutting machines. Int. J. Prod. Res. 56(14), 4819–4830 (2018). https://doi.org/10.1080/00207543.2017.1421784

Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959)MathSciNetCrossRef

Dewil, R., Küçükoǧlu, I., Luteyn, C., Cattrysse, D.: A critical review of multi-hole drilling path optimization. Arch. Comput. Meth. Eng. 26(2), 449–459 (2019). https://doi.org/10.1007/s11831-018-9251-x

Dewil, R., Vansteenwegen, P., Cattrysse, D.: Construction heuristics for generating tool paths for laser cutters. Int. J. Prod. Res. 52(20), 5965–5984 (2014). https://doi.org/10.1080/00207543.2014.895064CrossRef

10.

Dewil, R., Vansteenwegen, P., Cattrysse, D.: A review of cutting path algorithms for laser cutters. Int. J. Adv. Manuf. Technol. 87(5), 1865–1884 (2016). https://doi.org/10.1007/s00170-016-8609-1

11.

Dewil, R., Vansteenwegen, P., Cattrysse, D., Laguna, M., Vossen, T.: An improvement heuristic framework for the laser cutting tool path problem. Int. J. Prod. Res. 53(6), 1761–1776 (2015). https://doi.org/10.1080/00207543.2014.959268CrossRef

12.

Fischetti, M., González, J.J.S., Toth, P.: A branch-and-cut algorithm for the symmetric Generalized Traveling Salesman Problem. Oper. Res. 45(3), 378–394 (1997). https://doi.org/10.1287/opre.45.3.378MathSciNetCrossRefMATH

13.

Gendreau, M., Potvin, J.Y.: Handbook of Metaheuristics. International Series in Operations Research & Management Science, 3rd edn., vol. 272. Springer International Publishing, Heidelberg (2019)

14.

Ghilas, V., Demir, E., Van Woensel, T.: An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows and scheduled lines. Comput. Oper. Res. 72(C), 12–30 (2016). https://doi.org/10.1016/j.cor.2016.01.018

15.

Gurobi Optimization, LLC: Gurobi optimizer reference manual (2020). http://www.gurobi.com

16.

Gutin, G., Karapetyan, D.: A memetic algorithm for the Generalized Traveling Salesman Problem. Nat. Comput. 9(1), 47–60 (2010). https://doi.org/10.1016/j.cor.2009.05.004MathSciNetCrossRefMATH

17.

Helsgaun, K.: Solving the equality Generalized Traveling Salesman Problem using the Lin-Kernighan-Helsgaun algorithm. Math. Program. Comput. 7, 1–19 (2015). https://doi.org/10.1007/s12532-015-0080-8

18.

Karuppusamy, N.S., Kang, B.Y.: Minimizing airtime by optimizing tool path in computer numerical control machine tools with application of \(A^*\) and genetic algorithms. Adv. Mech. Eng. 9(12), 1687814017737448 (2017). https://doi.org/10.1177/1687814017737448CrossRef

19.

Khachay, M., Neznakhina, K.: Towards tractability of the Euclidean Generalized Traveling Salesman Problem in grid clusters defined by a grid of bounded height. In: Eremeev, A., Khachay, M., Kochetov, Y., Pardalos, P. (eds.) OPTA 2018. CCIS, vol. 871, pp. 68–77. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93800-4_6CrossRef

20.

Khachay, M., Neznakhina, K.: Complexity and approximability of the Euclidean Generalized Traveling Salesman Problem in grid clusters. Ann. Math. Artif. Intell. 88(1), 53–69 (2020). https://doi.org/10.1007/s10472-019-09626-wMathSciNetCrossRefMATH

21.

Kudriavtsev, A., Khachay, M.: PCGLNS: adaptive heuristic solver for the precedence constrained GTSP (2020). https://github.com/AndreiKud/PCGLNS/

22.

Makarovskikh, T., Panyukov, A., Savitskiy, E.: Mathematical models and routing algorithms for economical cutting tool paths. Int. J. Prod. Res. 56(3), 1171–1188 (2018). https://doi.org/10.1080/00207543.2017.1401746CrossRef

23.

Papadimitriou, C.: Euclidean TSP is NP-complete. Theoret. Comput. Sci. 4, 237–244 (1977). https://doi.org/10.1016/0304-3975(77)90012-3MathSciNetCrossRefMATH

24.

Punnen, A.P., Gutin, G., Punnen, A.P., (eds.): The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, 1 edn., vol. 12. Springer, New York (2002)

25.

Qudeiri, J.A., Yamamoto, H., Ramli, R.: Optimization of operation sequence in CNC machine tools using genetic algorithm. J. Adv. Mech. Des. Syst. Manuf. 1(2), 272–282 (2007). https://doi.org/10.1299/jamdsm.1.272CrossRef

26.

Roberti, R., Toth, P.: Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison. EURO J. Transp. Logistics 1(1), 113–133 (2012). https://doi.org/10.1007/s13676-012-0010-0CrossRef

27.

Salman, R., Carlson, J.S., Ekstedt, F., Spensieri, D., Torstensson, J., Söderberg, R.: An industrially validated CMM inspection process with sequence constraints. Procedia CIRP 44, 138–143 (2016). https://doi.org/10.1016/j.procir.2016.02.136. 6th CIRP Conference on Assembly Technologies and Systems (CATS)

28.

Salman, R., Ekstedt, F., Damaschke, P.: Branch-and-bound for the precedence constrained Generalized Traveling Salesman Problem. Oper. Res. Lett. 48(2), 163–166 (2020). https://doi.org/10.1016/j.orl.2020.01.009MathSciNetCrossRefMATH

29.

Sarin, S.C., Sherali, H.D., Bhootra, A.: New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints. Oper. Res. Lett. 33(1), 62–70 (2005). https://doi.org/10.1016/j.orl.2004.03.007MathSciNetCrossRefMATH

30.

Shaw, P.: A new local search algorithm providing high quality solutions to vehicle routing problems (1997)

31.

Smith, S.L., Imeson, F.: GLNS: an effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem. Comput. Oper. Res. 87, 1–19 (2017). https://doi.org/10.1016/j.cor.2017.05.010MathSciNetCrossRefMATH

Title: PCGLNS: A Heuristic Solver for the Precedence Constrained Generalized Traveling Salesman Problem
Authors: Michael Khachay
Andrei Kudriavtsev
Alexander Petunin
Publisher: Springer International Publishing
Book: Optimization and Applications
Print ISBN: 978-3-030-62866-6

Electronic ISBN: 978-3-030-62867-3

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-62867-3_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner