Методы решения задачи коммивояжера.

Введение Один из основных путей повышения эффективности работы транспорта — это модернизация системы управления и организации его работы. В последнее время все более интенсивно в процессы мониторинга, моделирования сложных транспортных объектов, принятия решений и контроля их исполнения, составляющих суть управления на транспорте, внедряются методы математического моделирования, а также обеспечивающие их передовые информационные технологии. В силу специфики основных технологических процессов на транспорте, представляется перспективным использование мате-матического аппарата теории графов. Характерными примерами может служить управление маневровой работой на сортировочных станциях, развозом грузов по сети магазинов города. Вместе с тем, многокритериальность указанных задач управления, а также их программно-математическое обеспечение, не в полной мере учитывающее специфику некоторых задач, повышают вероятность ошибочных действий со стороны человека-оператора, и, как следствие, вероятность сбоев в работе сортировочных станций, автотранспортных предприятий, срывов графиков движения поездов и автомашин. В связи с этим формализация (математическое описание) задач управления транспортными системами на основе использования задачи коммивояжера актуальна, так как позволяет использовать разработанные машинные методы принятия обоснованных решений. Задачи управления транспортными потоками являются многокритериальными и плохо формализуются вследствие нестационарности и зашумленности исходной информации, противоречивым экономическим, технологическим, экологическим и другим требованиям. Важнейшими проблемами совершенствования систем автоматического управления является повышение надежности и точности их функционирования, безопасности и быстродействия. Решение этих задач позволит снять ряд технологических и организационно-экономических проблем.

Введение 2 1. Теоретическая часть 4 1.1. Содержательное описание 4 1.2. Математическая модель 4 1.3. Постановка оптимизационной задачи 6 1.4. Методы решения задачи коммивояжера 6 1.4.1. Метод ветвей и границ 6 1.4.2. Алгоритм Литтла 9 1.4.3. Генетические алгоритмы 11 2. Практическая часть 12 2.1. Постановка задачи 12 2.2. Решение задачи методом полного перебора 13 2.3. Решение задачи методом ветвей и границ 25 2.4. Решение задачи методом Литтла 27 2.5. Программное решение муравьинным методом 36 2.6. Сравнение методов решения задачи коммивояжера 46 Заключение 47 Литература 48 Приложение 50

1. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., «Мир», 1965, 174 с. 2. В. П. Сигорский. Математический аппарат инженера. - К., «Техніка», 1975, 768 с. 3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил. 4. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. – М., Наука, 1979, 345 с. 5. Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с. 6. В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с. 7. Ф. А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с. 8. Bonavear E., DorigoM. Swarm Intelligence: from Natural to Artificial Systems.— Oxford University Press, 1999.— 307 p. 9. Corne D., Dorigo M., Glover F. New Ideas in Optimization.— McGrav Hill, 1999. 10. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization // Reader for CEU Summer University Course «Complex System».— Budapest, Central European University, 2001.— P. 1–38 11. http://irida.ulb.ac.de/ACO/ACO.html. 12. http://www.iwr.uniheidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html. 13. Reimann M. Ant Based Optimization in Good Transportation. PhD Thesis. University of Vienna.— Vienna, Austria, 2002.— 149 p. 14. Caro G. D., DorigoM. Anet: a Mobile Agents Approach to Adaptive Routing. Technical Report IRIDA 97 12. IRIDA— Universite Libre de Brusseles.— Brussels, Belgium, 1997.— 27 p. 15. http://www.swarm.org. 16. Cherix D. Note preliminaire sur la structure, la phenologie et le regime alimentaire d'une super colonie de Formica lugubris Zett. // Insects Sociaux 27, 1980.— P. 226–236.