Алгоритм расчета кротчайших расстояний

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

Для определения кратчайших расстояний в настоящее время применяют математические методы. Мы определяем кратчайшие расстояния самым распространенным методом, который называется метод " метлы".

Для расчета кратчайших расстояний необходимы исходные данные: модель транспортной сети, на которой указаны номера вершин длины звеньев; номер вершины, из которой начинается движение (будем называть ее вершиной " от"); номер вершины, до которой (назовем ее вершиной " до") нужно определить кратчайший путь. Рассчитывая последовательно каждый шаг, заполняем специальную таблицу (таблица 3.1).

Таблица 3.1 – Специальная таблица к алгоритму расчета кратчайших расстояний

Алгоритм состоит из следующих шагов.

Шаг 1. Его можно назвать подготовительным. В первую колонку таблицы 3.1 заносим номер вершины, во вторую - в сторону вершины " от ставим " 0" - ноль, во все другие строки запишем заведомо большое число М. В третьей колонке в строке вершины " от" ставим " 1" - единицу, т.е. условный знак проверки (см. таблицу 3.2).

Таблица 3.2 - Результат первого шага расчета кратчайших расстояний

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

зачеркиваем условный знак проверки;

перебираем все связи вершины с условным знаком проверки с другими вершинами.

Для каждых из таких вершин рассчитываем вариант расстояния от вершины " от" по формуле:

l_{k, j}=l_{k, I}+l_{i, j}, (3.1)

где l_{k, j}; l_{k, I} - расстояния от вершины " от" до j-й, i-й вершины

соответственно

l_{j, i} - расстояние от i-й до j-й вершины.

После этого полученное расстояние l_{k, j} сравниваем с имеющимся в строке j-й вершины (обозначим его l^*_{k, j}).

В противном случае зачеркиваем в строке с вершиной j значение l^*_{k, j}, заносим в эту строку расстояние l_{k, j}, в третьею колонку записываем условный знак проверки, в четвертую колонку - номер предыдущей вершины (см. таблицу 3.3).

Если l_{k, j}≥ l^*_{k, j}, то в таблицу 3.1 ничего не записываем.

Шаг 3. Расчет закончен. Во второй колонке таблице 3.1 в каждой строке не зачеркнутая цифра будет являться кратчайшим расстоянием от вершины " от" до вершины, записанной в первой колонке (см. таблицу 3.4).

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

Масштаб (М) дорожной сети условно принимаем следующим образом:

М=500 (Ц₁+Ц₂),

где Ц₁, Ц₂ - последняя и предпоследняя цифры номера зачетной книжки соответственно. Таким образом, каждому сантиметру на рисунке будет соответствовать М метров реальной дорожной сети. Получаем:

М=500 (3+2)=2500 м

Таблица 3.3 - Таблица кратчайших расстояний

Окончание таблицы 3.3

Таблица 3.4 - Соответствие точек графа нумерации грузовых пунктов

Таблица 3.5 - Матрица кратчайших расстояний без учета знаков, установленных на дорожной сети

Таблица 3.6 - Матрица кратчайших расстояний с учетом знаков, установленных на дорожной сети

4 Выбор подвижного состава

Эффективность перевозок непосредственно зависит от правильного выбора подвижного состава. При решении этой задачи исходят из величины и структуры грузопотоков, возможных способов выполнения перевозок. Для изучения грузопотоков их изображают графически, т.е. строят Эпюру (схему, картограмму) грузопотоков В Приложении Б1.

В процессе выбора типа кузова автомобиля определяющим фактором является физико-механические свойства груза. Так навалочные грузы перевозят на самосвалах.

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

Таблица 4.1 - Задание на перевозку грузов, тыс.т

Таблица 4.2 Задание на перевозку груза