Concorde TSP Solver - Concorde TSP Solver

В Concorde TSP Solver это программа для решения задача коммивояжера. Это было написано Дэвид Эпплгейт, Роберт Э. Биксби, Вашек Хватал, и Уильям Дж. Кук, в ANSI C, и свободно доступен для академического использования.

Конкорд был применен к проблемам генное картирование,[1] предсказание функции белка,[2] движение транспорта,[3] преобразование растровых изображений в непрерывные линейные рисунки,[4] планирование движения судов для сейсморазведки,[5] и при изучении масштабируемых свойств задач комбинаторной оптимизации.[6]

В соответствии с Малдер и Вунш (2003), Concorde «широко считается самым быстрым решателем TSP для крупных проектов из существующих в настоящее время». В 2001 году Concorde выиграл 5000 гульден приз от CMG для решения проблемы маршрутизации транспортных средств, которую компания поставила в 1996 году.[7]

Примечания

  1. ^ Hitte et al. (2003).
  2. ^ Джонсон и Лю (2006).
  3. ^ Applegate et al. (2002).
  4. ^ Бош и Герман (2004).
  5. ^ Гутин и др. (2005)
  6. ^ Олдос и перкус (2003).
  7. ^ Маршрут движения автомобилей Whizzkids '96 с веб-сайта Concorde, получено 26 августа 2008 г.

Рекомендации

  • Олдос, Дэвид; Перкус, Аллон Г. (2003), "Масштабирование и универсальность в комбинаторной оптимизации непрерывной длины", Proc. Natl. Акад. Sci. Соединенные Штаты Америки, 100 (20): 11211–11215, arXiv:cond-mat / 0301035, Bibcode:2003ПНАС..10011211А, Дои:10.1073 / pnas.1635191100, ЧВК  208736, PMID  14504403.
  • Эпплгейт, Дэвид; Кук, Уильям; Даш, Санджиб; Роэ, Андре (2002), "Решение задачи минимальной и максимальной маршрутизации транспортных средств", ИНФОРМС Журнал по вычислительной технике, 14 (2): 132–143, Дои:10.1287 / ijoc.14.2.132.118.
  • Босх, Роберт; Герман, Адрианна (2004), «Непрерывные линейные рисунки через задачу коммивояжера» (PDF), Письма об исследованиях операций, 32 (4): 302–303, Дои:10.1016 / j.orl.2003.10.001.
  • Гутин Григорий; Якубович, Гельмут; Ронен, Шуки; Зверович, Алексей (2005), «Сейсмическая проблема судна» (PDF), Коммуникации в DQM, 8: 13–20.
  • Hitte, C .; Lorentzen, T. D .; Guyon, R .; Kim, L .; Cadieu, E .; Parker, H.G .; Quignon, P .; Lowe, J. K .; и другие. (2003), «Сравнение MultiMap и TSP / CONCORDE для построения радиационных гибридных карт», Журнал наследственности, 94 (1): 9–13, Дои:10.1093 / jhered / esg012, PMID  12692156.
  • Джонсон, Олин; Лю, Цзин (2006), "Подход коммивояжера к прогнозированию функций белков", Исходный код для биологии и медицины, 1: 3, Дои:10.1186/1751-0473-1-3, ЧВК  1636333, PMID  17147783.
  • Малдер, Сэмюэл А .; Вунш, Дональд К., II (2003 г.), «Решение проблемы коммивояжера в миллионном городе с помощью кластеризации« разделяй и властвуй »с помощью адаптивных резонансных нейронных сетей», Нейронные сети, 16 (5–6): 827–832, Дои:10.1016 / S0893-6080 (03) 00130-8, PMID  12850040.

внешняя ссылка