Проблемы ограниченности пропускной способности автодорог

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

Данный метод позволяет определить кратчайший путь между 2-мя точками в городе.

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

Использование данного метода подразумевает существование пути из конечного пункта в начальный как такового.

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

При использовании данного метода множеству сегментов улиц города сопоставляется граф Х, вершинами которого являются точки пересечения/соединения сегментов улиц города. Ребра графа Х задаются по следующему правилу (матрица смежности):

Хij= 1, существует участок дороги, соединяющий перекрестки i и j (длинной в 1 квартал), пригодный для проезда данного транспорта.

Хij= 0, не существует таких участков дорог.

Также задается матрица весов для ребер С=[cij]. Пример задания графа автодорог населенного пункта - см. рис 1.

Далее для нахождения кратчайшего пути используется один из алгоритмов нахождения кратчайшего пути из теории графов, например алгоритм Дейкестры. При наличии отрицательных значенияй фактора можно использовать алгоритм Форда: Мура и Беллмана.

Замечания.

1. Граф Х- ориентированный по способу построения. Таким образом , возможно нахождение кратчайшего пути на улицах с односторонним движением.

2. Возможные варианты задания весов дуг.

В случае минимизации длины пройденного пути веса матрицы С- расстояние между перекрестками.

В случае минимизации времени движение веса матрицы С- время езды из i в j.

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

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

Нельзя гарантировать , что передвижение по полученному пути увеличит пропускную способность автодорог , но гарантируется ,что путь будет оптимальным -иметь минимальный вес. Таким образом , выбирая в качестве веса длину ,мы получим кратчайший по длине маршрут. Если в качестве веса было выбрано время ,то (при соответствии заданных данных действительности ) время езды будет минимальным. В результате этого самое заметное проявление проблемы ограниченности пропускной способности автодорог- задержки в “пробках” - будет минимизировано.

В случае, если требуется определить кратчайшие пути между всеми перекрестками населенного пункта: следует применять специальные дополнения к алгоритму Дейкестры, а также алгоритм Флойда.

Определение оптимального маршрута машин для обслуживания дороги.

Данный метод вырабатывает оптимальный маршрут для обхода всех ребер графа как минимум по 1 разу при минимизации суммы весов пройденных ребер.

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

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

При использовании данного метода множеству сегментов улиц района, подлежащего обработке сопоставляется граф Х, задаваемый по следующему правилу (матрица смежности [xij]):

Хij= 1, существует участок дороги ,соединяющий перекресток i и j (длинной в 1 квартал), подлежащий обработке.

Xij= 0, не существует такого участка дороги.

Также задается матрица весов для ребер С=[cij].

Пример задания маршрута на графе автодорог населенного пункта - см. рис 2.

Замечания.

1. Граф Х- ориентированный по способу построения. Таким образом, возможно нахождение кратчайшего маршрута на улицах с односторонним движением.

2. Общие требования-веса і 0. Веса для ребер задаются как вес пути из одной вершины в другую.

В случае минимизации длины пройденного пути веса матрицы С - расстояние между перекрестками.

В случае минимизации времени движение веса матрицы С- время езды из i в j.

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

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

Нельзя гарантировать , что передвижение по полученному пути увеличит пропускную способность автодорог , но гарантируется ,что путь будет оптимальным - иметь минимальный вес. Таким образом , выбирая в качестве веса длину, мы получим кратчайший по длине маршрут. Если в качестве веса было выбрано время, то (при соответствии заданных данных действительности ) время езды будет минимальным. В результате этого самое заметное проявление проблемы ограниченности пропускной способности автодорог- задержки в “пробках” - будет минимизировано.

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

Определение оптимального маршрута развозки товаров.

Данный метод вырабатывает оптимальный маршрут для обхода всех вершин графа при минимизации суммы весов пройденных ребер.

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

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

При использовании данного метода множеству сегментов улиц района, подлежащего обработке сопоставляется граф Х, задаваемый по следующему правилу (матрица смежности [xij]):

Хij= 1, существует участок дороги ,соединяющий перекресток i и j (длинной в 1 квартал), подлежащий обработке.

Xij= 0, не существует такого участка дороги.

Также задается матрица весов для ребер С=[cij].

Пример задания маршрута на графе автодорог населенного пункта - см. рис 3.

Замечания.

1. Граф Х- ориентированный по способу построения. Таким образом, возможно нахождение кратчайшего маршрута на улицах с односторонним движением.

2. Общие требования-веса і 0.

В случае минимизации длины пройденного пути веса матрицы С - расстояние между перекрестками.

В случае минимизации времени движение веса матрицы С- время езды из i в j.

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

Веса для ребер задаются как вес кратчайшего пути из одной вершины в другую.

Нельзя гарантировать , что передвижение по полученному пути увеличит пропускную способность автодорог , но гарантируется ,что путь будет оптимальным - иметь минимальный вес. Таким образом , выбирая в качестве веса длину, мы получим кратчайший по длине маршрут. Если в качестве веса было выбрано время, то (при соответствии заданных данных действительности ) время езды будет минимальным. В результате этого самое заметное проявление проблемы ограниченности пропускной способности автодорог- задержки в “пробках” - будет минимизировано.

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

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

Определение оптимального положения торговых баз и складов.

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

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

Входные данные и их интерпретация данным методом.

число баз, которое предполагается использовать - p.

граф Х, число вершин N которого равно числу пунктов назначения K плюс число вспомогательных точек. Матрица смежности графа Х строится по следующему правилу:

хij= 1, существует путь из i в j.

хij= 0, не существует путь из i в j. По соображениям здравого смысла следует заметить, что p