расстояние

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

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

Определение расстояний перевозок осуществляется несколькими практическими способами.

Непосредственный замер расстояний по местности. Этот метод мало пригоден из-за значительных расстояний, на которые перевозятся грузы.

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

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