On routing problem with starting point optimization. (English) Zbl 1465.90084

Chentsov, Alexander G.; Chentsov, Pavel A.

Ural Math. J. 6, No. 2, 44-62 (2020).

Summary: 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.

MSC:

90C27	Combinatorial optimization
90B06	Transportation, logistics and supply chain management
90C39	Dynamic programming

Keywords:

dynamic programming; precedence conditions; route

References:

[1]	Bellman R., “Dynamic programming treatment of the travelling salesman problem”, J. ACM, 9:1 (1962), 61-63 · Zbl 0106.14102
[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., 23:2 (2016), 211-227 (in Russian)
[3]	Chentsov A. G., Ekstremal’nye zadachi marshrutizacii i raspredeleniya zadanij: voprosy teorii [Extreme routing and distribution tasks: theory questions], R&C Dynamics. Izhevsk Institute of Computer Research, M.-Izhevsk, 2008, 240 pp. (in Russian)
[4]	Chentsov A. G., “To question of routing of works complexes”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2013, no. 1, 59-82 (in Russian) · Zbl 1299.90049
[5]	Chentsov A. G., Chentsov P. A., “Routing under constraints: Problem of visit to megalopolises”, Autom. Remote Control, 77:11 (2016), 1957-1974 · Zbl 1356.90153
[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, 55, 135-154 (in Russian) · Zbl 1458.90071
[7]	Cook W. J., In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton Univer. Press, N. J., 2012, 272 · Zbl 1236.00007
[8]	Dieudonné J., Foundations of Modern Analysis, Academic Press, New York, 1960, 361 pp. · Zbl 0100.04201
[9]	Held M., Karp R.M., “A dynamic programming approach to sequencing problems”, J. Soc. Indust. Appl. Math., 10:1 (1962), 196-210 · Zbl 0106.14103
[10]	Gimadi E. Kh., Khachay M., Ekstremal’nye zadachi na mnozhestvah perestanovok [Extremal Problems on Sets of Permutations], Izdatel’stvo UMC UPI, Ekaterinburg, 2016, 220 pp. (in Russian)
[11]	Gutin G., Punnen A. P., The Traveling Salesman Problem and Its Variations, Springer, Boston, 2007, 830 pp. · Zbl 1113.90134
[12]	Little J. D. C., Murty K. G., Sweeney D. W., Karel C., “An algorithm for the traveling salesman problem”, Oper. Res., 11:6 (1963), 972-989 · Zbl 0161.39305
[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, 21:4 (2015), 178-195 (in Russian)
[14]	Kuratowski K., Mostowski A., Set Theory, North-Holland, 1968, 417 pp. · Zbl 0165.01701
[15]	Lawler E. L., Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems, BW 106/79, CWI. Technical Reports. Stichting Mathematish Centrum. Mathematische Besliskunde, 1979, 16 pp. · Zbl 0416.90036
[16]	Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. I: Issues in theory”, Autom. Remote Control, 50:9 (1989), 1147-1173 · Zbl 0705.90070
[17]	Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. II: Exact methods”, Autom. Remote Control, 50:10 (1989), 1303-1324 · Zbl 0705.90071
[18]	Melamed I. I., Sergeev S. I., Sigal I. Kh. The traveling salesman problem. Approximate algorithms, Autom. Remote Control, 50:11 (1989), 1459-1479 · Zbl 0704.90095