Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Математическое моделирование, численные методы и комплексы программ

Диссертационная работа:

Казак Александр Александрович. Моделирование сложных процессов железнодорожного и автомобильного транспорта на основе использования задачи коммивояжера : дис. ... канд. техн. наук : 05.13.18 Ростов н/Д, 2006 176 с. РГБ ОД, 61:07-5/700

смотреть содержание
смотреть введение
Содержание к работе:

СОДЕРЖАНИЕ 2

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

1 ЗАДАЧА КОММИВОЯЖЕРА И ЕЕ МОДИФИКАЦИИ:
ОПИСАНИЕ, ПРОБЛЕМЫ, ПУТИ РЕШЕНИЯ 12

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

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

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

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

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

  3. Существующий подход к решению задачи оптимизации маневровых передвижений на сортировочной станции 36

  4. Постановка задач диссертационной работы 37

  5. Выводы 41

2 РАЗРАБОТКА МОДЕЛИ НЕСКОЛЬКИХ КОММИВОЯЖЕРОВ 43

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

  2. Метод полного перебора 47

  3. Метод решения, использующий деревья поиска 51

  4. Эвристический алгоритм 63

  5. Комбинированный алгоритм 72

  6. Выводы 73

3 ПУТИ РЕШЕНИЯ ЗАДАЧИ НЕСКОЛЬКИХ КОММИВОЯЖЕРОВ В
МНОГОКРИТЕРИАЛЬНОЙ ПОСТАНОВКЕ 74

  1. Постановка вопроса 74

  2. Сведение многокритериальной задачи к однокритериальной 76

  1. Многокритериальный подход решения задачи нескольких коммивояжеров 78

  2. Мера близости комбинаторных объектов 86

  3. Выводы 91

4 ИСПОЛЬЗОВАНИЕ РАЗРАБОТАННЫХ МЕТОДОВ ПРИ МОДЕЛИ
РОВАНИИ СПЕЦИФИЧЕСКИХ ТРАНСПОРТНЫХ ПРОЦЕССОВ 92

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

  2. Разработка редактора графов 104

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

  4. Задачи автомобильного транспорта 117

  1. Перевозка заданного количества груза 117

  2. Разработка и внедрение логистической системы «Чистый город» 120

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

  2. Выводы 129

ЗАКЛЮЧЕНИЕ 131

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 135

ПРИЛОЖЕНИЕ 149

АКТЫ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ РАБОТЫ

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

Введение к работе:

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

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

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

5 коммивояжера актуальна, так как позволяет использовать разработанные машинные методы принятия обоснованных решений.

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

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

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

Общие вопросы теории систем, рассматриваемые в работе, изложены в трудах Баранова Л.А., Вира Ст., Богданова А.А., Дружинина В.В., Ивницкого В.А., Мермельштейна Г.Г., Райбмана И.С., Растригина Л. А., Саридиса Дж.

Вопросы управления сложными объектами на транспорте и в экономике, поставлены и решались в трудах Иванченко В.Н., Лисенкова В.М., Лябаха Н.Н., Орлова А.И.

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

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

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

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

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

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

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

обоснование выбора модели, формализующей задачу управления перевозками;

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

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

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

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

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

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

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

Чтобы обеспечить достижение поставленной цели необходимо решить следующие математические задачи:

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

развить задачу на случай нескольких агентов;

разработать алгоритм решения задачи нескольких коммивояжеров;

предложить методы решения проблемы многокритериалыюсти;

учесть специфику железнодорожного и автомобильного транспорта;

разработать программное обеспечение, реализующее полученный алгоритм нахождения оптимального плана задачи нескольких коммивояжеров;

синтезировать методику использования математических формализмов и программно-математического обеспечения при решении практических задач на транспорте;

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

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

Теоретические исследования, проведенные в работе, апробировались на имитационном эксперименте и на реальных задачах управления.

Научная новизна состоит в следующем:

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

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

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

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

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

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

Теоретическая значимость работы состоит в развитии новых методов математического моделирования транспортных процессов, основанных на использовании современного аппарата теории графов (задача нескольких коммивояжеров).

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

9 на транспорте, связанными с оптимизацией перемещений подвижных единиц, что приводит к интенсификации работ и оптимизации экономических и производственных критериев.

Апробация работы. Основные положения диссертации и научные результаты исследования докладывались и обсуждались на заседаниях и семинарах кафедры «Информатика» Ростовского государственного университета путей сообщения (РГУПС); второй международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании», г. Таганрог, 2001 г.; на научно-теоретической конференции профессорско-преподавательского состава РГУПС «Транспорт-2002», г. Ростов-на-Дону, 2002 г.; научно-теоретической конференции профессорско-преподавательского состава «Транспорт-2003», г. Ростов-на-Дону, 2003 г.; всероссийской научно-практической конференции профессорско-преподавательского состава «Транспорт-2004», г. Ростов-на-Дону, 2004 г.; международной научной конференции «Актуальные проблемы развития транспорта России: стратегические, региональные, технические», посвященной 75-летию РГУПС, г. Ростов н/Д, 2004 г.; всероссийской научно-практической конференции «Транспорт-2005», г. Ростов-на-Дону, 2005 г.; всероссийской научно-практической конференции «Транспорт-2006», г. Ростов-на-Дону, 2006 г., VII всероссийском симпозиуме по прикладной и промышленной математике, г. Москва, 2006 г.

Публикации. По результатам диссертационного исследования опубликовано 13 печатных работ общим объемом в 4,57 п.л. (из них лично автору принадлежит 4,36 п.л.), в том числе 11 без соавторов.

Внедрение результатов работы. Математическое обеспечение, предложенное в диссертации, внедрено в Ростовском филиале Российского научно-исследовательского и проектно-конструкторского института информатизации, автоматизации и связи МПС России, в структурном подразделении администрации города Ростова-на-Дону муниципальном учреждении «Чистый город». Материалы диссертационного исследования были использованы для методиче-

10 ских целей в учебном процессе РГУПС при проведении занятий по информатике (были написаны методические указания к практическим занятиям). Получены акты о внедрении.

Структура и объем работы. Диссертация состоит из введения, четырех глав, содержащих 25 параграфов, заключения, библиографического списка и приложений. Основное содержание диссертации изложено на 148 страницах, содержит 60 рисунков и 4 таблицы. Библиографический список содержит 179 наименований отечественных и зарубежных источников.

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

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

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

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

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

Подобные работы
Ляликов Вадим Николаевич
Комплекс программ для исследования методов решения задачи о коммивояжере
Рубцова Варвара Петровна
Двумерное численное моделирование процессов физики взрыва и удара методом SPH на основе решения задачи Римана
Скобелева Анастасия Александровна
Моделирование процессов переноса при создании и очистке трещины гидроразрыва
Кириллов Евгений Николаевич
Моделирование процессов теплоснабжения зданий для прогнозирования температуры воздуха в помещениях
Капырин Иван Викторович
Трехмерное моделирование процессов переноса примесей в пористых средах сложной структуры
Кургузов, Владимир Дмитриевич
Численное моделирование процессов разрушения твердых тел со структурой
Михайличенко Игорь Николаевич
Моделирование процессов тепло- и массопереноса при закачке радиоактивных растворов в глубокозалегающие пласты
Михайлов Дмитрий Владимирович
Моделирование процесса распознавания сверхфразовых единств в текстах при установлении их семантической эквивалентности
Соболев Андрей Витальевич
Математическое моделирование процесса пылеулавливания в многосекционном циклоне
Васильев Юрий Владимирович
Моделирование процессов переноса и стратификации аэрозольных компонент в средней и верхней атмосфере Земли под действием гравитофотофореза

© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net