Расчет развозочно-сборочных маршрутов

Размещено на /

ИСХОДНЫЕ ДАННЫЕ

Из пункта А (база) доставляется груз в 11 других пунктов, перечисленных в исходных данных, из которых в свою очередь необходимо в пункт А доставить груз, например возвратную тару (рисунок 1). Количество единиц груза доставляемого из пункта А в каждый из них, дан в исходных данных.

Вместимость одного автомобиля составляет не более 250 ед. груза. Необходимо организовать перевозки между пунктами наименьшим пробегом автомобиля.

Таблица 1 – Исходные данные

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

РЕШЕНИЕ:

Решение находится путем последовательного расчета по нескольким этапам.

1 этап – нахождение кратчайшей связывающей сети.

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

Она определяется следующим образом:

на сети находим меньшее звено В-Г=2 км;

рассмотрим все звенья, связанные с одной из своих вершин с выбранным звеном, т. Е. звенья В-А=9; В-Б=3; В-Д=4; Г-Б=2; Г-Д=4; Г-Е=4;

из них выбираем звенья с наименьшим расстоянием Г-Б=2;

рассмотрим звенья, связанные с вершинами полученной линии В-Г-Б, и из них выберем наименьшее (при этом нельзя выбирать звено, соединяющее две ранее включенные в сеть вершины), такое звено – В-Б;

другими звеньями связанными своими вершинами с уже выбранной сетью являются звенья В-А, В-Д, Г-Д, Г-Е, Б-Е (последние 4 имеют = наименьшие расстояния);

примем наименьшее Б-Е и получим сеть В-Г-Б-Е. На рисунке 2 представлена кратчайшая связывающая сеть;

Рисунок 2 – Кратчайшая связывающая сеть

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

Таблица 2 – Группировка маршрутов

2 этап - набор пунктов в маршруты

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

В нашем случае условиями задачи установлено, что максимальная вместимость автомобиля составляет 250 ед. груза. Исходя из этого пункты, указанные на рисунке 2, можно сгруппировать так, как это сделано в таблице 2.

3 этап – определение очередности объезда пунктов маршрута

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

Для маршрута №1

Рисунок 3 – Маршрут №1

Для маршрута №2

Рисунок 4 – Маршрут№2

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

Для маршрута №1 симметричная матрица представлена в таблице 3.

Таблица 3 – Симметричная матрица для маршрута №1

Цифры показывают расстояние между этими пунктами. Дополнительно в этой матрице имеется итоговая строка — строка сумм. В ней проставляется сумма расстояний по каждому столбцу.

Затем строим начальный маршрут из 3 пунктов имеющих максимальную сумму, в нашем случае – АЖЗА. В него включаем следующий пункт с максимальной суммой – Б. Чтобы определить, между какими пунктами его ставить необходимо поочередно включать его между каждой соседней парой.

При этом находим величину прироста пробега автомобиля на маршруте при его включении.

Из полученных значений выбираем минимальную и между соответствующими ей пунктами вставляем данный. В нашем случае это - = 14 км, поэтому получаем маршрут – АБЖЗА.

км.

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

- min

км.

Затем в полученную последовательность вставляем пункт Г

- min

км.

Затем в полученную последовательность вставляем пункт Е

- min

км.

Можно утверждать, что полученная последовательность объезда пунктов маршрута дает наименьший или весьма близкий к наименьшему путь движения, так как при движении автомобиля по ранее выбранному маршруту общее расстояние равно 48 км, а скорректированный – 36 км, что дает уменьшение расстояния на 12 км.

По маршруту № 2 проводим аналогичные расчеты.

Составляем симметричную матрицу для маршрута №2, которая представлена в таблице 4.

Таблица 4 – Симметричная матрица для маршрута №2

Строим начальный маршрут из 3 пунктов имеющих максимальную сумму, в нашем случае – АДМА. В него включаем следующий пункт с максимальной суммой – Л. Чтобы определить, между какими пунктами его ставить необходимо поочередно включать его между каждой соседней парой.

При этом находим величину прироста пробега автомобиля на маршруте при его включении.