RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Avtomat. i Telemekh.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Avtomat. i Telemekh., 1989, Issue 9, Pages 3–33 (Mi at6414)  

This article is cited in 62 scientific papers (total in 62 papers)

Surveys

The traveling salesman problem. Issues in theory

I. I. Melamed, S. I. Sergeev, I. Kh. Sigal

Moscow

Abstract: The first part of the paper surveys the theoretical results in solving the traveling salesman problem. Various (combinatorial, graph-theoretic, etc.) descriptions and linear and integer linear programming statements of the problem are provided. Actual problems reducible to the traveling salesman problem are described in detail. The computing complexity of the problem, the existence of a Hamiltonian cycle (loop), and numerous varieties of the problem are discussed.

Full text: PDF file (4069 kB)

English version:
Automation and Remote Control, 1989, 50:9, 1147–1173

Bibliographic databases:
UDC: 519.854.2

Received: 17.10.1988

Citation: I. I. Melamed, S. I. Sergeev, I. Kh. Sigal, “The traveling salesman problem. Issues in theory”, Avtomat. i Telemekh., 1989, no. 9, 3–33; Autom. Remote Control, 50:9 (1989), 1147–1173

Citation in format AMSBIB
\Bibitem{MelSerSig89}
\by I.~I.~Melamed, S.~I.~Sergeev, I.~Kh.~Sigal
\paper The traveling salesman problem. Issues in theory
\jour Avtomat. i Telemekh.
\yr 1989
\issue 9
\pages 3--33
\mathnet{http://mi.mathnet.ru/at6414}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1026520}
\zmath{https://zbmath.org/?q=an:0705.90070}
\transl
\jour Autom. Remote Control
\yr 1989
\vol 50
\issue 9
\pages 1147--1173


Linking options:
  • http://mi.mathnet.ru/eng/at6414
  • http://mi.mathnet.ru/eng/at/y1989/i9/p3

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Cycle of papers

    This publication is cited in the following articles:
    1. L. N. Korotaeva, A. G. Chentsov, “On a generalization of the bottleneck traveling salesman problem”, Comput. Math. Math. Phys., 35:7 (1995), 853–859  mathnet  mathscinet  zmath  isi
    2. K. G. Sabiryanova, “The additive problem of optimal covering”, Comput. Math. Math. Phys., 36:4 (1996), 545–551  mathnet  mathscinet  zmath  isi
    3. K. G. Sabiryanova, “Ob odnom sposobe optimizatsii pokrytiya konechnogo mnozhestva”, Vestnik ChelGU, 1999, no. 4, 183–197  mathnet
    4. A. G. Chentsov, “Ekstremalnye zadachi marshrutizatsii s ogranicheniyami”, Izv. IMI UdGU, 2006, no. 3(37), 163–166  mathnet
    5. S. I. Sergeev, “Discrete optimization by optimal control methods. II. The static traveling salesman problem”, Autom. Remote Control, 67:6 (2006), 927–932  mathnet  crossref  mathscinet  zmath
    6. S. I. Sergeev, “Discrete optimization by optimal control methods. III. The dynamic traveling salesman problem”, Autom. Remote Control, 67:7 (2006), 1039–1050  mathnet  crossref  mathscinet  zmath
    7. P. P. Parkhomenko, “On the solution of the traveling salesman problem once again”, Autom. Remote Control, 67:12 (2006), 2036–2050  mathnet  crossref  mathscinet  zmath
    8. A. A. Chentsov, A. G. Chentsov, “O realizatsii metoda dinamicheskogo programmirovaniya v obobschennoi zadache kurera”, Tr. IMM UrO RAN, 13, no. 3, 2007, 136–160  mathnet  elib
    9. V. K. Leont'ev, “Discrete optimization”, Comput. Math. Math. Phys., 47:2 (2007), 328–340  mathnet  crossref  mathscinet  zmath
    10. S. I. Sergeev, “Hybrid control systems and the dynamic traveling salesman problem”, Autom. Remote Control, 69:1 (2008), 42–51  mathnet  crossref  mathscinet  zmath  isi
    11. A. A. Chentsov, A. G. Chentsov, “Extremal bottleneck routing problem with constraints in the form of precedence conditions”, Proc. Steklov Inst. Math. (Suppl.), 263, suppl. 2 (2008), S23–S36  mathnet  crossref  zmath  isi  elib
    12. A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Extremal routing problem with internal losses”, Proc. Steklov Inst. Math. (Suppl.), 264, suppl. 1 (2009), S87–S106  mathnet  crossref  isi  elib
    13. S. I. Sergeev, “The symmetric travelling salesman problem I. New fast lower bounds for the problem of optimal $2$-matching”, Autom. Remote Control, 70:11 (2009), 1901–1912  mathnet  crossref  mathscinet  zmath  isi
    14. A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Iteration method in the routing problem with internal losses”, Proc. Steklov Inst. Math. (Suppl.), 269, suppl. 1 (2010), S48–S68  mathnet  crossref  elib
    15. A. N. Sesekin, A. A. Chentsov, A. G. Chentsov, “One bottleneck routing problem”, Proc. Steklov Inst. Math. (Suppl.), 272, suppl. 1 (2011), S165–S185  mathnet  crossref  isi  elib
    16. A. N. Sesekin, A. A. Chentsov, A. G. Chentsov, “Marshrutizatsiya s abstraktnoi funktsiei agregirovaniya stoimostei peremeschenii”, Tr. IMM UrO RAN, 16, no. 3, 2010, 240–264  mathnet  elib
    17. A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “An extremal constrained routing problem with internal losses”, Russian Math. (Iz. VUZ), 54:6 (2010), 54–68  mathnet  crossref  mathscinet
    18. S. I. Sergeev, “The symmetric travelling salesman problem II. New low bounds”, Autom. Remote Control, 71:4 (2010), 681–696  mathnet  crossref  mathscinet  zmath  isi
    19. E. E. Ivanko, “Method of scaling in approximate solution of the traveling salesman problem”, Autom. Remote Control, 72:12 (2011), 2527–2540  mathnet  crossref  mathscinet  zmath  isi
    20. A. M. Grigorev, E. E. Ivanko, A. G. Chentsov, “Dinamicheskoe programmirovanie v obobschennoi zadache kurera s vnutrennimi rabotami: elementy parallelnoi struktury”, Model. i analiz inform. sistem, 18:3 (2011), 101–124  mathnet
    21. E. E. Ivanko, “Kriterii ustoichivosti optimalnogo marshruta v zadache kommivoyazhera pri dobavlenii vershiny”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 2011, no. 1, 58–66  mathnet
    22. A. G. Chentsov, “Odna parallelnaya protsedura postroeniya funktsii Bellmana v obobschennoi zadache kurera s vnutrennimi rabotami”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 2012, no. 12, 53–76  mathnet
    23. I. B. Cheblokov, A. G. Chentsov, “Ob odnoi zadache marshrutizatsii s vnutrennimi rabotami”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 2012, no. 1, 96–119  mathnet
    24. A. A. Chentsov, A. G. Chentsov, “Ob odnoi zadache marshrutizatsii s vnutrennimi rabotami”, Tr. IMM UrO RAN, 18, no. 1, 2012, 298–317  mathnet  elib
    25. A. A. Chentsov, A. G. Chentsov, “On an iterative procedure for solving a routing problem with constraints”, Proc. Steklov Inst. Math. (Suppl.), 283, suppl. 1 (2013), 24–45  mathnet  crossref  isi  elib
    26. A. G. Chentsov, “On a parallel procedure for constructing the Bellman function in the generalized problem of courier with internal jobs”, Autom. Remote Control, 73:3 (2012), 532–546  mathnet  crossref  isi
    27. S. I. Sergeev, “Nonlinear resolving functions for the travelling salesman problem”, Autom. Remote Control, 74:6 (2013), 978–994  mathnet  crossref  mathscinet  isi
    28. A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Elements of dynamic programming in extremal route problems”, Autom. Remote Control, 75:3 (2014), 537–550  mathnet  crossref  isi
    29. E. E. Ivanko, “Usechennyi metod dinamicheskogo programmirovaniya v zamknutoi zadache kommivoyazhera s simmetrichnoi funktsiei stoimosti”, Tr. IMM UrO RAN, 19, no. 1, 2013, 121–129  mathnet  mathscinet  elib
    30. E. E. Ivanko, “Dinamicheskoe programmirovanie v zadache perestanovki odnotipnykh ob'ektov”, Tr. IMM UrO RAN, 19, no. 4, 2013, 125–130  mathnet  mathscinet  elib
    31. A. G. Chentsov, “K voprosu o marshrutizatsii kompleksov rabot”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 2013, no. 1, 59–82  mathnet
    32. A. A. Chentsov, A. G. Chentsov, “Metod iteratsii v obobschennoi zadache kurera s osobennostyu v opredelenii funktsii stoimosti”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 2013, no. 3, 88–113  mathnet
    33. A. G. Chentsov, P. A. Chentsov, “Ob odnom nestatsionarnom variante obobschennoi zadachi kurera s vnutrennimi rabotami”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 6:2 (2013), 88–107  mathnet
    34. Chentsov A.G. Chentsov A.A., “Dynamic Programming in the Routing Problem with Constraints and Costs Depending on a List of Tasks”, Dokl. Math., 88:3 (2013), 637–640  crossref  mathscinet  isi
    35. A. G. Chentsov, “Problem of successive megalopolis traversal with the precedence conditions”, Autom. Remote Control, 75:4 (2014), 728–744  mathnet  crossref  isi
    36. A. A. Petunin, A. G. Chentsov, P. A. Chentsov, “Lokalnye vstavki na osnove dinamicheskogo programmirovaniya v zadache marshrutizatsii s ogranicheniyami”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 2014, no. 2, 56–75  mathnet
    37. S. I. Sergeev, “Maximum travelling salesman problem. I”, Autom. Remote Control, 75:12 (2014), 2170–2189  mathnet  crossref  isi
    38. A. G. Chentsov, “Bellmanovskie vstavki v zadache marshrutizatsii s ogranicheniyami i uslozhnennymi funktsiyami stoimosti”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 2014, no. 4, 122–141  mathnet
    39. A. G. Chentsov, Ya. V. Salii, “A model of “nonadditive” routing problem where the costs depend on the set of pending tasks”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 8:1 (2015), 24–45  mathnet  crossref  elib
    40. S. I. Sergeev, “Approximate algorithms for the traveling salesman problem. II”, Autom. Remote Control, 76:3 (2015), 472–479  mathnet  crossref  isi  elib  elib
    41. A. A. Petunin, A. G. Chentsov, P. A. Chentsov, “Ob odnoi zadache marshrutizatsii peremeschenii instrumenta pri listovoi rezke detalei”, Model. i analiz inform. sistem, 22:2 (2015), 278–294  mathnet  mathscinet  elib
    42. M. S. Kosheleva, A. A. Chentsov, A. G. Chentsov, “O zadache marshrutizatsii s ogranicheniyami, vklyuchayuschimi zavisimost ot spiska zadanii”, Tr. IMM UrO RAN, 21, no. 4, 2015, 178–195  mathnet  mathscinet  elib
    43. Chentsov A.G. Chentsov A.A., “Route Problem With Constraints Depending on a List of Tasks”, Dokl. Math., 92:3 (2015), 685–688  crossref  isi
    44. A. A. Chentsov, A. G. Chentsov, “Obobschennaya model kurera s dopolnitelnymi ogranicheniyami”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 9:1 (2016), 46–58  mathnet  crossref  elib
    45. Chentsov A.A. Chentsov A.G., “Generalized Model of Courier With Additional Restrictions”, Bull. South Ural State U. Ser.-Math Model Program Comput., 9:1 (2016), 46–58  isi
    46. A. G. Chentsov, A. A. Chentsov, “Zadacha marshrutizatsii, oslozhnennaya zavisimostyu funktsii stoimosti i “tekuschikh” ogranichenii ot spiska zadanii”, Model. i analiz inform. sistem, 23:2 (2016), 211–227  mathnet  crossref  mathscinet  elib
    47. A. G. Chentsov, P. A. Chentsov, “Routing under constraints: problem of visit to megalopolises”, Autom. Remote Control, 77:11 (2016), 1957–1974  mathnet  crossref  isi  elib  elib
    48. A. G. Chentsov, “Optimiziruyuschie vstavki v zadachakh marshrutizatsii i ikh realizatsiya na osnove dinamicheskogo programmirovaniya”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 26:4 (2016), 565–578  mathnet  crossref  mathscinet  elib
    49. A. G. Chentsov, A. A. Chentsov, “A discrete-continuous routing problem with precedence conditions”, Proc. Steklov Inst. Math. (Suppl.), 300, suppl. 1 (2018), 56–71  mathnet  crossref  crossref  isi  elib
    50. A. A. Petunin, A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints”, Autom. Remote Control, 78:4 (2017), 666–681  mathnet  crossref  isi  elib
    51. A. A. Petunin, A. G. Chentsov, P. A. Chentsov, “K voprosu o marshrutizatsii peremeschenii pri listovoi rezke detalei”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 10:3 (2017), 25–39  mathnet  crossref  elib
    52. A. G. Chentsov, A. A. Chentsov, “Modelnyi variant zadachi o posledovatelnoi utilizatsii istochnikov izlucheniya (iteratsii na osnove optimiziruyuschikh vstavok)”, Izv. IMI UdGU, 50 (2017), 83–109  mathnet  crossref  elib
    53. A. G. Chentsov, A. A. Chentsov, A. M. Grigorev, “Ob odnoi zadache marshrutizatsii, modeliruyuschei peremescheniya v radiatsionnykh polyakh”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 27:4 (2017), 540–557  mathnet  crossref  elib
    54. A. G. Chentsov, A. M. Grigoryev, A. A. Chentsov, “Solving a routing problem with the aid of an independent computations scheme”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 11:1 (2018), 60–74  mathnet  crossref  elib
    55. A. G. Chentsov, P. A. Chentsov, “Optimizatsiya tochki starta v zadache posledovatelnogo obkhoda megapolisov pri nalichii uslovii predshestvovaniya”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 11:2 (2018), 83–95  mathnet  crossref  elib
    56. V. V. Zakharov, A. V. Mugaiskikh, “Dinamicheskaya adaptatsiya geneticheskogo algoritma marshrutizatsii transporta na bolshikh setyakh”, UBS, 73 (2018), 108–133  mathnet  crossref  elib
    57. A. G. Chentsov, A. A. Chentsov, A. N. Sesekin, “Dinamicheskoe programmirovanie v obobschennoi zadache «na uzkie mesta» i optimizatsiya tochki starta”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 28:3 (2018), 348–363  mathnet  crossref  elib
    58. Chentsov A.G. Chentsov P.A. Petunin A.A. Sesekin A.N., “Model of Megalopolises in the Tool Path Optimisation For Cnc Plate Cutting Machines”, Int. J. Prod. Res., 56:14 (2018), 4819–4830  crossref  isi  scopus
    59. Alexander G. Chentsov, Alexey M. Grigoriev, Alexey A. Chentsov, “Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions”, Ural Math. J., 4:2 (2018), 43–55  mathnet  crossref  mathscinet
    60. A. G. Chentsov, A. M. Grigorev, “Optimiziruyuschie multivstavki v zadachakh marshrutizatsii s ogranicheniyami”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 28:4 (2018), 513–530  mathnet  crossref  elib
    61. A. G. Chentsov, P. A. Chentsov, “Ob odnoi zadache marshrutizatsii s optimizatsiei tochki starta–finisha”, Izv. IMI UdGU, 52 (2018), 103–115  mathnet  crossref  elib
    62. A. G. Chentsov, A. A. Chentsov, A. N. Sesekin, “O zadache posledovatelnogo obkhoda megapolisov s usloviyami predshestvovaniya i funktsiyami stoimosti s zavisimostyu ot spiska zadanii”, Tr. IMM UrO RAN, 26, no. 3, 2020, 219–234  mathnet  crossref  elib
  • Avtomatika i Telemekhanika
    Number of views:
    This page:1182
    Full text:513
    First page:2

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020