Оptimization of the Start Point in the Gtsp with the Precedence Conditions

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.

Keywords

route task; restrictions; start point.

References

1. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations, N.Y., Springer, 2002.
2. Cook W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation. New Jersey, Princeton University Press, 2012.
3. Melamed I.I., Sergeev S.I., Sigal I. The Traveling Salesman Problem. Issues in the Theory. Automation and Remote Control, 1989, vol. 50, no. 9, pp. 1147-1173.
4. Melamed I.I., Sergeev S.I., Sigal I. The Traveling Salesman Problem. Exact Methods. Automation and Remote Control, 1989, vol. 50, no. 10, pp. 1303-1324.
5. Melamed I.I., Sergeev S.I., Sigal I. The Traveling Salesman Problem. Approximate Algorithms. Automation and Remote Control, 1989, vol. 50, no. 11, pp. 1459-1479.
6. Chentsov A.G., Chentsov A.A. Route Problem with Constraints Depending on a List of Tasks. Doklady Mathematics, 2015, vol. 92, no. 3, pp. 685-688. DOI: 10.1134/S1064562415060083
7. Chentsov A.G., Chentsov P.A. Routing Under Constraints: Problem of Visit to Megalopolises. Automation and Remote Control, 2016, vol. 77, no. 11, pp. 1957-1974. 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, vol. 3, pp. 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. Moscow, Novye tekhnologii, 2012. (in Russian)
10. Bellman R. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the Association for Computing Machinery, 1962, vol. 9, pp. 61-63. 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, 1962, vol. 10, no. 1, pp. 196-210. DOI: 10.1137/0110015
12. Little J., Murty K., Sweeney D., Karel C. An Algorithm for the Traveling Salesman Problem, Operations Research, 1963, vol. 11, no. 6, pp. 972-989. DOI: 10.1287/opre.11.6.972
13. Kuratowski K., Mostowski A. Set Theory. Amsterdam, North-Holland Publishing Company, 1967.
14. Dieudonne J. Foundations of Modern Analysis. New York, Academic Press, 1960.
15. Cormen T., Leiserson C., Rivest R. Introduction to Algorithms. MIT Press and McGraw-Hill, 1990.
16. Engelking R. General Topology. Polish Scientific Publishers, 1977.
17. Chentsov A.G. Ekstremalnye zadachi marshrutizacii i raspredeleniya zadaniy voprosy teorii [Extreme Routing and Task Distribution Problems: Theory Questions]. Izhevsk, NITs 'Regulyarnaya i Khaoticheskaya Dinamika', 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, 2016, vol. 6, pp. 41-54.
19. Lawler E.L. Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems. CWI Technical report. Stichting Mathematisch Centrum. Mathematische Besliskunde-BW, 1979, vol. 106, no. 79, pp. 1-16.
20. Chentsov A.G. To Question of Routing of Works Complexes. Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 2013, no. 1, pp. 59-82. (in Russian)