МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
Лекція № 3. Задача коммивояжера
На контейнерную площадку под выгрузку прибыли вагон (вагоны) с контейнерами. Каждый контейнер (2, 3, 4, 5) должен быть выгружен в соответствующую секцию (6, 7, 8, 9).
Продолжительности пробегов крана приведены в табл. 1. Найти оптимальную очередность выгрузки, обеспечивающую минимальную продолжительность грузовых операций, если в начальный момент кран находится в состоянии 1.
| от \ до | ||||||||
| 0,5 | 0,5 | - | - | - | - | |||
| - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | - | ||
| - | - | - | - | - | - | 2,3 | - | |
| - | - | - | - | - | - | - | 2,5 | |
| - | 5,2 | 6,5 | - | - | - | - | ||
| 6,6 | - | - | - | - | - | |||
| 2,5 | - | 3,5 | - | - | - | - | ||
| 6,5 | 5,9 | 5,6 | - | - | - | - | - |
Ввиду того, что продолжительность операций выгрузки контейнеров одинакова для всех вариантов, то достаточно оптимизировать направление возврата крана за очередным контейнером после выгрузки предыдущего. В этом случае матрица прбегов будет выглядеть следующим образом.
| До От | (2®6) | (3®7) | (4®8) | (5®9) | |
| - | 5,5 | 2,8 | 3,5 | ||
| - | 11,2 | 8,3 | |||
| 11,6 | - | 7,3 | 6,5 | ||
| 7,5 | - | 6,0 | |||
| 11,5 | 11,9 | 7,9 | - |
Задача коммивояжера решается методом ветвей и границ. При этом перед очередной итерацией определяется верхняя граница решения В - т.е. лучшее решение которое мы знаем на данный момент. Выполняется направленный перебор вариантов на каждом шаге которого определяется нижняя граница решения Н - т.е. наименьшее возможное значение показателя при принятом на данном шаге порядке обхода вершин. Если на каком-то шаге нижняя граница превысит верхнюю, то от дальнейший перебор вариантов в данном прекращается и выполняется анализ альтернативных решений. Если получено допустимое решение, то изменяется верхняя граница и выполняется анализ альтернативных решений.
1) Составить произвольный план, например (1,6) (6,7) (7,8) (8,9) (9,1). Продолжительность возвратов крана а контейнерами составит 5,5+11,2+7,3+6,0+0=30. Полученный результат представляет собой верхнюю границу В=30.
2) Выполнить редукцию строк и столбцов матрицы. Для этого в каждой строке определяем минимальный элемент и вычитаем его со всех элементов строки. После этого та же операция повторяется со столбцами. (В данной таблице редукцию строк не выполняем т.к. каждая из них содержит ) 0.
| Ci | Ai | ||||||
| - | |||||||
| - | 5,2 | 5,5 | 5,5 | 5,2 | |||
| 6,1 | - | 4,5 | 3,0 | ||||
| - | 2,5 | 2,0 | |||||
| 5,9 | 5,1 | - | 5,1 | ||||
| Qj | 5,5 | 2,8 | 3,5 | 17,8 | |||
| Bj | 2,0 | 2,0 | 4,5 | 2,0 |
3) Добавить в маршрут одно ребро. Вероятнее всего в граф будет входить ребро, исключение которого максимально увеличит продолжительность выгрузки. Для определения этого ребра необходимо рассчитать штрафы Ai, Bj: в каждом строке найти нулевой элемент и определить ему альтернативу (т.е. минимальный элемент за исключением данного); эта же процедура повторяется и для столбцов.
Определяем значение нижней границы Н=5,5+6+2,8+3,5=17,8. Таким образом, продолжительность выгрузки не может быть меньше 17,8 мин. На дереве поиска рисуем вершину, на которой указываем нижнюю и верхнюю границы.
Определяем дополнительный пробег, вызываемый исключением ребра ij:
Фij = Ai + Bj
| Ф16=0+2=2 Ф17=0+2=2 Ф18=0+4,5=4,5 Ф19=0+2=2 | Ф61=5,2+0=5,2 Ф71=3+0=3 Ф81=2+0=2 Ф91=5,1+0=5,1 |
При исключении этого ребра нижняя граница составляет 17,8+5,2=23
Чтобы определить нижнюю границу решения в которое входит ребро 9.8 из матрицы необходимо исключить соответствующие строку и столбец.
| Ci | |||||
| - | |||||
| 6,1 | - | 4,5 | |||
| - | 2,5 | ||||
| 5,9 | 5,1 | - | 5,1 |
| Ci | Ai | |||||
| - | ||||||
| 3,1 | - | 1,5 | 1,5 | |||
| - | 0,5 | |||||
| 0,9 | 0,8 | - | 5,1 | 0,8 | ||
| Qj | 10,1 | |||||
| Bj | 0,9 |
Нижняя граница решения составляет 17,8+10,1=27,9
| Ф19=0+0=0 Ф17=0+0=0 Ф18=0+0=0 | Ф79=1,5+0=1,5 Ф86=0,9+0=0,9 Ф87=0+0=0 Ф98=0,8+0=0,8 |
| Ci | Ai | ||||
| - | |||||
| - | |||||
| 0,9 | - | 0,9 | |||
| Qj | |||||
| Bj | 0,9 |
| Ф17=0+0=0 Ф18=0+0=0 | Ф86=0+0=0 Ф87=0+0=0 Ф98=0+0,9=0,9 |
| - | ||
| - |
В результате получено новое решение 1-7-9-8-6-1. Продолжительность выгрузки составляет 27,9 мин.
Далее необходимо рассмотреть только ветвление ВСЕ - т.к. нижние границы остальных ветвлений выше новой верхней границы.
| Ci | ||||||
| - | ||||||
| - | - | 5,2 | 5,5 | 5,5 | 5,2 | |
| 6,1 | - | 4,5 | ||||
| - | 2,5 | |||||
| 5,9 | 5,1 | - |
| Ci | Ai | ||||||
| - | |||||||
| - | - | 0,3 | 5,2 | ||||
| 6,1 | - | 4,5 | |||||
| - | 2,5 | ||||||
| 5,9 | 5,1 | - | 5,1 | ||||
| Qj | 5,2 | ||||||
| Bj | 0,3 |
| Ф16=0+2=2 Ф17=0+0=0 Ф18=0+0=0 Ф19=0+0=0 | Ф67=0+0=0 Ф69=0+0=0 Ф71=3+0=3 Ф91=5,1+0=5,1 |
| Ci | |||||
| - | |||||
| - | 0,3 | ||||
| 6,1 | - | 4,5 | |||
| - | 2,5 |
| Ci | |||||
| - | |||||
| - | 0,3 | ||||
| 3,1 | - | 1,5 | |||
| - | 0,5 | ||||
| Qj |
Новая нижняя граница составляет 23+5=28, что больше верхней границы решения. Таким образом, лучшим порядком выгрузки контейнеров является следующий:
ДВНЗ «ПДАБА»