Задача проектирования городской транспортной сети

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

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

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

Рассмотрим алгоритм (последовательность действий) ее решения.

1. На плане города с границами районов отмечают важнейшие узлы (площади) массового формирования пассажиропотоков; осуществляют ранжирование пассажирообразующих узлов (пунктов) по ожидаемым трудовым и культурно-бытовым поездкам и выявляют их примерный объем (спрос на перевозки).

• 2. Определяют первоочередные кратчайшие транспортные связи (маршруты) по перевозке пассажиров в часы пик (к местам приложения труда), а также связи районов с железнодорожными (речным, морским, автомобильным) вокзалами, рынками, станциями метрополитена и др.
• 3. Территорию городских районов разбивают на микрорайоны и устанавливают первоочередные конечные пункты автобусных маршрутов. Выявляют первоочередность прямых транспортных связей между отдельными конечными пунктами как для трудовых, так и культурно-бытовых поездок.
• 4. Устанавливают наиболее важные промежуточные узлы большой сменяемости пассажиров между конечными пунктами основных автобусных маршрутов, производят выбор и обоснование рациональных вариантов ожидаемой трассы маршрута.
• 5. Определяют примерное ожидаемое распределение пассажиропотока по промежуточным узловым пунктам автобусных маршрутов. Составляют примерную матрицу ожидаемых корреспонденций пассажиров между конечными и промежуточными пунктами автобусных маршрутов во времени суток. Выявляют рациональную маршрутную систему автобусного транспорта города, имеющую наибольшую прямолинейность маршрутов и минимальный коэффициент пересадочности.

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

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

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

Рассмотрим неориентированный связный граф: С = {V, Е, /?}, в котором V =^, г₂,…, оЛ — конечное множество вершин, Е = {е₁, е₂>—, е,₁} — конечное множество реоер, И — весовая функция ребер. Для математической постановки задачи удобно обозначить отдельные значения весовой функции ребер через ц, =Ь (е_к), где ребро е_кеЕ соответствует паре вершин V.

Согласно содержательной постановке рассматриваемой задачи отдельные значения c_i j =/?(?', а_;) могут интерпретироваться как затраты времени пассажиров на передвижение по участку (?, 7) исходного графа.

Стоимость любого подмножества ребер Е_к в графе С равна сумме весов ребер, входящих в это подмножество. Требуется определить такое подмножество ребер, которое образует покрывающее или остовное дерево в графе С и обладает минимальной стоимостью.

Для формальной записи условий задачи о минимальном покрывающем дереве в графе в виде модели булева программирования следует воспользоваться двумя условиями покрывающего дерева в графе.

• 1. Каждая из вершин исходного графа должна иметь хотя бы одно инцидентное ей ребро, входящее в минимальное покрывающее дерево. В противном случае такие вершины в искомом дереве окажутся изолированными, и, следовательно, дерево не будет являться покрывающим.
• 2. Общее количество ребер в минимальном покрывающем дереве должно быть в точности равно п — 1, где п — общее количество вершин исходного 1рафа. Действительно, если некоторое дерево содержит меньше п — 1 ребер, то оно не будет покрывающим, если же дерево содержит более п — 1 ребер, то оно будет содержать цикл.

Введем в рассмотрение т булевых переменных, которые для удобства обозначаются через x-_t j и интерпретируются следующим образом. Переменная Xjj = 1, если ребро е_к еЕ, которому соответствует пара вершин {v^Vj}, входит в искомое покрывающее дерево минимальной стоимости, и х_х} =0 в противном случае, т. е. если ребро {Vj,V-.} не входит в оптимальное покрывающее дерево. Заметим, что количество рассматриваемых булевых переменных конечно и равно т, где т — количество ребер исходного графа.

Тогда математическая постановка задачи о минимальном покрывающем дереве в графе может быть сформулирована следующим образом.

Найти минимум целевой функции.

при ограничениях.

Первые три ограничения в системе ограничений (9.6) требуют выполнения первого из отмеченных ранее свойств, т. е. в искомом покрывающем дереве не должно быть изолированных вершин. Четвертое ограничение в системе (9.6) требует выполнения второго из отмеченных ранее свойств, т. е. искомое покрывающее дерево должно содержать ровно п — 1 ребер. Наконец, последнее ограничение в системе (9.6) требует, чтобы переменные принимали только булевы значения.

Методика решения задачи о минимальном покрывающем дереве в графе рассматривается в специальной литературе по исследованию операций^[1].

Контрольные вопросы и задания

• 1. Что называют сетью, цепью, циклом, путем, контуром, графом?
• 2. Дайте определение понятий «дерево», «остовное связующее дерево», «кратчайший остов графа» и «максимальный остов графа».
• 3. Дайте определение потока. Каково условие сохранения потока в узлах сети?
• 4. Дайте содержательную и математическую постановку задачи выбора кратчайшего пути.
• 5. Дайте содержательную и математическую постановку задачи коммивояжера.
• 6. Дайте содержательную и математическую постановку задачи о максимальном потоке.
• 7. Каковы особенности решения задачи о многополюсном максимальном потоке?
• 8. Охарактеризуйте задачу проектирования городской транспортной сети и подходы к ее решению.
• 9. Дайте содержательную и математическую постановку задачи о максимальном покрывающем дереве в графе.

• [1] См. наир.: Греишлов А. А. Математические методы принятия решений; Леоиенков А. В. Решение задач оптимизации в среде MS Excel.