Транспортировка в цепях поставок

Индивидуальное задание для выполнения курсовой работы
1.Нанести на оси координат ОXY расположение пунктов транспортной сети
2.Определить расстояния между пунктами транспортной сети
3.Решить транспортную задачу методом Фогеля, определить общий пробег, пробег с грузом и транспортную работу для маятниковых маршрутов
4.Составить маршруты движения транспортных средств с помощью методов Свира (количество пунктов, включаемых в один маршрут не более пяти) и «ветвей и границ»
5.Оценить интервал времени прибытия и отправления транспортных средств для каждого пункта маршрутов. Сделать вывод о соответствии графиков доставки и режимов работы пунктов
6.Произвести выбор транспортных средств, определить затраты на транспортировку (учитывая, что затраты на топливо составляют 30%)
Выводы
Список литературы

Транспортировка в цепях поставок

 
9
8
7
Строка разности
3
2
4
3
4
4
3
3ый потребитель закреплен за А
Пункт погрузки
Пункт разгрузки
Столбец разности
1
2
 3
4
5
6
7
8
9
10
А
11
 
 
17
9
 
16
 
13
11
8
Б
8
 
 
13
6
 
12
 
9
8
7
Строка разности
3
4
3
4
4
3
Закрепляем 5го потребителя за Б.
Пункт погрузки
Пункт разгрузки
Столбец разности
1
2
 3
4
5
6
7
8
9
10
А
11
 
 
17
 
 
16
 
13
11
6
Б
8
 
 
13
 
 
12
 
9
8
5
Строка разности
3
4
4
4
3
Пункт 10 закрепим за Б.
Пункт погрузки
Пункт разгрузки
Столбец разности
1
2
 3
4
5
6
7
8
9
10
А
11
 
 
17
 
 
16
 
13
 
6
Б
8
 
 
13
 
 
12
 
9
 
5
Строка разности
3
4
4
4
Пункт 1 закрепим за Б.
Пункт погрузки
Пункт разгрузки
Столбец разности
1
2
 3
4
5
6
7
8
9
10
А
 
 
 
17
 
 
16
 
13
 
4
Б
 
 
 
13
 
 
12
 
9
 
4
Строка разности
4
4
4
Пункт 9 закрепим за Б.
Оставшиеся пункты 4 и 7 закрепим за А, чтобы выполнялось условие – по пять пунктов за каждым поставщиком.
Получаем искомое закрепление потребителей за поставщиками, которое приведено в табл. 4.
Таблица 4
Оптимальное закрепление пунктов разгрузки за поставщиками
Пункт
погрузки
Расстояние до пункта разгрузки, км
Итого
1
2
3
4
5
6
7
8
9
10
А
 
5
6
17
 
 
16
3
 
 
47
Б
8
 
 
 
6
2
 
 
9
8
33
Объем груза, т
4,78
3,75
2,49
5,03
3,71
1,54
5,35
3,04
1,06
 
По формулам (2) – (4) находим значения:
4. Составить маршруты движения транспортных средств с помощью методов Свира (количество пунктов, включаемых в один маршрут не более пяти) и «ветвей и границ»
Решение задачи коммивояжера, то есть определение оптимального порядка объезда пунктов развозочного маршрута, производится методом «ветвей и границ», который состоит из следующих этапов:
производится приведение матрицы кратчайших расстояний и определение нижней границы (x) для множества "все маршруты" (вершины дерева решений):
(5)
где hi, hj – константы приведения соответственно по строкам и столбцам.
hi = min( lij), i = 1, 2, …, n; (6)
lij' = lij – hi, i, j = 1, 2, …, n (7)
где lij' – элемент новой матрицы приведенной по строкам;
hj = min (lij'), j = 1, 2, …, n; (8)
lij'' = lij' – hj, I, j = 1, 2, …, n (9)
где lij'' – элемент новой матрицы после следующего приведения исходной матрицы по столбцам;
определяются оценки Qij для клеток с нулевыми элементами lij = 0 в новой матрице L':
при условии: k  j; s  i; k, s = 1, 2, …, n,
где l'ik – наименьшее значение элемента в строке i;
l''sj – наименьшее значение элемента в столбце j.
определяются пары (ks) с максимальной оценкой, то есть:
(10)
От начальной вершины "все решения" проводят ответвление вершин ks и с нижними границами:
(11)
где ks – маршруты подмножества, включающего пункты k и s;
- маршруты подмножества, не включающего пункты k и s.
из матрицы исключаются строка k и столбец s. Элементу, находящемуся на пересечении строки s и столбца k, присваивается значение бесконечности (), то есть накладывается запрет на его включение в маршрут или блокирование.
после блокировки операция приведения повторяется, но уже для новой матрицы L' с вычеркнутой строкой k и столбцом s и заблокированными необходимыми элементами lij. Для ветвления выбирают следующую вершину, имеющую наименьшую нижнюю границу, и так до получения матрицы размером два на два. В этой матрице пары, включенные в маршрут, определяются однозначно, и в результате формируется оптимальный развозочный маршрут.
Таблица 6
Матрица кратчайших расстояний для первого маршрута
(грузоотправитель А)
Пункты маршрута
А
2
3
4
7
8
А
 
5
6
17
16
3
2
5
 
10
14
11
3
3
6
10
 
18
19
7
4
17
14
18
 
8
14
7
16
11
19
8
 
13
8
3
3
7
14
13
 
В каждой строке выбираем минимальный элемент и по формуле 7 приводим матрицу к виду (табл.7)
Таблица 7
Матрица кратчайших расстояний, приведенная по строкам
Пункты маршрута
А
2
3
4
7
8
hij
А
2
3
14
13
3
2
2
7
11
8
3
3
4
15
16
4
6
4
9
6
15
5
11
8
7
8
3
16
5
10
8
8
4
11
10
3
Таблица 8
Матрица кратчайших расстояний, приведенная по столбцам
Пункты маршрута
А
2
3
4
7
8
А
2
9
8
2
4
6
3
3
2
10
11
4
7
4
12
7
7
6
1
13
6
8
1
6
5
hij
2
2
3
5
5
4
Нижняя граница, то есть минимально возможная длина маршрута, определяется по формуле (5) и равна:
= 31 + 21 = 52
Таким образом, получаем маршрут – А-2-3-4-7-8.
Рассчитаем аналогично маршрут Б.
Пункты маршрута
Б
1
5
6
9
10
hij
Б
 
8
6
2
9
8
2
1
8
 
3
8
13
1
1
5
6
3
 
5
10
2
2
6
2
8
5
 
7
8
2
9
9
13
10
7
 
13
7
10
8
1
2
8
13
 
1
Приведенная матрица по строкам:
Пункты маршрута
Б
1
5
6
9
10
hij
Б
6
4
7
2
1
7
1
6
11
1
5
1
3
8
2
6
6
3
5
6
2
9
2
6
8
5
11
7
10
6
11
1
Приведенная матрица по столбцам:
Пункты маршрута
Б
1
5
6
9
10
Б
6
2
1
3
6
5
3
6
5
2
9
5
7
5
10
3
6
hij
2
1
1
3
5
6
Нижняя граница, то есть минимально возможная длина маршрута, определяется по формуле (5) и равна:
= 14 + 18 =32
Получим маршрут: Б-6-5-1-10-9
Решим задачу методом ветвей и границ:
Маршрут А:
Пункты маршрута
А
2
3
4
7
8
А
 
5
6
17
16
3
2
5
 
10
14
11
3
3
6
10
 
18
19
7
4
17
14
18
 
8
14
7
16
11
19
8
 
13
8
3
3
7
14
13
 
Из пункта А можно доехать до пункта 2, расстояние минимальное.
Затем из пункта 2 по минимальному расстоянию можно доехать до пункта 3.
Из пункта 3 – в пункт 4, а из 4го – в 7. Из 7го – в 8ой. Длина маршрута составит 54 км.
Машрут Б:
Пункты маршрута
Б
1
5
6
9
10
Б
 
8
6
2
9
8
1
8