Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Построение модели транспортной сети.
Множество всех дорог города или района составляет дорожную сеть. Транспортная сеть — это совокупность дорог региона, пригодных для движения заданных транспортных средств. Транспортная сеть всегда является частным случаем дорожной сети и, как правило, строится для различных типов транспортных средств: легковые автомобили, грузовые полной массой до 3,5 т и т.д. Модель транспортной сети может быть представлена в виде графа. Граф — это фигура, состоящая из точек (вершин) и соединяющих их отрезков (звеньев). Вершины графа — это точки на сети, наиболее важные для определения расстояний или маршрутов движения. Звенья графа — это отрезки транспортной сети, характеризующие наличие дорожной связи между соседними вершинами. Звенья графа характеризуются числами, которые могут иметь различный физический смысл. Чаще всего это расстояние, но может использоваться, например, и время движения. Ориентированные по направлению звенья графа называются дугами. Фактически всякое неориентированное звено графа включает в себя две равноценные, но противоположно направленные дуги. В зависимости от того, все или часть звеньев имеют направление, граф является ориентированным или смешанным. Граф, каждая вершина которого может быть соединена некоторой последовательностью звеньев с любой другой его вершиной, называется связанным графом. Иначе говоря, каждая вершина связанного графа должна иметь как минимум одну входящую и одну выходящую дугу. Граф, моделирующий транспортную сеть, обязательно должен быть связанным, чтобы всегда был путь из любой вершины в любую другую вершину. Числа, характеризующие звенья такого графа, обычно выражают протяженность пути, время или стоимость проезда. Для моделирования транспортной сети необходимо иметь: • картографический материал, обычно это карты крупного масштаба, так как они позволяют с большой точностью делать замеры расстояний между пунктами; • сведения о размещении основных грузообразующих (ГОП) и грузопоглощающих организаций (ГПП); • дополнительные сведения из коммунальных и дорожных организаций в виде перечня улиц с характеристикой их проезжей части; • сведения по организации уличного движения, т. е. схемы организации движения на перекрестках, площадях и транспортных развязках, а также сведения о различных ограничениях движения, связанные с установленными дорожными знаками.
Имея эти данные, моделирование транспортной сети начинают с размещения вершин графа. За вершины графа принимают ГОП, ГПП, центры крупных жилых кварталов или небольших обособленных жилых пунктов и пересечения улиц. Каждой вершине присваивается порядковый номер или другое условное обозначение. После размещения вершин их связывают дугами или звеньями. При построении модели транспортной сети особое внимание следует уделить максимально возможному уменьшению числа вершин. В противном случае транспортная сеть будет излишне сложна и определение кратчайших расстояний потребует длительного времени. Для снижения размерности и ускорения расчетов для транспортных сетей больших городов используется микро- и макрорайонирование. Микрорайонирование транспортной сети заключается в использовании в качестве вершин не пересечений дорожной сети (перекрестков), а центров микрорайонов (рис. 8.3). Макрораионирование (агрегирование) транспортной сети заключается в разбиении ее на отдельные подсети, расчеты по которым могут выполняться отдельно, а затем объединяться для получения общего результата. Этот способ особенно эффективен при пересчете расстояний из-за изменения дорожной обстановки, поскольку требуется пересчет только той подсети, в которой изменились транспортные связи. Алгоритмы определения кратчайших расстояний на графе. Интерес к задаче поиска кратчайших расстояний объясняется тем, что эта задача является одним из этапов в решении большинства задач, связанных с грузовыми перевозками. При этом в ходе решения задач, связанных с оптимизацией грузовых перевозок, приходится многократно определять кратчайшие расстояния между вершинами графа. Поэтому от быстродействия алгоритмов определения кратчайших расстояний между вершинами графа в большой степени зависит время решения всей задачи в целом. Сформулируем задачу о кратчайшем пути. Пусть дан связанный граф, имеющий К вершин и N ориентированных дуг, причем каждой дуге поставлено в соответствие неотрицательное число С,-,, называемое ее длиной. Требуется найти на графе кратчайшие пути и их длины от заданной вершины /0 до всех остальных вершин этого графа. Под длиной кратчайшего пути при этом подразумевается сумма длин составляющих этот путь дуг. В каждую вершину графа может входить только одна дуга, принадлежащая какому-нибудь кратчайшему пути.
Все специальные алгоритмы решения этой задачи являются итерационными, в которых на каждой итерации наращивается или корректируется уже построенное к этому множество кратчайших путей между вершинами графа. Большинство этих алгоритмов могут быть разбиты на две группы В алгоритмах первой группы уже построенное к данной итерации множество кратчайших путей остается неизменным, при этом на каждой итерации к этому множеству добавляется одна дуга т. е. находится кратчайший путь до очередной вершины. Задача решается за R - 1 итерацию. В алгоритмах второй группы построенное множество кратчайших путей может многократно корректироваться на последующую итерациях. Именно эти алгоритмы являются наиболее эффективными, когда количество вершин достаточно велико. Для нахождения оптимального решения задачи можно применять методы, позволяющие рассчитать кратчайшие пути вручную или с использованием ЭВМ. Метод потенциалов для определения кратчайших расстояний заключается в следующем. Начальной вершине сети, за которую может быть принята любая из вершин, присваивают потенциально равный нулю. Затем определяют потенциалы соседних с начальной точкой вершин сети. Значение потенциала равно расстоянию до вершины. Выбирают наименьший потенциал и присваивают его соответствующей вершине. Затем вычисляют потенциалы вершин, соседних с выбранной, и снова выбирают наименьший потенциал и присваивают его соответствующей вершине и т.д. Полное решение задачи включает в себя столько этапов, сколько вершин имеет транспортная сеть, поскольку на каждом определяют потенциал или кратчайшее расстояние от начально точки до одной из вершин сети. Метод «метлы» является методом решения этой задачи при помощи ЭВМ. Определение кратчайшего расстояния от заданной вершины, принятой за начальную точку сети, до всех отсталых вершин сети ведется путем построения однотипных таблиц. На любом этапе вычислений кратчайших расстояний от данной вершины все вершины сети разбиваются на три множества: • множество 1 — вершины, кратчайшие расстояния до которых уже определены; • множество 2 — вершины соседние (т.е. связанные дугой) вершинами, расстояние до которых уже определено; • множество 3 — все остальные вершины. 1. Выбирается начальная вершина сети, расстояние от которой до остальных вершин необходимо определить. Этой вершине присваивают расстояние, равное 0, остальным вершинам присваивают расстояние, равное М (очень большое число). 2. Затем выбирают вершину, расстояние до которой минимально. 3. Процесс повторяют до тех пор, пока все вершины не будут переведены в первое множество.
|
||||||
Последнее изменение этой страницы: 2017-02-17; просмотров: 1407; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.225.35.81 (0.006 с.) |