9.4. Постановка и
практическое применение задачи выбора оптимального маршрута
9.4.1. Сфера практической применимости задач
маршрутизации
В качестве примера
математической модели задачи принятия решения,
целесообразно рассмотреть постановку одной из самых распространенных
оптимизационных задач - задачи маршрутизации. Основной базовой моделью задач
маршрутизации можно вполне обосновано считать задачу о коммивояжере, ставшей
известной в отечественной литературе в 1960-1970 годах как задача о бродячем
торговце. Ее некоторая универсальность связана с необходимостью определения
оптимальных в некотором смысле маршрутов для нескольких коммивояжеров.
Первоначально задача
коммивояжера была сформулирована для сферы маркетинга. Позднее она нашла
применение в других областях управленческой деятельности, особенно там, где
имела место значительная территориальная рассредоточенность
объектов на местности. Примерами практического использования данного класса
задач может служить определение оптимальных маршрутов:
-
обслуживания
территориально рассредоточенных технических объектов в газовой и нефтяной промышленности;
-
облета
экспедиций и сброса соответствующих грузов;
-
обслуживания
технических объектов военного назначения;
-
поражения
боевыми блоками точечных целей вероятных противников и другие.
Значительное место
принадлежит задачам маршрутизации в деятельности правоохранительных органов.
Так по сути своей подразделения милиции общественной безопасности (МОБ) при
выполнении целого ряда служебных задач связаны с посещением отдельных граждан
по месту их жительства (деятельность участкового инспектора). Кроме того,
оптимизация маршрутов патрульной службы всецело определяет эффективность такой
службы на каждом из участков, поскольку оптимизируется продолжительность переходов
(переездов) между узловыми точками маршрута. Существуют и другие области применения
данного класса задач.
9.4.2. Постановка задачи маршрутизации
Постановка задачи. Пусть M - множество населенных пунктов,
необходимых для посещения коммивояжерами, m - их численность. Множество и
численность коммивояжеров H и h соответственно. Кроме того, можно считать известной
инфраструктуру рассредоточения населенных пунктов, представленной в виде
матрицы L=½ lij½, i=
, j=
. При
этом i=0 - пункт дислокации коммивояжеров
(пункт начала движения). Требуется оптимальным образом разбить M на подмножества Ml и в каждом из них определить оптимальную перестановку Ul элементов Ml, l=
, ml - численность Ml, M1
M2...Ml...=M, åml=m. Другими словами, из множества
населенных пунктов каждому коммивояжеру необходимо определить перечень населенных
пунктов и оптимальный маршрут их посещения. В такой модели может быть принято
множество ограничений и допущений, связанных с наличием и видами транспортных
средств, с общим видом матрицы L, с учетом возврата коммивояжеров в исходный пункт и другие.
В общем случае, точное
решение этой задачи зависит от ее размерности, определяемой, прежде всего,
величиной m и некоторыми вспомогательными возможностями, связанными, прежде всего, с
эффективностью разработанных алгоритмов и ЭВТ.
9.4.3. Построение
математической модели
Рассмотрим задачу, когда
множество исполнителей H состоит из одного элемента h=1 (один коммивояжер). Назовем такую
задачу частной.
Пусть дано количество
вершин графа равное числу m и дана матрица T=½tij½ (i=0,1,...,m;
j=1,2,...,m), представленная в виде выражения (9.1):
1 2
3 ... m
0 t01 t02 t03
... t0m
T = 1 - t12 t13 ... t1m . (9.1)
2 t21
- t23
... t2m
3 t31 t32
- ...
t3m
. .
. .
m
tm1 tm2 tm3
... -
Среди множества маршрутов
= (i0,i1,i2,...,ik,...,im),
где k - номер места в перестановке , k= 1,2,...,m,
iÎ M,
где M - множество номеров вершин в перестановке необходимо найти
кратчайший маршрут, проходящий через все вершины
®min,
(9.2)
где =
, jk=ik+1.
(9.3)
Целевой функцией в данном
случае является вполне обоснованно общая протяженность маршрута , находящаяся в простой аналитической зависимости с общей продолжительностью
процесса. В последнем случае очень важно учитывать еще одну составляющую tj - продолжительность работ в пункте j. Тогда выражение для примет вид
=
. (9.4)
Приведенная задача
относится к обширному классу задач дискретной оптимизации комбинаторного типа. Для ее решения могут быть использованы ряд математических методов.
9.4.4. Методы решения
задачи маршрутизации
Метод исчерпывающего перебора. Общая идея метода исчерпывающего
перебора состоит в том, что при заданном количестве вершин равному числу m проверяется все множество
перестановок (вариантов маршрутов) равное s=m!.
= (i0,
i1,
i2,...,
im).
При этом существует
несколько способов построения множеств вариантов решения.
Алгоритм исчерпывающего перебора
1.
Строится
первоначальная перестановка (причем все ее
элементы упорядочены по возрастанию) и определяется 
;
2.
Определяется
обрывающее число e: просматриваются с конца элементы перестановки и находится первое
число, удовлетворяющее условию
ik-1<ik ( e=ik-1);
3.
В
D (D= (ik, ik+1,...,im)) находится минимальный элемент больший числа
e, т. е. min ik>e. Эти элементы меняются местами;
4.
Все элементы D упорядочиваются по возрастанию;
5.
Определяется 
р), p=2,3,...,m!
, и если р)< р-1), то это значение берется за оптимальное и
алгоритм повторяется с пункта 2;
6.
Алгоритм
заканчивается, когда во вновь исследуемой отсутствует e.
7.
Выход
из алгоритма.
Графический метод. Идея метода заключается в том, что все множество решений на l шаге делится на m-l подмножеств. Затем просматривается
каждая ветка, т. е. находится , и если найденное решение меньше предыдущего, то это решение
берется за оптимальное и просматривается следующая
ветка. И так до конца.
Вместе с тем, при m>4 графический способ весьма
трудоемок. Приведем один из уже известных методов построения всего множества
вариантов.
Метод ветвей и границ.
Суть метода ветвей и границ состоит:
В
разбиении всего множества вариантов решения на подмножества (ветвление);
В
оценке значений границ каждого из исследуемых подмножеств и выборе стратегии
последующего ветвления.
Характерной особенностью
метода ветвей и границ является использование приближенного решения задачи для
отсечения бесперспективных вариантов путем оценки границы решения. Дальнейшее
развитие этой идеи привело к комплексному применению методов динамического
программирования и ветвей границ. Ниже представлен один из алгоритмов, построенных
на основе метода ветвей и границ.
1.
Обнуление
шага U=0;
2.
На U шаге множество маршрутов разбивается
на m-U подмножеств (U=0,1,2,...,m-1);
3.
Определяется
нижняя граница каждого из подмножеств g=
,
где jk=ik+1 , k - номер места в перестановке ;
4.
Из
нижних границ выбирается минимальная min gl
(l=
);
5.
Если уже определена,
т. е. проход алгоритма осуществляется не в первый раз, и если выполняется условие
gl>:
5.1. из перестановки 
удаляется последний
элемент iU;
5.2. U уменьшается на 1;
5.3.
на U шаге ищется
нижняя граница, удовлетворяющая условию
gl<. Если
такая граница не найдена, то переход на подпункт 5.1.
5.4.
если в дереве решений нет ветвей, удовлетворяющих условию gl<, то
осуществляется выход из алгоритма (п.7), т. к. найдено оптимальное решение , в
противном случае:
5.5. в перестановку заносится новый
элемент iU+1;
5.6. U увеличивается на 1;
5.7. осуществляется переход на пункт 2, т. е. ветвится
подмножество с номером iU+1;
6.
На m-1 шаге определяется 
y(). Если q() (q=
) не
было ранее определено или y()<q(), т. е. новое значение меньше предыдущего, то это значение
берется за оптимальное и осуществляется переход на подпункт 5.1.
7.
Выход из алгоритма.
Метод ближайшей точки. Этот метод относится к приближенным
методам решения задач. Суть его заключается в том, что оптимальное решение
находится путем выбора кратчайшего расстояния от каждой точки до оставшихся
точек, при условии, что один и тот же узел не может быть выбран дважды. Этапы
реализации метода следующие:
1. Обнуление переменной l=0 и шага U=0 (l=; U=);
2. На U шаге среди элементов матрицы T=½ tij½ в строке с номером l находится минимальный min tij,
который удовлетворяет условию jÏD, D= ( i0, i1,...,iU));
3. В D заносится новый элемент iU+1=j;
4. U увеличивается на 1;
5. Переменной l присваивается номер столбца j, в котором находится min tij,
l=j
и осуществляется переход на пункт 2;
6. Находится ;
7. Выход из алгоритма.
Предыдущая | Главная | Глава 9 | Следующая