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

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

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

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

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

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

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

1. А-Б₁- Б₂- Б₃-А; 2. А-Б₁- Б₃- Б₂-А; 3. А-Б₃- Б₁- Б₂-А; 4. А-Б₂- Б₁- Б₃-А; 5. А-Б₂- Б₃- Б₁-А; 6. А-Б₃- Б₂- Б₁-А .

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

Однако для 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 = L_ki + L_ip – L_kp,

где 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