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

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

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

• число баз, которое предполагается использовать - 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. Исходя из специфики города , а также пунктов доставки, как объекта, можно предположить, что все элементы матрицы Х будут = 1 единице. Способ построения графа Х поэтому приведен лишь для пояснительных целей.

2. Если быть точнее, распределение вершин, являющееся результатом работы данного метода будет оптимальным только для перемещения транспорта от базы до пунктов назначения. Речь идет о возможной неоптимальности пути от пункта назначения до базы (возвращение). В случае, если пути из каждой точки i в точку j и пути из j в i(обратно) эквивалентны по весу, то сумма весов путей туда и обратно для всех баз и пунктов назначения будут минимальны. Если же данное условие не выполняется (участки с односторонним движением), то сумма весов обратно для всех баз и пунктов назначения может не быть минимальной.

3. Вычислительные аспекты алгоритмов решения задач о р- медиане могут быть существенно улучшены, если число вспомогательных вершин K ограничить. Но применять такой "метод ускорения расчетов" следует только в случае достаточно плотного скопления пунктов потребления, в силу того, что решение задачи о р- медиане дает в качестве ответа одну из введенных в исходный граф Х вершин, то есть склад должен находиться в каком-либо пункте потребления или опорной точке. В случае больших расстояний между пунктами назначения суммарный путь для К=0 может быть существенно длиннее пути с заранее расставленными вспомогательными вершинами. Один из возможных вариантов действий в этом случае будет расстановка вспомогательных вершин в областях, где пункты достаточно редки и в местах, удобных для строительства баз.

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

Список использованных источников

1. Кристофедес К. Теория графов. Алгоритмический подход. М: 1978.

2. Кудрявцев Е.М. Исследование операций в задачах, алгоритмах и программах. М.: 1984.

I. Введение.

Постановка задачи

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

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

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

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

Как уже было сказано, проблема ограниченности пропускной способности автодорог проявляется во множестве аспектов человеческой деятельности. Негативное воздействие многих из этих воздействий объективно, а также в численном виде оценить невозможно - в частности те же проблемы экологического или социального плана. Среди воздействий, ущерб от которых может быть выражен в численной форме - это задержки в поставках отваров и прочие издержки из-за задержки в прибытии какого-либо транспорта.

Общие положения, принимаемые при рассмотрении проблемы ограниченности пропускной способности автодорог.