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

Введение

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

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

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