Кадура (Математическое моделирование процессов перевозки грузов железнодорожным транспортом на основе использования задачи коммивояжера)

Содержание

Введение………………………………………………………………………….. 3

1.Задача коммивояжера и ее модификации: описание, проблемы, пути решения

…………………………………………………………………………………….. 7

1. Формальная постановка задачи коммивояжера ………………………….. 7

2. Классификация задач коммивояжера……………………………………… 10

3. Понятия и особенности сложных задач коммивояжера…………………. 16

4. Мера сложности моделирования задачи …………………………………… 24

2 Разработка модели нескольких коммивояжеров…………………………….. 30

2.1 Определение модели нескольких коммивояжеров с использованием теории графов ……………………………………………………………….................. 30

2.2 Метод полного перебора …………………………………………………… 34

2.3 Метод, использующий деревья поиска ……………………………………. 37

2.4 Эвристический алгоритм …………………………………………………. 49

2.5 Комбинированный алгоритм……………………………………………….58

3 Использование разработанных методов при моделировании специфических транспортных процессов……………………………………………………….. .. 65

3.1 Предварительное преобразование исходного графа ………………………. 65

3.2 Разработка редактора графов ……………………………………………….. 71

3.3 Учет специфики железнодорожного транспорта ………………………….. 75

3.4 Оптимальное упорядочение ребер графа ………………………………….. 83

Заключение ……………………………………………………………………… 91

Библиографический список …………………………………………………… 95

Приложение 1……………………………………………………………………... 98

Введение

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

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

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

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

В работе использованы труды таких авторов, разрабатывающих теорию графов и, в частности, задачу коммивояжера, как Ахо А., Басакер Р., Беллман Р., Беллмор М., Белов В.В., Берж К., Голынтейн Е.Г., Гудман С., Евстигнеев В.А., Ерусалимский Я.М., Зыков А.А., Иванов Б.Н., Конвей Р.В., Кристофидес Н., Литл Дж., Майника Э., Новиков Ф.А., Оре О., Пападимитриу X., Рейнгольд Э., Романовский И.В., Свами М., Сергиенко И.В., Уилсон Р., Харари Ф.

Организация эксплуатационной работы на транспорте рассмотрена в трудах Буянова В.А., Зубкова В.Н., Кочнева Ф.П., Мамаева Э.А., Мусиенко Н.Н., Осьминина А.Т., Прилепина Е.В., Сапунова Н.А., Сологуба Н.К., Смехова А.А., Сотникова И.Б., Сотникова Е.А., Тишкина Е.М., Угрюмова А.К., Шарова В.А., Эрлиха Н.В.

Общие вопросы теории систем, рассматриваемые в работе, изложены в трудах Баранова JI.A., Бира Ст., Богданова А.А., Дружинина В.В., Ивницкого

B.А., Мермельштейна Г.Г., Райбмана И.С., Растригина JI.A., Саридиса Дж. Вопросы управления сложными объектами на транспорте и в экономике, поставлены и решались в трудах Иванченко В.Н., Лисенкова В.М., Лябаха Н.Н., Орлова А.И.

Частные вопросы, нашедшие отражение в диссертации, рассмотрены в работах Белявского Г.И., Берштейна Л.С., Бутаковой М.А., Гуды А.Н., Ковалева

C.М., Ульяницкого Е.М., Шабельникова А.Н. и др.

Вместе с тем, практическое применение разработанных подходов к управлению, методов математического моделирования транспортных процессов затруднено в настоящее время вследствие:

- слабой адаптируемости этих подходов и методов к решению транспортных задач;

- не разработанности ряда теоретических и практических положений;

- отсутствия методик использования задачи коммивояжера на транспорте.

Целью написания данной дипломной работы явилось развитие математической модели для решения практических задач процесса перевозки грузов железнодорожным транспортом на основе использования задачи коммивояжера.

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

Магистерская диссертация состоит из трех разделов.

Первая глава: Задача коммивояжера и ее модификации: описание, проблемы, пути решения посвящёна теоретическим аспектам выбранной темы выпускной квалификационной работы.

Вторая глава: Разработка модели нескольких коммивояжеров содержит характеристику объекта исследования, проведенный анализ исследуемой проблемы и выводы по нему.

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

Основные положения магистерского диссертационного исследования докладывались и обсуждались на конференциях, по результатам которых вышли сборники:

1. Кадура, Е.В. Математическое моделирование сложных процессов железнодорожного транспорта на основе использования задачи коммивояжера. Сборник статей ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ТРАНСПОРТНОЙ СИСТЕМЫ РЕГИОНА: ПРОБЛЕМЫ И ПЕРСПЕКТИВЫ Материалы Всероссийской научно-практической конференции с международным участием: в 3-х томах. Под редакцией П.В. Виноградовой. 2015. С. 41-44.

2. Кадура, Е.В. Комплекс программ для исследования методов решения задачи о коммивояжере. Сборник статей Всероссийской научно-практической конференции творческой молодежи «Научно-техническое и социально-экономическое развитие транспорта и промышленности стран АТР». 2017 г. С. 67-71

1. Задача коммивояжера и ее модификации: описание, проблемы, пути решения

1.1Формальная постановка задачи коммивояжера

Пусть V — множество узлов v₁ , v₂ , ,v_n , представляющих города, а d _ij  d ( v_i , v_j ) | i,j =1, …, n — расстояния между парой узлов. Требуется найти минимальное значение среди всех ( n 1)!/ 2

перестановок , где (i ) — i-й город в выбранной перестановке. При этом накладываются условия неотрицательности, симметричности, запрета на петли (1) и удовлетворения неравенству треугольника (2):

Таблица 1-Процесс увеличения размерности решенных задач коммивояжера

Напомним, что граф G = <X, R> — множество точек X, представляющих объекты, и множество соединяющих точки отрезков линий R, представляющих отношения между объектами. Точки x_i  X, i = 1, ..., N — вершины графа, а отрезки линий r_ij  R, i,j = 1, ..., N — дуги (если отрезки направленные) или ребра (в противном случае) графа.