И расчет кратчайших расстояний

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

Множество всех дорог города или района составляют дорожную сеть. Транспортная сеть – это совокупность дорог региона, пригодных для движения заданных транспортных средств. Транспортная сеть всегда является частным случаем дорожной сети и, как правило, строится для различных типов транспортных средств.

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

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

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

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

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

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

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