Теория оптимизации кольцевого маршрута
Одной из важных задач в логистике является разработка моделей транспортного обслуживанияпотребителей и поставщиков, расчет рациональных маршрутов перевозки, составление графиков доставки продукции потребителям.
Маршрутизация перевозок- наиболее совершенный способ организации материалопотока. Маршрутизация позволяет повысить производительность транспортных средств и сократить запасы поставщиков и потребителей.
Маршрут движения- это путь следования транспорта при выполнении перевозок. Выделяют маятниковые и кольцевые маршруты движения. При маятниковом маршруте путь следования транспорта между пунктами неоднократно повторяется. Кольцевой маршрут- это маршрут движения транспорта по замкнутому контуру, соединяющему несколько потребителей или поставщиков. Разновидностями кольцевого маршрута являются развозочные маршруты, сборные и сборно-развозочные. Развозочный кольцевой маршрут- это маршрут, при котором продукция загружается у одного поставщика и развозится нескольким потребителям. Сборный кольцевой маршрут- это маршрут движения, при котором продукция получается у нескольких поставщиков и доставляется одному потребителю. Сборно-развозочный кольцевой маршрут- это сочетание развозочного и сборного кольцевых маршрутов.
Организация кольцевого маршрута является одной из наиболее сложных задач транспортной логистики. По условию задачи из одного отправного пункта (например, с оптовой базы) отправляются разные товары в несколько пунктов получения (например, магазины розничной торговли) с последовательным их посещением. Целью задачи является поиск замкнутого маршрута с минимальной транспортной работой.
При расчете кольцевого маршрутаисходными данными является схема размещения транспортных пунктов и расстояний между ними. Выбор оптимального маршрута производится в результате перебора большого количества вариантов. Если в расчет принимается четыре пункта (одна база и три пункта получения), то количество возможных транспортных маршрутов будет равно шести.
Например, если обозначить пункт отправки А, а пункты получения Б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-го варианта и замените исходные данные. Если все формулы верны, то результат получится автоматически.
Пример расчета длины оптимального кольцевого маршрута
Схема размещения пунктов потребления и расстояния между ними
При составлении программы расчёта кольцевого маршрута на компьютере в ячейки таблиц вставлять толькоформулы!!! функций, чтобы в дальнейшем с изменением расстояний между пунктами, полученные расчеты по каждой схеме изменялись автоматически.
Таблица №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 и базовый маршрут переносим на следующий лист данного файла для расчета оптимального маршрута.