Санкт-Петербургский государственный университет
Прикладная математика и информатика
Исследование операций и принятие решений в задачах оптимизации,
управления и экономики
Яковенко Дарья Максимовна
Построение плана ремонта городских дорог
Бакалаврская работа
Научный руководитель:
д. ф-м. н., профессор Романовский И.В.
Рецензент:
к. ф.-м. н., доцент Григорьева Н.С.
Санкт-Петербург
2016
SAINT-PETERSBURG STATE UNIVERSITY
Applied Mathematics and Computer Science
Operation Research and Decision Making in Optimisation, Control and Economics
Problems
Iakovenko Daria
Construction of a plan of city road reconstructions
Bachelor’s Thesis
Scientific supervisor:
professor Joseph Romanovsky
Reviewer:
docent Natalia Grigorieva
Saint-Petersburg
2016
Оглавление
1.
2.
3.
4.
5.
6.
7.
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Транспортная задача и некоторые способы нахождения ее решения
Применение метода Брэгмана к транспортной задаче в сетевой
постановке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Модификация метода Брэгмана . . . . . . . . . . . . . . . . . . .
Моделирование ремонта дорог на примере г. Кронштадт . . . . .
5.1.
Ремонт Цитадельской дороги . . . . . . . . . . . . . . . . .
5.2.
Ремонт ул. Мартынова . . . . . . . . . . . . . . . . . . . . .
5.3.
Ремонт Макаровской ул. . . . . . . . . . . . . . . . . . . . .
5.4.
Ремонт Красной ул. . . . . . . . . . . . . . . . . . . . . . .
5.5.
Ремонт Советской ул. . . . . . . . . . . . . . . . . . . . . .
Выводы и рекомендации по построению плана ремонта дорог города Кронштадт . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Приложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
4
4
7
11
12
14
16
18
20
22
24
29
1.
Введение
В декабре 2015 года Комитет по развитию транспортной инфраструктуры СанктПетербурга утвердил план ремонта городских дорог на 2016 год. По мнению,
высказанному в газете [5], сроком начала работ будет лето, а самый разгар
работ придется на осень, во время завершения поры отпусков. Из-за этого ситуация на дорогах осложнится, могут возникнуть пробки. Целью этой работы
является составление плана ремонта городских дорог, такого, который позволит
предотвратить, насколько это возможно, затруднения движения, возникающие
на дорогах города при проведении ремонта.
Для составления плана ремонта городских дорог необходимо знать или уметь
моделировать дорожную ситуацию, а также уметь моделировать изменение дорожной ситуации в случае, если та или иная дорога будет перекрыта на ремонт.
В данной работе моделирование производится при помощи метода Брэгмана,
применяемого к транспортной задаче в сетевой постановке.
Мы будем рассматривать два способа закрыть дорогу на ремонт: первый —
дорога перекрывается полностью, движение по ней останавливается; второй —
дорога перекрывается частично (например, две из четырех полос четырехполосной дороги), движение по ней продолжается, но ограничивается. Для того,
чтобы моделировать второй случай, была придумана модификация известного
в транспортном моделировании метода Брэгмана, которая учитывает ограничения на пропускную способность дороги.
В этой работе описывается метод сравнения вариантов расписания в ограниченной части города, который описывается с использованием дорожной сети
города Кронштадт. Данные взяты из Интернета.
2.
Транспортная задача и некоторые способы нахождения ее решения
Транспортная задача — это задача о перевозке грузов из пунктов производства в пункты потребления с минимальными затратами на перевозку. Задача
рассматривается в матричной и в сетевой постановке.
При матричной постановке транспортной задачи даны положительные числа N и M — количество пунктов производства и потребления соответственно, а
4
также положительные векторы A = (ai )I , B = (bj )J , где I = 1 : N , J = 1 : M .
Каждый элемент ai вектора A соответствует количеству груза, отправляемого из i-го пункта производства, а элемент bj вектора B соответствует количеству груза, который требуется j-му пункту потребления. Часто накладывается
дополнительное требование того, что сумма всего производимого груза равна
P
P
сумме всего потребляемого груза: i∈I ai = j∈J bj . Если транспортная задача
удовлетворяет этому требованию, ее называют замкнутой.
Кроме того задана положительная матрица C = ||cij ||I,J , элемент cij которой
равен цене за перевозку единицы груза из i-го пункта производства в j-й пункт
потребления.
Требуется найти матрицу перевозок X = ||xi,j ||I,J , элемент xij которой равен количеству груза, перевозимого из i-го пункта производства в j-й пункт
потребления. Ясно, что нужно получить такую матрицу X, что
X
X
xij = ai ,
xij = bj ,
j∈J
i∈I
то есть сумма грузов, вывозимых из i-го пункта производства равна количеству
груза, произведенному в этом пункте, и сумма грузов, ввозимых в j-й пункт
потребления равна потребности этого пункта.
Сетевая постановка отличается от матричной тем, что в ней может не быть
дороги между некоторыми пунктами потребления и некоторыми пунктами производства. Кроме того, могут присутствовать промежуточные пункты, которые
ничего не производят и ничего не потребляют. В сетевой постановке транспортной задачи дан граф G = hV, Ei с M дугами и N вершинами, дуги которого
отображают дороги. Для каждой дуги известна цена перевозки по ней единицы
груза. Также задан вектор b = (bi )I , I = 1 : N , который отображает потребности вершин: если bi < 0, то i-я вершина — производитель, который производит
−bi единиц груза, если bi > 0, то i-я вершина — потребитель, которому необходимо bi единиц груза, если bi = 0, то i-я вершина является промежуточной: не
является ни производителем, ни потребителем. Требование того, чтобы сумма
производимых грузов была равна сумме потребляемых, для этой задачи выгляP
дит так: i∈I bi = 0.
Требуется найти вектор x = (xj )J , J = 1 : M потоков на дугах, элемент
xj которого равен количеству груза, перевозимого по j-й дуге. Этот вектор
5
должен удовлетворять требованию того, чтобы сумма ввозимых и вывозимых
P
из вершины i грузов была равна bi . То есть k∈J aik xk = bi для любого i ∈ I,
где A = ||aik ||I,J — матрица инциденций графа G.
Один из методов, которым можно решать транспортную задачу в матричной
постановке, был предложен ленинградским архитектором Г.В. Шелейховским.
Г.В. Шелейховский рассматривал замкнутую задачу, в которой вместо матрицы цен перевозки грузов по дорогам C = ||cij ||I,J задана матрица W = ||wij ||I,J
“весов” дорог. Решение, полученное при помощи метода Шелейховского, не минимизирует цену перевозки грузов по дорогам, но обладает другим интересным
свойством.
Алгоритм метода Шелейховского выглядит так:
• X := W ;
• Для каждого i ∈ I нормируем i-ю строку матрицы X:
P
находим S := j∈J xij /ai , назначаем xij = xij /S, j ∈ J.
• Для каждого j ∈ J нормируем j-й столбец матрицы X:
P
находим S := i∈I xij /bj , назначаем xij = xij /S, i ∈ I.
• Если S 6= 1 для какого-то j, возвращаемся к шагу 2.
И. В. Романовский заметил, что решение, полученное при помощи метода Шелейховского, максимизирует взвешенную энтропию, а сходимость этого
алгоритма была доказана Львом Мееровичем Брэгманом в 1966 году, тогда аспирантом матмеха ЛГУ.
Теорема 1 Если мы решаем задачу максимизации взвешенной энтропии с
транспортными ограничениями:
X
xij × ln(wij /xij ) → max
i,j
X
ai =
i∈I
X
bj
j∈J
и метод Шелейховского сходится, он сходится к оптимальному решению.
Доказательство этой теоремы можно найти в [3].
6
Чуть позже Брэгманом было представлено обобщение метода Шелейховского для произвольных линейных ограничений.
Теорема 2 (Брэгман, 1966) Если мы решаем задачу максимизации взвешенной энтропии с линейными ограничениями:
X
xi × ln(wi /xi ) → max
i
X
aik xk = bi
(1)
k∈J
где новое приближение вычисляется по формуле
x∗k = exp(λ × aik )xk ,
λ — единственное решение уравнения
X
aik exp(λ × aik )xk = bi ,
(2)
(3)
k∈J
и алгоритм сходится, то он сходится к оптимальному решению.
Подробно об этом написано в [2].
За прошедшее время метод Брэгмана стал всемирно признан. В рамках этой
работы рассматривается применение метода Брэгмана к транспортной задаче
в сетевой постановке.
3.
Применение метода Брэгмана к
транспортной задаче в сетевой постановке
Применяя метод Брэгмана к транспортной задаче в сетевой постановке, будем
моделировать движение по дорогам города.
Считаем, что задан граф G = hV, Ei с M дугами и N вершинами, дуги которого отображают дороги. Задан вектор b = (bi )I потребностей вершин, где
bi < 0, если из i-й вершины выезжает −bi автомобилей, bi > 0, если в i-ю вершину въезжает bi автомобилей и bi = 0 для промежуточных вершин. Задан
вектор w = (wj )J положительных “весов” дуг. Пусть A = ||aij ||I,J — матрица
7
инциденций графа G. Требуется найти вектор x = (xj )J потоков машин на дугах. Линейные ограничения, которым должны удовлетворять элементы вектора
x, выглядят так:
X
aik xk = bi для любого i ∈ I
k∈J
и новое приближение вычисляется по формулам (2), (3).
Рассмотрим подробнее уравнение (3). Поскольку матрица A — это матрица
инциденций графа, ее элементы aik могут принимать только значения 0, 1, и
−1. А значит, уравнение можно записать в виде
X
X
eλ xk −
e−λ xk = bi ,
(4)
k∈K1
k∈K−1
где K1 — множество таких k, что aik = 1, K−1 — множество таких k, что
aik = −1.
Вынесем eλ и e−λ за знаки суммирования:
X
X
λ
−λ
e
xk − e
xk = bi .
k∈K1
Обозначим
+
k∈K1 xk за S и
P
k∈K−1
P
k∈K−1
xk за S − , получим:
eλ S + − e−λ S − = bi .
Домножив на eλ , получим
e2λ S + − S − = eλ bi .
Перенесем eλ bi в левую часть неравенства и произведем замену переменной
eλ = t, получим уравнение относительно переменной t
t2 S + − tbi − S − = 0.
Предположим, что
S − 6= 0.
S + 6= 0,
Тогда корнями этого уравнения являются
p
p
bi − b2i + 4S + S −
bi + b2i + 4S + S −
,
t2 =
.
t1 =
2S +
2S +
8
(5)
Корень t2 нас не интересует, поскольку eλ не может принимать неположительные значения. Проведем обратную замену и получим ответ
p
b2i + 4S + S −
λ
.
e =
2S +
Новое приближение вычисляется по формуле (2). Поскольку aik могут принимать только значения 1, −1 и 0, элемент x∗k нового приближения будет равен
xk , полученному на предыдущем шаге, если aik = 0, будет равен eλ xk , если
aik = 1 и, наконец, будет равен e−λ xk , если aik = −1.
Уравнение решалось в предположении, что S + 6= 0 и S − 6= 0 В случае
bi +
S − 6= 0
S + = 0,
уравнение 5 принимает вид
−tbi − S − = 0.
При bi 6= 0 его решением является
t=−
S−
.
bi
Проверим, будет ли оно положительным. Условие S + = 0 означает, что суммарный поток по всем входящим в i-ю вершину дугам равен нулю. Поскольку
все потоки положительны, это означает также, что поток по каждой входящей
дуге равен нулю. По предположению S − 6= 0. Поскольку потоки на дугах удовлетворяют равенству (1) для каждого i ∈ I, а S − — это сумма потоков на
P
таких дугах, что aik = −1, то равенство (1) принимает вид k∈K−1 −xk = bi .
Поскольку потоки на дугах положительны, bi < 0.
С точки зрения модели условия S − 6= 0 и S + = 0 означают соответственно,
что в i-ю вершину не въезжает никаких машин, но какие-то выезжают. Значит,
машины, которые движутся по исходящим дугам, выезжают на дороги непосредственно из вершины i, то есть вершина i в терминах транспортной задачи
является производителем.
Полученное решение положительно, можем провести обратную замену.
S−
e =− .
bi
λ
Осталось разобраться со случаем S + 6= 0 и S − = 0 (случай S + = 0 и S − = 0
9
является вырожденным и соответствует изолированной вершине, его рассматривать не будем). Уравнение (5) принимает вид
t2 S + − tbi = 0.
Его корни
bi
,
t2 = 0.
S+
Корень t2 = 0 нам не подходит. Подходит ли корень t1 ?
Условие S − = 0 означает, что сумма потоков по исходящим дугам равна
нулю, т. е. все потоки по исходящим дугам равны нулю, а условие S + 6= 0 означает, что сумма потоков по входящим дугам положительна. Поскольку потоки
P
на дугах удовлетворяют равенству (1) для каждого i ∈ I, S + = k∈K1 xk , а K1
— это множество таких индексов, что aik = 1, то равенство (1) принимает вид
P
k∈K1 xk = bi . Потоки на дугах положительны, значит, bi > 0.
С точки зрения модели из i-й вершины не выезжает никаких машин, но
некоторые въезжают. Въезжающие машины не двигаются дальше, а остаются
в вершине i. В терминах транспортной задачи она потребитель.
Полученное решение положительно, значит, можем провести обратную замену:
bi
eλ = + .
S
Таким образом, решением уравнения (4) является
t1 =
eλ =
√
bi + b2i +4S + ·S −
, если S + 6= 0 и S − 6= 0;
2S +
S−
(6)
−
если S + = 0 и S − 6= 0;
bi ,
bi ,
если S + 6= 0 и S − = 0.
S+
P
P
где S + = k∈K1 xk и S − = k∈K−1 xk , K1 — множество таких k, что aik = 1,
K−1 — множество таких k, что aik = −1.
Алгоритм, которым будем решать транспортную задачу в сетевой постановке, можно описать так:
1. x := w;
2. Для каждого i ∈ I находим новое приближение x по формуле (2), где λ
вычисляется по (6);
10
3. Повторять шаг 2, пока значения элементов вектора x не перестанут меняться.
Итак, метод Брэгмана можно успешно применять для моделирования движения на дорогах. Необходимо понять, можно ли его применить для моделирования ситуации ремонта дорог.
Существует два варианта закрытия дороги на ремонт:
• Дорога полностью закрывается на ремонт. В этом случае мы просто выкидываем соответствующие ей дуги из графа.
• Дорога закрывается на ремонт частично (например, на четырехполосной
дороге перекрывается движение по двум из четырех полос). В этом случае
соответственно уменьшается пропускная способность дороги.
В первом случае по данному графу G можно построить граф G0 , в котором отсутствуют дуги, соответствующие закрытым на ремонт дорогам, и решить задачу на полученном графе G0 методом Брэгмана. Для второго случая
необходимо модифицировать метод Брэгмана так, чтобы потоки на дугах не
превышали заданной пропускной способности.
4.
Модификация метода Брэгмана
Задан граф G = hV, Ei с M дугами и N вершинами, A = ||aij ||I,J — его матрица
инциденций, заданы вектор b = (bi )I потребностей вершин, вектор w = (wj )J
положительных “весов” дуг, вектор r = (rj )J ограничений на дугах. Требуется найти вектор x = (xj )J , удовлетворяющий линейным ограничениям (1) и
условию xj 6 rj для любого j ∈ J.
На первом шаге, как ранее, положим x := w. Далее будем пересчитывать
значения вектора x по (2), где λ вычисляется по (6), с одним отличием: как только поток на дуге превышает пропускную способность, назначим его в точности
равным пропускной способности, а “излишек” распределим по дугам, инцидентным рассматриваемой вершине и идущим в ту же сторону, что и ограниченная
дуга.
Более формально это можно записать так. Пусть при рассмотрении вершины i0 поток на дуге j0 превысил ее пропускную способность: xj0 > rj0 . Найдем
11
x̂j0 — величину, на которую поток превышает пропускную способность: x̂j0 =
xj0 − rj0 . Назначим поток на дуге равным пропускной способности: xj0 := rj0 .
Величину x̂j0 распределим по дугам, инцидентным вершине i0 , и идущим в том
же направлении, что дуга j0 : если i0 — начало дуги j0 , распределим x̂j0 по дугам с началом в i0 . Если i0 — конец дуги j0 , распределим x̂j0 по дугам, концом
которых является i0 (чтобы найти такие дуги, рассмотрим строку i0 матрицы
инциденций A и выберем все такие j ∈ J, что ai0 j = ai0 j0 ).
Распределяя x̂j0 , необходимо помнить, что на других дугах тоже важно не
превысить пропускную способность. Пусть есть s дуг jl1 , . . . , jls , инцидентных
вершине i0 и направленных в ту же сторону, что и дуга j0 . Выберем среди них
s1 дуг jl1 , . . . , jls1 таких, что поток на них строго меньше пропускной способx̂
ности. Попробуем поровну распределить x̂j0 между ними: найдем величину sj10
и попробуем прибавить ее к потоку на каждой из дуг jl1 , . . . , jls1 . Если полученный поток на каждой из дуг jl1 , . . . , jls1 не превышает пропускную способx̂
ность, назначаем поток на этих дугах равным сумме исходного и величины sj10 ,
считаем, что дуга j0 обработана и переходим к рассмотрению следующей дуги.
Если на каких-то дугах полученный поток превышает пропускную способность,
выберем среди дуг jl1 , . . . , jls1 s2 таких, на которых не превышает. Попробуем
x̂
распределить x̂j0 между ними: найдем величину sj20 и попробуем прибавить ее к
потоку на каждой из дуг jl1 , . . . , jls2 и так далее, пока на итерации p не найдем
x̂
подмножество из sp дуг, прибавление к потоку на которых значения sjp0 сделает
поток не большим, чем пропускная способность этих дуг. Если найти непустое
множество из sp дуг не удастся, назначим поток на дуге j0 равным rj0 + x̂j0 , то
есть большим пропускной способности.
5.
Моделирование ремонта дорог на примере г.
Кронштадт
Была написана программа на языке C], реализующая метод Брэгмана и его
модификацию. Моделирование дорожной ситуации производится на примере
города Кронштадт.
Дороги Кронштадта отображены графом со 113 вершинами и 330 дугами,
дуги которого — это дороги, а вершины — перекрестки.
12
Рис. 1: Граф, отображающий дороги Кронштадта
Вектор потребностей вершин b задавался произвольно, все элементы вектора “весов” дорог w равны между собой, все элементы вектора ограничений r
изначально равны очень большому числу M , которого потоки на дугах гарантированно не достигнут.
Понятно, что для более реальных результатов необходимы данные о настоящих дорогах Кронштадта: вектор w должен зависеть от длины, ширины дороги, дорожного покрытия и прочих параметров. Значение wj должно быть
тем больше, чем дорога j в некотором смысле “популярнее”. Вектор b должен
отображать реальные перемещения машин внутри города. Вектор r должен зависеть от количества полос на дороге, дорожного покрытия, погодных условий
и прочего.
В данной работе рассмотрены два варианта ремонта дороги: первый — дорога полностью перекрывается на ремонт (интересно, что одинаковые результаты
получаются при применении метода Брэгмана для графа, из которого удалены
дуги, соответствующие дороге, и при применении модифицированного метода
Брэгмана, если дугам, соответствующим дороге, назначена пропускная способность 0). Второй вариант — дорога перекрывается на ремонт частично. Для
того, чтобы реализовать этот вариант, в данной работе по дороге “пропускается” в два раза меньше машин, чем едет обычно: была запущена программа
для исходного графа, посчитан поток на каждой из дуг. В случае, когда дорога перекрывается на ремонт, ее пропускная способность назначается равной
13
половине от потока в исходном графе.
Для того, чтобы отобразить изменение дорожной ситуации при закрытии
на ремонт той или иной дороги, дуги графа в иллюстрациях раскрашиваются
в разные цвета в зависимости от изменения потока на них: темно-зеленый цвет
соответствует случаю, когда новый поток по дуге меньше либо равен потоку
в исходном графе; светло-зеленый — поток увеличился, но не более, чем на 20
%; желтый — поток увеличился более, чем на 20, но не более, чем на 40 %;
оранжевый — более 40, но не более 50; и, наконец, красный — поток увеличился
более, чем на 50 %.
По данным Комитета по развитию транспортной инфраструктуры СанктПетербурга от 18.12.2015 известно, что в 2016 году семь улиц Кронштадтского
района Санкт-Петербурга подлежат ремонту:
• Макаровская ул. от Синего моста до Докового моста
• Советская ул. от ул. Рошаля до ул. Комсомола
• Красная ул. от Макаровской ул. до Манежного пер.
• Кронштадтское шоссе от д. 28 до ул. Адмирала Грейга
• ул. Мартынова от ул. Карла Маркса до ул. Зосимова
• ул. Литке от Кронштадтского шоссе до Цитадельского шоссе
• Цитадельская дорога от Кронштадского шоссе до Цитадельского шоссе
Пять из них, а именно Макаровская ул., Советская ул., Красная ул., ул.
Мартынова и Цитадельская дорога рассматриваются в этой работе.
5.1.
Ремонт Цитадельской дороги
Рассмотрим Цитадельскую дорогу (на Рис. 2 она отмечена синим цветом). Если
полностью перекрыть дорогу на ремонт, дорожная ситуация изменится следующим образом:
14
Рис. 2: Цитадельская дорога полностью перекрыта на ремонт
В случае, если дорога перекрыта на ремонт не полностью (перекрытая не
полностью Цитадельская дорога отмечена бирюзовым цветом), дорожная ситуация изменится так:
Рис. 3: Движение по Цитадельской дороге ограничено
Числовые данные, соответствующие потокам на некоторых дугах (отмечен15
ных на картинке числами), приведены в таблице ниже:
№
Название
Исходный Поток при Поток при
поток
перекрытой огранич.
дороге
движении
1
2
Цитадельская д.
0.083
11.995
0
0
0
5.000
3
4
Кронштадтское ш.
2.340
0.427
0.100
10.099
0.193
5.193
5
6
Ул. Зосимова
0.167
5.973
0.087
11.523
0.108
9.301
7
8
Ул. Восстания
1.013
0.987
0.300
3.328
0.441
2.268
9
10
11
12
Ул. Мартынова
0.599
1.670
0.186
5.390
0.147
6.795
0.105
9.507
0.220
4.539
0.129
7.773
Видно, что любой ремонт Цитадельской дороги существенно осложняет дорожную ситуацию во всей западной части города, но случай, когда дорога перекрыта наполовину, осложняет движение в меньшей степени.
5.2.
Ремонт ул. Мартынова
Изменение дорожной ситуации при полном закрытии ул. Мартынова (на Рис. 4
отмечена синим) на ремонт выглядит следующим образом:
16
Рис. 4: Ул. Мартынова полностью перекрыта на ремонт
В случае, если ул. Мартынова закрыта на ремонт наполовину (отмечена
бирюзовым на Рис. 5), изменение дорожной ситуации получилось таким же.
Рис. 5: Движение по ул. Мартынова ограничено
Ремонт ул. Мартынова существенно затрудняет движение на юго-западе и
на отдельных участках западной части города. Учитывая схожесть результа17
тов при полностью закрытой на ремонт дороге и при закрытой наполовину,
нет разницы, как перекрывать дорогу. Если ремонт всей дороги одновременно
производится быстрее, можно рекомендовать его.
5.3.
Ремонт Макаровской ул.
При полном закрытии на ремонт Макаровской ул. (отмечена синим на Рис. 6)
получается следующая ситуация:
Рис. 6: Макаровская ул. полностью перекрыта на ремонт
В случае, если Макаровская ул. (отмечена бирюзовым на Рис. 7) перекрыта
частично, результаты таковы:.
18
Рис. 7: Движение по Макаровской ул. ограничено
Числовые данные, отображающие поток на дорогах, отмеченных на картинке, выглядят так:
19
№
Название
Исходный Поток при Поток при
поток
перекрытой огранич.
дороге
движении
1
2
Макаровская ул.
4.690
0.213
0
0
2
0.004
3
4
5
6
7
8
Пр. Ленина
1.174
0.851
0.167
4.535
1.017
0.982
0.559
1.788
0.220
5.963
0.575
1.737
0.778
1.284
0.188
5.302
0.742
1.347
9 Коммунистич. ул.
10
11
12
13
14
0.399
2.502
0.283
3.526
0.187
5.329
1.437
0.695
0.784
1.274
0.381
2.618
0.798
1.251
0.474
2.106
0.267
3.736
15
16
Петровская ул.
5.836
0.171
7.372
0.135
6.620
0.151
17
18
Советская ул.
0.069
14.370
0.055
18.004
0.061
16.380
Полное закрытие этой улицы существенно влияет на дорожную ситуацию
практически во всем городе (кроме самой восточной его части), в то время
как закрытие наполовину осложняет движение главным образом в центральной
части, особенно на юге. Более предпочтительным кажется второй вариант.
5.4.
Ремонт Красной ул.
При закрытии на ремонт Красной ул. (отмечена синим на Рис.‘8) затрудняется
движение на юге города в непосредственной близости к улице:
20
Рис. 8: Красная ул. полностью перекрыта на ремонт
Если Красная ул. (отмечена бирюзовым на Рис. 9) перекрыта на ремонт
частично, результаты выглядят так:
Рис. 9: Движение по Красной ул. ограничено
А так выглядят числовые данные для отмеченных на рисунке дорог:
21
№
Название
1
2
3
4
Красная ул.
0.475
2.101
1.546
0.646
0
0
0
0
0.067
1.3
0.149
0.051
5
Манежный пер.
0.100
1
0.901
6 Коммунистич. ул.
7
8
9
10
11
0.399
2.502
0.283
3.526
0.187
5.329
0.659
1.515
0.232
4.304
0.190
5.262
0.454
2.200
0.244
4.092
0.194
5.141
12
13
14
0.213
4.690
1.204
0.197
5.053
2.414
0.211
4.725
1.454
Макаровская ул.
Исходный Поток при Поток при
поток
перекрытой огранич.
дороге
движении
Второй вариант, когда на ремонт закрыта только половина дороги, кажется
более предпочтительным.
5.5.
Ремонт Советской ул.
Если полностью перекрыть на ремонт Советскую ул. (на Рис. 10 отмечена синим), получим такие результаты:
22
Рис. 10: Советская ул. полностью перекрыта на ремонт
Следующие результаты получаются в случае, если Советская ул. перекрыта
наполовину (на Рис. 11 отмечена бирюзовым):
Рис. 11: Движение по Советской ул. ограничено
Таким образом, ремонт Советской ул. локально осложняет ситуацию в непосредственной близости к этой улице и совсем немного влияет на движение по
23
остальным дорогам города.
6.
Выводы и рекомендации по построению плана ремонта дорог города Кронштадт
Как видно, практически во всех случаях (кроме ул. Мартынова) закрытие на
ремонт половины дороги оказывается более предпочтительным, чем перекрытие дороги полностью.
Поскольку ремонт Цитадельской дороги затрудняет движение на западе и в
центральной части города, не рекомендуется проводить ремонт Цитадельской
дороги одновременно с ремонтом какой-либо еще улицы, а особенно — Макаровской, которая заметно влияет на движение на юго-западе.
Не рекомендуется одновременно ремонтировать ул. Мартынова и Макаровскую ул. (результат можно видеть на Рис. 12) из-за большого увеличения потоков на дорогах юго-запада и центральной части города.
Рис. 12: Ремонт ул. Мартынова и Макаровской ул.
Не рекомендуется также одновременно ремонтировать Советскую ул. и Макаровскую ул. (Рис. 13), поскольку повышается нагрузка на многих участках,
особенно в центре города. Кроме того, при проведении такого ремонта становится сложно попасть с севера города на юг: на любом пути с севера на юг
24
кроме одного есть дорога, нагрузка на которую увеличена более чем на 20 %,
либо дорога, перекрытая на ремонт.
Рис. 13: Ремонт Советской ул. и Макаровской ул.
Более предпочтительным кажется вариант одновременного ремонта Советской ул. и ул. Мартынова (результат представлен на Рис. 14).
Рис. 14: Ремонт Советской ул. и ул. Мартынова
25
Также стоит отметить вариант одновременного ремонта Советской ул. и
Красной ул. (Рис. 15): центр оказывается более загруженным, зато нет большого влияния на ситуацию на западе и востоке.
Рис. 15: Ремонт Советской ул. и Красной ул.
Ремонт Красной ул. главным образом сказывается на очень близких к ней
дорогах, поэтому кажется возможным ремонтировать одновременно с ней и ул.
Мартынова (Рис. 16):
26
Рис. 16: Ремонт Красной ул. и ул. Мартынова
И Макаровскую ул. (Рис. 17):
Рис. 17: Ремонт Красной ул. и Макаровской ул.
Хотя в обоих случаях возникают участки, поток машин по которым существенно увеличивается.
Исходя из увеличения потоков на дорогах, возникающего при перекрытии
27
на ремонт уже двух дорог, вероятно, не стоит одновременно ремонтировать
три и более дороги. Единственный вариант ремонта трех дорог одновременно, который кажется приемлемым — ремонт Красной ул., Советской ул. и ул.
Мартынова (Рис. 18).
Рис. 18: Ремонт Красной ул., Советской ул. и ул. Мартынова
Алгоритм Брэгмана сходится достаточно быстро: на обработку каждого из
рассмотренных выше случаев ушло от 8 до 14 секунд. При этом большинство
случаев обрабатывалось не более, чем за 10 секунд, а самое большое время достигалось в тех ситуациях, где перекрывалась на ремонт Макаровская ул. (11
секунд для полностью перекрытой Макаровской ул. и 14 секунд для перекрытых ул. Мартынова и Макаровской ул.). Параметр, управляющий точностью,
имел высокое значение — нам было интересно поведение программы. Если потребовать меньшую точность вычислений, можно добиться более быстрой работы программы.
Метод Брэгмана можно успешно применять для моделирования движения
на дорогах города. Его существенным достоинством является быстрота, поэтому его можно применять как для небольших, так и для больших наборов данных: начиная с участков, состоящих из нескольких улиц, и заканчивая целыми
районами города или городами. Конечно, для того, чтобы надеяться на правдоподобный результат необходимо иметь более достоверные данные, описыва28
ющие дороги и потребности вершин графа.
7.
Приложение
Так может выглядеть подпрограмма на языке C], реализующая модифицированный метода Брэгмана. По заданным вектору “весов” w, вектору ограничений
r, вектору потребностей вершин b, матрице инциденций графа a и целым числам n,m — количеству вершин и дуг соответственно, программа генерирует
вектор x потоков на дугах.
static void Bregman(int[,] a, double[] w, int n, int m,
double[] b, double[] r, out double[] x) {
double[] xk = new double[m];
double[] xp = new double[m];
double[] xadd = new double[m];
double eps = 0.0000000001;
for (int i = 0; i < m; i++) {
xk[i] = w[i];
xadd[i] = 0;
}
double S = 0;
double S1 = 0;
double S2 = 0;
int counter = 0;
while (counter != m) {
for (int i = 0; i < n; i++) {
S = 0;
S1 = 0;
S2 = 0;
for (int l = 0; l < m; l++) {
xp[l] = xk[l];
29
xadd[l] = 0;
}
for (int j = 0; j < m; j++) {
if (a[i, j] == 1)
S1 = S1 + xk[j];
else if (a[i, j] == -1)
S2 = S2 + xk[j];
}
if ((S1 == 0) || (S2 == 0)) {
if (b[i] != 0) {
double ttemp = 0;
if ((S1 == 0) & (S2 != 0)) ttemp = -S2 / b[i];
else if ((S1 != 0) & (S2 == 0)) ttemp = b[i] / S1;
for (int j = 0; j < m; j++) {
if (a[i, j] != 0) {
double temp = ttemp;
if (a[i, j] == -1) temp = 1 / ttemp;
if (xk[j] * temp <= r[j])
xk[j] = xk[j] * temp;
else if (xk[j] * temp > r[j]) {
int k = 0;
for (int l = 0; l < m; l++) {
if ((a[i, l] == a[i, j]) &&
(xk[l] < r[l]) && (l != j)) k++;
}
if (k == 0)
xk[j] = xk[j] * temp;
30
else if (k > 0) {
bool p = false;
double z;
int kk;
while (p) {
z = (xk[j] * temp - r[j]) / k;
kk = 0;
for (int l = 0; l < m; l++) {
if ((a[i, j] == a[i, l]) && (j != l)
&& (xk[l] + z + xadd[l] < r[l]))
kk++;
}
if (kk == k) {
for (int l = 0; l < m; l++) {
if ((a[i, j] == a[i, l]) && (j != l)
&& (xk[l] + z + xadd[l] < r[l])) {
xadd[l] = xadd[l] + z;
p = true;
}
}
}
else {
k = kk;
}
}
xk[j] = r[j];
}
}
}
}
for (int l = 0; l < m; l++) {
xk[l] = xk[l] + xadd[l];
31
xadd[l] = 0;
}
}
}
else {
S = (b[i] + (Math.Sqrt(b[i] * b[i] +
4 * S1 * S2))) / (2 * S1);
for (int j = 0; j < m; j++) {
if ((a[i, j] == 1) && (xk[j] * S <= r[j]))
xk[j] = xk[j] * S;
else if ((a[i, j] == -1) && (xk[j] / S <= r[j]))
xk[j] = xk[j] / S;
else if ((a[i, j] == 1) && (xk[j] * S > r[j])) {
int k = 0;
for (int l = 0; l < m; l++) {
if ((a[i, l] == a[i, j]) &&
(xk[l] < r[l]) && (l != j)) k++;
}
if (k == 0) xk[j] = xk[j] * S;
else if (k > 0) {
bool p = false;
double z;
int kk;
while (p) {
z = (xk[j] * S - r[j]) / k;
kk = 0;
for (int l = 0; l < m; l++) {
if ((a[i, j] == a[i, l]) && (j != l)
&& (xk[l] + z + xadd[l] < r[l]))
32
kk++;
}
if (kk == k) {
for (int l = 0; l < m; l++) {
if ((a[i, j] == a[i, l]) && (j != l)
&& (xk[l] + z + xadd[l] < r[l])) {
xadd[l] = xadd[l] + z;
p = true;
}
}
}
else {
k = kk;
}
}
xk[j] = r[j];
}
}
else if ((a[i, j] == -1) && (xk[j] / S > r[j])) {
int k = 0;
for (int l = 0; l < m; l++) {
if ((a[i, l] == a[i, j]) &&
(xk[l] < r[l]) && (l != j)) k++;
}
if (k == 0) xk[j] = xk[j] / S;
else if (k > 0) {
bool p = false;
double z;
int kk;
while (p) {
33
z = (xk[j] / S - r[j]) / k;
kk = 0;
for (int l = 0; l < m; l++) {
if ((a[i, j] == a[i, l]) && (j != l)
&& (xk[l] + z + xadd[l] < r[l]))
kk++;
//xadd[l] = xadd[l] + z;
}
if (kk == k) {
for (int l = 0; l < m; l++) {
if ((a[i, j] == a[i, l]) && (j != l)
&& (xk[l] + z + xadd[l] < r[l])) {
xadd[l] = xadd[l] + z;
p = true;
}
}
}
else {
k = kk;
}
}
xk[j] = r[j];
}
}
}
for (int l = 0; l < m; l++) {
xk[l] = xk[l] + xadd[l];
xadd[l] = 0;
}
}
}
counter = 0;
34
for (int l = 0; l < m; l++) {
if ((xk[l] >= xp[l] - eps) & (xk[l] <= xp[l] + eps))
counter++;
}
}
x = xk;
}
35
Литература
[1] Шелейховский Г. В. Транспортные основания композиции городского плана.
Л.: Гипрогор, 1936.
[2] Брэгман Л. М. Нахождение общей точки выпуклых множеств методом последовательного проектирования. Докл. АН СССР, 1965, 162, №3, с. 487–490.
[3] Брэгман Л. М. Доказательство сходимости метода Г. В. Шелейховского для
задачи с транспортными ограничениями. Журн. вычислит. мат. и мат. физики, 1967, т.7, №1, с. 147–156.
[4] Брэгман Л. М. Релаксационный метод нахождения общей точки выпуклых
множеств и его применение для решения задач выпуклого программирования. Журн. вычислит. мат. и мат. физики, 1967, т.7, №3, с. 620–631.
[5] Тищенко И. Закатали в асфальт: как отремонтируют петербургские дороги
летом [Электронный ресурс, Дата обращения: 18.05.2016]
URL: http://www.spbdnevnik.ru/news/2016-02-29/zakatali-v-asfalt
-kak-otremontiruyut-peterburgskiey-dorogi-letom
36
Отзывы:
Авторизуйтесь, чтобы оставить отзыв