Artificial intelligence

Abstract: The paper proposes a classification of the fundamental tasks of building closed routes to complete and incomplete graphs. Generalizations and special cases of the traveling salesman problem and the problem of the postman are discussed. Links between tasks and formulate their mathematical models are analyzed.

Keywords: transport network, routing problem, traveling salesman problem, postman problem.

References:

1. Bronshtein E. M/ Deterministic optimization problems of transport logistics / E. M Bronshtein, T. AZayko // Automation and Remote Control. – 2010. – №10. – P. 133–147.
2. Gary M. Computers and Intractability / M. Gary, D. Johnson. – M .: Mir, 1982. – 416 p.
3. Melamed I. I. Traveling Salesman Problem. Problems in the theory / I. I. Melamed, S. I. Sergeev, I. H.Sigal // Automation and Remote Control. – 1989. – № 9. – P. 3–33.
4. Papadimitriou H. Combinatorial optimization. Algorithms and Complexity / H. Papadimitriou, K.Stayglits. – M.: Mir, 1985. – 510 p.
5. Vyalitsin A. A Enumeration of Hamiltonian cycles / A. A Vyalitsin // Discrete mathematics. – 1991. –Volume 3, No. 3. – P. 46–49.
6. Zabinyako G. I Organization of parallel calculations in some problems of discrete optimization / G. I.Zabinyako, E. A. Kotelnikov // Siberian Journal of Computational Mathematics. – 2008. – V. 11, № 4. –P. 414–422.
7. Orlovich Y. L. Hamiltonian cycles in graphs triangulated lattice / Y. L. Orlovich, V. S. Gordon, F.Werner // Reports of the National Academy of Sciences of Belarus. – 2005. – V. 49, № 5. – P. 21–25.
8. Maynika E. Optimization algorithms on networks and graphs / E. Maynika – M .: Mir, 1981. – 323 p.
9. Panov S. A. Models routing in road transport / S. A. Panov. – M .: Transport, 1974. – 152 p.
10. Morozov A. V. Branch and bound method in the Hamiltonian Rural Postman Problem / A. V. Morozov,A. V. Panishev // System Research and Information Technologies. – 2012. – №2. – P. 57–66