Транспортная логистика. (Тема 6)

1. Тема 6. Транспортная логистика

Презентация подготовлена
преподавателем кафедры
«Прикладной математики»
Тесёлкиной Е.С.

2.

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

3.

Задачи ТЛ решаются во взаимной связи с
другими задачами логистики, такими, как
производственная логистика (ПС),
складская логистика, логистика запасов,
сбытовая логистика, информационная
логистика.

4. «Задача коммивояжера»

5. Постановка задачи

Имеется n городов, пронумерованных
числами 1,2,..., n.
Для любой пары городов (i,j) задано
расстояние (время, путевые расходы)
C(i,j) 0 между ними.
В общем случае C(i,j) C(j,i), причём
С(i,i) = .
Иногда С(i,j) = при i j, если переезд
от города i до города j невозможен или
очень дорог.

6. Постановка задачи

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

7.

Другая интерпретация этой задачи связана
с минимизацией времени переналадок при
обработке на одном станке партии из n
различных деталей.
Здесь C(i, j) – время переналадки при
переходе от обработки детали i к
обработке детали j. Требуется найти
последовательность обработки деталей,
минимизирующую общее время
переналадок.

8.

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

9. Гамильтонов цикл

Замкнутый маршрут (i1, i2,…,in, i1),
проходящий, через каждый город один и
только один раз, т.е. набор переездов (дуг)
(i1,i2), (i2,i3), …, (in-1,in), (in,i1)
называется гамильтоновым циклом или
просто циклом, маршрутом коммивояжёра
и обозначается через
х = (i1,i2), (i2,i3), …, (in-1,in), (in,i1) .

10.

Через Т обозначим множество всех
гамильтоновых циклов, а через F(x) –
издержки цикла Х.
Необходимо отыскать такой маршрут
х* , что
F(x*) = min F(x) .
x T

11.

Для записи постановки задачи в терминах ЗЦЛП
(задачи целочисленного линейного
программирования) определим переменные
следующим образом:
хij= 1, если коммивояжер переезжает и i-го города
в j-й;
хij=0, в противном случае.
Тогда задача заключается в отыскании значений
переменных , удовлетворяющих следующим
соотношениям:
n
n
c
i 1 j 1
ij
xij min
(1)

12.

при условиях
n
x
i 1
n
x
j 1
ij
ij
1,
j 1, n (въезд в город j);
1, i 1, n (выезд из города i);
ui u j (n 1) xij n 2, i j,
(2)
(3)
j,i =2, ...,n;
(4)
xij = {0,1}, u i 0, целые, i =1, ...,n, j =1, ...,n.
(5)
Ограничения (4) требуют, чтобы маршрут
образовывал контур, т.е. служат для устранения
нескольких не связанных между собой маршрутов
и циклов.

13.

Пример, когда маршрут распадается на два
не связанных между собой подцикла
2
1
3
4
6
5
7

14. Решение

Решение описанной выше математической
модели можно реализовать с помощью
надстройки «Поиск решения» в Excel (см.
пример «6_Задача коммивояжера.xlsx»).
Кроме того задача может быть решена
методом ветвей и границ.
Выбирайте любой удобный для вас
способ.

15. Применение метода ветвей и границ для решения задачи коммивояжера

Применение метода
ветвей и границ для
решения
задачи
Допустимый маршрут
х представим как
множество упорядоченных пар городов:
коммивояжера
x (i , i ), (i , i ), , (i , i ), (i , i ) .
1
2
2
3
n -1
n
n
1
Длина F(х) маршрута х равна сумме
соответствующих элементов C(i,j). Заметим, что
множество всех допустимых маршрутов X
содержит (n-1)! элементов.
Обозначим через C (C ij ) n nматрицу расстояний.
Чтобы запретить переезды вида (i,i) положим
С(i,i) = +∞ (i = 1,…, n).

16.

Обозначим через Z0 = F(x0) верхнюю
границу длин всех маршрутов, т.е.
F(x*) Z0 ,
где x* - оптимальный гамильтонов цикл
(маршрут).
Определить F(x0) можно, отыскав какойлибо произвольный допустимый маршрут
коммивояжёра и подсчитав его издержки.
Например, допустимым будет являться
следующий гамильтонов цикл
x0= (1,2); (2,3); (3,4); ((4,5); (5,1) .

17.

Пусть
Pi min C ij ,
j (1, n),
Q j min C ij Pi , i (1, n );
C ij C ij Pi Q j
Тогда
Пусть
C (C ij ) n n – редуцированная матрица.
n
n
i 1
j 1
d ( x) Pi Q j – сумма констант
редуцирования.

18.

Тогда для любого маршрута
x (i1 i2 ), (i2 i3 ), , (in 1 in ), (in i1 ) X
справедливо
F ( x) C (i1 , i2 ) C (i2 , i3 ) ... C (in , i1 ) =
= C (i1 , i2 ) C (i2 , i3 ) ... C (in , i1 ) d(x) ≥ d(х)
Это неравенство показывает, что в качестве
нижней оценки издержек любого цикла х
на множестве Т можно взять суммарную
константу приведения d(х) матрицы С.

19. Ветвление

Процесс ветвления можно представить в виде
дерева, каждая вершина которого соответствует
некоторому множеству маршрутов, являющемуся
подмножеством множества Х. При этом
начальная вершина соответствует множеству
всех маршрутов Х.
На каждом шаге из числа кандидатов на
ветвление выбирается множество Х1 с
наименьшей оценкой.
Оно
разветвляется на два
1
1
подмножества X 1 и X 2. Подмножество состоит
из всех маршрутов множества Х1 содержащих
некоторую выбранную на данном шаге дугу (r, s),
подмножество , – из всех маршрутов множества
Х1, не содержащих дуги (r,s).

20.

Ребро дерева, соединяющее вершины Х1 и X 11,
помечается (r,s), а ребро дерева, соединяющее
1
Х1 и X 2 помечается ( r , s ).

21.

Ясно, что для разбиения лучше выбирать множество с
минимальной нижней оценкой, так как вероятнее всего
именно в нём содержится оптимальный цикл х*.
Дугу (r,s) будем выбирать из следующих соображений:
С одной стороны, издержка с rs должна быть как можно
меньше, чтобы в конце концов из всех фиксированных
дуг получить гамильтонов цикл, близкий к оптимальному.
С другой стороны, будем максимально увеличивать
нижнюю оценку d(y) множества 1, тогда возрастает
X 2 всякий раз будет
вероятность того, что для разбиения
выбираться множество
, и появится возможность
1
X1
быстрее получить гамильтонов
цикл.
Если при этом окажется, что его издержки меньше z 0, то
z0 будет скорректирована (уменьшена), а это сократит
число просматриваемых циклов.

22.

Кроме того, такой подход к выбору дуги (r,s)
позволяет сократить объём хранимой в памяти
информации, а именно, необходимо иметь
исходную матрицу издержек С(Т), рабочую
матрицу C ( X 21 ) и информацию о каждом
множестве: его нижнюю оценку издержек и все
фиксированные и запрещённые для него дуги.
Если в процессе решения задачи нужно будет
1
X
разбивать множество, отличное от
2 , то
соответствующую ему матрицу издержек можно
восстановить их исходной матрицы С(Т) на
основании этой информации.

23. Выбор фиксированного переезда (r,s):

1)
в приведенной
матрице издержек С (Xi)
2)
просмотреть все элементы c ij =0; (стремление к
1
d
(
X
уменьшению
1 ))
для каждого из них определить величину ij,
равного сумме минимального элемента i-той
строки и j-го столбца, за исключением самого
элемента c ij;
( , ) min C ( , ) min С ( , ) ,
1
:
1
:
где (m,v) – дуга, для которой c ij =0.

24.

3)
выбрать фиксированный переезд (r,s) из
условия
(r , s )
max
1
( , ) .
, :C ( , ) 0
1
d
(
X
(стремление увеличить
2 ) ).
Смысл введения функции
состоит в том, что
величина ( , ) является оценкой снизу для
длины любого маршрута из Х1, не содержащего
дуги ( , ), так как величина ( , ) выражает
дополнительное расстояние, которое
коммивояжер проезжает в случае, когда в
маршрут не включена дуга ( , ).

25. Построение редуцированных матриц и и вычисление оценок снизу

1
С
Построение редуцированных 1
1
С2
матриц
и
и
вычисление оценок снизу
Рассмотрим , как на произвольной итерации
1
1
С
С
получить матрицы 1 и 2 , если
известны матрица С 1 и дуга (r,s).

26. Схема получения матрицы

1
Схема получения матрицы
С2
Так как дуга (r,s) не должна входить ни в один
гамильтонов
цикл, принадлежащий
множеству
1
1
X 2, то в матрице С полагаем с rs= .
1
C
(i, j ), (i, j ) (r , s ),
1
С 2 (i, j )
(i, j ) (r , s ).
1
2.
1
2,
Приводим матрицу С получим С
Сумма констант редуцирования равна при этом
(r , s) .
1
Нижняя граница издержек для множества X 2
определится по формуле
d ( X ) d ( X ) (r , s)
1
2
1

27. Схема получения матрицы

1
1
С
Схема получения матрицы
Так как дуга (r,s) уже входит в любой
гамильтонов
цикл, принадлежащий множеству
1
X 1 , то согласно постановке задачи необходимо
запретить выезд из города
r и въезд в город s,
1
поэтому в матрице С вычеркиваем строку r и
столбец s.
Для устранения подциклов необходимо
составить из всех
дуг, фиксированных для
1
множества X 1, связный путь, обязательно
содержащий последнюю фиксированную дугу
(r,s).
1
1
С
Полагаем С1 (t , m) в матрице , где t и
m – соответственно конец и начало связного
пути, в результате получим матрицу С11 .

28.

1
С
Редуцированная матрица расстояний 1для
1
X 11
вершины
получается
из матрицы
сС1
помощью операции редуцирования.
Обозначим через константу приведения
1
(редуцирования) матрицы С1 .
Оценка снизу для функции F(x) на
1
множестве X 1 вычисляется по формуле
d ( X ) d ( X )
1
1
1

29. Формирование списка кандидатов на ветвление (ответа)

Формирование списка
кандидатов на ветвление
1
d
(
X
После вычисления каждой
из
оценок
(i = 1,2)
i )
(ответа)
1
следует проверить, не состоит ли множество X
из
i
единственного маршрута:
если в каждой строке и в каждом столбце матрицы
оказалось
С i1 лишь по одному элементу,
1
отличному от + , то множество содержит X i
единственный маршрут, длина которого равна
. В этом случаеd верхняя
граница (наименьшее из
( X i1 )
уже вычисленных значений F(x) полагается равной
минимуму из предыдущего значения Z0 и
,
1
т.е.
d(Xi )
Z0 = min {Z0,
}.
d ( X i1 )

30. иначе…

Если X i1 содержит более одного маршрута
и d ( X i1 ) меньше текущего значения Z0, то
рассматриваемое множество включается в
число кандидатов на ветвление.
(продолжаем по описанной схеме)
Остановка производится, если
наименьшая из оценок снизу кандидатов
на ветвление не меньше (равна либо
превышает) текущего значения Z0.

31. Решить методом ветвей и границ задачу коммивояжера с матрицей

Решить методом ветвей и
границ задачу
коммивояжера с
10 25 25 10
матрицей
1 10 15 2
C 8 9 20 10
14 10 24 15
10 8 25 27

32. Редуцирование

10 25 25 10 10
1 10 15 2 1 0
C 8 9 20 10 8 0
14 10 24 15 10 4
10 8 25 27 8 2
0
0 15 15 0
9 14 1
1 12 2
0 14 5
0 17 19
0
9
12 0
0 6 3 0
0 0 2 1
0 1 0 2
4 0 5 5
2 0 8 7
C

33. Дерево решений