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

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

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

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

Планирование маршрута доставки груза в смешанном сообщении на основе сетевого графика

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

Смешанная перевозка – транспортировка грузовой партии от пункта отправления до пункта назначения, когда в процессе перемещения используется более одного вида транспорта. Для планирования смешанной перевозки грузов наиболее актуальным является использование сетевых моделей. Задача сетевого планирования сводится к построению рационального плана проведения сложного комплекса работ, состоящего из отдельных элементарных взаимно обусловленных операций. Сетевой график позволяет изобразить логическую и временную структуру комплекса работ. Работы на графике изображаются векторами (дугами). Моменты завершения работ - это узлы графика (рис. 2). Дуге, идущей из i-го события в j-ое, присваивается время выполнения . В том случае, если точное время выполнения работ неизвестно, то, зная максимальное , минимальное и наиболее вероятное , можно определить: .

Рис.2

Предполагая, что исходное событие происходит в нулевой момент времени, определяют ранние сроки совершения событий . Для исходного события =0. Для остальных работ расчет производится исходя из следующих условий. Пусть в i-ое событие входит несколько работ, находятся все суммы , выбирается максимальная сумма. Поздний срок наступления события характеризует последний момент времени, в которых может произойти событие. Для последней работы = . Для нахождения всех остальных поздних сроков работ вычисляются все разности , выбирается минимальный. Путь, состоящий из работ, где совпадают ранние и поздние сроки выполнения, называется критическим.

Общий резерв времени ( ) – это время, на которое можно перенести начало работы, не увеличивая общее время выполнения проекта. . Свободный резерв - показывает, насколько можно отодвинуть начало работы.

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

При смешанных перевозках выбор варианта доставки осуществляется на основе следующих критериев:

Ø Время (T);

Ø Стоимость (С);

Ø Приведенная стоимость, определяемая по формуле: , где - оценка стоимости груза и его доставки с учетом фактора времени; - закупочная стоимость груза; - стоимость перевозки; - множитель наращивания процентов по процентной ставке i за n периодов, .

Каждой работе соответствуют три значения - время (T_i), стоимость доставки (C_i) и С^*, которые определяются как сумма дуг по различным вариантам доставки. Условной работе - соответствуют 3 значения, равные 0.

Пусть следования из одного узла в другой может быт альтернативным, например:

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

Ø Если дуга означает процесс оформления груза в пункте, то привлечение посредников и отказ от их услуг приведут к появлению нескольких альтернативных друг другу вариантов.

Таким образом, для пунктов, где пересекаются альтернативные пути доставки, появляется несколько суммарных значений, например :

.

Выбор производится на основе одного определяющего на данный момент времени показателя. В случае, если важность показателей имеет примерно одинаковое значение и если ни для одной из схем доставки не оказалось, что все значения ниже, чем для любой другой, для выбора схемы перевозки можно использовать критерии принятия решения в условиях неопределенности. Наиболее известны критерии Лапласа, Вальда, Сэвиджа и Гурвица, позволяющие принять решение на основании матрицы возможных результатов: строки соответствуют возможным действиям (варианты доставки груза); столбцы – возможным состоянием (критерии доставки); элементы матрицы – результат при выборе -го действия и реализации i-го состояния .