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 11, Pages 3–26 (Mi at6463)  

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

Surveys

The traveling salesman problem. Approximate algorithms

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

Moscow

Abstract: This third part of the survey covers a way to develop and estimate the efficiency of heuristic algorithms for solution of the traveling salesman problem. Data is given on the worst behavior of the algorithms. Results of computing experiments are extended. Interactive and hybrid algorithms and methods to solve high dimension problems are discussed.

Full text: PDF file (3128 kB)

English version:
Automation and Remote Control, 1989, 50:11, 1459–1479

Bibliographic databases:
UDC: 519.854.2

Received: 17.10.1988

Citation: I. I. Melamed, S. I. Sergeev, I. Kh. Sigal, “The traveling salesman problem. Approximate algorithms”, Avtomat. i Telemekh., 1989, no. 11, 3–26; Autom. Remote Control, 50:11 (1989), 1459–1479

Citation in format AMSBIB
\Bibitem{MelSerSig89}
\by I.~I.~Melamed, S.~I.~Sergeev, I.~Kh.~Sigal
\paper The traveling salesman problem. Approximate algorithms
\jour Avtomat. i Telemekh.
\yr 1989
\issue 11
\pages 3--26
\mathnet{http://mi.mathnet.ru/at6463}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1033619}
\zmath{https://zbmath.org/?q=an:0704.90095}
\transl
\jour Autom. Remote Control
\yr 1989
\vol 50
\issue 11
\pages 1459--1479


Linking options:
  • http://mi.mathnet.ru/eng/at6463
  • http://mi.mathnet.ru/eng/at/y1989/i11/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. A. O. Alekseev, “The minimax problem of $M$-travelling salesmen”, U.S.S.R. Comput. Math. Math. Phys., 31:12 (1991), 101–106  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. V. G. Anisimov, E. G. Anisimov, “Algorithm for optimal distribution of discrete nonuniform resources on a network”, Comput. Math. Math. Phys., 37:1 (1997), 51–57  mathnet  mathscinet  zmath
    4. K. G. Sabiryanova, “Ob odnom sposobe optimizatsii pokrytiya konechnogo mnozhestva”, Vestnik ChelGU, 1999, no. 4, 183–197  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, “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
    9. 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
    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. 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
    12. 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
    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. 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
    15. 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
    16. 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
    17. 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
    18. 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
    19. 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
    20. 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
    21. 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
    22. S. I. Sergeev, “Nonlinear resolving functions for the travelling salesman problem”, Autom. Remote Control, 74:6 (2013), 978–994  mathnet  crossref  mathscinet  isi
    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. 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
    37. 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
    38. 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
    39. 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
    40. 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
    41. 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
    42. 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
    43. 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
    44. 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
    45. 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
    46. 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
    47. 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
    48. 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
    49. V. V. Zakharov, A. V. Mugaiskikh, “Dinamicheskaya adaptatsiya geneticheskogo algoritma marshrutizatsii transporta na bolshikh setyakh”, UBS, 73 (2018), 108–133  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:925
    Full text:324
    First page:2

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