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

Рисунок 48-Преобразованный смешанный граф

Отметим на середине каждого ребра, по которому нужно пройти, фик­тивную вершину, справа от ее номера поставим штрих. В результате получим сеть, изображенную на рисунке 48. В новом графе вершины и b_i i = базо­вые, остальные 14 (6 вершин исходного графа плюс 8 фиктивных) - небазовые. Преобразуем последний граф к полному используя алгоритм Флойда . Потребуем, чтобы каждый маршрут в задаче нескольких коммивояжеров содержал хотя бы одну фиктивную вершину (т.е. хотя бы одно ребро исходного графа). Приведем, к примеру, такой набор маршрутов, в совокупности содер­жащих все вершины, удовлетворяющий этому условию:

1. 3, 10', 4, 9', 2, 8', 1, 7', 5, 11', [3], 12', [5],

2. , [4], 13', 6,14', [6], .

Заметим, что отрезок пути [5,14'] никем не пройден. Следовательно, дан­ное решение, являясь допустимым решением задачи нескольких коммивояже­ров на преобразованном графе, не является таковым для исходной задачи. Ана­лиз на предмет допустимости заключается в последовательном просмотре фик­тивных вершин каждого маршрута, отмеченных на серединах неориентирован­ных ребер. Следует сравнивать между собой их соседние вершины (обозначим непосредственно предшествующую точку через prev, а следующую - через next). Например, у вершины 10' из первого маршрута соседние 3 и 4 - prev=3, next=4. В случае выполнения для некоторой фиктивной вершины равенства prev =пех1 (во втором маршруте указанного решения как раз и содержится такой отрезок пути 6, 14', [6]) решение не допустимо, и его следует исключить из дальнейшего рассмотрения.

Оптимум задачи нескольких коммивояжеров с учетом наложенных огра­ничений будет иметь вид:

1. , [3], 10', [4], 9', 2, 8', 1,7,5,6,

2. а₂, 4, 13', 6,14', [5], 11', 3,12', [5,14', 6], .

Суммарная длина маршрутов = 130, длина максимального маршрута = 70. Значение критерия качества равно 9100.

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

1. , (3,4), (4,2), (2,1), (1,5),

2. , (4, 6), (6, 5), (5, 3), (3, 5), [6],

с тем же значением критерия качества, равным 9100. Каждое ребро указывается в обходе ровно один раз. Последовательности вершин в маршрутах, приводя­щие к повторным вхождениям некоторых ребер, заключаются в квадратные скобки (к примеру, ребро, инцидентное вершинам 5 и 6, во втором маршруте встречается два раза, поэтому во второй раз вместо данного ребра указывается кратчайший путь от конечной вершины s предыдущего ребра (3,5) к , заклю­чаемый в квадратные скобки).

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

1. Каждый маршрут из этого решения должен содержать как минимум одну фиктивную вершину;

2. Для каждой фиктивной вершины, которая делит пополам неориенти­рованное ребро, не должно выполняться равенство prev=пеxt,

3. Суммарное количество груза на каждом маршруте не должно превы­шать грузоподъемность автомобиля, работающего на данном маршруте.

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

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

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

Рисунок 49 -Исходный смешанный граф

Рисунок 49 представляет иллюстрацию исходного графа с указанием весов его ребер, созданную посредством редактора графов. Предполагается, что ком­мивояжеры находятся в вершинах 6 и 8 (а₁ = 6, а₂=8), а завершить обход должны в точках 7 и 9 ( 1 , 9). Пусть грузоподъемность первого транс­портного средства равна 2000, второго - 1000. Рисунке 50, а) представляет иллю­страцию графа идентификации, где не требующие обхода ребра имеют нулевой вес, а требующие - ненулевой. Если в графе идентификации существует пара противоположно направленных дуг (x,y), (у,x), и вес дуги (х,у) равен весу (у,x), то в исходном смешанном графе данная пара интерпретируется как одно неори­ентированное ребро (x,y). Если же на рис. 50, а) вес дуги (x,y) не равен весу (у,x), считаем, что в исходном графе имеется два ориентированных ребра (x,y) и (у,x) для посещения. Рис. 50, б) иллюстрирует граф количества. Вес каждой его дуги характеризует количество (например, объем или вес) подлежащего сбору груза на данном отрезке пути.

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

, (2,1),(1, 4), (3,4), (4, 3),

,[4],(5,1),(1,2), (2, 3), (3,1), [2],

Суммарная длина маршрутов J₁ = 686. Длина максимального из маршру­тов J₂= 354. Значение критерия качества равно 242844.

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

Выводы по главе:

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

2. Рассмотрена специфика железнодорожного транспорта, заключающая­ся в том, что точки для посещения имеют разный приоритет. Введены дополни­тельные критерии качества решения задачи нескольких коммивояжеров, не дающие локомотивам одновременно находиться в одной точке, тем самым пре­пятствуя возникновению "пробок" и крушений. Показано как подсчитывать значения этих новых критериев, а также результирующего критерия. Изменена формула вычисления длины маршрута каждого локомотива, в связи с тем, что локомотивы начинают работу не одновременно. Делается вывод: метод, ис­пользующий деревья поиска и комбинированный алгоритм не могут быть раз­виты на случай указанной модификации модели нескольких коммивояжеров. Приводится иллюстративный материал.

Заключение

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

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

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

Вопросы, нашедшие свое отражение в выпускной квалификационной работе:

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

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

3. Задача нескольких коммивояжеров, методы поиска ее минимума.

4. Виды критериев эффективности функционирования транспортных сис­тем, вопросы согласования и оптимизации многих критериев.

5. Формализация и решение ряда прикладных задач методами теории гра­фов.

Основные научные результаты исследований состоят в следующем:

1. Известные точные и приближенные методы поиска оптимума задачи коммивояжера (метод полного перебора, ветвей и границ, эвристические под­ходы) развиты для нахождения оптимального плана разрабатываемой задачи нескольких коммивояжеров. Указана область применения полученных алго­ритмов. Приведены конкретные численные примеры работы алгоритмов.

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

2. Предложено схематичное графическое изображение ситуаций в манев­ровом районе. Описан переход от предложенных схем к математическому представлению ситуации в виде исходного графа с определенной нумерацией вершин, который затем следует преобразовать к полному графу по алгоритму Флойда.

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

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

5. Разработан комплекс программ на ЭВМ, реализующих предложенные методы и подходы, а в частности редактор графов, облегчающий создание и ре­дактирование исходных данных оптимизационных задач на графах.

Возможные направления дальнейших научных исследований по данной теме:

1. Совершенствование разработанного метода, использующего деревья поиска.

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

• Изменить политику ветвления: вместо производимого методом ветвле­ния в глубину реализовать ветвление побегами, в ширину, или указать какое- либо другое, лучшее правило ветвления, позволяющее сократить размеры де­ревьев.

  1. Совершенствование эвристического алгоритма.

• Помимо методов Монте-Карло, Лина-Кернигана и ближайшего непосещенного города, составляющих предлагаемый в данной работе эвристический алгоритм, развить на случай задачи с несколькими коммивояжерами прочие из­вестные методы решения задачи с одним коммивояжером, а в частности, рас­смотренные в первой главе. Дополнить ими разработанный эвристический ал­горитм.

• Указать наилучший выбор вероятностей работы алгоритмов, входящих в общий эвристический алгоритм.

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

Список используемых источников

1. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложе­ния. - М.: Вузовская книга, 2010. - 280 с.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислитель­ных алгоритмов. - М., 2011. - 536 с.

3. Гудман С., Хидитниеми С. Введение в разработку и анализ алгоритмов. -М., 2013.-368 е.: ил.

4. Белоусов А.И., Ткачев С.Б. Дискретная математика. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 744 с.

5. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. -М.: Лаборатория Базовых Знаний, 2002.-288 е.: ил.

6. Иозайтис B.C., Львов Ю.А. Экономико-математическое моделирование производственных систем. - М., 2012. - 192 с.

7. Катулев А.Н., Северцев Н.А. Исследование операций: принципы при­нятия решений и обеспечение безопасности. - М.: Физ.-мат.лит., 2010. - 320 с.

8. Кузнецов A.B., Холод Н.И. Математическое программирование / Учеб. пособие для эконом, спец. вузов. - Минск: Вышэйшая школа, 2014. - 221 с.

9. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 2012. - 480 е.: ил.

10. Кук Д., Бейз Г. Компьютерная математика. - М.: Наука, 2011. - 384 с.

11. Роберте Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. - М.: Наука. Гл. ред. физ.-мат. лит., 2012.-496 с.

12. Романовский И.В. Алгоритмы решения экстремальных задач. - М.: Наука, 2011.-352 с.

13. Романовский И.В. Дискретный анализ. - СПб.: Невский диалект, 2010.-240 с.

14. Моргунов И.Б. Основы дискретной оптимизации некоторых задач упорядочения. - М.: Исследовательский центр проблем качества подготовки специалистов, 2014.-215 с.

15. Москинова Г.И. Дискретная математика. - М.: Логос, 2010. - 240 с.

16. Варфоломеев В.В., Колодий Л.П. Устройство пути и станций/ Учебник для техникумов железнодорожного транспорта. - М.: Транспорт, 2012. - 303 с.

17. Васильев В.В., Ралдугин Е.А. Электронные модели задач на графах. - Киев: Наукова думка, 2015. -152 с.

18. Айзинбуд С.Я., Козубенко В.Г., Курков В.Н. Машинист и безопас­ность. - М.: Транспорт, 2012. - 48 с.

19. Железнодорожные станции и узлы промышленного транспорта: учеб­ник для вузов. - М.: Транспорт, 2016. - 352 с.

20. Железнодорожные станции и узлы промышленных районов: учебник для вузов. - Ростов н/Д: Изд. РГУПС, 2015. - 488 с.

21. Железные дороги. Общий курс: учебник для вузов / 4-е изд. - М.: Транспорт, 2012.-295 с.

ПРИЛОЖЕНИЕ