Тема 3: методы определения кратчайших расстояний между пунктами транспортной сети. Метод потенциалов. Метод «метлы»

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

Большая часть перевозок грузов осуществляется по сложившейся сети дорог и улиц с конкретными условиями эксплуатации подвижного состава и организации движения. Практически между двумя пунктами, расположенными на транспортной сети города (рис. 1) может быть n вариантов проезда, которым соответствуют определенные расстояния l_i, скорости V_i, и время t_i,(i = 1, 2, 3,..., n).

Варианты проезда между пунктами А и В

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

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

Модель участка транспортной сети и расстояний между пунктами (вершинами)

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

Дан граф

G=(x, и)

Каждому ребру этого графа приписано некоторое число l_ij ≥ 0, называемое длиной ребра. Тогда любая цепь μ, составленная из нескольких ребер, характеризуется длиной l_(μ).

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

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

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

Построив модель транспортной сети, замеряют расстояние между соседними (ближайшими) вершинами.

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