алгоритм

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

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

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

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

В Приволжском территориальном автотранспортном управлении при включении варианта, удовлетворяющего системе ограничений, в графике перевозок зерна устанавливают следующие приоритеты:

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

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

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

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