Главная Грузовые перевозки Алгоритмы определения кратчайших расстояний на графе (2008, 288с.)

Вопрос-ответ

Применение OLTP- и OLAP- технологий в логистических системах OLTP (On-Line Transacting Process) - способ получения аналитической информации из систем...
Как осуществляется управление составляющими ценообразования Управление составляющими ценообразования подразумевает отдельные решения по уровням цен для...
Информационные каналы в логистической системе Любое общение, осуществляемое через материальный носитель,, является информационным каналом. Очевидно, что...
Какова организация ФИАТА   В структуру FIАТА входят институты (Institutes), консультативные органы (Advisory Bodies) и рабочие группы (Working Groups),...
Почему при оценке уровня предлагаемого фирмой сервисного обслуживания следует использовать метод экспертных оценок При оценке уровня предлагаемого фирмой...
Когда и для каких целей введен унифицированный список пассажиров при перевозке пассажиров   В целях гармонизации условий осуществления перевозок...

Разместить рекламу на сайте

Алгоритмы определения кратчайших расстояний на графе (2008, 288с.)

Рейтинг пользователей: / 0
ХудшийЛучший 
Материал из категории  Грузовые перевозки
21.09.2015 15:06

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

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

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

Большинство этих алгоритмов могут быть разбиты на две группы.

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

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

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

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

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

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

На любом этапе вычислений кратчайших расстояний от заданной вершины все вершины сети разбиваются на три множества:

- множество 1 — вершины, кратчайшие расстояния до которых уже определены;

- множество 2 — вершины соседние (т.е. связанные дугой) с вершинами, расстояние до которых уже определено;

- множество 3 — все остальные вершины. Суть метода сводится к следующему.

1. Выбирается начальная вершина сети, расстояние от которой до остальных вершин необходимо определить. Этой вершине присваивают расстояние, равное 0, остальным вершинам присваивают расстояние, равное …. (очень большое число).

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

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

 

Источник: Грузовые автомобильные перевозки: Учеб. пособие для студ. высш. учеб. заведений / А. Э. Горев. — 5-е изд., испр. — М.: Издательский центр «Академия», 2008. — С. 185-187 (288 с.)




Подобные материалы:
Последние похожие материалы:
Более поздние похожие материалы:

 

Ваше мнение

Какая форма образования для Вас предпочтительна?

Результаты тестов

Результаты тестов
<->(БТТ-2013) Бакалаврський екзамен - Вантажні перевезення (52 тест.завдань) 26.92 %
<->(Лог-М) Тема 05. Зв'язок логістики з основними функц... (15 тест.завдань) 66.67 %
<->(ГП) Тема 11. Выбор транспортных средств при грузовых перевозках (14 тест.заданий) 28.57 %
Перейти к тестам
Что такое предельные издержки предприятия Предельные издержки предприятия — это вовсе не максимально допустимые затраты, а приращение соответствующих...
Что входит в понятие «количественное удовлетворение потребностей» В понятие «количественное удовлетворение потребностей» входит...
Что характерно для оперативных логистических решений Для оперативных логистических решений характерно то, что такие решения принимаются на сравнительно...
Правила логистики Выделяют семь правил логистики: 1) продукт должен быть необходим потребителю; 2) продукт должен быть соответствующего качества; 3)...
Когда и для каких целей введен унифицированный список пассажиров при перевозке пассажиров   В целях гармонизации условий осуществления перевозок...
Как трактуются обязанности сторон при перевозке   Так как Инкотермс предлагают комплект терминов для использования в различной сфере торговли и...
В каких случаях необходимо осуществлять маршрутизацию грузопотоков Маршрутизация грузопотоков становится особенно актуальной в условиях многовариантности...
В чем заключаются задачи распределительной логистики Распределительная логистика охватывает весь комплекс задач по правлению материальным потоком на...
Понятие потока Поток - это один или множество объектов (река, косяк рыбы, лава, конвейер, деньги и др.), воспринимаемое как единое целое, существующее...
Виртуальные формы организации поставки На рынке промышленных товаров наметилась тенденция распространения виртуальных партнёрских отношений между...

Образование в сфере логистики и транспорта Copyright © 2011-2023. При использовании материалов сайта - гиперссылка обязательна. All Rights Reserved.