Результат решения задачи развозки

№ п/п	Маршрут	Объем поставки, шт	Пробег, км
	0-12-3-8-5-0		33,9
	0-1-11-0		19,0
	0-9-4-0		16,0
	0-2-7-10-6-0		20,8
Итого		89,7

Методы расчета расстояний на сети

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

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

Результатом расчетов расстояний являются две матрицы – матрица расстояний и матрица указателей. Для разъяснения сущности и назначения второй матрицы рассмотрим следующий пример.

Пример

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

Представим, что схема транспортной сети – это карта, на которой в одном из пунктов располагается игральная фишка, например, в пункте A. Необходимо передвинуть фишку из пункта 1 в пункт 7. Поставим два вопроса:

1) Какой путь должна пройти фишка?

2) Какой маршрут для фишки является оптимальным?

Ответы на эти вопросы легко найти самостоятельно, поскольку сеть маленькая и решение определяется элементарным подсчетом. Однако для сетей больших размеров, в которых представлено 20, 30, 50, 100 и более пунктов решение уже не представляется таким легким. В этом случае и применяется матрица расстояний и матрица указателей, которые для рассматриваемого случая представлены в следующих таблицах 3.6 и 3.7.

Расстояние от пункта 1 до пункта 7 находится из матрицы расстояний – это ячейка, которая располагается на пересечении строки 1 и столбца 7. Расстояние это составляет 31 км.

Для поиска оптимального маршрута используется матрица указателей. Находим ячейку на пересечении строки 1 и столбца 7. В найденной ячейке указан пункт 3. Перемещаем фишку в пункт 3 и ставим новый вопрос: как добраться из пункта 3 в пункт 7? Находим ячейку на пересечении строки 3 и столбца 7, где указан новый пункт 8. Перемещаем фишку в пункт 8 и формулируем вопрос: как добраться из пункта 8 в пункт 7? На пересечении строки 8 и столбца 7 указан пункт 6. Перемещаем фишку в пункт 6. На пересечении строки 6 и столбца 7 стоит число 7. Перемещаем фишку в пункт 7. Оптимальный маршрут найден: 1 – 3 – 8 – 6 – 7.

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

d(1,7) = d(1,3) + d(3,8) + d(8,6) + d(6,7) = 9 + 7 + 8 + 7 = 31 км.

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

Задание

Используя рисунок, постарайтесь самостоятельно составить матрицу расстояний и указателей. Используйте для расчетов калькулятор. В конце сравните полученный Вами результат с данными матрицы расстояний и указателей, представленных в табл. 3.6 и 3.7.

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

Ÿ метод потенциалов,

Ÿ метод «мельницы».

Метод потенциалов

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

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

v(i) – значение потенциала i-ой вершины;

w(i) – значение указателя i-й вершины;

c(i,j) – длина звена, связующего i-ю и j-ю вершины.

На рисунке значение потенциала i-й вершины указывается над самой i-й вершиной, а радом в скобках обозначается значение указателя i-й вершины. Например, вершина 4: v(4) = 20, w(4) = 5. Значение длины связующего звена указывается рядом со звеном с добавлением знака «+», например, c(3,4) = 5.

1. Выберем в качестве начальной вершины – вершину 2. Начальной вершине присвоим следующие значения: v(2) = 0, w(2) = 2. Иными словами, начальная вершина обладает нулевым потенциалом и нулевым указателем.

2. Все вершины сети распределяем по уровням, как показано на рисунке … . Распределение производится следующим образом:

1) первый уровень включает в себя только одну начальную вершину;

2) второй уровень включает вершины, которые имеют связующие звенья с вершиной первого уровня, т.е. вершины 9, 1 и 5;

3) третий уровень включает вершины, которые имеют связующие звенья с вершинами второго уровня, т.е. вершины 3, 4 и 7;

4) четвертый уровень включает вершины, которые имеют связующие звенья с вершинами третьего уровня, т.е. вершины 8 и 6.

3. Вводим такие понятия, как ведущий и ведомый уровни:

Ÿ ведущий уровень – это последний по счету уровень, у которого определены значения потенциалов и указателей;

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

Множество вершин ведущего уровня будем обозначать множеством X, множество вершин ведомого уровня – множеством Y.

Определяем ведущий и ведомый уровни. На данном этапе расчетов ведущим является первый уровень, т.е. X = {2}, а ведомым, соответственно, второй уровень, т.е. Y = {1, 5, 9}.

4. Известно, что вершины ведомого уровня связаны с начальной вершиной. Длины связующих звеньев: c(2,9) = 8, c(2,1) = 7, c(2,5) = 13. Тогда определяем потенциалы и указатели вершин ведомого второго уровня по следующей схеме:

Ÿ v(j) = v(i) + c(i,j) = c(i,j), iÎX, jÎY

Ÿ w(j) = j, jÎY

В результате получаем:

1) вершина 9: v(9) = c(2,9) = 8, w(9) = 9;

2) вершина 1: v(1) = c(2,1) = 7, w(1) = 1;

3) вершина 5: v(5) = c(2,5) = 13, w(5) = 5.

5. Производим проверку на разность потенциалов вершин ведомого уровня. Находим вершины ведомого уровня, которые имеют между собой связующее звено. Такими вершинами на втором уровне являются вершины 1 и 9: c(1,9) = 5. Известно, что v(1) = 7 и v(9) = 8. Проверка разности потенциалов состоит в проверке выполнения следующего условия:

Ÿ v(i) – v(j) £ c(i,j), i,jÎY, v(i) ³ v(j),

то есть, применительно к вершинам 1 и 9:

Ÿ v(9) – v(1) £ c(1,9) ® 8 – 7 £ 5 (выполняется).

Поскольку условие выполняется, то объявляется, что проверка на разность потенциалов пройдена успешно. В этом случае никаких действий по пересчету значений потенциалов и указателей вершин 1 и 9 не производится.

6. После проверки на разность потенциалов переопределяем ведущий и ведомый уровни сети. Первый уровень теряет статус ведущего. Ведущим уровнем объявляется второй уровень, т.е. X = {9, 1, 5}, а ведомым уровнем, соответственно, третий уровень, т.е. Y = {3, 4, 7}.

7. Известна длина связующих звеньев между вершинами ведущего и ведомого уровней: c(9,3) = 8, c(1,3) = 9, c(5,4) = 7, c(5,7) = 12. Определяем потенциалы и указатели вершин ведомого третьего уровня по следующей схеме:

Ÿ v(j) = min{v(i) + c(i,j) | iÎX}, jÎY, т.е. путь к вершине j проводим через такую вершину i, которая обеспечивает вершине j минимальное значение потенциала;

Ÿ w(j) = w(i*) : v(i*) + c(i*,j) = min{v(i) + c(i,j) | iÎX}, i*ÎX, jÎY, т.е. указатель j-й вершины полагается равной указателю той i-й вершины ведущего уровня, которая обеспечивает j-й вершине минимальное значение потенциала.

Таким образом, получаем:

Ÿ вершина 3: v(3) = min{v(9)+c(9,3); v(1)+ c(1,3)} = min{8 + 8 = 16; 7 + 9 = 16} = 16, w(3) = w(9) = 9 или w(3) = w(1) = 1. В данном случае складывается ситуация, когда из пункта 2 в пункт 3 можно проехать либо через пункт 9, либо через пункт 1. И в том, и в другом случае длина пути будет одинаковая – 16 км. Поскольку все равно, через какой пункт добираться, то можно выбрать любой, например, w(3) = w(1) = 1;

Ÿ вершина 4: v(4) = v(5) + c(5,4) = 13 + 7 = 20, w(4) = w(5) = 5;

Ÿ вершина 7: v(7) = v(5) + c(5,7) = 13 + 12 = 25, w(7) = w(5) = 5.

8. Производим проверку на разность потенциалов вершин ведомого уровня. Между вершинами 3 и 4 существует связующее звено: c(3,4) = 5 при 3, 4ÎY. Известны потенциалы: v(3) = 16, v(4) = 20. Проверяем на выполнение условие:

Ÿ v(4) – v(3) £ c(3,4) ® 20 – 16 £ 5 (выполняется).

Проверка пройдена, никаких действий не производим.

9. После проверки на разность потенциалов переопределяем ведущий и ведомый уровни сети. Второй уровень теряет статус ведущего. Ведущим уровнем объявляется третий уровень, т.е. X = {3, 4, 7}, а ведомым уровнем, соответственно, четвертый уровень, т.е. Y = {8, 6}.

10. Известна длина связующих звеньев между вершинами ведущего и ведомого уровней: c(3,8) = 7, c(4,8) = 6, c(7,6) = 7. Определяем потенциалы и указатели вершин ведомого четвертого уровня по известной уже схеме:

Ÿ v(j) = min{v(i) + c(i,j) | iÎX}, jÎY;

Ÿ w(j) = w(i*) : v(i*) + c(i*,j) = min{v(i) + c(i,j) | iÎX}, i*ÎX, jÎY.

Таким образом, получаем:

Ÿ вершина 3: v(8) = min{v(3)+c(3,8); v(4)+ c(4,8)} = min{16 + 7 = 23; 20 + 6 = 26} = 23, w(8) = w(3) = 1. В данном случае минимальное значение потенциала вершины 8 обеспечивается при движении через вершину 3. Поэтому указатель вершины 8 полагается равным указателю вершины 3;

Ÿ вершина 6: v(6) = v(7) + c(7,6) = 25 + 7 = 32, w(6) = w(7) = 5.

11. Производим проверку на разность потенциалов вершин ведомого уровня. Между вершинами 8 и 6 существует связующее звено: c(8,6) = 8 при 8, 6ÎY. Известны потенциалы: v(8) = 23, v(6) = 32. Проверяем на выполнение условие:

Ÿ v(6) – v(8) £ c(6,8) ® 32 – 23 £ 8 (не выполняется).

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

Ÿ v(i) = v(j) + c(i,j) и

Ÿ w(i) = w(j).

Применительно к вершинам 6 и 8 получаем:

Ÿ вершина 6: v(6) = v(8) + c(8,6) = 23 + 8 = 31, w(6) = w(8) = 1.

Данные расчеты означают, что из пункта 2 в пункт 6 следует ехать через пункт 8, а не пункт 7, поскольку в первом случае длина пути составит 31 км против 32 км во втором случае.

12. Четвертый уровень является последним по счету, а потому цикл расчета можно считать завершенным. Полученные значения потенциалов и указателей заносим во вторую строку матрицы расстояний и матрицы указателей, как показано в таблице:

Таблица 3.8

Матрица	Вершины сети
Расстояний
Указателей

Полученные данные можно сравнить с данными второй строки матрицы расстояний и матрицы указателей ( табл. 3.6 и 3.7).

По окончании первого цикла расчета начинаются новые циклы, в которых в качестве начальной вершины выбираются вершины 1, 3, 4, …, 9.

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

Шаг 1. Определяется начальная вершина сети.

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

Ÿ вершины (k-1)-го уровня имели связующие звенья с вершинами k-го уровня;

Ÿ вершины k-го уровня имели связующие звенья с вершинами (k+1)-го уровня;

Ÿ вершины (k-1)-го уровня не имели связующих звеньев с вершинами (k+1)-го уровня.

Шаг 3. Первый уровень объявляется ведущим уровнем, а второй уровень – ведомым.

Шаг 4. Определяются значения потенциалов и указателей вершин ведомого уровня. Если ведомым является второй уровень сети, то значения определяются по формулам:

Ÿ v(j) = v(i) + c(i,j) = c(i,j), iÎX, jÎY

Ÿ w(j) = j, jÎY

где X – множество вершин ведущего уровня, Y – множество вершин ведомого уровня.

Если ведомым является третий, четвертый и остальные уровни сети, то значения определяются по формулам:

Ÿ v(j) = min{v(i) + c(i,j) | iÎX}, jÎY;

Ÿ w(j) = w(i*) : v(i*) + c(i*,j) = min{v(i) + c(i,j) | iÎX}, i*ÎX, jÎY.

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

Ÿ v(i) – v(j) £ c(i,j), i,jÎY, v(i) ³ v(j).

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

Ÿ v(i) = v(j) + c(i,j),

Ÿ w(i) = w(j).

Шаг 6.Переопределяются ведущий и ведомый уровни сети по следующей схеме:

Ÿ ведущий уровень теряет статус ведущего уровня;

Ÿ ведомый уровень теряет статус ведомого и становится ведущим уровнем;

Ÿ уровень, следующий за ведомым, приобретает новый статус ведомого уровня.

Шаг 7. Повторять шаги 4–6 до тех пор, пока в ходе очередного повторения на шаге 6 не обнаружится, что ведомый уровень является последним уровнем сети.

Шаг 8. Полученные значения потенциалов и указателей занести в соответствующую строку матрицы расстояний и матрицы указателей с номером, равным номеру начальной вершины.

Шаг 9. Повторять шаги1–8, поочередно выбирая в качестве начальной все вершины сети, до тех пор, пока все строки матрицы расстояний и матрицы указателей не будут заполнены соответствующими значениями.

Метод «мельницы»

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

Шаг 0. Определяются значения матрицы расстояний D = [d_ij] и матрицы указателей L = [l_ij]. Если d_ij>0, то l_ij=j, i¹j.

Шаг 1. Выбираются пара вершин данной сети (i, j), i¹j.

Шаг 2. Выбирается вершина k данной сети, k¹i, k¹j.

Шаг 3. Если значение d(i,j) не определено, а значения d(i,k) и d(k,j) определены, или если определены все три значения d(i,j), d(i,k), d(k,j), но при этом выполняется условие d(i,j)>d(i,k)+d(k,j), то d(i,j):=d(i,k)+d(k,j), l_ij=l_ik.

Шаг 4. Повторять шаги 2-3 до тех пор, пока не будут перебраны все вершины k данной сети.

Шаг 5. Повторять шаги 1-4 до тех пор, пока не будут перебраны все пары вершин (i,j) данной сети.

Шаг 6. Процесс решения (цикл) повторяется до тех пор, пока в ходе очередного решения не будет изменено ни одно значение d(i,j).

% Вопросы для проверки знаний

1. Дайте своими словами определение задачи развозки

2. Опишите, что такое радиальный и кольцевой маршруты

3. В чем заключаются основные особенности метода Кларка-Райта?

4. Каким целям служат матрица расстояний и матрица указателей?

O Задачи для самостоятельного решения

Задача 3.1. Задача развозки

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

Вариант 1	Вариант 2	Вариант 3
№ п/п	Координаты	Объем заказа, шт	№ п/п	Координаты	Объем заказа, шт	№ п/п	Координаты	Объем заказа, шт
X	Y	X	Y	X	Y