Расчет кратчайших расстояний
Моделирование транспортной сети. Алгоритм расчета кратчайших расстояний, особенности применения математических методов в данном процессе. Расчет кратчайших расстояний на ЭВМ посредством специально разработанной программы "РКР", оценка результатов.
| Рубрика | Транспорт |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 17.02.2013 |
| Размер файла | 1,9 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Расчет кратчайших расстояний
Моделирование транспортной сети
Модель транспортной сети представляет собой геометрическую фигуру (граф), состоящую из вершин (точек) и отрезков (ребер), соединяющих эти вершины (точки графа). Для ее построения берем схему дорожной сети г. Красноярска. На первом этапе из дорожной сети исключаем улицы, переулки и т.п., не имеющие существенного значения для транзитного движения (служащие для подъезда к домам, заводам и т.д.), и получаем схему транспортной сети. Каждой вершине транспортной сети присваивают порядковый номер. Отрезки, соединяющие соседние вершины, называют звеньями транспортной сети. Совокупность всех вершин и звеньев - модель (граф) транспортной сети. Проезды с односторонним движением отражают (моделируют) посредством ориентированного звена графа (ребро со стрелкой). Далее приходим к модели транспортной сети (рис. 1).
Рисунок 1. Схема дорожной сети
Таблица 1. Список знаков, установленных на дорожной сети
|
Улица Перекресток с улицей |
Код установленного знака |
|||
|
прямое направление |
обратное направление |
|||
|
Победы |
Мира |
3.11 |
3.11 |
|
|
Знаний |
3.11 |
3.11 |
||
|
Знаний |
Майская |
3.1 |
||
|
Суворова |
3.1 |
|||
|
Майская |
Знаний |
4.4 |
||
|
Ильича |
4.4 |
|||
|
Новослободская |
4.4 |
4.4 |
||
|
Шоссе Энтузиастов |
4.4 |
4.4 |
||
|
Ильича |
Кутузова |
- |
3.1 |
|
|
Чкалова |
- |
3.1 |
||
|
Майская |
- |
4.4 |
||
|
Кутузова |
Жуковского |
- |
3.1 |
|
|
Новослободская |
- |
3.1 |
||
|
Шоссе Энтузиастов |
- |
3.1 |
||
|
Жуковского |
Чкалова |
- |
3.1 |
|
|
Уральская |
3.13 |
3.1 |
||
|
Северная |
- |
3.1 |
||
|
Горняков |
- |
3.1 |
||
|
Красноярская |
- |
3.1 |
||
|
Новослободская |
Суворова |
3.2 |
- |
|
|
Майская |
3.2 |
- |
||
|
Кутузова |
3.2 |
- |
||
|
Чкалова |
3.2 |
- |
||
|
Уральская |
3.2 |
- |
||
|
Алтайская |
Уральская |
3.11 |
3.11 |
|
|
Красноярская |
3.11 |
3.11 |
||
|
Красноярская |
Уссурийская |
- |
3.2 |
|
|
Алтайская |
- |
3.2 |
||
|
Жуковского |
- |
3.2 |
||
|
Шоссе энтузиастов |
- |
3.2 |
||
|
Горняков |
Жуковского |
3.2 |
- |
|
|
Солнечный бульвар |
Печати |
- |
3.2 |
|
|
Парковая |
- |
3.2 |
||
|
9 мая |
- |
3.2 |
||
|
Федина |
- |
3.2 |
||
|
1 мая |
- |
3.2 |
||
|
Бунина |
- |
3.2 |
||
|
Вавилова |
- |
3.2 |
||
|
С. Лазо |
- |
3.2 |
||
|
Лесная |
Солнечный бульвар |
- |
3.2 |
|
|
Первомайская |
- |
3.2 |
||
|
Печати |
Шоссе Энтузиастов |
4.4 |
4.4 |
|
|
Солнечный бульвар |
4.4 |
4.4 |
||
|
Первомайская |
4.4 |
4.4 |
||
|
Цеховая |
Парковая |
3.2 |
- |
|
|
9 мая |
3.2 |
- |
||
|
Федина |
3.2 |
- |
||
|
Бунина |
Солнечный бульвар |
- |
3.2 |
|
|
Первомайская |
- |
3.2 |
||
|
Вавилова |
Шоссе Энтузиастов |
3.2 |
- |
|
|
Солнечный бульвар |
3.2 |
- |
||
|
Ленина |
3.2 |
- |
Масштаб (М) дорожной сети условно принимаем следующим образом:
М=500 (Ц1+Ц2),
где Ц1, Ц2 - последняя и предпоследняя цифры номера зачетной книжки соответственно. Таким образом, каждому сантиметру на рисунке будет соответствовать М метров реальной дорожной сети. Получаем:
М=500 (3+1)=2000 м
Таблица 2 - Данные по основной транспортной сети
|
№ вершины сети |
№ соседней вершины |
Длина звена, км |
Наименование улицы |
|
|
1 |
2 3 |
2,4 4,0 |
Победы Маркса |
|
|
2 |
1 4 |
2,4 2,6 |
Мира знаний |
|
|
3 |
1 5 |
4,0 1,8 |
Мира Суворова |
|
|
4 |
2 6 5 |
2,6 1,4 2,0 |
Победы Майская Суворова |
|
|
5 |
3 21 4 |
1,8 3,6 2,0 |
Маркса Новосибирская Знаний |
|
|
6 |
4 7 22 |
1,4 1,8 3,0 |
Знаний Ильича Новослободская |
|
|
7 |
6 8 15 |
1,8 2,0 1,4 |
Майская Чкалова Кутузова |
|
|
8 |
7 16 |
2,0 1,8 |
Ильича Жуковского |
|
|
9 |
11 12 |
8,8 2,4 |
Уссурийская Красноярская |
|
|
10 |
11 13 |
1,0 2,2 |
Уссурийская Алтайская |
|
|
11 |
10 12 |
1,0 5,6 |
Уральская Красноярская |
|
|
12 |
9 11 14 |
2,4 5,6 1,8 |
Камчатская Уссурийская Алтайская |
|
|
13 |
10 14 17 |
2,2 6,8 1,6 |
Уссурийская Алтайская Жуковского |
|
|
14 |
12 13 20 |
1,8 6,8 1,2 |
Красноярская Уральская Жуковского |
|
|
15 |
7 16 23 |
1,4 1,8 1,8 |
Ильича Жуковского Новослободская |
|
|
16 |
8 15 17 24 |
1,8 1,8 3,2 1,8 |
Чкалова Кутузова Уральская новослободская |
|
|
17 |
13 16 18 25 |
1,6 3,2 3,2 2,0 |
Алтайская Чкалова Северная Новослободская |
|
|
18 |
17 19 33 |
3,2 2,0 3,8 |
Уральская Горняков Северная |
|
|
19 |
18 20 35 |
2,0 1,8 3,2 |
Северная Красноярская Горняков |
|
|
20 |
19 14 36 |
1,8 1,2 3,0 |
Жуковского Алтайская Сергея Лазо |
|
|
21 |
5 22 26 |
3,6 2,2 1,6 |
Знаний Новослободская Шоссе Интузиастов |
|
|
22 |
6 21 23 27 |
3,0 2,2 1,2 1,6 |
Майская Суворова Новослободская Шоссе Интузиастов |
|
|
23 |
15 22 24 29 |
1,8 1,2 1,4 1,6 |
Жуковского Новослободская Чкалова Шоссе Интузиастов |
|
|
24 |
16 23 25 |
1,8 1,4 3,0 |
Чкалова Кутузова Уральская-Федина |
|
|
25 |
24 17 31 |
3,0 2,0 1,6 |
Чкалова Уральская Федина |
|
|
26 |
21 27 41 |
1,6 1,8 2,0 |
Суворова Ш. Интузиастов Б. Солнечный |
|
|
27 |
22 26 28 |
1,6 1,8 0,8 |
Майская Суворова-Лесная Печати |
|
|
28 |
27 29 42 |
0,8 0,8 2,4 |
Ш. Интузиастов Кутузова Печати |
|
|
29 |
23 28 30 |
1,6 0,8 0,8 |
Кутузова Печати 9 Мая |
|
|
30 |
29 31 37 |
0,8 3,4 1,8 |
Кутузова Федина 9 Мая |
|
|
31 |
25 30 32 39 |
1,6 3,4 1,6 1,6 |
Новослободская 9 Мая 1 Мая Федина |
|
|
32 |
31 33 40 |
1,6 1,4 1,6 |
Федина Бунина-Северная 1 Мая |
|
|
33 |
18 32 34 47 |
3,8 1,4 1.6 2,6 |
Северная 1 Мая Вавилова Бунина |
|
|
34 |
33 35 48 |
1,6 0,8 3,0 |
Северная-Бунина Горняков Вавилова |
|
|
35 |
19 34 36 |
3,2 0,8 1,6 |
Горняков Вавилова С. Лазо |
|
|
36 |
20 35 49 |
3,0 1,6 3,6 |
Красноярская Горняков Б. Солнечный |
|
|
37 |
30 38 43 |
1,8 1,4 1,0 |
Ш. Энтузиастов Цеховая Б. Солнечный |
|
|
38 |
37 39 44 |
1,4 2,0 1,0 |
9 Мая Федина Парковая |
|
|
39 |
31 38 40 45 |
1,6 2,0 1,6 1,0 |
Федина Парковая 1 Мая Федина |
|
|
40 |
32 39 46 |
1,6 1,6 1,0 |
Ш. Энтузиастов Цеховая Б. Солнечный |
|
|
41 |
26 42 50 |
2,0 1,6 1,4 |
Ш. Энтузиастов Б. Солнечный Ул. Первомайская |
|
|
42 |
28 41 43 51 |
2,4 1,6 1,2 1,4 |
Ш. Энтузиастов Лесная 9 Мая первомайская |
|
|
43 |
37 42 44 52 |
1,0 1,2 1,4 1,4 |
Цеховая Печати Парковая Первомайская |
|
|
44 |
38 43 45 53 |
1,0 1,4 2,0 1,4 |
Цеховая 9 Мая Федина первомайская |
|
|
45 |
39 44 46 54 |
1,0 2,0 1,6 1,4 |
Федина Парковая 1 Мая первомайская |
|
|
46 |
40 45 47 55 |
1,0 1,6 1,4 1,4 |
Цеховая Федина Бенина первомайская |
|
|
47 |
33 46 48 56 |
2,6 1,4 1,6 1,6 |
Ш. Энтузиастов 1 Мая Вавилова Первомайская |
|
|
48 |
34 47 49 58 |
3,0 1,6 1,8 3,6 |
Ш. Энтузиастов Б. Солнечный С. Лазо Ленина |
|
|
49 |
36 48 59 |
3,6 1,8 3,8 |
Ш. Энтузиастов Б. Солнечный ленина |
|
|
50 |
41 51 |
1,4 1,6 |
Б. Солнечный Первомайская |
|
|
51 |
50 42 52 |
1,6 1,4 1,2 |
Лесная Печати 9Мая |
|
|
52 |
51 43 53 |
1,2 1,4 1,6 |
Печати 9 Мая Парковая |
|
|
53 |
52 44 54 |
1,6 1,4 2,0 |
9 Мая Парковая Федина |
|
|
54 |
53 45 55 |
2,0 1,4 1,4 |
Парковая Федина 1 Мая |
|
|
55 |
54 56 46 |
1,4 1,4 1,4 |
Федина 1 Мая Бунина |
|
|
56 |
47 55 57 |
1,6 1,4 2,0 |
Бунина 1 Мая Ленина |
|
|
57 |
56 58 |
2,0 1,6 |
Первомайская Ленина |
|
|
58 |
57 48 59 |
1,6 3,6 1,2 |
Бунина Вавилова С. Лазо |
|
|
59 |
49 58 |
3,8 1,2 |
Б. Солнечный Ленина |
Алгоритм расчета кратчайших расстояний
Для расчета кратчайших расстояний в настоящее время применяют математические методы. Одним из таких методов является метод «метлы». Ниже приведен алгоритм расчета кратчайших расстояний методом «метлы».
Выбирается начальная вершина сети, в расчетной таблице указывается «0» для начальной и «M» для всех остальных вершин.
Определяем длину звена, соединяющего начальную вершину с соседними и расстояние «M» заменяется на фактически меньшее.
Вершины сети последовательно проверяются сверху вниз и отмечаются знаком проверки в таблице.
Значения расстояний, полученные в результате расчета, заносятся в таблицу. Для каждой вершины из нескольких значений выбирается наименьшее.
Решение повторяется до тех пор, пока из таблицы не будут вычеркнуты все знаки проверки для вершин сети.
Повторить все предыдущие пункты для всех вершин сети, объявляя их начальными.
При определении кратчайшего маршрута движения, начиная с вершины «до», перечислить номера предыдущих вершин до вершины «от».
Расчет кратчайших расстояний на ЭВМ
Кратчайшие расстояния на ЭВМ можно рассчитать посредством специально разработанной программы «РКР», которая работает в диалоговом режиме. После всех расчетов кратчайших расстояний составляем матрицу кратчайших расстояний, в которой указываем только те пункты, между которыми осуществляются перевозки согласно заданию.
Таблица 3 - Соответствие точек графа нумерации грузовых пунктов
|
№ вершины |
3 |
1 |
2 |
5 |
33 |
36 |
19 |
12 |
17 |
|
|
№ пункта |
Г1 |
Г2 |
Г3 |
Г4 |
Г15 |
Г18 |
Г19 |
Г20 |
Г21 |
транспортный сеть расстояние программа
Таблица 4 - Матрица кратчайших расстояний
|
№ в |
Г1 |
Г2 |
Г3 |
Г4 |
Г15 |
Г18 |
Г19 |
Г20 |
Г21 |
||
|
№ в |
3 |
1 |
2 |
5 |
33 |
36 |
19 |
12 |
17 |
||
|
Г1 |
3 |
4 |
6,4 |
1,8 |
17,6 |
23,4 |
|||||
|
Г2 |
1 |
4 |
2,4 |
9,4 |
19,8 |
19,8 |
|||||
|
Г3 |
2 |
6,4 |
2,4 |
8,2 |
17,4 |
17,4 |
|||||
|
Г4 |
5 |
1,8 |
5,8 |
4,6 |
15,8 |
||||||
|
Г15 |
33 |
17,6 |
21,6 |
24 |
5,8 |
||||||
|
Г18 |
36 |
21,6 |
25,6 |
21,4 |
13,6 |
||||||
|
Г19 |
19 |
26,4 |
30,4 |
32,8 |
8,8 |
||||||
|
Г20 |
12 |
29 |
33 |
||||||||
|
Г21 |
17 |
18,6 |
22,6 |
Кратчайшие расстояния:
Г4-Г21
Г4-Г19 5-21-26-27-28-29-30-31-32-33-18-19 (17,6 км)
Г15-Г1 3-5-21-26-27-28-29-30-31-32-33 (17,6 км)
Г18-Г2
Г20-Г3
Размещено на Allbest.ru
...Подобные документы
Анализ транспортной сети и обьема перевозок. Определение кратчайших расстояний между пунктами транспортной сети, минимизация груженных и холостых пробегов. Составление кольцевых маршрутов и подвижного состава; расчет его количества и показателей работы.
курсовая работа [1,3 M], добавлен 14.03.2014Определение кратчайших расстояний между пунктами транспортной сети, проверка исходной маршрутной схемы на возможность. Расчет необходимого числа автобусов, рациональной организации их работы и составление сводного маршрутного расписания движения.
курсовая работа [361,3 K], добавлен 18.04.2011Составление модели транспортной сети и разработка исходного варианта. Улучшение исходного варианта сети и определение кратчайших расстояний. Определение маршрутов и показателей транспортной работы. Составление первоначального базисного распределения.
курсовая работа [433,8 K], добавлен 16.05.2015Выбор подвижного состава для перевозки груза. Определение кратчайших расстояний между пунктами транспортной сети. Разработка плана рациональных маршрутов. Расчет времени на выполнение погрузочно-разгрузочных работ. Маршрутная карта перевозок грузов.
курсовая работа [907,3 K], добавлен 09.04.2011Решение транспортной задачи методом линейного программирования, нахождение кратчайших расстояний. Закрепление маршрутов за АТП. Расчёт эффективности разработанного варианта перевозок. Построение эпюр и схем грузопотоков. Расчет тарифов на перевозку груза.
курсовая работа [289,9 K], добавлен 30.12.2010Выбор автотранспортных средств для перевозки грузов подвижным составом. Определение кратчайших расстояний между пунктами транспортной сети. Разработка плана рациональных маршрутов перевозки, расчет времени на выполнение погрузочно-разгрузочных работ.
курсовая работа [782,4 K], добавлен 25.12.2011Маршрутизация автомобильных и железнодорожных перевозок. Методика определения кратчайших расстояний между пунктами транспортной сети с использованием метода потенциалов. Проблемы при построении маршрутов перевозок и автоматизация транспортной логистики.
курсовая работа [183,4 K], добавлен 01.10.2015Порядок определения кратчайших расстояний между пунктами транспортной сети, составление специальной матрицы. Построение плана перевозок щебня, который обеспечивал бы минимальное значение грузооборота. Маршруты движения автомобилей без холостого хода.
практическая работа [75,7 K], добавлен 08.02.2012Определение кратчайших расстояний между грузообразующими и грузопоглощающими пунктами. Выбор подвижного состава и погрузочных механизмов по критерию максимального использования грузоподъёмности состава. Расчёт необходимого числа автомобилей самосвалов.
курсовая работа [5,8 M], добавлен 29.11.2010Определение кратчайших расстояний от пунктов погрузки до пунктов выгрузки, плана перевозок для навалочного груза. Разработка модели осуществления перевозок при заданных грузопотоках и поиск соответствующих решений для гипотетического предприятия.
курсовая работа [84,7 K], добавлен 12.03.2012- Кратчайшие расстояния между пунктами транспортной сети с использованием компьютерной программы NAKRA
Описание района перевозок и формирование транспортной сети региона. Определение кратчайших путей следования, потребности в транспорте для работы на маршрутах. Расчет технико-эксплуатационных показателей использования автомобильных транспортных средств.
курсовая работа [458,7 K], добавлен 24.01.2016 Выбор автотранспортных средств для перевозки груза, условия его упаковки и транспортирования. Определение кратчайших расстояний между пунктами. Маршрутизация перевозок; составление матрицы планов перевозки грузов и подачи подвижного состава под погрузку.
курсовая работа [2,0 M], добавлен 17.01.2014Построение графика оборота пассажирских поездов. Расчёт основных показателей пригородного пассажирского движения. Определение типа локомотива и композиции составов пассажирских поездов. Определение кратчайших расстояний между узловыми станциями полигона.
курсовая работа [165,3 K], добавлен 15.02.2013Расчет расстояний между пунктами транспортной сети, общего пробега, пробега с грузом, затрат на транспортировку; интервалов времени прибытия и отправления транспортных средств. Формирование маршрутов их движения с помощью методов Свира, "ветвей и границ".
курсовая работа [275,7 K], добавлен 09.04.2014Модель транспортной сети и расчет расстояний между грузопунктами. Правила перевозки груза навалом. Сравнительная оценка подвижного состава. Структура перевозок. Выбор типа погрузо-разгрузочного механизма. Определение оптимального плана возврата порожняка.
курсовая работа [2,7 M], добавлен 20.10.2014Проблемы развития водного транспорта Украины, логистический подход к их решению. Модели нахождения кратчайших путей: алгоритм Дейкстры, Данцинга; оптимального транспортного средства. Математическая модель оптимизации водной транспортной системы Украины.
курсовая работа [587,1 K], добавлен 07.08.2013Определение расстояний между центрами смежных стрелочных переводов. Расчет элементов сокращенного соединения двух параллельных путей. Расчет координат центров стрелочных переводов и вершин углов поворота путей. Расчет элементов круговых кривых.
курсовая работа [20,0 K], добавлен 12.11.2008Моделирование транспортной сети. Обобщенный алгоритм исследования и оптимизации. Управление и контроль потоками воздушных судов (воздушного движения). Факторы, влияющие на загруженность диспетчера. Совершенствование наземной инфраструктуры аэропорта.
курсовая работа [1,4 M], добавлен 02.11.2015Определение расстояний между центрами смежных стрелочных переводов для горловин станции, используемые при этом показатели. Расчет сокращенного соединения всех параллельных путей, координат центров стрелочных переводов и вершин углов поворота путей.
контрольная работа [502,1 K], добавлен 29.04.2019Планирование автобусных перевозок. Сущность задачи выбора схемы автобусных маршрутов в городах. Возможности повышения степени использования вместимости автобусов на схеме маршрутов. Определение кратчайших путей. Пассажиропоток по участкам сети.
реферат [676,1 K], добавлен 08.04.2011
