4981

Оптимальное проектирование процессов транспортировки

Контрольная

Логистика и транспорт

По картографическому материалу составить: а) граф сложного перекрестка с фиктивными дугами б) модель транспортной сети (ст. метро Курская - ст. метро Чистые пруды) Определить кратчайшее расстояние для модели трансп...

Русский

2012-11-30

118.5 KB

17 чел.

Вариант 41

1. По картографическому материалу составить:

а) граф сложного перекрестка с фиктивными дугами;

б) модель транспортной сети  (ст. метро "Курская" -  ст. метро "Чистые пруды ")

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

3. Построить схему кратчайшего пути для модели транспортной сети.

Рис. 1. Сложный перекресток

1 а. Составление графа сложного перекрёстка

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

1 б. Составление модели транспортной сети

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

Рис. 2. Модель сложного перекрестка

 

 

 

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

При определении кратчайших маршрутов от заданной вершины все множество вершин сети разбивается на три группы. В I группу входят вершины, до которых кратчайшие расстояния  уже найдены; во II - вершины, смежные  (связанные с другой) с вершинами I группы; в III- все остальные вершины. Нахождение кратчайших расстояний от вершины I до всех остальных для сети (рис. 2) состоит из нескольких однотипных этапов. Перед первым этапом в I группу входит только начальная вершина Кратчайшее расстояние до нее равно 0. Остальные вершины остальные входят в группу. Расстояния до них не определены и равны большому числу, которое обозначим буквой М (табл. 1).  В последней строке таблицы фиксируется номера вершин, предшествующих данным в кратчайшем расстоянии до них. У вершины 1 нет предшествующих   поскольку она является начальной. У остальных предшествующие вершины пока не определены.  В результате все элементы последней строки равны нулю.

Таблица  1  Анализ транспортной сети

Номер  вершины

1

2

3

4

5

Расстояние

0

М

М

М

М

Номер предшествующей вершины

0

0

0

0

0

Этап I  На рис. 2 найдем вершины, смежные с вершиной 1. С ней смежны вершины 2, 4, которые относятся к группе II. Расстояние до них определяется по формуле

   dj = rj+lij                                                                   (1)

где dj - расстояние от начальной до j-й вершины; ri - кратчайшее расстояние от начальной до i-й вершины; lij - длина ребра, связывающего i-ю вершину с j-й. Подставив значение формулы (1), получим:

d2 = r1+ l1,2 = 0 + 25=25;

d4 = r1+ l4,1= 0 + 19=19

Ищем минимальное расстояние до вершин, входящих во  II группу им оказывается расстояние до вершины 4. Она переводится в I группу Полученный  результат запишем в табл. 2.

Таблица  2  Анализ транспортной сети

Номер  вершины

1

2

3

4

5

Расстояние

0

25

М

19

М

Номер предшествующей вершины

0

1

0

1

0

Этап II Ищем вершины, смежные с вершиной 4. Это вершина 3. Вершину 1 рассматривать не будем, так как она входит в I группу. Для остальных вычислим расстояние по формуле (1):

d3 = r4+ l4,3 = 19 + 24=43;

Вершины 3 переходит из III группы во II. Для неё предшествующей становится вершина 4 (табл. 3).

          Таблица  3  Анализ транспортной сети

Номер  вершины

1

2

3

4

5

Расстояние

0

25

43

19

М

Номер предшествующей вершины

0

1

4

1

0

Этап III Определяем кратчайшее расстояние до вершины 2

d2 = r3+ l3,2 = 43 + 20=63

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

Таблица  4 Анализ транспортной сети

Номер  вершины

1

2

3

4

5

Расстояние

0

25

43

19

М

Номер предшествующей вершины

0

1

4

1

0

Вершина 2 переходит в I группу

Этап IV Ищем вершины, смежные с вершиной 2. Это вершины 3 и 5.

d3 = r2+ l2,3 = 25 + 20=45;

             d5 = r2+ l5,2 = 25 + 30=55;

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

       Таблица  5 Анализ транспортной сети

Номер  вершины

1

2

3

4

5

Расстояние

0

25

43

19

55

Номер предшествующей вершины

0

1

4

1

2

3. Построение схемы кратчайшего пути для модели транспортной сети

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

Пусть, например, нужно определить кратчайший путь из вершины 1 в вершину 5. Вершине 5 предшествует вершина 2, вершине 2 - вершина 1. Таким образом, в данном примере кратчайший путь проходит через вершины 1, 2, 5.

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

Рис. 3. Схема кратчайшего пути по маршруту  ст. метро "Курская" -  ст. метро "Чистые пруды "

 

 

 

Вершины

Расстояние

Вершины Ki

K1

K2

K3

K4

K5

Kj

 

K1

 

K2

 

24

K3

 

20

K4

 

19

24

K5

 

30


 

А также другие работы, которые могут Вас заинтересовать

73996. Огосударствление экономики СССР.Индустриализация и коллективизация в СССР 28.31 KB
  Необходимость проведения индустриализации в России мало у кого вызывает какиелибо сомнения. Впрочем по вопросу о темпах и методах индустриализации в советском руководстве не существовало единства мнений. оставляла единственную возможность получить средства для индустриализации за счет мобилизации внутренних ресурсов. С точки зрения наиболее решительных сторонников индустриализации Е.
73997. Основные особенности и этапы внешней политики СССР между двумя мировыми войнами 18.92 KB
  Основные особенности и этапы внешней политики СССР между двумя мировыми войнами. Условия возникновения Советского государства в рамках мировой и гражданской войн активного участия в этом процессе значительного числа иностранных государств и особенности большевистской идеологии с приоритетом в постановке задач общемировым устремлениям во многом обусловили цели и средства внешней политики СССР в 20 30х гг. С другой стороны СССР являлся наследником Российской империи с ее очевидными национальными и государственными интересами защита...
73998. Великая Отечественная война: крупнейшие военные операции 1941 – 1945 годов 21.99 KB
  Великой Отечественной войне первоначальный ход военных действий сложился крайне неблагоприятно для СССР. Суворовым идея неподготовленности СССР к войне оборонительной ввиду подготовки его к войне наступательной иными словами воскрешение еще Гитлером выдвинутой концепции превентивной вынужденной войны с целью обезопасить себя от нападения Красной Армии. Таким образом Советский Союз в упорной борьбе сумел одержать победу в Великой Отечественной и разделить успех с союзниками по антигитлеровской коалиции во II мировой войне. Полководческое...
73999. Деятельность тыла в Великой Отечественной войне. Партизанское движение в годы Великой Отечественной войны 17.77 KB
  Партизанское движение в годы Великой Отечественной войны. Благодаря высокому уровню централизации государственного хозяйства в первые же месяцы войны удалось обеспечить его перестройку на военномобилизационный лад. Успех во многом определялся удачной организацией управления страной в условиях войны: при всех своих издержках советская система как раз и была предназначена для действия в условиях чрезвычайных обстоятельств для быстрой и решительной мобилизации имеющихся ресурсов и их перераспределения в соответствии с первоочередными...
74000. СССР во 2-й половине 50 - 1-й половине 80-х гг. XX в. От попыток либерализации к всеобщему кризису 22.46 KB
  Первые послевоенные годы принесли мало изменений в функционирование политической системы СССР. Будучи отражением реальной потребности в мобилизации сил для быстрого завершения восстановительных работ централизация в то же время подошла к своему пределу за которым она теряла всякую эффективность что отчетливо проявилось в нарастании кризисных явлений во всех сферах жизни СССР в начале 50х гг. Все это подводило руководящие круги СССР к осознанию необходимости преобразований.
74001. Основные направления и этапы внешней политики СССР в годы «холодной войны» 19.09 KB
  Основные направления и этапы внешней политики СССР в годы холодной войны. Победа СССР в войне значительно изменило его международное положение. СССР принял участие в создании ООН где ему было определено место одного из постоянных членов Совета безопасности.президент США сформулировал доктрину Трумена меры против экспансии СССР.
74002. Перестройка 1985 – 1990 годов 22.31 KB
  Именно эти меры положили начало развалу политической системы СССР поскольку именно партийная вертикаль обеспечивала реальное функционирование политической системы; советские органы были властью сугубо номинальной а потому оказались не готовы к выполнению возложенных на них полномочий. когда оппозиции удалось добиться отмены 6й статьи Конституции СССР закрепляющей особую роль КПСС в государственной системе СССР и внушительного представительства в ряде...
74003. Становление новой российской государственности в 1990-е годах 18.55 KB
  Распавшийся Советский Союз оставил весьма сложное наследство России в виде экономического кризиса всеобщего социального недовольства и наконец отсутствия реальной российской государственности. В условиях краха умеренной и консервативной моделей периода перестройки вполне естественной была победа весьма радикальной для России концепции демократического либеральнорыночного государства с ориентацией на западные страны. В принципе основные направления реформ к моменту их осуществления в России были уже испытаны в ряде государств Восточной...
74004. Основные этапы развития исторической науки в России XVIII – начале XX веков 20.07 KB
  Главною заслугою Миллера было собирание материалов по русской истории; его рукописи так наз. И исследования Миллера имели значение он был одним из первых ученых заинтересовавшихся позднейшими эпохами нашей истории им посвящены его труды: Опыт новейшей истории России и Известие о дворянах Российских. видное место трудами по русской истории занял и М.