Порядок выполнения работы

1. Изучить теоретическую часть работы.

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

3. С помощью компьютера и стандартной программы найти кратчайшие расстояния между всеми вершинами графа дорожной сети. Распечатку привести в отчете.

Защита отчета на следующем занятии Лабораторная работа № 3

(4 часа)

Изучение методов оптимизации кольцевых маршрутов (задача коммивояжера)

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

Теоретические сведения

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

Имеется n пунктов (городов), связанных между собой сетью дорог. Требуется выехать из одного пункта, объехать все остальные и вернуться в исходный. В каждый пункт можно заезжать только один раз, поэтому маршрут движения будет представлять собой замкнутый цикл без петель, т.е. транспортное средство должно двигаться по кольцевому маршруту. Последовательность объезда пунктов в маршруте, в принципе, может быть любой. Однако от этого зависит общая протяженность всего маршрута. Ясно, что последовательность объезда следует выбрать такой, чтобы суммарная длина всего кольцевого маршрута оказалась минимальной. Эта задача, имеющая важное прикладное значение, получила название "Задачи о коммивояжере" (коммивояжер – агент по сбыту). В теории оптимизации она относится к комбинаторным задачам дискретного (целочисленного) программирования. Например, для графа дорожной сети (рис. 1) существует огромное число кольцевых маршрутов с различными комбинациями последовательностей объезда пунктов.

Рис. 1. Граф дорожной сети

Число этих комбинаций легко подсчитать. Например, из пункта 1, в следующий пункт маршрута, в общем случае, можно выехать n-1 путями: 1–2, 1–3, …,1–i, …,1–(n-1), 1–n. Дальнейшее движение от любого пункта из (2, 3, …, n) к следующему пункту можно осуществить уже (n-2) способами. В итоге, два отрезка маршрута можно построить уже (n-1)(n-2) вариантами. Рассуждая аналогично, получим, что для дорожной сети, состоящей из n пунктов, общее количество кольцевых маршрутов будет равно (n-1)!=(n-1)(n-2)·…·3·2·1. Это число с ростом значения n быстро растет. Так при n=5 число возможных маршрутов (5-1)!=24, при n=8 получим (8-1)!=5040, а при n=10 (вполне возможное число пунктов в автомобильном кольцевом маршруте, например, при развозке хлебобулочных изделий), число вариантов будет (10-1)!=362880.

Построим сначала математическую модель задачи, обозначая:

где i, j = 1, 2, …, n; i ≠ j.

Требуется минимизировать

(1)

где c_ij –расстояние (время, стоимость перевозки) между пунктами i и j, при условиях

(2)

(3)

(4)

Здесь u_i и u_j – произвольные вещественные значения.

Условия (2) и (3) означают, что автомобиль из каждого пункта выезжает и въезжает в любой пункт только один раз; условие (4) – обеспечивает замкнутость маршрута, содержащего n пунктов, и отсутствие петель.

Для решения этой задачи разработаны различные приближенные и точные методы.

Рассмотрим наиболее простые из приближенных методов – метод, основанный на алгоритме пошаговой оптимизации и метод сумм.

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

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

Таблица 1

Построение маршрута осуществляется в следующей последовательности:

1. Отыскивается клетка с наименьшим значением расстояния (у нас это расстояние равно 8; оно определяет начальное звено машрута 6–7). Число в клетке обводится кружком.

2. В строке 6 и столбце 7, на пересечении которых расположена клетка с минимальным расстоянием, ищется

.

Клетка с этим расстоянием обводится кружком и соединяется с предыдущей клеткой стрелкой. В итоге получается фрагмент маршрута 5–6–7. Поскольку теперь пункт 6 оказался внутренним в маршруте строку 6 и столбец 6 мысленно вычеркиваем из таблицы.

3. Затем поиск клетки с минимальным расстоянием ведем в 5-ом и 7-ом столбцах таблицы. Эта клетка со значением 14 обводится кружком, соединяется с клеткой (6-7) стрелкой. В итоге маршрут движения удлинняется 5–6–7–8. Седьмой столбец и седьмую строку мысленно вычеркиваем.

4. Описанные выше действия повторяются до тех пор, пока не будет сформирован замкнутый контур (строится так, как ходит шахматная ладья), который окончательно дает полный кольцевой маршрут 5–6–7–8–4–3–2–1–9–5 с общим расстоянием равным 132. В данном случае полученное решение совпало с оптимальным.

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

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

Так в нашем примере выбор другой клетки со значением 14 в столбце 7 (пункт 3) и дальнейшее построение контура приведет к маршруту 5–6–7–3–2–1–9–8–4. Чтобы этот маршрут стал кольцевым, необходимо его дополнить звеном 4–5. Однако прямой дороги между этими пунктами не существует, а кратчайший маршрут между ними проходит через узел 3. Таким образом, получится маршрут 5–6–7–3–2–1–9–8–4–3–5, длина которого равна 144, а пункт 3 посещается 2 раза. В нашем случае можно избежать первого посещения пункта 3, так как между пунктами 7 и 2 имеется прямая дорога длиной 28. В итоге получится маршрут 5–6–7–2–1–9–8–4–3–5 длиной 148. Таким образом, несмотря на то, что в этом маршруте каждый пункт был посещен один раз, реально более выгодным на практике является предыдущий маршрут.

Метод сумм. Этот приближенный метод считается точнее метода пошаговой оптимизации, хотя в некоторых конкретных случаях его результаты могут оказаться даже худшими. Сущность метода рассмотрим на примере предыдущей задачи. В таблицу 2 поместим данные из таблицы 1. В пустые клетки (отсутствует прямая дорога между соответствующими пунктами) впишем большое по величине положительное число. В нашем случае достаточно, например, вписать число 100. Данный прием позволит "блокировать" эти клетки, так как маршруты с подобными расстояниями не будут оптимальными. В таблицу 2 добавим еще одну строку (последнюю), в клетки которой запишем суммы всех расстояний в каждом столбце, т.е.

Таблица 2

Номера пунктов	1	2	3	4	5	6	7	8	9
1		15	100	24	18	30	100	35	20
2	15		10	100	22	100	28	30	100
3	100	10		13	18	28	14	36	100
4	24	100	13		100	24	38	14	100
5	18	22	18	100		12	15	100	26
6	30	100	28	24	12		8	15	30
7	100	28	14	38	15	8		14	22
8	35	30	36	14	100	15	14		20
9	20	100	100	100	26	30	22	20
Итого	342	405	319	413	311	247	239	264	418

Дальнейшие вычисления ведут по следующей схеме:

1. В итоговой строке выбираются три максимальные суммы (S₉ =418; S₄ =413; S₂ =405), индексы которых (номера столбцов) дают три начальных пункта будущего кольцевого маршрута (9–4–2–9).

2. Определяется номер пункта k, вставка которого в строящийся маршрут приведет к наименьшему увеличению его длины. Номер этого пункта соответствует номеру столбца, в котором находится следующая по величине сумма расстояний (S₁ =342, т.е. k=1).

3. Находится место вставки пункта k между известными уже пунктами строящегося маршрута (в нашем случае между 9–4, 4–2 или 2–9), которое приведет к наименьшему удлиннению маршрута. С этой целью вычисляются значения специальной функции "выгоды":

где i и j – номера пунктов, между которыми вставляется пункт k;

– расстояния между соответствующими пунктами.

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

4. Наименьшая по величине функция "выгоды" (-65) определяет точку вставки пункта k (в нашем случае получилась точка вставки 2–9 и, соответственно, маршрут удлинился 9–4–2–1–9).

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

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

В нашем случае, в итоге, получился кольцевой маршрут 9–8–4–3–2–1–5–6–7–9, длина которого 132 является оптимальной. Однако сам маршрут отличается от маршрута с такой же длиной, но найденного методом пошаговой оптимизации.