ON ROUTING PROBLEM WITH STARTING POINT OPTIMIZATION

Alexander G. Chentsov     (Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, 16 S. Kovalevskaya Str., Ekaterinburg, 620108; Ural Federal University, 19 Mira Str., Ekaterinburg, 620002, Russian Federation)
Pavel A. Chentsov     (Ural Federal University, 19 Mira Str., Ekaterinburg, 620002, Russian Federation)

Abstract


One problem focused on engineering applications is considered. It is assumed that sequential visits to megacities have been implemented. After all visits have been made, it is required to return to the starting point (a more complex dependence on the starting point is also considered). But the last requirement is not strict: some weakening of the return condition is acceptable. Under these assumptions, it is required to optimize the choice of starting point, route, and specific trajectory. The well-known dynamic programming (DP) is used for the solution. But when using DP, significant difficulties arise associated with the dependence of the terminal component of the criterion on the starting point. Starting point enumeration is required. We consider the possibility of reducing the enumeration associated with applied variants of universal (relative to the starting point) dynamic programming. Of course, this approach requires some transformation of the problem.

Keywords


Dynamic programming, Precedence conditions, Route

Full Text:

PDF

References


  1. Bellman R. Dynamic programming treatment of the travelling salesman problem. J. ACM, 1962. Vol. 9, No. 1. P. 61–63. DOI: 10.1145/321105.321111
  2. Chentsov A.A., Chentsov A.G. Routization problem complicated by the dependence of costs functions and “current” restrictions from the tasks list. Model. Anal. Inf. Sist., 2016. Vol. 23, No. 2. P. 211–227. DOI: 10.18255/1818-1015-2016-2-211-227 (in Russian)
  3. Chentsov A.G. Ekstremal’nye zadachi marshrutizacii i raspredeleniya zadanij: voprosy teorii [Extreme routing and distribution tasks: theory questions]. M.-Izhevsk: R&C Dynamics. Izhevsk Institute of Computer Research, 2008. 240 p. (in Russian)
  4. Chentsov A.G. To question of routing of works complexes. Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2013. No. 1. P. 59–82. (in Russian)
  5. Chentsov A.G., Chentsov P.A. Routing under constraints: Problem of visit to megalopolises. Autom. Remote Control, 2016. Vol. 77, No. 11. P. 1957–1974. DOI: 10.1134/S0005117916110060
  6. Chentsov A.G., Chentsov P.A. To the question of optimization of the starting point in the routing problem with restrictions. Izv. IMI UdGU, 2020. Vol. 55. P. 135–154. DOI: 10.35634/2226-3594-2020-55-09 (in Russian)
  7. Cook W.J. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. N.J.: Princeton Univer. Press, 2012. 272 p. https://www.jstor.org/stable/j.ctt7t8kc
  8. Dieudonné J. Foundations of Modern Analysis. New York: Academic Press, 1960. 361 p.
  9. Held M., Karp R.M. A dynamic programming approach to sequencing problems J. Soc. Indust. Appl. Math., 1962. Vol. 10, No. 1. P. 196–210. DOI: 10.1137/0110015
  10. Gimadi E.Kh., Khachay M. Ekstremal’nye zadachi na mnozhestvah perestanovok [Extremal Problems on Sets of Permutations]. Ekaterinburg: Izdatel’stvo UMC UPI, 2016. 220 p. (in Russian)
  11. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Boston: Springer, 2007. 830 p. DOI: 10.1007/b101971
  12. Little J.D.C., Murty K.G., Sweeney D.W., Karel C. An algorithm for the traveling salesman problem. Oper. Res. , 1963. Vol. 11, No. 6. P. 972–989. DOI: 10.1287/opre.11.6.972
  13. Kosheleva M.S., Chentsov A.A., Chentsov A.G. On a routing problem with constraints that include dependence on a task list. Trudy Inst. Mat. i Mekh. UrO RAN, 2015. Vol. 21, No. 4. P. 178–195. (in Russian)
  14. Kuratowski K., Mostowski A. Set Theory. North-Holland, 1968. 417 p.
  15. Lawler E.L. Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems. CWI. Technical Reports. Stichting Mathematish Centrum. Mathematische Besliskunde, 1979. BW 106/79. 16 p.
  16. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. I: Issues in theory. Autom. Remote Control, 1989. Vol. 50, No. 9. P. 1147–1173.
  17. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. II: Exact methods. Autom. Remote Control, 1989. Vol. 50, No. 10. P. 1303–1324.
  18. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Approximate algorithms. Autom. Remote Control, 1989. Vol. 50, No. 11. P. 1459–1479.



DOI: http://dx.doi.org/10.15826/umj.2020.2.005

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.