ON ROUTING PROBLEM WITH STARTING POINT OPTIMIZATION
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:
PDFReferences
- 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
- 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)
- 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)
- 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)
- 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
- 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)
- 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
- Dieudonné J. Foundations of Modern Analysis. New York: Academic Press, 1960. 361 p.
- 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
- 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)
- Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Boston: Springer, 2007. 830 p. DOI: 10.1007/b101971
- 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
- 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)
- Kuratowski K., Mostowski A. Set Theory. North-Holland, 1968. 417 p.
- 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.
- 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.
- 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.
- 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.
Article Metrics
Metrics Loading ...
Refbacks
- There are currently no refbacks.