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 10, Pages 3–29 (Mi at6433)  

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

Surveys

The traveling salesman's problem. Exact methods

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

Moscow

Abstract: An algorithm is discussed for optimal solution of the traveling salesman's problem. Dynamic programming methods, versions of the branch-and-bound method, Lagrangeans multiplier methods, sectioning planes method, and various combinations of these methods are discussed. Data of numerical experiments is provided.

Full text: PDF file (3620 kB)

English version:
Automation and Remote Control, 1989, 50:10, 1303–1324

Bibliographic databases:
UDC: 519.854.2(047)

Received: 17.10.1988

Citation: I. I. Melamed, S. I. Sergeev, I. Kh. Sigal, “The traveling salesman's problem. Exact methods”, Avtomat. i Telemekh., 1989, no. 10, 3–29; Autom. Remote Control, 50:10 (1989), 1303–1324

Citation in format AMSBIB
\Bibitem{MelSerSig89}
\by I.~I.~Melamed, S.~I.~Sergeev, I.~Kh.~Sigal
\paper The traveling salesman's problem. Exact methods
\jour Avtomat. i Telemekh.
\yr 1989
\issue 10
\pages 3--29
\mathnet{http://mi.mathnet.ru/at6433}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1026534}
\zmath{https://zbmath.org/?q=an:0705.90071}
\transl
\jour Autom. Remote Control
\yr 1989
\vol 50
\issue 10
\pages 1303--1324


Linking options:
  • http://mi.mathnet.ru/eng/at6433
  • http://mi.mathnet.ru/eng/at/y1989/i10/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. K. G. Sabiryanova, “The additive problem of optimal covering”, Comput. Math. Math. Phys., 36:4 (1996), 545–551  mathnet  mathscinet  zmath  isi
    2. K. G. Sabiryanova, “Ob odnom sposobe optimizatsii pokrytiya konechnogo mnozhestva”, Vestnik ChelGU, 1999, no. 4, 183–197  mathnet
    3. S. I. Sergeev, “Improved lower bounds for the quadratic assignment problem”, Autom. Remote Control, 65:11 (2004), 1733–1746  mathnet  crossref  mathscinet  zmath  isi
    4. 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
    5. 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
    6. 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
    7. 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
    8. 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
    9. 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
    10. 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
    11. 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
    12. 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
    13. 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
    14. 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
    15. 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
    16. 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
    17. 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
    18. 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
    19. 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
    20. 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
    21. S. I. Sergeev, “Nonlinear resolving functions for the travelling salesman problem”, Autom. Remote Control, 74:6 (2013), 978–994  mathnet  crossref  mathscinet  isi
    22. Yu. L. Kostyuk, “Effektivnaya realizatsiya algoritma resheniya zadachi kommivoyazhera metodom vetvei i granits”, PDM, 2013, no. 2(20), 78–90  mathnet
    23. 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
    24. 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
    25. A. G. Chentsov, “K voprosu o marshrutizatsii kompleksov rabot”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 2013, no. 1, 59–82  mathnet
    26. 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
    27. 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
    28. 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
    29. A. G. Chentsov, “Problem of successive megalopolis traversal with the precedence conditions”, Autom. Remote Control, 75:4 (2014), 728–744  mathnet  crossref  isi
    30. 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
    31. S. I. Sergeev, “Maximum travelling salesman problem. I”, Autom. Remote Control, 75:12 (2014), 2170–2189  mathnet  crossref  isi
    32. 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
    33. 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
    34. S. I. Sergeev, “Approximate algorithms for the traveling salesman problem. II”, Autom. Remote Control, 76:3 (2015), 472–479  mathnet  crossref  isi  elib  elib
    35. 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
    36. A. G. Chentsov, M. Yu. Khachai, M. Yu. Khachai, “An exact algorithm with linear complexity for a problem of visiting megalopolises”, Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 38–46  mathnet  crossref  mathscinet  isi  elib
    37. 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
    38. 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
    39. 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
    40. 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
    41. 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
    42. 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
    43. 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
    44. 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
    45. 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
    46. 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
    47. 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
    48. 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
    49. 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
    50. 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
    51. 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
    52. 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
    53. 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
    54. 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
    55. Yu. L. Kostyuk, “Zadacha kommivoyazhera: priblizhennyi algoritm po metodu vetvei i granits s garantirovannoi tochnostyu”, PDM, 2019, no. 45, 104–112  mathnet  crossref
    56. 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
    57. A. G. Chentsov, P. A. Chentsov, “K voprosu ob optimizatsii tochki starta v zadache marshrutizatsii s ogranicheniyami”, Izv. IMI UdGU, 55 (2020), 135–154  mathnet  crossref
  • Avtomatika i Telemekhanika
    Number of views:
    This page:683
    Full text:304
    First page:2

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