Моделирование сложных процессов железнодорожного и автомобильного транспорта на основе использования задачи коммивояжера

• Автор: Казак, Александр Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Ростов-на-Дону
• Количество страниц: 176 с.

СОДЕРЖАНИЕ
СОДЕРЖАНИЕ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

1 ЗАДАЧА КОММИВОЯЖЕРА И ЕЕ МОДИФИКАЦИИ

ОПИСАНИЕ, ПРОБЛЕМЫ, ПУТИ РЕШЕНИЯ

1.1 Характеристика объекта исследования.

1.1.1 Роль и место задачи коммивояжера в совершенствовании транспортных процессов.

1.1.2 Постановка задач управления в рамках исследуемых оптимизационных задач.

1.2 Обзор методов решения задачи коммивояжра.

1.3 Возможные механизмы учета многих критериев в задаче коммивояжера.

1.4 Существующий подход к решению задачи оптимизации маневровых передвижений на сортировочной станции.
1.5 Постановка задач диссертационной работы.
1.6 Выводы
2 РАЗРАБОТКА МОДЕЛИ НЕСКОЛЬКИХ КОММИВОЯЖЕРОВ
2.1 Определение модели нескольких коммивояжеров с использованием теории графов
2.2 Метод полного перебора
2.3 Метод решения, использующий деревья поиска
2.4 Эвристический алгоритм
2.5 Комбшшрованный алгоритм.
2.6 Выводы
3 ПУТИ РЕШЕНИЯ ЗАДАЧИ НЕСКОЛЬКИХ КОММИВОЯЖЕРОВ В МНОГОКРИТЕРИАЛЬНОЙ ПОСТАНОВКЕ.
3.1 Постановка вопроса
3.2 Сведение многокритериальной задачи к однокритериальной
3.3 Многокритериальный подход решения задачи нескольких коммивояжеров
3.4 Мера близости комбинаторных объектов.
3.5 Выводы.
4 ИСПОЛЬЗОВАНИЕ РАЗРАБОТАННЫХ МЕТОДОВ ПРИ МОДЕЛИРОВАНИИ СПЕЦИФИЧЕСКИХ ТРАНСПОРТНЫХ ПРОЦЕССОВ
4.1 Предварительное преобразование исходного графа.
4.2 Разработка редактора графов
4.3 Учет специфики железнодорожного транспорта
4.4 Задачи автомобильного транспорта
4.4.1 Перевозка заданного количества груза.
4.4.2 Разработка и внедрение логистической системы Чистый город
4.5 Оптимальное упорядочение ребер графа
4.6 Выводы
ЗАКЛЮЧЕНИЕ.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.
ПРИЛОЖЕНИЕ.
АКТЫ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ РАБОТЫ
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность


Предполагается, что маршрут движения коммивояжёра начинается и заканчивается в одной и той же точке, например в городе номер 1. Необходимо до начала движения рассчитать маршрут движения коммивояжёра, удовлетворяющий требованию: суммарная длина всех отрезков маршрута минимальна [5]. Если немного видоизменить постановку и опустить условие возвращения торговца в исходный пункт, получим разомкнутую задачу коммивояжера. Рассмотренная задача и ее модификации имеют большое число практических приложений в различных областях человеческой деятельности, и в том числе на транспорте. Задача возникает при планировании рационального использования транспортных средств. К примеру, грузовику, находящемуся на продовольственной базе необходимо доставить товары определенному количеству потребителей и вернуться обратно на базу. Либо требуется указать маршрут движения локомотиву, выполняющему операции в маневровом районе. Поскольку суммарная длина всех отрезков маршрута прямо пропорциональна пройденному транспортным средством расстоянию, маршрут минимальной длины может быть получен путем решения соответствующей задачи коммивояжера. Вместе с тем традиционная постановка задачи не отражает многие практические случаи. Дело в том, что минимизируя общий километраж, пройденный транспортным средством, время, затраченное на работу, или что-то другое, мы необязательно получим маршрут, обеспечивающий минимальные транспортные издержки. Экстремумы каждому из этих критериев доставляют, вообще говоря, различные решения задачи коммивояжера. Интересующая нас общая «стоимость передвижений», выражаемая в финансовых, временных, энергетических и других затратах зачастую не пропорциональна фактически пройденному транспортным средством расстоянию, или значению какого-либо одного экономического показателя. Требуется одновременный учет многих, возможно противоречивых, экономических показателей. Маршрут с минимальными транспортными издержками может быть получен только путем решения задачи коммивояжера, адекватно учитывающей все эти показатели (см. Кроме того, при развозке продукции со складов и выполнении маневров, в целях повышения скорости выполнения работ, часто задействуется не один, а несколько грузовиков (локомотивов). Поэтому представляет интерес разработка задачи коммивояжера на случай нескольких коммивояжёров, что и осуществляется в данной работе. Минимизировать можно как сумму длин маршрутов, так и длину наибольшего маршрута, либо некую обобщенную составляющую, учитывающую оба варианта []. Оперативно-диспетчерский персонал железнодорожной станции функционирует в условиях большой размерности задач контроля и управления, дефицита времени на принятие решений, наличия ошибок в данных, многокрите-риальности задачи управления, открытости объекта и системы управления. В связи с этим формализация (математическое описание) задачи управления актуальна, так как позволяет использовать хорошо разработанные машинные методы идентификации объекта (состояния) и принятия обоснованных решений [5]. Одним из подходов к моделированию сложных транспортных процессов, недостаточно разработанных теоретически и ещё не имеющих практической ценности, является использование постановок проблем в смысле задачи коммивояжёра. Как было сказано в п. Рассмотрим эти и другие примеры более подробно. Пример 1. Важнейшим звеном процесса расформирования составов на сортировочных станциях являются сортировочные горки (СГ)- На рис. СГ с указанием технологических операций, выполняемых последовательно различными подсистемами, которые в комплексе автоматизируют сортировочный процесс [4]. Это: телеуправление горочным локомотивом (ТГЛ), который обозначен номером 1 на рис. ГАЦ), автоматическое регулирование скорости скатывания отцепов на спускной части горки (АРС - ЦНИИ, АРС - ГТСС). Кроме того, на рисунке обозначены: 2 - тормозные позиции, 3 - стрелки, 4 - указатель скорости надвига отцепа, 5 - горочный светофор, который через комбинацию цветов может выполнять функции 4, 6 - измерительный участок, 7 - радиолокационный скоростемер, 8 - устройства заполнения путей.