RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Автомат. и телемех.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Автомат. и телемех., 1989, выпуск 10, страницы 3–29 (Mi at6433)  

Эта публикация цитируется в 55 научных статьях (всего в 55 статьях)

Обзоры

Задача коммивояжера. Точные методы

И. И. Меламед, С. И. Сергеев, И. Х. Сигал

Москва

Аннотация: Рассматриваются алгоритмы оптимального решения задачи коммивояжера. Описываются методы динамического программирования, различные варианты метода ветвей и границ, методы множителей Лагранжа, методы отсекающих плоскостей и различные сочетания этих методов. Приводятся данные вычислительных экспериментов.

Полный текст: PDF файл (3620 kB)

Англоязычная версия:
Automation and Remote Control, 1989, 50:10, 1303–1324

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.854.2(047)

Поступила в редакцию: 17.10.1988

Образец цитирования: И. И. Меламед, С. И. Сергеев, И. Х. Сигал, “Задача коммивояжера. Точные методы”, Автомат. и телемех., 1989, № 10, 3–29; Autom. Remote Control, 50:10 (1989), 1303–1324

Цитирование в формате AMSBIB
\RBibitem{MelSerSig89}
\by И.~И.~Меламед, С.~И.~Сергеев, И.~Х.~Сигал
\paper Задача коммивояжера. Точные методы
\jour Автомат. и телемех.
\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


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/at6433
  • http://mi.mathnet.ru/rus/at/y1989/i10/p3

    ОТПРАВИТЬ: 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
    Цикл статей

    Эта публикация цитируется в следующих статьяx:
    1. К. Г. Сабирянова, “Аддитивная задача оптимального накрытия”, Ж. вычисл. матем. и матем. физ., 36:4 (1996), 148–155  mathnet  mathscinet  zmath; K. G. Sabiryanova, “The additive problem of optimal covering”, Comput. Math. Math. Phys., 36:4 (1996), 545–551  isi
    2. К. Г. Сабирянова, “Об одном способе оптимизации покрытия конечного множества”, Вестник ЧелГУ, 1999, № 4, 183–197  mathnet
    3. С. И. Сергеев, “Улучшенные нижние границы для решения квадратичной задачи назначения”, Автомат. и телемех., 2004, № 11, 49–63  mathnet  mathscinet  zmath; S. I. Sergeev, “Improved lower bounds for the quadratic assignment problem”, Autom. Remote Control, 65:11 (2004), 1733–1746  crossref  isi
    4. С. И. Сергеев, “Использование методов теории оптимального управления для решения некоторых задач дискретной оптимизации. II. Статическая задача коммивояжера”, Автомат. и телемех., 2006, № 6, 106–112  mathnet  mathscinet  zmath; S. I. Sergeev, “Discrete optimization by optimal control methods. II. The static traveling salesman problem”, Autom. Remote Control, 67:6 (2006), 927–932  crossref
    5. С. И. Сергеев, “Использование методов теории оптимального управления для решения некоторых задач дискретной оптимизации. III. Динамическая задача коммивояжера”, Автомат. и телемех., 2006, № 7, 27–40  mathnet  mathscinet  zmath; S. I. Sergeev, “Discrete optimization by optimal control methods. III. The dynamic traveling salesman problem”, Autom. Remote Control, 67:7 (2006), 1039–1050  crossref
    6. П. П. Пархоменко, “Еще раз о решении задачи коммивояжера”, Автомат. и телемех., 2006, № 12, 190–204  mathnet  mathscinet  zmath; P. P. Parkhomenko, “On the solution of the traveling salesman problem once again”, Autom. Remote Control, 67:12 (2006), 2036–2050  crossref
    7. А. А. Ченцов, А. Г. Ченцов, “Экстремальная задача маршрутизации “на узкие места” с ограничениями в виде условий предшествования”, Тр. ИММ УрО РАН, 14, № 2, 2008, 129–142  mathnet  zmath  elib; 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  crossref  isi
    8. А. А. Ченцов, А. Г. Ченцов, П. А. Ченцов, “Экстремальная задача маршрутизации с внутренними потерями”, Тр. ИММ УрО РАН, 14, № 3, 2008, 183–201  mathnet  elib; 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  crossref  isi
    9. С. И. Сергеев, “Гибридные системы управления и динамическая задача коммивояжера”, Автомат. и телемех., 2008, № 1, 45–54  mathnet  mathscinet  zmath; S. I. Sergeev, “Hybrid control systems and the dynamic traveling salesman problem”, Autom. Remote Control, 69:1 (2008), 42–51  crossref  isi
    10. С. И. Сергеев, “Симметричная задача коммивояжера I. Новые быстрые нижние границы для задачи оптимального $2$-паросочетания”, Автомат. и телемех., 2009, № 11, 148–160  mathnet  mathscinet  zmath; 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  crossref  isi
    11. А. А. Ченцов, А. Г. Ченцов, П. А. Ченцов, “Метод итераций в задаче маршрутизации с внутренними потерями”, Тр. ИММ УрО РАН, 15, № 4, 2009, 270–289  mathnet  elib; 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  crossref
    12. А. Н. Сесекин, А. А. Ченцов, А. Г. Ченцов, “Маршрутизация с абстрактной функцией агрегирования стоимостей перемещений”, Тр. ИММ УрО РАН, 16, № 3, 2010, 240–264  mathnet  elib
    13. С. И. Сергеев, “Симметричная задача коммивояжера II. Новые нижние границы”, Автомат. и телемех., 2010, № 4, 150–168  mathnet  mathscinet  zmath; S. I. Sergeev, “The symmetric travelling salesman problem II. New low bounds”, Autom. Remote Control, 71:4 (2010), 681–696  crossref  isi
    14. Е. Е. Иванко, “Метод масштабирования в приближенном решении задачи коммивояжера”, Автомат. и телемех., 2011, № 12, 115–129  mathnet  mathscinet  zmath; E. E. Ivanko, “Method of scaling in approximate solution of the traveling salesman problem”, Autom. Remote Control, 72:12 (2011), 2527–2540  crossref  isi
    15. А. М. Григорьев, Е. Е. Иванко, А. Г. Ченцов, “Динамическое программирование в обобщенной задаче курьера с внутренними работами: элементы параллельной структуры”, Модел. и анализ информ. систем, 18:3 (2011), 101–124  mathnet
    16. Е. Е. Иванко, “Критерий устойчивости оптимального маршрута в задаче коммивояжера при добавлении вершины”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2011, № 1, 58–66  mathnet
    17. А. Г. Ченцов, “Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 2012, № 12, 53–76  mathnet
    18. И. Б. Чеблоков, А. Г. Ченцов, “Об одной задаче маршрутизации с внутренними работами”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2012, № 1, 96–119  mathnet
    19. А. А. Ченцов, А. Г. Ченцов, “Об одной задаче маршрутизации с внутренними работами”, Тр. ИММ УрО РАН, 18, № 1, 2012, 298–317  mathnet  elib
    20. А. А. Ченцов, А. Г. Ченцов, “Об одной итерационной процедуре решения задачи маршрутизации с ограничениями”, Тр. ИММ УрО РАН, 18, № 3, 2012, 261–281  mathnet  elib; 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  crossref  isi
    21. С. И. Сергеев, “Задача коммивояжера. Использование нелинейных разрешающих функций”, Автомат. и телемех., 2013, № 6, 101–120  mathnet  mathscinet; S. I. Sergeev, “Nonlinear resolving functions for the travelling salesman problem”, Autom. Remote Control, 74:6 (2013), 978–994  crossref  isi
    22. Ю. Л. Костюк, “Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ”, ПДМ, 2013, № 2(20), 78–90  mathnet
    23. А. А. Ченцов, А. Г. Ченцов, П. А. Ченцов, “Элементы динамического программирования в экстремальных задачах маршрутизации”, Пробл. управл., 5 (2013), 12–21  mathnet; 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  crossref  isi
    24. Е. Е. Иванко, “Усеченный метод динамического программирования в замкнутой задаче коммивояжера с симметричной функцией стоимости”, Тр. ИММ УрО РАН, 19, № 1, 2013, 121–129  mathnet  mathscinet  elib
    25. А. Г. Ченцов, “К вопросу о маршрутизации комплексов работ”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2013, № 1, 59–82  mathnet
    26. А. А. Ченцов, А. Г. Ченцов, “Метод итераций в обобщенной задаче курьера с особенностью в определении функций стоимости”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2013, № 3, 88–113  mathnet
    27. А. Г. Ченцов, П. А. Ченцов, “Об одном нестационарном варианте обобщенной задачи курьера с внутренними работами”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 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. А. Г. Ченцов, “Задача последовательного обхода мегаполисов с условиями предшествования”, Автомат. и телемех., 2014, № 4, 170–190  mathnet; A. G. Chentsov, “Problem of successive megalopolis traversal with the precedence conditions”, Autom. Remote Control, 75:4 (2014), 728–744  crossref  isi
    30. А. А. Петунин, А. Г. Ченцов, П. А. Ченцов, “Локальные вставки на основе динамического программирования в задаче маршрутизации с ограничениями”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2014, № 2, 56–75  mathnet
    31. С. И. Сергеев, “Задача коммивояжера на максимум. I”, Автомат. и телемех., 2014, № 12, 101–124  mathnet; S. I. Sergeev, “Maximum travelling salesman problem. I”, Autom. Remote Control, 75:12 (2014), 2170–2189  crossref  isi
    32. А. Г. Ченцов, “Беллмановские вставки в задаче маршрутизации с ограничениями и усложненными функциями стоимости”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2014, № 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”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 8:1 (2015), 24–45  mathnet  crossref  elib
    34. С. И. Сергеев, “Приближенные алгоритмы решения задачи коммивояжера. II”, Автомат. и телемех., 2015, № 3, 125–134  mathnet  elib; S. I. Sergeev, “Approximate algorithms for the traveling salesman problem. II”, Autom. Remote Control, 76:3 (2015), 472–479  crossref  isi  elib
    35. А. А. Петунин, А. Г. Ченцов, П. А. Ченцов, “Об одной задаче маршрутизации перемещений инструмента при листовой резке деталей”, Модел. и анализ информ. систем, 22:2 (2015), 278–294  mathnet  mathscinet  elib
    36. А. Г. Ченцов, М. Ю. Хачай, Д. М. Хачай, “Точный алгоритм с линейной трудоемкостью для одной задачи обхода мегаполисов”, Тр. ИММ УрО РАН, 21, № 3, 2015, 309–317  mathnet  mathscinet  elib; 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  crossref  isi
    37. М. С. Кошелева, А. А. Ченцов, А. Г. Ченцов, “О задаче маршрутизации с ограничениями, включающими зависимость от списка заданий”, Тр. ИММ УрО РАН, 21, № 4, 2015, 178–195  mathnet  mathscinet  elib
    38. А. А. Ченцов, А. Г. Ченцов, “Обобщенная модель курьера с дополнительными ограничениями”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 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. А. Г. Ченцов, А. А. Ченцов, “Задача маршрутизации, осложненная зависимостью функций стоимости и “текущих” ограничений от списка заданий”, Модел. и анализ информ. систем, 23:2 (2016), 211–227  mathnet  crossref  mathscinet  elib
    41. А. Г. Ченцов, П. А. Ченцов, “Маршрутизация в условиях ограничений: задача о посещении мегаполисов”, Автомат. и телемех., 2016, № 11, 96–117  mathnet  elib; A. G. Chentsov, P. A. Chentsov, “Routing under constraints: problem of visit to megalopolises”, Autom. Remote Control, 77:11 (2016), 1957–1974  crossref  isi  elib
    42. А. Г. Ченцов, “Оптимизирующие вставки в задачах маршрутизации и их реализация на основе динамического программирования”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 26:4 (2016), 565–578  mathnet  crossref  mathscinet  elib
    43. А. Г. Ченцов, А. А. Ченцов, “Дискретно-непрерывная задача маршрутизации с условиями предшествования”, Тр. ИММ УрО РАН, 23:1 (2017), 275–292  mathnet  crossref  elib; 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  crossref  isi
    44. А. А. Петунин, А. А. Ченцов, А. Г. Ченцов, П. А. Ченцов, “Элементы динамического программирования в конструкциях локального улучшения эвристических решений задач маршрутизации с ограничениями”, Автомат. и телемех., 2017, № 4, 106–125  mathnet  elib; 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  crossref  isi
    45. А. А. Петунин, А. Г. Ченцов, П. А. Ченцов, “К вопросу о маршрутизации перемещений при листовой резке деталей”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 10:3 (2017), 25–39  mathnet  crossref  elib
    46. А. Г. Ченцов, А. А. Ченцов, “Модельный вариант задачи о последовательной утилизации источников излучения (итерации на основе оптимизирующих вставок)”, Изв. ИМИ УдГУ, 50 (2017), 83–109  mathnet  crossref  elib
    47. А. Г. Ченцов, А. А. Ченцов, А. М. Григорьев, “Об одной задаче маршрутизации, моделирующей перемещения в радиационных полях”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 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”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 11:1 (2018), 60–74  mathnet  crossref  elib
    49. А. Г. Ченцов, П. А. Ченцов, “Оптимизация точки старта в задаче последовательного обхода мегаполисов при наличии условий предшествования”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 11:2 (2018), 83–95  mathnet  crossref  elib
    50. А. Г. Ченцов, А. А. Ченцов, А. Н. Сесекин, “Динамическое программирование в обобщенной задаче «на узкие места» и оптимизация точки старта”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 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. А. Г. Ченцов, А. М. Григорьев, “Оптимизирующие мультивставки в задачах маршрутизации с ограничениями”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 28:4 (2018), 513–530  mathnet  crossref  elib
    54. А. Г. Ченцов, П. А. Ченцов, “Об одной задаче маршрутизации с оптимизацией точки старта–финиша”, Изв. ИМИ УдГУ, 52 (2018), 103–115  mathnet  crossref  elib
    55. Ю. Л. Костюк, “Задача коммивояжёра: приближённый алгоритм по методу ветвей и границ с гарантированной точностью”, ПДМ, 2019, № 45, 104–112  mathnet  crossref
  • Автоматика и телемеханика
    Просмотров:
    Эта страница:654
    Полный текст:292
    Первая стр.:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020