ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2014, том 50, № 3, с. 134-140
МЕТОДЫ ОПТИМИЗАЦИИ
ОСОБЕННОСТЬ ИСПОЛЬЗОВАНИЯ МЕТОДА ВЕТВЕЙ И ГРАНИЦ В ЗАДАЧЕ МАРШРУТИЗАЦИИ ПРИ НЕПОЛНОМ
Исследуется вырождение решений при использовании метода ветвей и границ для определения оптимальных маршрутов на неполных графах. Разработан усовершенствованный алгоритм, позволяющий получить точное решение. Приведены примеры.
Ключевые слова: граф, маршрут, алгоритм, вырождение.
Классификация JEL: С61.
Метод ветвей и границ (ВиГ) используется в учебных целях (Кожин, Мезенцев, 1994, с. 158) и в научных работах (Пожидаев, 2010, с. 17; Прокофьева, 2004, с. 66). Он считается точным методом определения оптимального кольцевого маршрута в полном графе, позволяющем решить задачу коммивояжера (Литл, Мурти, 1965, с. 94). Однако в неполном графе метод ВиГ может иметь вырождение решения.
В результате нашего исследования установлено, что вырождение решения заключается в образовании двух замкнутых независимых контуров или одного контура и ветви. Чтобы этого не происходило, требуется обеспечить вычеркивание, минимум, двух из всех существующих дуг, разделяющих полученный вырожденный контур с остальным множеством. Для этого необходимо после обнаружения вырождения решения изменить алгоритм метода ВиГ. Изменения алгоритма заключаются в том, что после получения приведенной матрицы из нее вычеркивается одна из разделяющих ветвей по выбору. После ее удаления алгоритм метода ветвей и границ остается прежним. Положение оптимальной дуги, разделяющей множества, устанавливается из сравнения всех возможных вариантов ее удаления.
Для подтверждения вырождения решения двух видов рассмотрим два примера. Далее покажем результат вычислений по усовершенствованному алгоритму против вырождения.
Пример 1. Исходный граф показан на рис. 1. Его матрица весов представлена в табл. 1. Решение, к которому приводит метод ВиГ, показано на рис. 2.
ТРАНСПОРТНОМ ГРАФЕ
© 2014 г. С.Ф. Подшивалов, К.С. Подшивалова
(Пенза)
Рис. 1. Исходный граф
Рис. 2. Схема вырождения в примере 1
Кратко остановимся на алгоритме решения задачи, приведенном в (Литл, Мурти, 1965, с. 94-107; Кожин, Мезенцев, 1994, с. 158).
Он заключается в следующем:
- приведение исходной матрицы путем нахождения и вычитания наименьшего элемента в каждой строке и столбце;
- оценка нулевого элемента по сумме наименьших весов, расположенных в строке и столбце на его пересечении;
- удаление — ветви множества с наибольшей оценкой;
- блокировка ]— ветви, а также ячейки, ведущей к зацикливанию в новой матрице меньшего размера.
В табл. 2 представлены результаты операции приведения исходной матрицы. Здесь в пустых клетках находятся очень большие числа. Справа от таблицы даны наименьшие числа в каждой строке. В низу ее указаны наименьшие приведенные веса в столбцах. Оценка нулевых элементов приведенной матрицы дана в табл. 3.
Таблица 1. Исходная матрица Таблица 2. Приведенная матрица
1 2 3 4 5 6
1 31 23 21 21
2 11 3 3 21
3 31 11 12
4 23 3 12
5 21 3 1
6 21 21 1
Таблица 3. Оценочная матрица
1 2 3 4 5 6
1 2 2 00 00
2 01 01 00 18
3 00 00 1
4 о0 00 1
5 00 2 00
6 00 20 00
1 2 3 4 5 6
1 2 2 0 0 21
2 0 0 0 18 3
3 0 0 1 11
4 0 0 1 3
5 0 2 0 1
6 0 20 0 1
20 8
Таблица 4. Матрица 1
1 2 4 5 6
1 2 0 21
3 0 1
4 0 0
5 0 2 0
6 0 20 0
В табл. 3 две ячейки 2-3 и 2-4 имеют одинаковую наибольшую оценку, равную 1, которая стоит в правом верхнем углу. В качестве примера рассмотрим вычеркивание ветви 2-3, строка и столбец которой выделены в оценочной матрице. Получаем матрицу 1 меньшей размерности (табл. 4), в которой блокируем звено 3-2 против зацикливания, согласно методу ветвей и границ.
Далее алгоритм расчета повторяется. В матрице 1 выполняется операция приведения для столбца с номером 4 и производится оценка полученных элементов. В результате получаем табл. 5, где вычеркиваем ячейку 4-2 с наибольшей оценкой 2.
136 ПОДШИВАЛОВ, ПОДШИВАЛОВА
Создаем новую матрицу меньшего размера, табл. 6, в которой блокируем ветвь 3-4 против зацикливания. Здесь же дана оценка ее элементов. Наибольшую оценку да имеют две ветви 1-4 и 3-1.
Таблица 5. Таблица 6.
Оценочная матрица 1 Оценочная матрица 2
1 2 4 5 6
1 1 00 00
3 00 01
4 о0 02
5 00 2 00
6 00 20 00
2
1 4 5 6
1 0да 00 00
3 0да
5 00 00
6 00 00
Вначале рассмотрим удаление ячейки 1-4 и получаем табл. 7, в которой должны заблокировать ветвь 3-1 против зацикливания согласно методу ВиГ. Тогда в ее строке с номером 3 будут располагаться очень большие числа и выход из узла 3 будет невозможен. Получаем вырождение решения. Если нарушить алгоритм решения и вычеркнуть ветвь 3-1, то образуется подцикл 1-4-2-3-1 и ветвь 5-6 (табл. 8, 9), не соединенные друг с другом.
Таблица 7.
Оценочная матрица 3
1 5 6
3
5 00 0да
6 00 0да
Таблица 8.
Оценочная матрица 4
Таблица 9.
Оценочная матрица 5
5 6
5 0да
6 0да
4 5 6
1 00 00
5 0да
6 0да
При рассмотрении всех остальных возможных вариантов вычеркивания ветвей, начиная с табл. 3, окончательный результат решения задачи не изменяется, а кольцевой маршрут пойдет в обратном направлении 1-3-2-4-1.
Таким образом, доказано вырождение решения метода ВиГ (см. рис. 2). В действительности гамильтонов контур существует, например 1-3-4-2-6-5-1.
Пример 2. Матрица весов дана в табл. 10. Исходный граф показан на рис. 3.
Таблица 10. Исходная матрица
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 3 1 5
2 3 11 7 9
3 11 3 13 5
4 3 4
5 1 11 12
6 5 7 11 6 9 10 16
7 9 13 6 3 5
8 5 4 3 8 8
9 12 9 6 9
10 10 6 11 9
11 16 5 8 11 1 2
12 8 1 5 7
13 9 3
14 9 3 3
15 2 5 3 3
16 7 3
Приведенная матрица по строкам и столбцам показана в табл. 11.
Таблица 11. Приведенная матрица
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 0 0 1
2 0 8 1 6
3 6 0 10 2
4 0 1
5 0 7 11
6 0 0 6 1 4 5 11
7 4 10 0 0 2
8 2 1 0 5 5
9 6 0 0 3
10 1 0 5 3
11 12 4 7 10 0 1
12 7 0 4 5
13 6 0
14 6 0 0
15 0 3 1 0
16 4 0
В табл. 12 представлена оценочная матрица 1, в которой две ветви 5-1 и 13-14 имеют наибольшую оценку 7. Далее необходимо рассмотреть все варианты удаления ветвей на дереве решений, аналогично - как в примере 1, до того момента, пока вырождение не станет очевидным.
138 ПОДШИВАЛОВ, ПОДШИВАЛОВА
Таблица 12. Оценочная матрица 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 00 06 1
2 01 8 1 6
3 6 03 10 2
4 03 1
5 07 7 11
6 00 00 6 1 4 5 11
7 4 10 00 01 2
8 2 1 02 5 5
9 6 00 05 3
10 1 05 5 3
11 12 4 7 10 04 1
12 7 04 4 5
13 6 07
14 6 03 00
15 00 3 1 05
16 4 04
Таблица 13. Приведенная матрица
1 3 4 5 6
1 2 2 0 0
2 0 0 0 18
3 0 1
4 0 1
6 0 0
Таблица 14. Оценочная матрица
1 3 4 5 6
1 2 2 00 018
2 01 01 18
3 01 1
4 01 1
6 00 00
В результате расчетов получаем вырождение, ведущее к появлению двух замкнутых контуров, которые показаны на рис. 3 жирными линиями. Однако гамильтонов контур существует и может быть представлен, например, маршрутом: 1-5-6-10-9-13-14-15-16-12-11-7-8-4-3-2-1.
В результате исследования установлено, что наличие вырождения, а также его вид зависят от структуры исходного графа и длины его ветвей.
Представим методику исключения вырождения решения на примере 1. Нарушаем алгоритм метода ВиГ и вычеркиваем в приведенной матрице одну из дуг, разделяющих подцикл и ветвь 5-6 (см. рис. 1): 1-5, 1-6, 5-2, 6-2. В качестве примера удаляем в табл. 2 звено 5-2 и получаем табл. 13. Блокируем дугу 2-5, а также производим в ней операции приведения и оценки. Новая оценочная матрица дана в табл. 14.
Далее в процессе решения удалены ветви 1-6, 6-5, 2-3, 3-4, 4-1. В результате получаем га-мильтонов контур: 1-6-5-2-3-4-1 весом 71 единица. Существует второй маршрут: 1-6-5-2-43-1 с таким же весом.
В примере 2 два контура вырождения разделены хордами: 5-9, 6-9, 6-10, 6-11, 7-11, 8-11,
8-12. Рассмотрим в качестве примера вычеркивание ветви 6-10 в приведенной матрице, представленной в табл. 11. Результат показан в табл. 15.
Далее алгоритм метода ВиГ сохраняется, и выполняются операции приведения и оценки в табл. 15. В процессе решения задачи последовательно вычеркиваются ветви: 6-10, 10-9, 13-14,
9-13, 14-15, 1-5, 16-12, 5-6, 15-16, 2-1, 12-11, 11-7, 3-2, 8-4, 4-3 и 7-8.
Таблица 15. Приведенная матрица 1
1 2 3 4 5 6 7 8 9 11 12 13 14 15 16
1 0 0 1
2 0 8 1 6
3 6 0 10 2
4 0 1
5 0 7 11
7 4 10 0 0 2
8 2 1 0 5 5
9 6 0 3
10 1 0 5 3
11 12 4 7 0 1
12 7 0 4 5
13 6 0
14 0 0
15 0 3 1 0
16 4 0
Получаем оптимальный маршрут 6-10-9-13-14-15-16-12-11-7-8-4-3-2-1-5-6, весом 83 единицы. Он представлен на рис. 4.
Следует отметить, что рассмотрение других вариантов вычеркивания дуг не дает улучшения результата. Рассмотренная методика является универсальной и может применяться во всех случаях вырождения решения.
Таким образом, доказана возможность существования вырождения решения в методе ВиГ. Предложена методика его исключения.
ПОДШИВАЛОВ, ПОДШИВАЛОВА СПИСОК ЛИТЕРАТУРЫ
Кожин А.П., Мезенцев В.Н. (1994). Математические методы планирования и управления грузовыми автомобильными перевозками. М.: Транспорт.
Пожидаев М.С. (2010). Алгоритмы решения задачи маршрутизации транспорта. Автореф. дис. ... канд. техн. наук. Томск.
Прокофьева О.С. (2
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.