×

Optimization of the start point in the GTSP with the precedence conditions. (Russian. English summary) Zbl 1402.90140

Summary: The paper is devoted to the routing problem with constraints and cost functions that can depend on the list of tasks. It is assumed that the initial condition for the process with discrete time can be selected within a metric space that satisfies the condition of complete boundedness. It is supposed that the problem includes a visiting of a finite system of megalopolises (non-empty finite sets) with the fulfillment of some works. The cost of these works each time depend on the point of arrival and the point of departure. The costs of movement and work are aggregated additively. For the problem solution widely understood dynamic programming method providing \(\epsilon\)-optimal solution for any \(\epsilon>0\) is used.

MSC:

90C27 Combinatorial optimization
90B10 Deterministic network models in operations research
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI MNR

References:

[1] G. Gutin, A.P. Punnen, The Traveling Salesman Problem and Its Variations, Springer, N.Y., 2002 · Zbl 0996.00026
[2] W.J. Cook, In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation, Princeton University Press, New Jersey, 2012 · Zbl 1236.00007
[3] Melamed I.I., Sergeev S.I., Sigal I., “The Traveling Salesman Problem. Issues in the Theory”, Automation and Remote Control, 50:9 (1989), 1147–1173 · Zbl 0705.90070
[4] Melamed I. I., Sergeev S. I., Sigal I., “The Traveling Salesman Problem. Exact Methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 · Zbl 0705.90071
[5] Melamed I. I., Sergeev S. I., Sigal I., “The Traveling Salesman Problem. Approximate Algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 · Zbl 0704.90095
[6] Chentsov A. G., Chentsov A. A., “Route Problem with Constraints Depending on a List of Tasks”, Doklady Mathematics, 92:3 (2015), 685–688 · Zbl 1334.90139 · doi:10.1134/S1064562415060083
[7] Chentsov A. G., Chentsov P. A., “Routing Under Constraints: Problem of Visit to Megalopolises”, Automation and Remote Control, 77:11 (2016), 1957–1974 · Zbl 1356.90153 · doi:10.1134/S0005117916110060
[8] Chentsov A. G., “One Parallel Procedure for the Construction of the Bellman Function in the Generalized Problem of the Courier with the Inner Workings”, Automation and Remote Control, 2012, no. 3, 134–149
[9] Korobkin V. V., Sesekin A. N., Tashlykov O. L., Chentsov A. G., Routing Methods and Their Applications to the Enhancement of Safety and Efficiency of Nuclear Plant Operation, Novye tekhnologii, M., 2012 (in Russian)
[10] Bellman R., “Dynamic Programming Treatment of the Travelling Salesman Problem”, Journal of the Association for Computing Machinery, 9 (1962), 61–63 · Zbl 0106.14102 · doi:10.1145/321105.321111
[11] Held M., Karp R. M., “A Dynamic Programming Approach to Sequencing Problems”, Journal of the Society for Industrial and Applied Mathematics, 10:1 (1962), 196–210 · Zbl 0106.14103 · doi:10.1137/0110015
[12] Little J., Murty K., Sweeney D., Karel C., “An Algorithm for the Traveling Salesman Problem”, Operations Research, 11:6 (1963), 972–989 · Zbl 0161.39305 · doi:10.1287/opre.11.6.972
[13] Kuratowski K., Mostowski A., Set Theory, North-Holland Publishing Company, Amsterdam, 1967
[14] Dieudonne J., Foundations of Modern Analysis, Academic Press, New York, 1960 · Zbl 0100.04201
[15] Cormen T., Leiserson C., Rivest R., Introduction to Algorithms, MIT Press and McGraw-Hill, 1990 · Zbl 1158.68538
[16] Engelking R., General Topology, Polish Scientific Publishers, 1977
[17] Chentsov A. G., Extreme Routing and Task Distribution Problems: Theory Questions, NITs “Regulyarnaya i Khaoticheskaya Dinamika”, Izhevsk, 2008 (in Russian)
[18] Chentsov A. G., Chentsov A. A., “On the Problem of Obtaining the Value of Routing Problem with Constraints”, Journal of Automation and Information Sciences, 6 (2016), 41–54
[19] E.L. Lawler, Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems, CWI. Technical Reports, BW 106/79, Stichting Mathematish Centrum. Mathematische Besliskunde, 1979, 16 pp. · Zbl 0416.90036
[20] Chentsov A. G., “To Question of Routing of Works Complexes”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 2013, no. 1, 59–82 (in Russian) · Zbl 1299.90049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.