nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Optimization “In Windows” for Routing Problems with Constraints

verfasst von : Alexander G. Chentsov, Alexey M. Grigoryev, Alexey A. Chentsov

Erschienen in: Mathematical Optimization Theory and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We investigate the problem of sequentially visiting a number of megalopoleis while satisfying precedence constraints where the travel cost functions depend on the set of pending tasks. It is supposed that the dimension of the investigated problem is sufficiently large, therefore, an exact solution is practically impossible; in these circumstances, heuristics are used very widely. We investigate some possibilities for local improvement of results achievable in a class of heuristics. For such improvement of a result, optimizing insertions and finite systems of optimizing insertions are used. We view these systems as multi-insertions. The given approach is combined with the employment of a parallel algorithm implemented for a multiprocessor computing system. The optimizing insertions are designed by means of a broadly understood dynamic programming.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Iterative Method with Exact Fulfillment of Constraints in Optimal Control Problems

Nächstes Kapitel The Stochastic Coverings Algorithm for Solving Applied Optimal Control Problems

see http://www.cs.nott.ac.uk/~pszdk/gtsp.html.

Gutin, G., Punnen, A.P.: The Traveling Salesman Problem and its Variations. Springer, Berlin (2002)MATH

William, J.C.: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, p. 248. Princeton University Press, Princeton (2012)

Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. Assoc. Comput. Mach. 9, 61–63 (1962)MathSciNetCrossRef

Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196–210 (1962)MathSciNetCrossRef

Chentsov, A.G.: 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.G., Chentsov, A.A.: Route problem with constraints depending on a list of tasks. Doklady Math. 92(3), 685–688 (2015). https://doi.org/10.1134/S1064562415060083MathSciNetCrossRefMATH

Chentsov, A.G.: The Bellman insertions in the route problem with constraints and complicated cost functions. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp’yuternye Nauki 2014(4), 122–141 (2014). https://doi.org/10.20537/vm140410. (in Russian) CrossRefMATH

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.1421784CrossRef

Petunin, A.A., Chentsov, A.G., Chentsov, P.A.: Optimizing inserts in a routing task with constraints and complicated cost functions. Izvestija RAN. Teorija i sistemy upravlenija 1, 117–130 (2019). (in Russian)

10.

Chentsov, A.G., Grigoryev, A.M.: Dynamic programming method in a routing problem: a scheme of independent computations. Mekhatronika, Avtomatizatsiya, Upravlenie 17(12), 834–846 (2016). (in Russian)CrossRef

11.

Chentsov, A.G., Grigoryev, A.M., Chentsov, A.A.: Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions. Ural Math. J. 4(2), 43–55 (2018). https://doi.org/10.15826/umj.2018.2.006MathSciNetCrossRef

12.

Chentsov, A.G.: The Bellmann insertions in route problems with constraints and complicated cost functions. II. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp’yuternye Nauki 26(4), 565–578 (2016). https://doi.org/10.20537/vm160410. (in Russian)CrossRefMATH

13.

Petunin, A.A., Chentsov, A.A., Chentsov, A.G., Chentsov, P.A.: Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints. Autom. Remote Control 78(4), 666–681 (2017). https://doi.org/10.1134/S0005117917040087MathSciNetCrossRefMATH

14.

Chentsov, A.G., Grigoryev, A.M.: Optimizing multi-inserts in routing problems with constraints. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp’yuternye Nauki 28(4), 513–530 (2018). https://doi.org/10.20537/vm180406. (in Russian)CrossRef

15.

Gimadi, E.Kh., Khachai, M.Yu.: Extremal Problems on Sets of Permutations, p. 220. UMC UPI, Yekaterinburg (2016). (in Russian)

16.

Melamed, I.I., Sergeev, S.I., Sigal, I.Kh.: The traveling salesman problem. I Issues in theory; II Exact methods; III Approximate algorithms. Autom. Remote Control 50(9), 1147–1173; 50(10), 1303–1324; 50(11), 1459–1479 (1989)

17.

Litl, Dzh., Murti, K., Suini, D., Kerel, K.: Algorithm for the traveling salesman problem. Ekon. Mat. Metod. 1(1), 94–107 (1965)

18.

Chentsov, A.G.: Extreme Problems of Routing and Tasks Distribution: Regular and Chaotic Dynamics, 240 p. Izhevsk Institute of Computer Research (2008). (in Russian)

19.

Chentsov, A.G., Chentsov, P.A.: Routing under constraints: problem of visit to megalopolises. Autom. Remote Control 77(11), 1957–1974 (2016). https://doi.org/10.1134/S0005117916110060MathSciNetCrossRefMATH

20.

Chentsov, A.G., Chentsov, A.A.: A model variant of the problem about radiation sources utilization (iterations based on optimization insertions). Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta 50, 83–109 (2017). https://doi.org/10.20537/2226-3594-2017-50-08. (in Russian)CrossRefMATH

21.

Chentsov, A.A., Chentsov, A.G., Chentsov, P.A.: Extremal routing problem with internal losses. Proc. Steklov Inst. Math. 264(Suppl. 1), 87–106 (2009)MathSciNetCrossRef

22.

Chentsov, A.G., Chentsov, P.A.: Optimization of the start point in the GTSP with the precedence conditions. Bull. South Ural State Univ.: Series Math. Model., Prog. Comput. Soft. 11(2), 83–95 (2018). https://doi.org/10.14529/mmp180207CrossRefMATH

23.

Alkaya, A.F., Duman, E.: Combining and solving sequence dependent traveling salesman and quadratic assignment problems in PCB assembly. Discrete Appl. Math. 192, 2–16 (2015)MathSciNetCrossRef

24.

Salii, Y.V.: Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization. Eur. J. Oper. Res. 272(1), 32–42 (2019)MathSciNetCrossRef

25.

Gouveia, L., Ruthmair, M.: Load-dependent and precedence-based models for pickup and delivery problems. Comput. Oper. Res. 63, 56–71 (2015)MathSciNetCrossRef

Titel: Optimization “In Windows” for Routing Problems with Constraints
verfasst von: Alexander G. Chentsov
Alexey M. Grigoryev
Alexey A. Chentsov
Verlag: Springer International Publishing
Buch: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-33393-5

Electronic ISBN: 978-3-030-33394-2

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-33394-2_36

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"