Характеристика расположения пунктов транспортной сети на оси координат OXY

Введение

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

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

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

Для наглядного представления  расположения пунктов погрузки и  разгрузки построим систему координат  ОXY и отметим на ней грузоотправителей  и грузополучателей. Полученная схема  также содержит сведения о потребности  каждого пункта. На графике (Рис.1) предоставлено  расположение пунктов транспортной сети согласно данным в задании, на графике подписан каждый пункт и  указан объем груза в тоннах.

Рис.1 Расположение пунктов  транспортной сети

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

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

r² = (x_i – x_j)² + (y_i – y_j)²_,                               (1)

где x_i (y_i), x_j (y_j) – координаты i-го и j-го пунктов транспортной сети в декартовой системе координат соответственно. (см. табл. 1).

Таблица 1

Таблица расстояний между  пунктами транспортной сети

Пример расчетов:

r²(А-1) = (5 – 6)² + (14 – 2)² = 145

r(А-1) = = 12

r²(А-2) = (5 – 1)² + (14 – 4)² = 116

r(А-2) = = 11

r²(А-3) = (5 – 12)² + (14 – 10)² = 65

r(А-3) = = 8

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

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

Для исходных данных требуется  определить план доставки груза. По формуле (1) были определены расстояния между  пунктами, результат приведен в табл. 2.

Таблица 2

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

В первой строке два наименьших элемента - 3 и 4, поэтому разность составит 1 (табл.3). Выбираем строку с наименьшей разницей.

Таблица 3

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

По результатам первого  решения получаем закрепление третьего пункта разгрузки за пунктом погрузки А, столбец из дальнейшего рассмотрения исключаем и определяем заново строку и столбец разностей. (табл.4). Мы видим, что в столбцах получается три одинаковых наибольших значения равные 1. Если в строке и (или) столбце разностей находятся одинаковые наибольшие значения, то выбирается тот, которому соответствует минимальный элемент матрицы – в данном случае выберем пункт разгрузки 5, который будет закреплен за грузоотправителем А.

Таблица 4

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

Проводя расчеты аналогичным  образом, получаем искомое закрепление  потребителей за поставщиками, которое приведено в табл. 5.

Таблица 5

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

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

      (2)

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

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

      (3)

     (4)

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

L_г = 10+9+8+7+4+11+9+3+10+8= 79 км

L_o = 2*79 = 158 км

P = 10*2+9*0,59+8*3,65+7*4,62+4*3,74+11*0,74+9*0,73+3*4,20+

+10*2,17+8*0,40= 154,02ткм

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

Учитывая результаты, полученные при решении транспортной задачи по методу Фогеля, определим кольцевые  маршруты. По методу Свира следует учитывать, что количество пунктов включаемых в один маршрут должно быть не более пяти. Рассмотрим пункт А. За Пунктом А закреплено четыре грузополучателя (3,4,5,8), следовательно из них можно создать один кольцевой маршрут, т.к. это не противоречит условиям. Таким образом, метод Свира предполагает использование автомобиля грузоподъемностью 16,21 тонн для грузоотправителя А. Для работы на маршруте выберем автомобиль  Mercedes-Benz Actros 2641 S, с грузоподъемностью 17,2 тонны.

 Рассмотрим пункт Б.  За пунктом Б закреплено шесть  грузополучателя (1,2,6,7,9,10). Из них  мы не сможем создать одни  маршрут, поэтому мы разделим  их на два. Первый маршрут  будет с грузополучателями в пунктах 1,6,7, а второй маршрут с пунктами 2,9,10. Для работы на данных маршрутах выберем автомобиль IVECO Daily 70C15 с грузоподъемностью 4 тонн.

Руководствуясь таблицей 1, для грузоотправителя А построим матрицу кратчайших расстояний (табл. 6).

Таблица 6

Матрица кратчайших расстояний для первого маршрута от А

В каждой строке находим  минимальный элемент h_i и выполним приведение матрицы по строкам (табл. 7).

Таблица 7

Матрица кратчайших расстояний, приведенная по строкам

Далее полученную в табл. 7 матрицу необходимо привести по столбцам. Результат приведения представлен в табл. 8

Таблица 8

Матрица кратчайших расстояний, приведенная по столбцам

Нижняя граница, то есть минимально возможная длина маршрута, определяется по формуле (5):

                                          (5)

где hi, hj – константы приведения соответственно по строкам и столбцам.

Следовательно = 3+6+6+3+3 = 21

По формуле (6) для нулевых элементов матрицы, приведенной в таблице 8, определим оценки Qij, которые проставим в правом нижнем углу соответствующей ячейки.

 при условии: k ¹ j; s ¹ i; k, s = 1, 2, …, n,

где  l'ik – наименьшее значение элемента в строке i;

l''sj – наименьшее значение  элемента в столбце j.

• определяются пары (ks) с максимальной оценкой, то есть:

                                (6)

Так для нулевого элемента, находящегося на пересечении строки А и столбца 8, оценка Q_А8 = 1 + 0 = 1 (минимальное значение по строке – 1, а по столбцу – 0). При этом необходимо помнить, что элемент, для которого производиться расчет, не учитывается и необходимо искать следующее наименьшее значение.

Результаты расчета оценок представлены в таблице 9.

Таблица 9

Расчет оценок для нулевых  элементов

  В таблице 9 получили две максимальные оценки равные 6. Для дальнейшего решения выберем одну из них, какую не имеет принципиального значения. Пусть ветвь маршрута будет 3-4. Таким образом, исключает из дальнейшего рассмотрения строку k = 3 и столбец s = 4. На пересечении строки 4 и столбца 3 ставим знак « ».

Таблица 10

Матрица кратчайших расстояний, после исключения строки A, столбца 5

Проверяем условие, что бы в каждой строке и столбце усеченной  матрицы были нулевые значения, оно  не выполняется, поэтому операция приведения проводится заново. (табл. 11)

От начальной вершины "все решения" проводят ответвление  вершин ks и с нижними границами:

Графическое изображение  полученного решения приведено на рис. 2.

Таблица 11

Приведение матрицы усеченной  на строку 3 и столбец 4

Рис. 2. Первое ветвление «дерева решений» для метода «ветвей и границ»

Далее производится расчет оценок для нулевых значений усеченной  матрицы, выбирается максимальное значение, которое покажет новое ветвление «дерева решений» (табл. 12).

Таблица 12

Расчет оценок для нулевых  элементов

Полученное ветвление  отмечаем на «дереве решений» (рис. 3).

В таблице 11 получили четыре максимальных оценки равные 4. Для дальнейшего решения выберем одну из них, какую не имеет принципиального значения. Выберем 4-А. Получаем две «ветки дерева решений» 4 – А и . Исключаем из дальнейшего рассмотрения указанные строку и столбец. Знак не проставляется, так как столбец четыре уже был исключен при первой усечении матрицы кратчайших расстояний (табл. 13).

Рис. 3. Второе ветвление «дерева решений»

Таблица 13

Матрица кратчайших расстояний, после исключения строку 4 и столбец А

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

Следующее усечение матрицы представлено в табл. 14

Таблица 14

Расчет оценок для нулевых  элементов

Наибольшее искомое значение получаем 4, выбираем на пересечении столбца 5 и строки 8. Исключаем из дальнейшего рассмотрения указанные строку и столбце (табл. 15).

Таблица 15

Приведение матрицы усеченной на строку 8 и столбец 5

Проверяем условие, что бы в каждой строке и столбце усеченной  матрицы были нулевые значения, оно не выполняется, поэтому операция приведения проводится заново (Табл. 16).

Таблица 16

Приведение матрицы усеченной на строку 8 и столбец 5

И получаем матрицу 2 х 2, в  которой однозначно представлены две  последние «ветки» маршрута (табл. 17).

Таблица 17

Матрица 2 х 2 для метода «ветвей  и границ»

При этом «дерево решений» примет окончательный вид, который  проиллюстрирован на рис. 4.

Анализируя полученные участки (ветви), имеем следующий маршрут: A 8 5 3 4 A, длина которого составляет 31 км.

Рис. 4. «Дерево решений» для маршрута грузоотправителя А

Проверим, правильно ли была определена нижняя граница, для чего просуммируем соответствующие расстояния между пунктами маршрута: 3 + 3 + 12 + 6 + 7 = 31 км.

Теперь проводим аналогичные  вычисления для двух маршрутов грузоотправителя Б.

Для первого маршрута (1,6,7) грузоотправителя Б построим матрицу кратчайших расстояний (Табл. 18).

Таблица 18

Матрица кратчайших расстояний для маршрута от Б

В каждой строке находим  минимальный элемент hi и выполним приведение матрицы по строкам (Табл. 19).

Таблица 19

Матрица кратчайших расстояний, приведенная по строкам

Далее, полученную в табл. 19 матрицу необходимо привести по столбцам. Результат приведения представлен в табл. 20.

Таблица 20

Матрица кратчайших расстояний, приведенная по столбцам