phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2012 - 1 issue » pp. 96-119

Archive of Issues

Russia Yekaterinburg
Year
2012
Issue
1
Pages
96-119
<<
>>
Section Mathematics
Title About one route problem with interior works
Author(-s) Cheblokov I.B.a, Chentsov A.G.ab
Affiliations Ural Federal Universitya, Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesb
Abstract The route problem about visiting of multifunction sections with constraints of type of preceding conditions is considered. By setting of this problem the fulfilment of works on the above-mentioned sections is provided. Any solution is defined in the form of the ordered pair for which components have the sense of the route (the index permutation) and the trace (trajectory) of the movements with respect to sections of multifunctions. The agreement of the trace and route is realized by procedures of the sequential choice of ordered pairs (the point of arrival and the starting point) of Descartes "squares" of the multifunction sections numbered in correspondence with a route. The cost aggregation is presupposed additive; the total criterion includes the costs of (exterior) movements between sections of multifunctions, interior works, and the final state. Under constructing of extension of the basic problem that realizes the used Bellman function, the equivalent transformation of constraints is applied: admissibility of routes by preceding is replaced onto admissibility by deletion of tasks (of the list) that corresponds to the constraints variant with respect to the current movements from one set onto another. An analog of the Bellman equation realized by procedure of the transformation of layers of Bellman function is obtained. The operation defining this transformation is further used for constructing of heuristic algorithms realized on PC.
Keywords route, permutation, trace, Bellman function
UDC 517.977
MSC 76D55, 90C27
DOI 10.20537/vm120109
Received 9 February 2011
Language Russian
Citation Cheblokov I.B., Chentsov A.G. About one route problem with interior works, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2012, issue 1, pp. 96-119.
References
  1. Melamed I.I., Sergeev S.I., Sigal I.Kh. Traveling salesman problem. Questions of theory, Avtomatika i Telemekhanika, 1989, no. 9, pp. 3–34.
  2. Melamed I.I., Sergeev S.I., Sigal I.Kh. Traveling salesman problem. Precise algorithms, Avtomatika i Telemekhanika, 1989, no. 10, pp. 3–29.
  3. Melamed I.I., Sergeev S.I., Sigal I.Kh. Traveling salesman problem. Approximate algorithms, Avtomatika i Telemekhanika, 1989, no. 11, pp. 3–26.
  4. Garey M., Johnson D. Computers and Intractability, 1979, 340 p. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Moscow: Mir, 1982, 416 p.
  5. Bellmann R. Application of dynamic programming to traveling salesman problem, Kibernet. Sb., Moscow: Mir, 1964, vol. 9, pp. 219–228.
  6. Kheld M., Karp R.M. Application of dynamic programming to the problem of ordering, Kibernet. Sb., Moscow: Mir, 1964, vol. 9, pp. 202–218.
  7. Sigal I.Kh., Ivanova A.P. Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitel’nye algoritmy (Introduction in applied discrete programming: the models and computing algorithms), Moscow: Nauka, 2007, 304 p.
  8. Henry-Labordere A.L. The record-balancing problem: a dynamic programming solution of a generalized traveling salesman problem, R. I. R. O., 1969, vol. 3, no. 2, pp. 43–49.
  9. Laporte G., Nobert Y. Generalized traveling salesman problem through n-sets of nodes: an integer programming approach, INFOR, 1983, vol. 21, no. 1, pp. 61–75.
  10. Leiten A.K. Some modifications of traveling salesman problem, Trudy Vychisl. Tsentra Tart. Univ., 1973, no. 28, pp. 44–58.
  11. Melamed I.I., Plotinskii Yu.M. Heuristic algorithm for solving the generalized problem of delivery, Avtomatika i Telemekhanika, 1979, no. 29, pp. 167–172.
  12. Plotinskii Yu.M. General problem of delivery, Avtomatika i Telemekhanika, 1973, no. 6, pp. 100–104.
  13. Korotaeva L.N., Sesekin A.N., Chentsov A.G. About a modification of the dynamic programming method to the problem of sequential approach, Zh. Vychisl. Mat. Mat. Fiz., 1989, vol. 29, no. 8, pp. 1107–1113.
  14. Korotaeva L.N., Trukhin M.P., Chentsov A.G. To the issue of routing connections, Avtomatika i Telemekhanika, 1997, no. 12, pp. 175–192.
  15. Zobnin B.B., Korotaeva L.N., Chentsov A.G. On a problem of routing optimization and its applications, Problemy Peredachi Informatsii, 1997, vol. 33, no. 4, pp. 70–87.
  16. Chentsov A.A., Chentsov A.G. About solving the problem of routing optimization by method of dynamic programming, Avtomatika i Telemekhanika, 1998, no. 9, pp. 117–129.
  17. Chentsov A.A., Chentsov A.G. About solving the problem of routing optimization by method of dynamic programming, Izv. Akad. Nauk Teor. Sist. Upr., 1999, no. 3, pp. 76–87.
  18. Chentsov A.G. About the structure of an extremal problem in routing restrictions as conditions of precedence, Vestn. Udmurt. Univ. Mat., 2006, no. 1, pp. 127–148.
  19. Chentsov A.G., Chentsov P.A. Routing with the terms of precedence (task courier): a method of dynamic programming, Vestn. Ural. Gos. Tekh. Univ. – Ural. Politekh. Inst., Yekaterinburg, USTU–UPI, 2004, vol. 1, no. 15 (45), pp. 148–152.
  20. Chentsov A.G. Ekstremal’nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extremal problems of routing and assignment of tasks: questions of theory), Izhevsk: Institute of Computer Science, 2008, 240 p.
  21. Chentsov A.A., Chentsov A.G., Chentsov P.A. Extreme routing problem with internal losses, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk, Yekaterinburg, 2008, vol. 14, no. 3, pp. 183–201.
  22. Chentsov A.G. Dynamic programming method in extremal problems with constraints routing, Izv. Akad. Nauk Teor. Sist. Upr., 2010, no. 3, pp. 52–66.
  23. Chentsov A.A., Chentsov A.G., Chentsov P.A. Extreme movements of routing problem with constraints and internal losses, Izv. Vyssh. Uchebn. Zaved. Mat., Kazan, 2010, no. 6, pp. 64–81.
  24. Kormen A., Leizerson Ch., Rivest R. Algoritmy. Postroenie i analiz (The algorithms. Construction and analysis), Moscow: Moscow Center for Continuous Mathematical Education, 2007, 1296 p.
Full text
/doc/issues-2012/12-01-09.pdf
<< Previous article
Next article >>