Теория оптимизации кольцевого маршрута

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

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

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

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

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

Например, если обозначить пункт отправки А, а пункты получения Б1, Б2, Б3, то можно выбрать один из следующих шести маршрутов:

1. А-Б1- Б2- Б3-А; 2. А-Б1- Б3- Б2-А; 3. А-Б3- Б1- Б2-А; 4. А-Б2- Б1- Б3-А; 5. А-Б2- Б3- Б1-А; 6. А-Б3- Б2- Б1-А .

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

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

Порядок выполнения работы:

1. Войти в операционную систему Windows, открыть диск с программами Programs Jailer S,открыть папку Logistic, открыть программный файл Logistic 2 и сохранить его под своей фамилией в папке с лабораторными работами вашей группы по логистике.

Например, файл Иванов лг2.xls в папке М-31 2006г. логистика.

2. Ваш рабочий файл является книгой Excel и содержит два листа:

1-й лист называется «Таблица-матрица»;

2-й лист - «Расчет оптимального маршрута».

На 1-м листе дана схема размещения пунктов потребления и расстояния между ними. Это первый вариант исходных данных для расчета. Следующий вариант данных для расчета представлен на листе «Исходные данные» пособия и его назначает руководитель. Необходимо рассчитать длину оптимального кольцевого маршрута для двух схем.

Расчеты на 1-м листе «Таблица-матрица»

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

1. В таблице №1 нужно определить возможные варианты доезда из одного пункта в другой и рассчитать суммарное расстояние каждого варианта по формуле суммы, используя ячейки с данными расстояний в схеме размещения транспортных пунктов. При этом суммарное расстояние от пункта до пункта считать не более чем через два пункта.

2. В таблице №2 необходимо определить минимальные расстояния между пунктами среди вариантов расстояний, представленных в таблице №1. Если из пункта А в пункт Е можно доехать тремя вариантами, то из них следует выбрать тот, который имеет минимальное расстояние, используя стандартную формулу определения минимального значения из ряда данных: = МИН (число1; число2; ...).

3. Для определения базового маршрута необходимо заполнить таблицу №3, в которой располагаются пункты и суммарные расстояния таблицы №2 по убыванию.

Последовательность расчетов в таблице№3

• После расчетов в таблице №2 в таблице №3 появится строка с итоговыми результатами этой таблицы. Она будет располагаться в столбце итоговые результаты и являться исходной для дальнейших расчетов.

• Рассчитать столбец «Расстояние» по формуле = МАКС (число1; число 2; ...). Формула должна определять максимальное значение строк таблицы №3. Каждая последующая формула определяет максимальное значение предыдущей строки. На данном этапе только в первой ячейке столбца «Расстояние» будет число, а в остальных ячейках столбца будут нули, так как соответствующие строки еще не сформированы.

• В столбце «Итоговые результаты» повторяем исходную строку (из таблицы №2) в последующих строках столбца «Итоговые результаты», исключая каждый раз максимальную величину, рассчитанную в столбце «Расстояние» и заменяя ее на ноль. Для этого нужно применить логическую функцию:

= Если (лог_выражение;[значение_если_истина];[значение_если_ложь]), где истина = 0.

Таким образом, выстроится цепочка расстояний по убыванию.

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

Базовый маршрутбудет состоять из первых трех пунктов с максимальными величинами, выделенными в таблице №3 жирным шрифтом. Выбранные пункты необходимо перенести в строку базового маршрута путем ссылки на соответствующие ячейки таблицы №3.

Расчеты на2-м листе «Расчет оптимального маршрута»

1. Переносим результаты, полученные в таблице №2, и базовый маршрут на 2-й лист в таблицу-матрицу, определяющую минимальные расстояния между пунктами кольцевого маршрута путем ссылок. Заполнять следует ту часть таблицы, ячейки которой свободны и не содержат нули. Расчетная таблица №1 заполняется автоматически.

2. Далее включаем в базовый маршрут следующие три пункта. Первым включаем пункт, который имеет следующую наибольшую сумму расстояний по столбцу после первых трех базовых (4-й по рангу из таблицы №3). Необходимо решить между какими пунктами его следует включить. Для этого определяем размер приращения маршрута для каждой пары пунктов по формуле: ΔL = Lki + Lip – Lkp,

где L – расстояние между пунктами, км;

i - индекс включаемого пункта;

k - индекс первого пункта из пары;

р - индекс второго пункта из пары.

Размеры приращений считаем в «Таблице для расчета приращений».

Например, если базовыми являлись пункты А, С, В, а четвертым пунктом – пункт D, то формулы расчета приращений будут выглядеть следующим образом:

Δ AC = AD+DC-AC; Δ CB-CD + DB-CB; Δ BA = BD + DA-BA.

Пункт D разместиться между пунктами, которые имеют минимальное приращение. При сравнении и выборе их полученных значений приращении минимальное, используется формула: = МИН (число1; число2; ...).

В результате получаем последовательность из 4-х пунктов. Расположение 5-го и 6-го пунктов определяем тем же способом.

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

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

Пример расчета длины оптимального кольцевого маршрута

Схема размещения пунктов потребления и расстояния между ними

Теория оптимизации кольцевого маршрута - student2.ru

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

Таблица №1

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

От А до От В до
В D S С Е D S С Е
13,5 9,5 13,8 11,2 5,5 3,1 12,1 5,3
12,6 11,8 11,1 15,4 11,7 5,4 7,8 9,4 10,0
  13,4 13,4 13,2 13,3   17,5 7,4 7,4
  18,1   17,7       7,3 11,4
От D до От S до От С до      
S С Е С Е Е      
2,3 3,9 5,9 - 4,3 2,2 2,0      
8,6 6.6 4,5 6,2 6,3 6,5      
8,2   8,6 4,2          

Таблица №2

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

по формуле = МИН(число1;[число2];...))

  А В D S С Е
А 11,8 9,5 13,2 11,2
В 5,4 3,1 7,3 5,3
D 11,8 5,4 2,3 3,9 4,5
S 9,5 3,1 2,3 4,2 2,2
С 13,2 7,3 3,9 4,2 2,0
Е 11,2 5,3 4,5 2,2 2,0
Итого 53,7 29,1 27,9 21,3 30,6 25,2

Последовательность расчетов в таблице №3

1. Рассчитать столбец "Расстояние" по формуле: = МАКС (число1 ;[число2];...). где (число1; [число2];...) = (ΣА; [ΣВ]; Σ...). Каждая последующая формула будет определять максимальное значение предыдущей строки с итоговыми результатами.

2. В столбцах "Итоговые результаты" повторяем значения сумм, постепенно, исключая максимальные величины, применив логическую функцию:

= Если(лог _выражение; (значение _если_ истина); [значение _если_ ложь]), где истина = 0.

Таким образом выстроится цепочка расстояний по убыванию.

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

Таблица №3

Таблица-матрица для определения базового маршрута

Суммарные расстояния и пункты по убыванию Итоговые результаты (из таблицы № 2)
Пункт Расстояние 53,7 29,1 27,9 21,3 30,6 25,2
А 53,7 29,1 27,9 21,3 30,6 25,2
С 30,6 29,1 27,9 21,3 25,2
В 29,1 27,9 21,3 25,2
D 27,9 21,3 25,2
Е 25,2 21,3
S 21,3

Базовый маршрут состоит из трех первых пунктов с максимальными величинами. В нашей задаче они выделены жирным цветом

Базовый маршрут: А ž С ž В ž А

Полученные результаты в таблице-матрице № 2 и базовый маршрут переносим на следующий лист данного файла для расчета оптимального маршрута.

Наши рекомендации