2. Определение кратчайших расстояний между пунктами транспортной сети

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

Транспортная сеть представляет собой систему дорог (улиц города), которые пригодны по качеству дорожного покрытия, ширине проезжей части и открыты для движения подвижного состава. Транспортная сеть состоит из отдельных элементов. Элементами транспортной сети являются вершины (пункты) и звенья сети. Вершины транспортной сети представляют собой точки на карте города или местности (перекрестки, площади, крупные грузообразующие и грузопоглощающие пункты), наиболее важные для определения расстояний или маршрутов движения автомобилей. Каждой вершине присваивается порядковый номер или другое условное обозначение. Две соседние вершины (два соседних пункта) можно соединить линией, по которой осуществляется непосредственная связь между этими вершинами с указанием расстояния между ними. Эти линии называются звеньями сети. Совокупность всех вершин и звеньев называется сетью, что показано на рисунке 2.1.

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

Рис. 2.1. Транспортная сеть

Расстояния между вершинами или отдельными пунктами транспортной сети можно определить следующими способами, широко распространенными на практике:

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

2) непосредственный замер расстояний на местности по показаниям спидометра при движении автомобиля по маршруту. Такой способ замера дает возможность определить расстояние между двумя пунктами с большой точностью, "от ворот до ворот", но он связан со значительными материальными и трудовыми затратами.

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

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

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

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

Определение кратчайших расстояний с использованием метода потенциалов

Задана транспортная сеть (рисунок 2.1). Пункты транспортной сети представляют собой вершины, обозначенные буквами от 1 до 10. Заданы расстояния между пунктами, т. е. определены звенья сети и их длина.

Задача решается следующим образом.

Шаг I. Вершина, от которой требуется определить кратчайшие расстояния, называется начальной. Начальной вершине присваивается нулевой потенциал Ui = 0.

Шаг II. Просматриваются все звенья, начальные вершины i которых имеют потенциалы Ui, а конечные j - не имеют. Определяется значение потенциалов конечных вершин Uj по следующей формуле:

Uj = Ui + Cij

где Cij -- длина звена (i - j), т. е. расстояние между вершинами i и j.

Из всех полученных потенциалов выбирается наименьший (поскольку определяются кратчайшие расстояния), и его значение присваивается соответствующей конечной вершине. Звено (i - j) отмечается стрелкой.

Шаг II повторяется до тех пор, пока всем вершинам данной сети не будут присвоены потенциалы.

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

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

Этап 1: примем нулевой потенциал в вершине 1.

Рисунок 2.2. Кратчайшие расстояния из вершины 1 относительно других вершин.

Расчеты:

Этап 2: примем нулевой потенциал в вершине 2.

Рисунок 2.3. Кратчайшие расстояния из вершины 2 относительно других вершин.

Расчеты:

U₉=U₈+C_8-9=18+6 = 24

Этап 3: примем нулевой потенциал в вершине 3.

Рисунок 2.4. Кратчайшие расстояния из вершины 3 относительно других вершин.

Расчеты:

Этап 4: примем нулевой потенциал в вершине 4.

Рисунок 2.5. Кратчайшие расстояния из вершины 4 относительно других вершин.

Расчеты:

Этап 5: примем нулевой потенциал в вершине 5.

Рисунок 2.6. Кратчайшие расстояния из вершины 5 относительно других вершин.

Расчеты:

Этап 6: примем нулевой потенциал в вершине 6.

Рисунок 2.7. Кратчайшие расстояния из вершины 6 относительно других вершин.

Расчеты:

U₅ =U₈ + C_5-8 = 13 + 5 = 18

Этап 7: примем нулевой потенциал в вершине 7.

Рисунок 2.8. Кратчайшие расстояния из вершины 7 относительно других вершин.

Расчеты:

Этап 8: примем нулевой потенциал в вершине 8.

Рисунок 2.9. Кратчайшие расстояния из вершины 8 относительно других вершин.

Расчеты:

Этап 9: примем нулевой потенциал в вершине 9.

Рисунок 2.10. Кратчайшие расстояния из вершины 9 относительно других вершин.

Расчеты:

Этап 10 можно не рассчитывать, так как маршрут 1-10=10-1; 2-10=10-2; 3-10=10-3; 4-10=10-4; 5-10=10-5; 6-10=10-6; 7-10=10-7; 8-10=10-8; 9-10=10-9.

На основании проведенных расчетов может быть составлена таблица кратчайших расстояний между пунктами транспортной сети (таблица 2.1).

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

Так как расстояние между одноименными пунктами равно нулю то в таблице 2.1 расстояния между этими пунктами не проставлены.

Таблица 2.1 Кратчайшие расстояния между пунктами транспортной сети

*4-6 и 7-8 считаются закрытыми для движения грузового автотранспорта