Алгоритм составления оптимального маршрута

Общий алгоритм планирования грузовых автомобильных перевозок

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

Наиболее простейшей задачей организации автомобильных перевозок является организация перевозки по схеме «Один ко многим». В данной схеме рассматривается склад (Ц) и количество продукции, необходимое для транспортировки. Дана грузоподъемность транспортного средства (Г). Есть несколько пунктов потребления продукции, заданные графом расстояния и количества потребляемой продукции. Задача: за минимальное количество рейсов и с минимальным пробегом транспортного средства распределить продукцию от склада до пунктов потребления.

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

1. Центры потребления разбиваются на 2 и более группы (в зависимости от исходных данных, то есть количества продукции и грузоподъемности транспортного средства) таким образом, чтобы в каждой группе сумма потребляемой продукции в пунктах была одинаковой (возможен вариант приблизительно одинаковой).
2. Для каждой группы поочередно строится таблица-матрица минимальных расстояний по исходному графу. Элементами матрицы являются кратчайшие расстояния от склада (Ц) до пунктов потребления (при этом перебираются все возможные варианты).
3. Значения матрицы суммируются по столбцам, и из этих значений выбирается 3 наибольших. По этим пунктам строится начальный маршрут.
4. Для пунктов, не вошедших в начальный маршрут (обозначаются i) поочередно определяется разница (начиная с наибольшего значения суммы по столбцу) длины расстояний от пунктов по следующей формуле: , где N – начальный пункт, К – конечный пункт.
5. Из этой разницы выбирается минимальная, и данный пункт вставляется в начальный маршрут между пунктами, где была получена эта разница. Строится новый маршрут.
6. В полученный новый маршрут по п.5 и 6 вставляются все оставшиеся пункты.
7. По окончательному маршруту перевозки считается длина пути.

Пример 1. В таблице задан граф пунктов потребления продукции. Также указано расстояние от каждого пункта и количество потребляемой продукции. Всего продукции на складе 300 контейнеров, грузоподъемность транспортного средства 150 контейнеров. За минимальное количество рейсов и с минимальным пробегом транспортного средства распределите продукцию от склада до пунктов потребления.

Пункт потребления

A

B

C

D

E

K

L

M

N

O

P

Q

R

S

Центр

Кол-во продукции

Расстояние

Ц-А

А-В

B-D

B-S

S-D

S-P

D-P

D-C

A-C

К-M

Ц-M

Ц-R

M-N

N-O

R-O

2,0

3,0

4,0

7,0

9,0

8,0

7,0

5,0

6,0

12,0

11,0

14,0

15,0

19,0

4,0

N-L	O-L	C-K	P-Q	Q-L	C-E	D-E	P-E	E-K	K-L	Q-K
15,0	10,0	12,0	8,0	3,0	9,0	12,0	8,0	11,0	10,0	10,0

Дата добавления: 2014-01-07