Определение
кратчайшего
пути между
двумя точками.
Данный метод позволяет определить кратчайший путь между 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].
Замечания.
1. Граф Х- ориентированный по способу построения. Таким образом, возможно нахождение кратчайшего маршрута на улицах с односторонним движением.
2. Общие требования-веса і 0. Веса для ребер задаются как вес пути из одной вершины в другую.
В случае минимизации длины пройденного пути веса матрицы С - расстояние между перекрестками.
В случае минимизации времени движение веса матрицы С- время езды из i в j.
Веса могут быть также заданы в соответствии с другими критериями.
3. Как правило , машины обслуживания дороги двигаются медленно , т.е. увеличивая возможность “пробки”. Поэтому применение данного метода может существенно сократить вероятность “пробок” на “опасных” улицах .
Нельзя гарантировать , что передвижение по полученному пути увеличит пропускную способность автодорог , но гарантируется ,что путь будет оптимальным - иметь минимальный вес. Таким образом , выбирая в качестве веса длину, мы получим кратчайший по длине маршрут. Если в качестве веса было выбрано время, то (при соответствии заданных данных действительности ) время езды будет минимальным. В результате этого самое заметное проявление проблемы ограниченности пропускной способности автодорог- задержки в “пробках” - будет минимизировано.
4. Так как данный алгоритм не учитывает стоимость захода на маршрут, то решение может быть не оптимальнеым относительно стоимости выхода и схода на линию автотранспорта. Алгоритм дает лишь кратчайший маршрут обхода всехребер графа. Поэтому после выдачи результата данным алгоритмом требуется найти ближайший перекресток к базе транспортных средств относительно стоимости выхода на маршрут.
Определение оптимального маршрута развозки товаров.
Данный метод вырабатывает оптимальный маршрут для обхода всех вершин графа при минимизации суммы весов пройденных ребер.
Метод может быть применен для нахождения оптимального маршрута для машин развозки товара, почты, общественного транспорта и других случаев минимизации весов пройденного пути с условием обязательного посещения всех вершин, таких как маршрут обхода выставки в музеях...
Данный метод находит оптимальный путь только для одной машины , поэтому он наиболее пригоден для использования муниципальными и коммерческими организациями для планирования маршрута внутри района или с использованием только одного транспортного средства.
При использовании данного метода множеству сегментов улиц района, подлежащего обработке сопоставляется граф Х, задаваемый по следующему правилу (матрица смежности [xij]):
Хij= 1, существует участок дороги ,соединяющий перекресток i и j (длинной в 1 квартал), подлежащий обработке.
Xij= 0, не существует такого участка дороги.
Также задается матрица весов для ребер С=[cij].
Замечания.
1. Граф Х- ориентированный по способу построения. Таким образом, возможно нахождение кратчайшего маршрута на улицах с односторонним движением.
2. Общие требования-веса і 0.
В случае минимизации длины пройденного пути веса матрицы С - расстояние между перекрестками.
В случае минимизации времени движение веса матрицы С- время езды из i в j.
Веса могут быть также заданы в соответствии с другими критериями.
Веса для ребер задаются как вес кратчайшего пути из одной вершины в другую.
Нельзя гарантировать , что передвижение по полученному пути увеличит пропускную способность автодорог , но гарантируется ,что путь будет оптимальным - иметь минимальный вес. Таким образом , выбирая в качестве веса длину, мы получим кратчайший по длине маршрут. Если в качестве веса было выбрано время, то (при соответствии заданных данных действительности ) время езды будет минимальным. В результате этого самое заметное проявление проблемы ограниченности пропускной способности автодорог- задержки в “пробках” - будет минимизировано.
В теории графов также есть алгоритмы, вырабатывающие оптимальный путь обхода всех вершин при заданных начальных и конечных вершинах.
В теории графов также есть алгоритмы, вырабатывающие оптимальный путь обхода всех вершин при нескольких автотранспортных средствах, т.е. для случая, когда можно выделить несколько транспортных средств для объезда района.
Определение оптимального положения торговых баз и складов.
Данный метод позволяет определить оптимальное местоположение заданного количества торговых баз и складов на территории города с точностью до квартала. Оптимальность выбранного положения будет заключаться в минимальном суммарном расстоянии от баз до всех пунктов назначения. Под базой в широком смысле понимается объект, являющийся одновременно исходной и конечной точкой всех маршрутов транспортных средств.
Данный метод предполагает, что транспортные средства двигаются по траектории "база" - "пункт назначения" "база", то есть с посещением только одного пункта назначения. Если допускается возможность посещения транспортными средствами более чем одного пункта назначения, то данный метод определения оптимального положения торговых баз и складов не будет давать оптимального решения такой задачи, то есть надо применять другие методы.
Входные данные и их интерпретация данным методом.
число баз, которое предполагается использовать - p.
граф Х, число вершин N которого равно числу пунктов назначения K плюс число вспомогательных точек. Матрица смежности графа Х строится по следующему правилу:
хij= 1, существует путь из i в j.
хij= 0, не существует путь из i в j. По соображениям здравого смысла следует заметить, что p<=N.
матрица С весов кратчайших путей. сij равно весу кратчайшего пути из хi в хj. Вес кратчайшего пути, как и сам кратчайший путь, может быть найден методом нахождения кратчайшего пути между двумя точками. Следует также отметить, что для нахождения кратчайшего пути следует использовать граф, с требуемой степенью точности соответствующий сети дорог города. Таким образом, в неявном виде требуется решения N*N задач нахождения кратчайших путей для нахождения весов путей графа Х.
таблицей весов вершин L, элемент li которой определяется по следующему правилу:
вершина хi не является пунктом назначения - li =1;
вершина xi является пунктом назначения - li задается важностью данного пункта доставки, 1 <= li <= k, k => 1. Значению 1 соответствует важность пункта доставки, важность которого бесконечно мала. li=k соответствует вершине, имеющей наибольшую важность. В частности, в качестве веса вершины может выступать число единиц транспортных средств, необходимых для отправки в данный пункт.
Алгоритм начинает работу с построения матрицы взвешенных расстояний В; каждому i-му столбцу матрицы В соответствует i-ый столбец матрицы C, умноженный на li.
Для нахождения оптимального положения торговых баз и складов следует воспользоваться алгоритмом решения задачи о р - медиане из теории графов. Существует несколько алгоритмов решения задач о р- медиане, в частности алгоритм направленного древовидного поиска, приближенный алгоритм Гейтца и Барта, и даже алгоритм решения данной задачи как задачи линейного программирования. Данные алгоритмы приведены здесь не будут.
Результатом решения задачи о р- медиане графа будут являться множество S , состоящее из р вершин, принадлежащих графу Х, являющихся точками оптимального положения торговых баз и складов. Также для каждой вершины из S будет задано множество вершин Н, "прикрепленных" к данной. Множество Н можно интерпретировать как множество пунктов обслуживания данной базой.
Замечания.
Исходя из специфики города , а также пунктов доставки, как объекта, можно предположить, что все элементы матрицы Х будут = 1 единице. Способ построения графа Х поэтому приведен лишь для пояснительных целей.
Если быть точнее, распределение вершин, являющееся результатом работы данного метода будет оптимальным только для перемещения транспорта от базы до пунктов назначения. Речь идет о возможной неоптимальности пути от пункта назначения до базы (возвращение). В случае, если пути из каждой точки i в точку j и пути из j в i(обратно) эквивалентны по весу, то сумма весов путей туда и обратно для всех баз и пунктов назначения будут минимальны. Если же данное условие не выполняется (участки с односторонним движением), то сумма весов обратно для всех баз и пунктов назначения может не быть минимальной.
Вычислительные аспекты алгоритмов решения задач о р- медиане могут быть существенно улучшены, если число вспомогательных вершин K ограничить. Но применять такой "метод ускорения расчетов" следует только в случае достаточно плотного скопления пунктов потребления, в силу того, что решение задачи о р- медиане дает в качестве ответа одну из введенных в исходный граф Х вершин, то есть склад должен находиться в каком-либо пункте потребления или опорной точке. В случае больших расстояний между пунктами назначения суммарный путь для К=0 может быть существенно длиннее пути с заранее расставленными вспомогательными вершинами. Один из возможных вариантов действий в этом случае будет расстановка вспомогательных вершин в областях, где пункты достаточно редки и в местах, удобных для строительства баз.
Если в качестве весов путей брать время прохождения пути автотранспортом, оптимальное распределение будет минимизировать время всех перевозок. При таком выборе веса пути простои в пробках будут минимизированы. Если в качестве веса пути была выбрана длина соответствующих маршрутов, то будет минимизировано суммарное расстояние перевозок.
Список использованных источников
Кристофедес К. Теория графов. Алгоритмический подход. М: 1978.
Кудрявцев Е.М. Исследование операций в задачах, алгоритмах и программах. М.: 1984.
I. Введение.
Постановка задачи
Проблема ограниченности пропускной способности автодорог наиболее ощутимым образом проявляет себя в так называемых мегаполисах - городах с большим населением и концентрацией жителей. Данная проблема вызывает целый спектр негативных явлений, но наиболее ощутимой из них является проблема автотранспортных пробок - и как следствие их целый комплекс подпроблем ,от экологического до социального плана.
В связи с постоянным ростом населения городов данная проблема рано или поздно станет актуальной в большинстве населенных пунктов. В связи с этим проблему ограниченности пропускной способности автодорог будем рассматривать лишь в отношении относительно крупных населенных пунктов и для настоящего времени. Результаты рассмотрения данной проблемы будут применимы в перспективе и для других населенных пунктов, в которых данная проблема в настоящий момент времени не так остра.
Взаимосвязь автодорог и города очевидна. Основными особенностями данных объектов является их большой срок службы и высокая стоимость, что органически приводит к положению о том, что данная проблема для настоящего времени может решаться при сохранении данных объектов в настоящем виде. Грубые экономические расчеты показывают, что воздействие на объекты первого типа (дороги) более предпочтительно, чем на объекты второго типа (дома), хотя тоже не безболезненно с экономической точки зрения.
Существуют различные методики решения проблем такого плана, которые условно можно разделить на экстенсивные и интенсивные. Под первыми будем понимать методики коренного изменения существующих систем, а также создание новых экземпляров систем. Под методиками второго типа (интенсивными) будем понимать приспособление к существующим системам, а также легкие, незначительные изменения в структуру рассматриваемых систем. Далее будут рассматриваться методики интенсивного, второго типа.
Как уже было сказано, проблема ограниченности пропускной способности автодорог проявляется во множестве аспектов человеческой деятельности. Негативное воздействие многих из этих воздействий объективно, а также в численном виде оценить невозможно - в частности те же проблемы экологического или социального плана. Среди воздействий, ущерб от которых может быть выражен в численной форме - это задержки в поставках отваров и прочие издержки из-за задержки в прибытии какого-либо транспорта.
Общие положения, принимаемые при рассмотрении проблемы ограниченности пропускной способности автодорог.
Далее под понятием автодорога будет подразумеваться часть дороги, по ширина которой соответствует ширине части автодороги, на которой происходит движение в одном направлении.
Под пропускной способностью участка автодороги будем понимать максимальное количество единиц автотранспорта в единицу времени (достаточно большую относительно скорости автотранспорта, чтобы не проявились флуктуации в движении автотранспорта), способное проехать по данному участку дороги при данной скорости. Пропускная способность участка дороги зависит от множества факторов, которые можно разделить на две категории - постоянные (в условиях данного подхода рассмотрения) и варьируемые.
К первой категории при рассмотрении лишь интенсивной методики рассмотрения проблемы относятся:
ширина автодороги - как уже было сказано, данный параметр может быть изменен при больших экономических (порой даже астрономических величин) затратах, поэтому считаем данный параметр постоянным;
ширина автотранспортного средства - те же замечания, что и для предыдущего пункта;
длина автотранспортного средства - те же замечания, влияет лишь на максимальную скорость передвижения по криволинейным участкам;
максимальная скорость транспортного средства - совершенно очевидно, что максимальная скорость, развиваемая потоком автотранспорта на дороге ограничена минимальной из максимальных скоростей автотранспортных средств, передвигающихся по автодороге. Здесь так же надо учитывать эффект, проявляющийся на автодорогах, ширина которых больше максимальной ширины автотранспортного средства - образование так называемых рядов, представляющих собой несколько колон автотранспортных средств, каждая из которых (колон) движется со своей скоростью, т.н. скоростью ряда.
кривизна дороги - влияет на максимальную скорость автотранспорта.
Ко второй категории - варьируемых параметров относятся следующие:
состояние покрытия дороги - оно влияет на максимальную скорость, которую может развить транспортное средство. Изменение этого параметра связано с ощутимыми экономическими расходами.
максимальная допустимая скорость передвижения автотранспортного средства - ее влияние на максимальную скорость, которую способно развить транспортное средство, мягко говоря, очевидно. Относя данный параметр к варьируемым, мы имеем ввиду предположение, что данным вопросом должны заниматься управляющие структуры.
распределение автотранспорта по автодорогам.
Задача-минимум, которая стоит у автодорог - пропускание определенного количества автотранспорта. Причем это количество зависит от времени - времени суток, дня года = дня недели, сезона, наличия праздников. Также следует отметить, что среднегодовой объем автотранспорта изменяться с годами. Что в целом делает пропускную способность автодорог конечной? Ответ - скорость передвижения автотранспорта по дороге. Если бы скорость автотранспорта на дорогах стала бы бесконечной, то пропускная способность тоже бы устремилась к бесконечности. Но по концепции, выбранной нами, скорость не есть варьируемый параметр.
Одной из простейших мер повышения пропускной способности автодорог могло быть группировка автотранспорта по скорости. Как уже было замечено выше, минимальная из максимальных скоростей автотранспортных средств и есть скорость, с которой движется транспорт по автодороге. При группировке транспортных средств по скоростям средняя максимальная скорость транспорта приближается со скоростью передвижения по автодороге. Данный метод увеличения пропускной способности уже широко применяется на практике в виде организации потока транспорта в ряды. Очевидно, что количество рядов, которые могут быть сформированы на дороге меньше или равно ширины дороги, деленной на максимальную ширину автотранспортного средства. Данный факт может быть учтен при строительстве новых дорог, хотя большое количество рядов не оправдано из-за возрастания потенциальной возможности столкновения транспорта при перемещении из одного ряда в другой.
Другой возможной мерой повышения пропускной способности автодорог является повышение лимита разрешенной максимальной скорости на автодорогах. Данный способ используется некоторыми водителями самовольно, незаконно. Повышение лимита максимальной скорости ограничено опасностью всевозможных ДТП.
Необходимо отметить еще один аспект автотранспортного движения. Цель передвижения транспортных средств в большинстве случаев - перевозка какого-либо полезного груза из одного места в другое. Из-за специфики автодорог не всегда существует дороги из какого-либо пункта в данный. Данный пункт в этом случае достигается перемещением по некоторым существующим автодорогам вплоть до пересечения (соединения) с автодорогой, на которой лежит данный пункт. В свою очередь из-за специфики города как объекта всегда существует хотя - бы одна дорога в любой выбранный потенциальный пункт назначения/отправки. При данных обстоятельствах совершенно очевидно, что некоторое снижение пропускной способности автодорог возможно из-за неоптимального перемещения автотранспорта по автодорогам в условиях существования нескольких альтернативных маршрутов передвижения. Именно оптимизации передвижения автотранспорта по существующей системе дорог и посвящены большинство разделов данной работы.
Общие особенности подхода методов этой работы.
Итак, данная работа посвящена методам оптимального распределения потока транспорта по сети автодорог. Основной особенностью данного подхода является его нетребовательность к финансам. Методы, рассмотренные в данной работе, не заключаются как в полном сносе города и постройке широких высокоскоростных дорог, так и их ремонта. Они заключаются в реорганизации потока транспорта в соответствии с оптимальными маршрутами, полученными в результате применения алгоритмов теории графов. Данные методы могут быть адаптированы и использованы как ответственной за разрешение поставленной проблемы организацией, так и коммерческими структурами со значительным грузо- и товарооборотом - но не в целях увеличения пропускной способности, а в целях сокращения транспортных расходов - таким образом эти методы универсальны и пригодны для решения целого спектра задач.
Следует также отметить, что методы, будучи интенсивными по свой природе будут иметь предел применения, и на некотором этапе развития города возможно применение экстенсивных методов, таких как постройка новой дороги и ремонт части старых. Предел этих методов будет достигнут при тотальном их использовании. Если после их тотального применения пропускная способность некоторых автодорог будет недостаточна, то возникнет необходимость применения экстенсивных методов. Также следует отметить, что для применения методов данной работы требуемом количестве необходима достаточно точная информация. Кроме того, алгоритмы теории графов, применяемые приведенными методами, при объеме информации о достаточно большом городе будут требовать вычислительные мощности современных компьютеров класса main-frame или выше.
II. Методы устранения проблемы
Международный институт рынка
Кафедра менеджмента
Курсовая работа
по менеджменту
на тему:
Проблема ограниченности пропускной способности автодорог.
выполнили студенты гр. М21: Харчев В.В.
гр. М22: Ефимов Р..,
Звягин М. .,
Манахова Е..
преподаватель: Маркелов ?.?.
Самара 1997
Международный институт рынка
Кафедра менеджмента
Реферат по курсовой работе
по предмету менеджмент
тема курсовой работы:
Проблема ограниченности пропускной способности автодорог.
выполнили студенты гр. М21: Харчев В.В.
гр. М22: Ефимов Р..,
Звягин М. .,
Манахова Е..
преподаватель: Маркелов ?.?.
Самара 1997
Ключевые слова: пробки, логистика, логистические центры, маршруты, критический путь, торговые базы и склады, мегаполисы, автотранспорт, транспорт, город.
Реферативная заметка: Данная работа посвящена проблемам ограниченности пропускной способности автодорог и методам, с помощью которых можно снизить вероятность появления автомобильных пробок. Основной подход методов, приводимых в работе - подстройка под существующее положение и вещей и решение проблемы за счет изменения лишь маршрутов транспортных средств. Алгоритмы нахождения оптимальных маршрутов в данной работе основаны на алгоритмах теории графов. Некоторые методы данной работы направлены на минимизацию транспортных расходов торговых баз и складов.
Авторство частей данной работы:
часть 1 - введение - совместные усилия всех авторов данной работы
часть 2 - Определение кратчайшего пути между двумя точками - автор: Манахова Е.
часть 3 - Определение оптимального маршрута машин для обслуживания дороги - автор: Звягин М.
часть 4 - Определение оптимального маршрута развозки товаров - автор: Ефимов Р.
часть 5 - Определение оптимального положения торговых баз и складов - автор: Харчев В.
Содержание:
I Введение
Постановка задачи
Общие положения, принимаемые при рассмотрении проблемы ограниченности пропускной способности автодорог.
Общие особенности подхода методов этой работы.
II Методы устранения проблемы
Определение кратчайшего пути между двумя точками
Определение оптимального маршрута машин для обслуживания дороги
Определение оптимального маршрута развозки товаров
Определение оптимального положения торговых баз и складов
29-04-2015, 04:09