1] Введение [1

Будь умным!

1] Введение [1

Оглавление

1. Характеристика расположения пунктов транспортной сети на оси координат ОXY

2. Определение расстояний между пунктами транспортной сети

3. Решение транспортной задачи методом Фогеля, определение общего пробега, пробега с грузом и транспортной работы для маятниковых маршрутов.

4. Формирование маршрутов движения транспортных средств с помощью методов Свира и «ветвей и границ»

5. Определение интервалов времени прибытия и отправления транспортных средств для каждого пункта маршрутов

6. Определение затрат на транспортировку для выбранного транспортного средства

Выводы.

Список литературы

Введение

1. Характеристика расположения пунктов транспортной сети на оси координат ОXY

2. Определение расстояний между пунктами транспортной сети

3. Решение транспортной задачи методом Фогеля, определение общего пробега, пробега с грузом и транспортной работы для маятниковых маршрутов.

4. Формирование маршрутов движения транспортных средств с помощью методов Свира и «ветвей и границ»

5. Определение интервалов времени прибытия и отправления транспортных средств для каждого пункта маршрутов

6. Определение затрат на транспортировку для выбранного транспортного средства

Выводы.

Список литературы

Работа добавлена на сайт samzan.net:

Курсовая работа по дисциплине

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

Целью выполнения курсовой работы является закрепление знаний, полученных при изучении дисциплины, и приобретение навыков решения задач по формированию маршрутов доставки груза при внутригородских перевозках на основе принципов «точно во время» и «от двери до двери», а так же в оценке времени доставки груза на основании статистических закономерностей и расчете основной статьи себестоимости – затрат на топливо.

Курсовая работа заключается в решении задач транспортной логистики с использованием экономико-математических методов на основе заданной мощности грузоотправителей и потребности грузополучателей.

В данной курсовой работе для решения индивидуального задания были использованы следующие методы:

1. Метод Фогеля

2. Метод Свира

3. Метод «Ветвей и Границ»

А также был использован ряд формул для расчета расстояний между пунктами транспортной сети, оценки интервалов времени прибытия и отправления транспортных средств, а также для определения затрат на транспортировку.

Для наглядного представления расположения пунктов погрузки и разгрузки в выбранном масштабе построим систему координат ОXY и отметим на ней грузоотправителей и грузополучателей.

На данном графике (Рис.1) каждой точке соответствует положение пункта транспортной сети с указанием буквенного обозначения пунктов погрузки и числового пунктов разгрузки.

Рисунок 1. Пункты погрузки и разгрузки

Расстояние между двумя пунктами определяется по формуле, округляя получаемое значение до целого:

где xi (yi), xj (yj) – координаты i-го и j-го пунктов транспортной сети в декартовой системе координат соответственно.

Формула (1) эффективно применяется для определения расстояний между пунктами в условиях густо разветвленной транспортной сети, то есть в крупных городах и экономически развитых районах, в этом случае погрешность в расчетах будет минимальной.

Результаты расчета расстояний между пунктами представлены в таблице

Таблица 2.1

Расстояния между пунктами транспортной сети

	А	Б	1	2	3	4	5	6	7	8	9	10
А		17	14	20	9	14	15	20	8	10	15	8
Б	17		4	10	9	3	6	12	9	20	2	12
1	14	4		9	6	2	3	10	6	16	3	9
2	20	10	9		11	11	6	2	12	17	11	12
3	9	9	6	11		6	6	12	1	11	8	3
4	14	3	2	11	6		5	13	6	17	1	9
5	15	6	3	6	6	5		7	7	15	6	8
6	20	12	10	2	12	13	7		13	16	13	13
7	8	9	6	12	1	6	7	13		11	8	3
8	10	20	16	17	11	17	15	16	11		19	8
9	15	2	3	11	8	1	6	13	8	19		11
10	8	12	9	12	3	9	8	13	3	8	11

Метод Фогеля позволяет без использования компьютера получить оптимальный или близкий к нему результат. Решение проводится по следующему алгоритму:

- исходная матрица дополняется столбцом и строкой. Затем в каждой строке и каждом столбце матрицы находятся два наименьших элемента, и определяется абсолютная разность между ними, которая заносится соответственно разности по строке в столбец разностей, разности по столбцам – в строку разностей. Если две клетки в одной и той же строке или столбце имеют одинаковые значения, то разность для этой строки или столбца принимается равной нулю.

- выбирается наибольшая величина разности независимо от того, стоит ли она в столбце или строке разностей. В клетку с минимальным элементом в данной строке или столбце заносится максимально возможная загрузка, учитывая при этом соотношение ресурсов поставщика и спрос потребителя. Если окажется, что спрос потребителя полностью удовлетворен или ресурс поставщика полностью исчерпан, то данная строка или столбец матрицы из дальнейшего рассмотрения исключается.

- после заполнения и последующего исключения клетки матрицы разности пересчитываются, и операция повторяется вновь до тех пор, пока не будет составлен допустимый план закрепления потребителей за поставщиками.

Пробег с грузом (Lг), общий пробег (Lо) и транспортная работа (Р) для маятниковых маршрутов определяются по формулам:

где n, k – количество пунктов, закрепленных за грузоотправителями А и Б соответственно;

liA, ljБ – расстояние от соответствующего грузоотправителя до i-ого и j-ого грузополучателя, км;

- масса груза, перевозимая i-ому и j-ому грузополучателю соответственно, т.

Таблица 3.1

Расстояния между пунктами транспортной сети

	Расстояние до пункта разгрузки, км
	1	2	3	4	5	6	7	8	9	10
А	14	20	9	14	15	20	8	10	15	8
Б	4	10	9	3	6	12	9	20	2	12

Дополним таблицу кратчайших расстояний строкой и столбцом разностей.

Таблица 3.2

Исходная матрица для метода Фогеля

Пункты транспортной сети	1	2	3	4	5	6	7	8	9	10	Раз-ность
А	14	20	9	14	15	20	8	10	15	8	0
Б	4	10	9	3	6	12	9	20	2	12	1
Разность	10	10	0	11	9	8	-1	-10	13	-4

В первой строке два наименьших элемента - 8 и 8, поэтому разность составит 0 (табл.3.2). Во второй строке наименьшие элементы 3 и 2, следовательно, разность составляет 1. Наибольшая величина разности, равная 13, находится в столбце грузополучателя 9, в ней выбираем наименьший элемент - 2, который находится в столбце второго отправителя.

По результатам первого решения получаем закрепление первого пункта разгрузки за пунктом погрузки Б, столбец 9 из дальнейшего рассмотрения исключаем и определяем заново строку и столбец разностей (табл. 3.3). Для дальнейших расчетов поступаем так же.

Таблица 3.3

Матрица для метода Фогеля с добавленными столбцами и строками разности.

Пункты транспортной сети	1	2	3	4	5	6	7	8	10	Разность
А	14	20	9	14	15	20	8	10	8	0
Б	4	10	9	3	6	12	9	20	12	1
Разность	10	10	0	11	9	8	-1	-10	-4

Таблица 3.4.

Матрица для метода Фогеля с исключенным столбцом 4

Пункты транспортной сети	1	2	3	5	6	7	8	10	Разность
А	14	20	9	15	20	8	10	8	0
Б	4	10	9	6	12	9	20	12	2
Разность	10	10	0	9	8	-1	-10	-4

Таблица 3.5.

Матрица для метода Фогеля после исключения столбца 1

Пункты транспортной сети	2	3	5	6	7	8	10	Разность
А	20	9	15	20	8	10	8	0
Б	10	9	6	12	9	20	12	3
Разность	10	0	9	8	-1	-10	-4

Таблица 3.6

Матрица для метода Фогеля после исключения столбца 8

Пункты транспортной сети	2	3	5	6	7	10	Разность
А	20	9	15	20	8	8	0
Б	10	9	6	12	9	12	3
Разность	10	0	9	8	-1	-4

Таблица 3.7

Матрица для метода Фогеля после исключения столбца 2

Таблица 3.8

Матрица для метода Фогеля после исключения столбца 5

Пункты транспортной сети	3	6	7	10	Разность
А	9	20	8	8	0
Б	9	12	9	12	3
Разность	0	8	-1	-4

Таблица 3.9

Матрица для метода Фогеля после исключения столбца 2

Пункты транспортной сети	3	7	10	Разность
А	9	8	8	0
Б	9	9	12	3
Разность	0	-1	-4

Таблица 3.10

Матрица для метода Фогеля после исключения 10 столбца

Пункты транспортной сети	3	7	Разность
А	9	8	0
Б	9	9	3
Разность	0	-1

В случае 3 пунктом получателя расстояние до обоих грузоотправителей одинаково, поэтому мы выберем того, который наименее нагружен – т.е грузоотправителя А

Закрепление грузоотправителей за грузополучателями отражено в таблице 3.10. В столбце «Итого» приведено количество груза, которое должно быть у грузоотправителя, найденное как сумма потребностей, закрепленных за ним грузополучателей.

Таблица 3.11

Оптимальное закрепление пунктов разгрузки за поставщиками

Пункты транспортной сети	1	2	3	4	5	6	7	8	9	10	Итого
А			4.75				1.87	4.64		0.25	11.51
Б	5.42	3.72		3.87	3.41	4.08			3.12		23.62

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

Пробег с грузом (Lг) находится по формуле:

где n, k – количество пунктов, закрепленных за грузоотправителями А и Б соответственно;

liA, ljБ – расстояние от соответствующего грузоотправителя до i-ого и j-ого грузополучателя, км.

км

Общий пробег (Lо) находится по формуле:

Lо=2∙Lг

Lо=2∙72=144 км.

Транспортная работа (P) находится по формуле:

где - масса груза, перевозимая i-ому и j-ому грузополучателю соответственно, т.

P=5.42∙4+3.72∙10+3.87∙3+3.41∙6+4.08∙12+3.12∙2+4.75∙9+1.87∙8+4.64∙10+0.25∙8=

=252.26 ткм

Метод Свира предполагает воображаемый луч, исходящий из точки, где расположен грузоотправитель, который постепенно вращается по (или против) часовой стрелке, "стирая" с карты изображения грузополучателей (Рис.2). В тот момент, когда сумма заказов "стертых" грузополучателей достигнет вместимости транспортного средства, фиксируется сектор, обслуживаемый одним кольцевым маршрутом. При использовании метода Свира следует учитывать, что количество пунктов, включаемых в один маршрут должно быть не более пяти.

Так как в нашем случае получается, что за пунктом Б закреплено 6 пунктов, поделим сформируем 3 маршрута:

За маршрутом А закрепляем 7, 3, 10, 8 пункты.
За маршрутом Б1 закрепляем пункты 9, 4, 1.
За маршрутом Б2 закрепляем 5, 2, 6 пункты.

Рисунок 2. Закрепление за грузоотправителями грузополучателей с помощью метода Свира

На маршруте А общий вес получается 11.51 т

На маршруте Б1 общий вес 12.41 т

На маршруте Б2 11.21 т

Для работы на всех трех маршрутах привлекаем машину HYUNDAI 170 с грузоподъемностью 13 тонн.

Примем

А=1,

Пункт 3=2,

Пункт 7=3,

Пункт 8=4,

Пункт 10=5

Возьмем в качестве произвольного маршрута:

X0 = (1,2);(2,3);(3,4);(4,5);(5,1)

Тогда F(X0) = 9 + 1 + 11 + 8 + 8 = 37

Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.

di = min(j) dij

Таблица 4.1

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

Таблица 4.2

i j	1	2	3	4	5
1	M	1	0	2	0
2	8	M	0	10	2
3	7	0	M	10	2
4	2	3	3	M	0
5	5	0	0	5	M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

dj = min(i) dij

Таблица 4.3

i j	1	2	3	4	5
1	M	1	0	2	0
2	8	M	0	10	2
3	7	0	M	10	2
4	2	3	3	M	0
5	5	0	0	5	M
dj	2	0	0	2	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.

Таблица 4.3

i j	1	2	3	4	5
1	M	1	0	0	0
2	6	M	0	8	2
3	5	0	M	8	2
4	0	3	3	M	0
5	3	0	0	3	M

Сумма констант приведения определяет нижнюю границу H:

H = ∑di + ∑dj

H = 8+1+1+8+3+2+0+0+2+0 = 25

Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.

Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0

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

Длина маршрута определяется выражением:

F(Mk) = ∑dij

Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .

Шаг №1.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

Таблица 4.4

i j	1	2	3	4	5	di
1	M	1	0(0)	0(3)	0(0)	0
2	6	M	0(2)	8	2	2
3	5	0(2)	M	8	2	2
4	0(3)	3	3	M	0(0)	0
5	3	0(0)	0(0)	3	M	0
dj	3	0	0	3	0	0

d(1,3) = 0 + 0 = 0; d(1,4) = 0 + 3 = 3; d(1,5) = 0 + 0 = 0; d(2,3) = 2 + 0 = 2; d(3,2) = 2 + 0 = 2; d(4,1) = 0 + 3 = 3; d(4,5) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0;

Наибольшая сумма констант приведения равна (0 + 3) = 3 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(1*,4*) = 25 + 3 = 28

Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.

Таблица 4.5

i j	1	2	3	4	5	di
1	M	1	0	M	0	0
2	6	M	0	8	2	0
3	5	0	M	8	2	0
4	0	3	3	M	0	0
5	3	0	0	3	M	0
dj	0	0	0	3	0	3

Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 3

После операции приведения сокращенная матрица будет иметь вид:

Таблица 4.6

i j	1	2	3	5	di
2	6	M	0	2	0
3	5	0	M	2	0
4	M	3	3	0	0
5	3	0	0	M	0
dj	3	0	0	0	3

Нижняя граница подмножества (1,4) равна:

H(1,4) = 25 + 3 = 28 ≤ 28

Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 28

Шаг №2.

Таблица 4.7

i j	1	2	3	5	di
2	3	M	0(2)	2	2
3	2	0(2)	M	2	2
4	M	3	3	0(5)	3
5	0(2)	0(0)	0(0)	M	0
dj	2	0	0	2	0

d(2,3) = 2 + 0 = 2; d(3,2) = 2 + 0 = 2; d(4,5) = 3 + 2 = 5; d(5,1) = 0 + 2 = 2; d(5,2) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0;

Наибольшая сумма констант приведения равна (3 + 2) = 5 для ребра (4,5), следовательно, множество разбивается на два подмножества (4,5) и (4*,5*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(4*,5*) = 28 + 5 = 33

Исключение ребра (4,5) проводим путем замены элемента d45 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,5*), в результате получим редуцированную матрицу.

Таблица 4.8

i j	1	2	3	5	di
2	3	M	0	2	0
3	2	0	M	2	0
4	M	3	3	M	3
5	0	0	0	M	0
dj	0	0	0	2	5

Включение ребра (4,5) проводится путем исключения всех элементов 4-ой строки и 5-го столбца, в которой элемент d54 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 0

После операции приведения сокращенная матрица будет иметь вид:

Таблица 4.9

i j	1	2	3	di
2	3	M	0	0
3	2	0	M	0
5	0	0	0	0
dj	0	0	0	0

Нижняя граница подмножества (4,5) равна:

H(4,5) = 28 + 0 = 28 ≤ 33

Чтобы исключить подциклы, запретим следующие переходы: (5,1),

Поскольку нижняя граница этого подмножества (4,5) меньше, чем подмножества (4*,5*), то ребро (4,5) включаем в маршрут с новой границей H = 28

Шаг №3.

Таблица 4.10

i j	1	2	3	di
2	1	M	0(1)	1
3	0(1)	0(0)	M	0
5	M	0(0)	0(0)	0
dj	1	0	0	0

d(2,3) = 1 + 0 = 1; d(3,1) = 0 + 1 = 1; d(3,2) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0;

Наибольшая сумма констант приведения равна (1 + 0) = 1 для ребра (2,3), следовательно, множество разбивается на два подмножества (2,3) и (2*,3*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(2*,3*) = 28 + 1 = 29

Исключение ребра (2,3) проводим путем замены элемента d23 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,3*), в результате получим редуцированную матрицу.

Таблица 4.11

i j	1	2	3	di
2	1	M	M	1
3	0	0	M	0
5	M	0	0	0
dj	0	0	0	1

Включение ребра (2,3) проводится путем исключения всех элементов 2-ой строки и 3-го столбца, в которой элемент d32 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 0

После операции приведения сокращенная матрица будет иметь вид:

Таблица 4.12

i j	1	2	di
3	0	M	0
5	M	0	0
dj	0	0	0

Нижняя граница подмножества (2,3) равна:

H(2,3) = 28 + 0 = 28 ≤ 29

Поскольку нижняя граница этого подмножества (2,3) меньше, чем подмножества (2*,3*), то ребро (2,3) включаем в маршрут с новой границей H = 28

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,1) и (5,2).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(1,4), (4,5), (5,2), (2,3), (3,1),

Длина маршрута равна F(Mk) = 30

Для маршрута Б1 пункты

Б=1,

1=2,

4=3,

9=4.

Возьмем в качестве произвольного маршрута:

X0 = (1,2);(2,3);(3,4);(4,1)

Тогда F(X0) = 4 + 2 + 1 + 2 = 9

di = min(j) dij

Таблица 4.13

i j	1	2	3	4	di
1	M	4	3	2	2
2	4	M	2	3	2
3	3	2	M	1	1
4	2	3	1	M	1

Таблица 4.14

i j	1	2	3	4
1	M	2	1	0
2	2	M	0	1
3	2	1	M	0
4	1	2	0	M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

dj = min(i) dij

Таблица 4.15

i j	1	2	3	4
1	M	2	1	0
2	2	M	0	1
3	2	1	M	0
4	1	2	0	M
dj	1	1	0	0

Таблица 4.16

i j	1	2	3	4
1	M	1	1	0
2	1	M	0	1
3	1	0	M	0
4	0	1	0	M

Сумма констант приведения определяет нижнюю границу H:

H = ∑di + ∑dj

H = 2+2+1+1+1+1+0+0 = 8

Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.

Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0

Длина маршрута определяется выражением:

F(Mk) = ∑dij

Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .

Шаг №1.

Таблица 4.17

i j	1	2	3	4	di
1	M	1	1	0(1)	1
2	1	M	0(1)	1	1
3	1	0(1)	M	0(0)	0
4	0(1)	1	0(0)	M	0
dj	1	1	0	0	0

d(1,4) = 1 + 0 = 1; d(2,3) = 1 + 0 = 1; d(3,2) = 0 + 1 = 1; d(3,4) = 0 + 0 = 0; d(4,1) = 0 + 1 = 1; d(4,3) = 0 + 0 = 0;

Наибольшая сумма констант приведения равна (1 + 0) = 1 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(1*,4*) = 8 + 1 = 9

Таблица 4.18

i j	1	2	3	4	di
1	M	1	1	M	1
2	1	M	0	1	0
3	1	0	M	0	0
4	0	1	0	M	0
dj	0	0	0	0	1

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 1

После операции приведения сокращенная матрица будет иметь вид:

Таблица 4.19

i j	1	2	3	di
2	1	M	0	0
3	1	0	M	0
4	M	1	0	0
dj	1	0	0	1

Нижняя граница подмножества (1,4) равна:

H(1,4) = 8 + 1 = 9 ≤ 9

Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 9

Шаг №2.

Таблица 4.20

i j	1	2	3	di
2	0(0)	M	0(0)	0
3	0(0)	0(1)	M	0
4	M	1	0(1)	1
dj	0	1	0	0

d(2,1) = 0 + 0 = 0; d(2,3) = 0 + 0 = 0; d(3,1) = 0 + 0 = 0; d(3,2) = 0 + 1 = 1; d(4,3) = 1 + 0 = 1;

Наибольшая сумма констант приведения равна (0 + 1) = 1 для ребра (3,2), следовательно, множество разбивается на два подмножества (3,2) и (3*,2*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(3*,2*) = 9 + 1 = 10

Исключение ребра (3,2) проводим путем замены элемента d32 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,2*), в результате получим редуцированную матрицу.

Таблица 4.21

i j	1	2	3	di
2	0	M	0	0
3	0	M	M	0
4	M	1	0	0
dj	0	1	0	1

Включение ребра (3,2) проводится путем исключения всех элементов 3-ой строки и 2-го столбца, в которой элемент d23 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 0

После операции приведения сокращенная матрица будет иметь вид:

Таблица 4.22

i j	1	3	di
2	0	M	0
4	M	0	0
dj	0	0	0

Нижняя граница подмножества (3,2) равна:

H(3,2) = 9 + 0 = 9 ≤ 10

Поскольку нижняя граница этого подмножества (3,2) меньше, чем подмножества (3*,2*), то ребро (3,2) включаем в маршрут с новой границей H = 9

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,1) и (4,3).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(1,4), (4,3), (3,2), (2,1),

Длина маршрута равна F(Mk) = 9

Для маршрута Б2 примем, что пункты

Б=1,

2=2,

5=3,

6=4,

Возьмем в качестве произвольного маршрута:

X0 = (1,2);(2,3);(3,4);(4,1)

Тогда F(X0) = 10 + 6 + 7 + 12 = 35

di = min(j) dij

Таблица 4.23

i j	1	2	3	4	di
1	M	10	6	12	6
2	10	M	6	2	2
3	6	6	M	7	6
4	12	2	7	M	2

Таблица 4.24

i j	1	2	3	4
1	M	4	0	6
2	8	M	4	0
3	0	0	M	1
4	10	0	5	M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

dj = min(i) dij

Таблица 4.25

i j	1	2	3	4
1	M	4	0	6
2	8	M	4	0
3	0	0	M	1
4	10	0	5	M
dj	0	0	0	0

Таблица 4.26

i j	1	2	3	4
1	M	4	0	6
2	8	M	4	0
3	0	0	M	1
4	10	0	5	M

Сумма констант приведения определяет нижнюю границу H:

H = ∑di + ∑dj

H = 6+2+6+2+0+0+0+0 = 16

Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.

Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0

Длина маршрута определяется выражением:

F(Mk) = ∑dij

Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .

Шаг №1.

Таблица 4.27

i j	1	2	3	4	di
1	M	4	0(8)	6	4
2	8	M	4	0(5)	4
3	0(8)	0(0)	M	1	0
4	10	0(5)	5	M	5
dj	8	0	4	1	0

d(1,3) = 4 + 4 = 8; d(2,4) = 4 + 1 = 5; d(3,1) = 0 + 8 = 8; d(3,2) = 0 + 0 = 0; d(4,2) = 5 + 0 = 5;

Наибольшая сумма констант приведения равна (4 + 4) = 8 для ребра (1,3), следовательно, множество разбивается на два подмножества (1,3) и (1*,3*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(1*,3*) = 16 + 8 = 24

Исключение ребра (1,3) проводим путем замены элемента d13 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,3*), в результате получим редуцированную матрицу.

Таблица 4.28

i j	1	2	3	4	di
1	M	4	M	6	4
2	8	M	4	0	0
3	0	0	M	1	0
4	10	0	5	M	0
dj	0	0	4	0	8

Включение ребра (1,3) проводится путем исключения всех элементов 1-ой строки и 3-го столбца, в которой элемент d31 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 8

После операции приведения сокращенная матрица будет иметь вид:

Таблица 4.29

i j	1	2	4	di
2	8	M	0	0
3	M	0	1	0
4	10	0	M	0
dj	8	0	0	8

Нижняя граница подмножества (1,3) равна:

H(1,3) = 16 + 8 = 24 ≤ 24

Поскольку нижняя граница этого подмножества (1,3) меньше, чем подмножества (1*,3*), то ребро (1,3) включаем в маршрут с новой границей H = 24

Шаг №2.

Таблица 4.30

i j	1	2	4	di
2	0(2)	M	0(1)	0
3	M	0(1)	1	1
4	2	0(2)	M	2
dj	2	0	1	0

d(2,1) = 0 + 2 = 2; d(2,4) = 0 + 1 = 1; d(3,2) = 1 + 0 = 1; d(4,2) = 2 + 0 = 2;

Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(2*,1*) = 24 + 2 = 26

Исключение ребра (2,1) проводим путем замены элемента d21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.

Таблица 4.31

i j	1	2	4	di
2	M	M	0	0
3	M	0	1	0
4	2	0	M	0
dj	2	0	0	2

Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d12 заменяем на М, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 1

После операции приведения сокращенная матрица будет иметь вид:

Таблица 4.32

i j	2	4	di
3	0	1	0
4	0	M	0
dj	0	1	1

Нижняя граница подмножества (2,1) равна:

H(2,1) = 24 + 1 = 25 ≤ 26

Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 25

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,2) и (4,4).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(1,3), (3,2), (2,1),

Длина маршрута равна F(Mk) = 22

Пробег с грузом (Lг), общий пробег (Lо) и транспортная работа (Р) для развозочных маршрутов определяются по следующим формулам:

Lг=(10+8+3+1)+(2+1+3)+(6+6+2)=42 км

Lо=(10+8+3+1+8)+(2+1+3+4)+(6+6+2+10)=64 км

РА=10*4.64+8*0.25+3*4.75+1*1.87=64.52 ткм

РБ1=2*3.12+1*3.87+3*5.42=26.37 ткм

РБ2=6*3.41+6*3.72+2*4.08=50.94 ткм

Робщ=64.52+26.37+50.94=141.83 ткм

По результатам решения третьего и четвертого пунктов задания сформируем сводную таблицу, сделаем количественные и качественные выводы.

Таблица 4.33

Сравнение технико-эксплуатационных показателей

Показатель

Пробег с грузом, км

Общий пробег, км

Транспортная работа, ткм

После решения транспортной

задачи

144

252.26

После решения задачи

маршрутизации

141.83

Как можно сделать вывод из полученных данных, после решения задачи маршрутизации значительно уменьшился пробег с грузом (в 1.7 раз), общий пробег (в 2,25 раз) и транспортная работа в 1.78 раза. Можно сделать вывод о том, что кольцевые маршруты значительно уменьшают общий пробег и увеличивают транспортную работу по сравнению с маятниковыми.

Оценка времени доставки груза производиться по формулам:

для верхней границы

для нижней границы

- среднее значение доставки объема груза, ч;

Тн – время начала работы, ч (устанавливается студентом самостоятельно).

– среднее квадратическое отклонение времени доставки груза, ч;

– квантиль нормального распределения, соответствующий вероятности P

Выберем = 1,5; что будет соответствовать вероятности 86,6% нахождения затрат времени в пределах расчетных.

Величины и определяются по формулам:

где

- среднее значение времени доставки груза к j-ому потребителю, ч;

– среднее квадратическое отклонение времени доставки груза к j-ому потребителю, ч;

rij – коэффициент парной корреляции между временем на выполнение i-ой и j-ой ездки (в расчетах принимается равным нулю).

Время движения на i –ом участке маршрута рассчитывается по формуле:

Основные показатели работы на внутригородском маршруте:

Техническая скорость, Vт - 17,9 (км/ч)
Коэффициент вариации (движение)- 0,3
Коэффициент вариации (погрузки) – 0,6
Коэффициент вариации (разгрузки)- 0,7

А средние значения времени погрузки и разгрузки для одного автомобиля рассчитывается исходя из нормативов: 30 мин. на первую тонну и по 15 мин. на каждую следующую полную или неполную тонну

Среднее квадратическое отклонение времени движения находится исходя из следующего условия: коэффициенты вариации для времени движения и для технической скорости равны:

Так же будем производить округление нецелых минут в большую сторону до целого.

Для маршрута, включающего грузоотправителя А и закрепленные за ним грузополучателей, оценим время прибытия и отправления в каждый пункт. Краткая характеристика маршрута приведена в табл. 5.1.

Таблица 5.1

Краткая характеристика маршрута А

Пункт	Расстояние	Погрузка	Разгрузка	Время в пути	Tпог	Траз
А	10	11.51	0.00	34	195	0
8	8	0.00	4.64	27	0	90
10	3	0.00	0.25	11	0	30
3	1	0.00	4.75	4	0	90
7	8	0.00	1.87	27	0	45

Производя расчеты по данным формулам мы получаем

Таблица 5.2

Таблица времени для маршрута А

Пункт	Время прибытия	Время отправления

А	08:00	08:00	08:00	11:15	08:19	14:11
8	11:49	08:52	14:46	13:19	09:59	16:39
10	13:46	10:25	17:07	14:16	10:53	17:39
3	14:27	11:04	17:50	15:57	12:13	19:41
7	16:01	12:17	19:45	16:46	12:57	20:35

На основании этих расчетов можно сказать, что если автомобиль будет двигаться согласно среднему времени – то тогда план будет выполнен. Если автомобиль будет следовать минимальному времени, то скорее всего будет много простоев, как к примеру, в случае с 8 пунктом, который открывается в 10, и если автомобиль приедет в 8.52, то будет достаточно большое время простоя. Так же если автомобиль будет идти по максимальному времени, то он не успеет загрузить и развезти вовремя товар.

Так же рассчитаем маршрут Б1.

Таблица 5.3

Краткая характеристика маршрута Б1

Пункт	Расстояние	Погрузка	Разгрузка	Время в пути	Tпог	Траз
Б	2	12.41	0.00	7	210	0
9	1	0.00	3.12	4	0	75
4	2	0.00	3.87	7	0	75
1	4	0.00	5.42	14	0	105

Таблица 5.4

Таблица времени для маршрута Б1

Пункт	Время прибытия	Время отправления

Б	07:00	07:00	07:00	10:15	07:19	13:11
9	10:36	07:40	13:32	11:51	08:38	15:04
4	12:12	08:59	15:25	13:27	09:58	16:56
1	13:34	10:05	17:03	15:04	11:15	18:53

На основании этих расчетов можно сказать, что если если транспорт будет двигаться со средней скоростью – то в 9 пункте будет простой – прибытие в 10.36, а открытие пункта в 11, следовательно, будет простой, так же по прибытии в пункт 1 будет простой, так как в этом пункте обед с 13 до 14.

В случае если транспорт будет идти с минимальной скоростью, то простой будут еще больше на первом пункте, так как прибытие в 7.40, а открытие в 11.00.

Так же в случае движения по верхнему времени отправление из пункта Б будет не возможно, так как он работает до 12, а по верхнему времени отправление запланировано в 13.11. Следовательно все остальное так же не возможно.

Так же рассчитаем данные для маршрута Б2.

Таблица 5.5

Краткая характеристика маршрута Б2

Пункт	Расстояние	Погрузка	Разгрузка	Время в пути	Tпог	Траз
Б	6	11.21	0.00	21	195	0
5	6	0.00	3.41	21	0	75
2	2	0.00	3.72	7	0	75
6	12	0.00	4.08	41	0	90

Таблица 5.6

Таблица времени для маршрута Б2

Пункт	Время прибытия	Время отправления

Б	07:00	07:00	07:00	10:15	07:19	13:11
5	10:36	07:40	13:32	11:51	08:38	15:04
2	12:12	08:59	15:25	13:27	09:58	16:56
6	13:34	10:05	17:03	15:04	11:15	18:53

В случае, если транспорт будет двигаться со средней скоростью – то в 5 пункте будет простой – прибытие в 10.36, а открытие пункта в 12, следовательно, будет простой.

В случае если транспорт будет идти с минимальной скоростью, то простой будут еще больше на первом пункте, так как прибытие в 7.40, а открытие в 12.00.

Для работы на всех маршрутах привлекается HYUNDAI 170

Таблица 6.1

Характеристика автомобиля HYUNDAI 170

Полная масса автомобиля, кг	23100
Грузоподъемность, кг	13000
Максимальная скорость, км/ч	118
Вид топлива	Дизель
Базовая норма расхода топлива на пробег в снаряженном состоянии, л/100км	27

Затраты на топливо для грузовых автомобилей рассчитываются по следующей формуле:

Qн = 0,01 * (Hsan * Lо + Hw * P) * (1 + 0,01 * D),

Где Qн – нормативный расход топлива, л;

Lо – общий пробег автомобиля или автопоезда, км;

Hsan – норма расхода топлива на пробег автомобиля или автопоезда в снаряженном состоянии без груза:

Hsan = Hs + Hg * Gпр, л/100 км,

Где Hs – базовая норма расхода топлива на пробег автомобиля (тягача) в снаряженном состоянии, л/100 км (Hsan = Hs, л/100 км, для одиночного автомобиля, тягача);

Hg - норма расхода топлива на дополнительную массу прицепа или полуприцепа, л/100 ткм (для бензиновых двигателей – 2 л/100 ткм, для дизельных – 1,3 л/100 ткм);

Gпр - собственная масса прицепа или полуприцепа, т;

Hw - норма расхода топлива на транспортную работу, л/100 ткм (для бензиновых двигателей – 2 л/100 ткм, для дизельных – 1,3 л/100 ткм),

P - транспортная работа, выполняемая автомобилем на маршруте, ткм;

D - поправочный коэффициент (суммарная относительная надбавка или снижение) к норме, %.

D = 35 (работа автотранспорта в городах с населением свыше 3 млн. человек + работа автотранспорта, требующая частых технологических остановок, связанных с погрузкой и разгрузкой)

Таблица 6.2

Расчетная таблица для маршрутов

Маршрут	Lo	Hsam	Hw	P	D	Qh
A	30	27	1.3	64.52	35	12.07
Б1	10	27	1.3	50.94	35	4.54
Б2	24	27	1.3	141.83	35	11.24

Ежедневные затраты на топливо, при цене на 09-04-2014 1 литр=30 руб. равны

З.т= 30*(12.07+4.54+11.24)= 835.30 руб.

Так как известно, что затраты на топливо составляют 30% от общих расходов, можно посчитать их.

З.о. =835.30/30*100= 2784.35 руб.

В качестве вывода рассмотрим данные таблицы 4.33

Таблица 4.33

Сравнение технико-эксплуатационных показателей

Показатель

Пробег с грузом, км

Общий пробег, км

Транспортная работа, ткм

После решения транспортной

задачи

144

252.26

После решения задачи

маршрутизации

141.83

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

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

Результаты анализа, соответствия графиков доставки грузов и режимов работы грузополучателей, проведенного в пятой части, показывают, что соблюдение логистического принципа «Just-in-time» возможно на всех маршрутах. По маршрутам Б с небольшими поправками и рекомендациями по перевозке. По маршруту А без каких-либо проблем.

Транспортировка в цепях поставок: Методические указания по выполнению курсовой работы для студентов всех форм обучения / составитель И.А. Пластуняк.
Модели и методы теории логистики: Учебн. пособие. 2-е изд. / Под ред. В.С. Лукинского. – СПб.: Питер, 2010. – 448 с.
Бауэрсокс Доналд Дж., Клосс Дейвид Дж. Логистика: интегрированная цепь поставок / Пер. с англ. – М.: ЗАО “Олимп-Бизнес”, 2001. – 640 с.
Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. – М.: Изд-во МГТУ им. И.Э. Баумана, 2009. – 436 с.
Гаджинский А.М. Логистика: Учебник для высших и средних специальных учебных заведений. – 5-е изд., перераб. и доп. – М.: Издательско-книготорговый центр «Маркетинг», 2009. – 408 с.
Гаджинский А.М. Практикум по логистике. 2-е изд., перераб. и доп. – М.: Издательско-книготорговый центр «Маркетинг», 2001. – 180 с.
Кожин А.П. Математические методы в планировании и управлении грузовыми автомобильными перевозками: Учебник для вузов. – М.: Транспорт, 1994. – 304 с.
Краткий автомобильный справочник/ Понизовкин А.Н., Власко Ю.М., Ляликов М.Б. и др. – М.: ОА «Трансконсалтинг», НИИАТ, 2010. – 779 с.
Логистика: управление в грузовых транспортно - логистических системах: Учеб. пособие / Под ред. Л.Б. Миротина. – М.: Юрист, 2009. – 414 с.

1. тема політичної економії 1841 р
2. ТЕМАТИКА КОНТРОЛЬНЫХ РАБОТ политология Задание на след
3. за всех тех наслоений которые наложила жизнь.
4. ОСНОВЫ СТАНДАРТИЗАЦИИ И СЕРТИФИКАЦИИ
5. Солнечный Свет 4050 гр 6 видов с экстрактом и Dпантенолом- Летний сон Аура счастья Обитаемый остров
6. Месопотамия Бухгалтерский учет и использование в хозяйстве статистикоэкономической отчетности ведут с
7. Переміщення через митний кордон України товарів, що містять обєкти права інтелектуальної власності
8. Курсовая работа- Гражданское общество- понятие, сущность и структура
9. Годы Великого бедствия по своим разрушительным последствиям сравнимы с- B монгольским нашествием Закон
10. Руки вверх И п
11. варіанту 13 Клас 2 Тип стаційний Діапазон вхід
12. 1- Таблица 5
13. II століттям н е
14. Специфические особенности страхования от несчастных случаев
15. Cреды жизни и загрязнение окружающей среды
16. по теме- Липиды Первый вопрос- 1
17. Тема- Основи конституційного права України I
18. тема 3 Процесуальні строки та судові витрати
19. реферат диссертации на соискание учёной степени кандидата социологических наук.
20. Рис2 Выступление Специфика зашиты от радиолокационного наблюдения вызвана особенностями п

Материалы собраны группой SamZan и находятся в свободном доступе

Пункты транспортной сети

	А	Б	1	2	3	4	5	6	7	8	9	10
А		17	14	20	9	14	15	20	8	10	15	8
Б	17		4	10	9	3	6	12	9	20	2	12
1	14	4		9	6	2	3	10	6	16	3	9
2	20	10	9		11	11	6	2	12	17	11	12
3	9	9	6	11		6	6	12	1	11	8	3
4	14	3	2	11	6		5	13	6	17	1	9
5	15	6	3	6	6	5		7	7	15	6	8
6	20	12	10	2	12	13	7		13	16	13	13
7	8	9	6	12	1	6	7	13		11	8	3
8	10	20	16	17	11	17	15	16	11		19	8
9	15	2	3	11	8	1	6	13	8	19		11
10	8	12	9	12	3	9	8	13	3	8	11

	А	Б	1	2	3	4	5	6	7	8	9	10
А		17	14	20	9	14	15	20	8	10	15	8
Б	17		4	10	9	3	6	12	9	20	2	12
1	14	4		9	6	2	3	10	6	16	3	9
2	20	10	9		11	11	6	2	12	17	11	12
3	9	9	6	11		6	6	12	1	11	8	3
4	14	3	2	11	6		5	13	6	17	1	9
5	15	6	3	6	6	5		7	7	15	6	8
6	20	12	10	2	12	13	7		13	16	13	13
7	8	9	6	12	1	6	7	13		11	8	3
8	10	20	16	17	11	17	15	16	11		19	8
9	15	2	3	11	8	1	6	13	8	19		11
10	8	12	9	12	3	9	8	13	3	8	11

	А	Б	1	2	3	4	5	6	7	8	9	10
А		17	14	20	9	14	15	20	8	10	15	8
Б	17		4	10	9	3	6	12	9	20	2	12
1	14	4		9	6	2	3	10	6	16	3	9
2	20	10	9		11	11	6	2	12	17	11	12
3	9	9	6	11		6	6	12	1	11	8	3
4	14	3	2	11	6		5	13	6	17	1	9
5	15	6	3	6	6	5		7	7	15	6	8
6	20	12	10	2	12	13	7		13	16	13	13
7	8	9	6	12	1	6	7	13		11	8	3
8	10	20	16	17	11	17	15	16	11		19	8
9	15	2	3	11	8	1	6	13	8	19		11
10	8	12	9	12	3	9	8	13	3	8	11