Буслаев А.П. Вероятностные и имитационные подходы к оптимизации автодорожного движения
Подождите немного. Документ загружается.
161
0.03
k,kI_q:...-
__
..,...-
___________
..,...-
___
-,
о
0.2 0.4 0.6 0.8
r 1
-о
-0-0
.1
-tr-O.2
--0.3 --0.4
-0-0.5
-+-0.6
-0.7
--0
.8
--0
.9
Рис.
7.19.
Зависимость
k~~),
(L =
2,
р
= 0.9,
(з
= 0.5,
а
= 0,0.1, ... ,0.9)
0.014
k,kI_q-=--
______________
..,...-
___
-,
о
0.2 0.4 0.6 0.8 r 1
-о
-0-0.1
-0-0.2
--0.3
-+-0.4
-0-0
.5
-+-0.6
-0
.7
--0
.8
-+-0.9
Рис.
7.20.
Зависимость
~
:'~C1.
,
(L =
2,
р
= 0.5,
(з
= 0.5,
а
= 0,0.1, ... ,0.9)
162
Глава
7.
Сегрегация
АТП
0.009
k,k
___
--_-----
__
--,
0.008
0.007
0.006
0.005
0.004
0.003
0.002
o.oo~
L-
A,~~=::~~a:~~~~...J
Рис.
7.21.
Зависимость
kk(r),
(а
=0,
{31
=
f32
=
0.5,
L = 1,2,
...
,
9)
r
L
-1
-+-2
-3
-4
...........
5
----6
-7
--8
-9
10
На
рис.
7.21
показана
зависимость
kk
от
плотности
r
/31
= .82=0.5,
а=О,
К=2
при разных
значениях
длины
зоны
П.
0.35
...,.:~--.-----.----.------.---.---__,
L
о.
3
--1
-+-2
~
-3
0.2
-4
0.15
...........
5
----6
0.1
-7
0.05
--8
О-t----г--т----т-,--г----т--,..-----г-,----I
-9
r
10
0.050.150.250.35 0.45 0.550.650.750.850.95
Рис.
7.22.
Зависимость
q(r),
(а
=
о,
{31
=
f32
=
0.5,
L = 1,2,
...
,
9)
ование
163
На
рис.
7.22
показана
зависимость
q
от
плотности
r
/3
=
5,
а
=
О,
К
= 2
при
разных
значениях
длины
зоны
1I,
с
ЛИ''lеF.[ием
зоны
11,
интенсивность
увеличивается
,
но
не
0.006
kт-
k
___
--.
______
----.,..-----.
JЗ
0.005
--о-
0.1
-6-0
.2
0.004
~0.3
0.003
--*-0.4
0.002
-0.5
---
0.6
0.001
-0.7
-0.8
r
-0.9
ис.
7.23.
Зависимость
kk(r),
(а
=
О,
L =
2,
/3=0.1,
0.2,
..
,
0.9)
0.35
...--=--.---..,.--.,....--..,----,--------.,--,
0.3
0.25
0.2
0.15
0.1
0.05
0.05
0.150.250.35
0.450.55 0.
650.750
.85 0.95
--о-
0.1
-6-0
.2
~0
.
3
--*-
0.4
-0
.5
---0.6
-0
.7
-0.8
-0.9
Рис.
7.24.
Зависимость
q(r),
(а
=
О,
L =
2,
/3=0.
1,
0.
2,
..
,
0.9)
164
Глава
7.
Сегрегация
АТП
На
рис.
7.23
и
7.24
показано,
как
изменяется
значение
kk
и
q
соответственно
в
зависимости
от
f3
=
fЗ1
= 1 -
fЗ2
(про
цент
АТС,
которые
стремятся
сменить
поло
су
движения).
Проведем
нормировку
по
q
и
построим
отношение
~k
Для
двух
случаев,
показанных на
рис.
7.21
и
7.23.
0.03
;..·······;············+·,г·г''',······!·············;···
.....
, ........ ;
..............
;
.......
:
.......
,
0.025
-1
.....
·.,..········,п····,······!.··
...........
"
...
! ...........
..
: •.......... ;
.......•...
.,
!····I
0.02
-1
.............. ; ..... ,
I+···········+
·,,····--!-··············!·······'
••
'.i:···········!······
....
+
...........
+
0.015
0.01
L
-1
-1-2
-3
-4
-*"""
5
-11-6
-7
0.005
--+-8
'~~~~
__
~~~~~~~~~~~
-9
0+
r 10
0.050.150.250.350.450.550.650.750.850.95
Рис.
7.25.
Зависимость
~(~),
(а
=
О,
(3
= 0.5, L = 1,2, ... ,
9)
13
0.025
-<>-0.1
-iz-
0.2
0.02
---Q-
0.3
0.015
----*-
0.4
0.01
-0.5
---0.6
0.005
-0.7
О
--+-0.8
<:>"
~"
",,"
'Ъ"
~
,,"
~"
'\"
ta"
0.>"
r
---
0.9
<:>. <:>. <:>.
<:>.
<:>.
<:>. <:>.
<:>.
<:>.
<:>.
Рис.
7.26.
Зависимость
~(~),
(а
=
О,
L =
2,
(3=0.1, 0.2,
..
, 0.9)
165
Сравнивая
рис.
7.25
и
7.21
и
рис.
7.26
и
7.23,
можно
сде
вывод,
что они
похожи,
т
.
к.
интенсивность,
особенно
изменении
L,
сильно
не
меняется.
Сценарий
В2
движения
в
зоне
П.
В
данном
сценарии
в
отличие
от
сценария
В
1,
запол
следующего такта
времени
происходит
непосред
II'Вf~HH:O
за
предыдущим.
Когда
АТС
расположено
на
~D.'\"т.r"
полосе
разрешение
дорожной
ситуации
происходит
же,
как
и
в
сценарии
В1.
Рассмотрим
ситуацию,
когда
АТС
находится
на
"чу
полосе.
АТС
приняло
решение
двигаться.
В
этом
для
того,
чтобы
АТС
перестроилось
необходимо:
отсутствие
рядом
с
АТС,
находящимся
в
клетке
(1,3),
АТС
в
клетках
(2,3)
и
(2,4).
Если
это
условие
выпол
няется,
.
то
АТС
перемещается
в
клетку
(2,4),
выполняя
маневр
опережения
(рис.
7.27,а);
если
клетка
(2,4)
занята,
а
клетка
(2,3)
свободна,
то
про
веряется,
нет
ли
сзади
него
АТС,
которые
могут
за
нять
клетку
(2,4).
Если
клетки
(2,2)
и
(1,2)
пусты,
то
АТС
на
данном
такте
перемещается
в
клетку
(2,3),
выполняя
маневр
перестроения
(рис.
7.27,б);
если
клетка
рядом
с
АТС
занята
(2,3),
то
АТС
двигается
вперед
в
клетку
(1,4)
по
той
полосе,
на
которой
оно
находится.
2 3 4 5
2 3 4 5
2
2
а) б)
Рис.
7.27.
ПравИJIа
движения
в
зоне
II,
случай
В2
"
::
: i
: (,
. j
.
'!
'
.,
I
,
,1,
.
' 1
'1.
I
" , !
I,i
i
I
166
Глава
7.
Сегрегация
АТП
7.3.
Математическая
модель
Описание
математи'Чес7СОЙ
моде.л.и
1.
Рассмотрим
простую
математи'Ческую
модель
сегрега
цИИ
АТП. На
OCHo~e
этой
модели
предложим
приближенный
способ
вы'Числения
среднего
времени
между
моментами
ту
пиковых
состояний
модели,
соответствующих
состояниям
"клина"
в
имитационной
модели,
описанной
в
пп.
7.1, 7.2.
В
описанной
ниже
математи'Ческой
модели
имеются
не
которые
упрощения
по
отношению
к
имитационной
модели.
В
'Частности,
предполагается,
'Что
все
АТС
одинаковы
по
своим
скоростным
характеристикам
и
в
текущий
такт
вре
мени
передвигаются
(при
возможности
перемещения)
с
за
данной
вероятностью
р.
Ес.tш
б
t.ШuтационноЙ
модели
задано,
'Что
до.л..я
медлен
ных
АТС
равна
еж
и
в
ер
о-ятности
.nеремещенu.я
быстрого
u
медленного
А
ТС
равны
соответственно
Pl
и])2,
то
в
ма
темати'Чесх;ой
моде.tш
можно
положить
р
=
(l-a)pl
+аР2.
Другим
упрощением
по
отношению
7с
t.ШитационноЙ
мо
дели
яв.л..яетс-я
то,
'Что
в
математи'Чес7СОЙ
модели
АТС,
nО7Синувшие
зону
сегрегации
(вторую
зону),
сразу
вновь
ох;азываютс-я
впервой
зоне,
где
обгоны
разрешены.
Та
х;ое
допущение
можно
объ-яснить
дополнительным
пред
положением,
'Что
плотности
nотО7Сов
во
всех
трех
зонах
имuтационной
моделu
разлu'Чаютс-я
не
СЛUШ7Сом
СU.lLЬНО
.
.
Сна'Чала
будет
рассмотрен
вариант
математи'Ческой
мо
дели,
соответствующий
алгоритму,
при
котором
переход
АТСна
другую
полосу
разрешен
лишь
в
слу'Чае,
когда
пара
клеток,
расположенная
позади
данного
АТС,
свободна.
За
тем
будет
исследован
другой
вариант
модели,
в
котором
переходы
на
другую
полосу
имеют
приоритет над
переме
щениями
вперед.
Рассмотрение
.
этого
алгоритма
оправдано
тем,
'Что
в
реальной
ситуации
такой
переход
требует
суще
ствецно
меньше
времени.
Перейдем
к
описанию
модели
.
Пусть
имется
набор
клеток,
занумерованных
парой
ин
дексов
(i,
j),
i = 1,2,
...
,
N;
j = 1,2; j -
номер
полосы
Математическая
167
НI~~РJ:lая
полоса
соответствует
правой
полосе
в
имитацион-
'
мо,цели,
а
вторая
-
левой);
i -
номер
клетки
в
полосе.
Имеется
тl
АТС
первого
типа
и
т2
АТС
второго
типа;
,=
Гн";
Т2
=
J~;
r =
Тl
+
Т2·
А!С
первого
типа
соответ-
....
,.,,'tЛГ1.,.,
тем
AT<..J
в
имитационнои
мо,цели,
которым
пре,цпи-
в
зоне
III
,цвигаться
по
правой
полосе,
а
АТС
второго
соответствуют
тем
АТС
в
имитационной
модели,
ко
II'01DblM
в
зоне
III
пре,цписано
,цвигаться
по
левой
полосе.
В
,...а.
....
,u,DLП
момент
времени
в
клетке
может
нахо,циться
не
60-
о,цного
АТС.
Перемещение
АТС
может
происхо,цить
в
'Iис:;л:е:нные
моменты
времени.
Множество
клеток
по
разбивается
на
,цве
зоны.
Ко
второй
зоне
относятся
полосы
с
номерами
от
1
,цо
L.
Эта
зона
соответ
'
·
-..'о,,,,.,.,
зоне
II
имитационной
мо,цели.
Остальные
клетки
.
'
m'HO,('..R']~CJI
к
первой
зоне.
Считаем,
что
значение
N - L
до
~'1'а'I'ОЧ:НО
велико
..
Бу,цем
говорить,
что
Qk,(i, j, t) = 1,
если
момент
времени
t k-e
АТС
s-го
типа
находится
в
клетке
.
(i,j)
и
Qk,(i,j,
t)
=
О в
противном
случае;
Q(i,j,
t)
=
о,
если
.
в
момент
времени
t
клетка
(i,j)
пуста;
Q(i,j, t) =
1,
если
JI
момент
времени
t
в
клетке
(i,
j)
находится
АТС
первого
'
типа;
Q(i,j, t) = 2,
если
в
момент
времени
t
в
клетке
(i,j)
нахо,цится
АТС
второго
типа.
Прибавление
1
к
значению
,
первого индекса
(или
вычитание
1
или
2
от
значения
пер
вого
ин,цекса)
бу,цем
понимать
как
сложение
(вычитание)
по
мо,цулю
N,
например,
(N
+
1,Л
=
(1,Л;
при6авление
1
к
значению
второго индекса
бу,цем
понимать
как
сложение
по
МОдУлю
2.
Перемеще'Ние
АТС
из
tc.aemox:
первой
ЗО'НЫ
осуществА.Я
етс.я
по
сдедующtJ..М,
пр
ав
Uдa.4t.
Пусть
Qk,(i,j,t)
=1,
i > L, Q(i +
1,j,t)
=
о.
Тогда
с
вероятностью
р
Qks(i
+ 1,j, t +
1)
=
1.
Если
Qks(i,j, t) =
1,
Q(i +
1,j,t)
>
о,
Q(i,j
+ 1,t) = Q(i +
1,j
+ 1,t) =
о,
то
с
вероятностью
р
Qks
(i +
1,
j +
1,
t +
1)
=
1.
Это
соответствует
правилам
,цвижения
АТС
в
зоне
1
имитационной
мо,цели.
Перемеще'Ние
АТС
из
tc.aemOK
второй
ЗО'НЫ
происходит
по
сдедующим
правилам.
Предположим,
что
в
момент
вре
мени
t k-e
АТС
в-го
типа
нахо,цится
в
клетке
(i,
в
+
1)
1:
168
Глава
7.
Сегрегация
АТП
(8
= 1,
..
. , L -
1)
второй
зоны,
Т.е.
Qks(i,8 +
1,
t) =
1,
:и
Q(i - 1,8, t) = Q(i - 1,8 +
1,
t) = Q(i,
8,
t) = Q(i +
1,
s,
t) =
о.
Тогда
с
вероятностью
р
Qks(i + 1,8, t +
1)
= 1
(данное
АТС
перемещается
на клетку
вперед
с
переходом
на
другую
по
лосу),
а
с
вероятностью
1-
р
имеем
Qks(i,
s,
t+
1) = 1
(АТС
переходит
на
другую
полосу
без
продвижения
вперед).
Если
Qks(i,8+1,t) =
1,
Q(i-1,8,t)+Q(i-1,s+1,t)
>
о,
Q(i,
8,
t) = Q(i +
1,8+
1, t) =
О,
то
Qks(i +
1,
s,
t + 1) = 1
с
вероятностью
р
(перемещение
k-го
АТС
в-го
типа
в
клетку
(i,
В)
недопустимо,
так
как
в
клетке
(i-
1,
В)
или
в
клетке
(i-1,
в+1)
находится
АТС,
которое
может
перейти
в
клетку
(i,
В)).
Если
Qks(i,
В
+
1,
t) =
1,
Q(i -
1,
В,
t) = Q(i -
1,
s +
1,
t) =
Q(i,
В,
t) =
О,
Q(i + 1,8, t) >
О,
то
Qks(i,
В,
t +
1)
= 1
(АТС
с
вероятностью
1
переходит
на
соседнюю
полосу
без
продви-
жения
вперед)
.
.
Если
Qks(i,
в+
1,
t) = 1, Q(i, s, t) >
О,
Q(i+ 1,
s+
1, t) =
О,
то
с
вероятностью
р
имеет
место
равенство
Qks(i + 1,
В
+
1,
t +
1)
=
1,
Т.е.
АТС
передвигается
на
одну
клетку
вперед,
оставаясь
на
"чужой"
полосе.
Если
Qks(i,
В
+
1,
t) = 1, Q(i,
В,
t) =
О,
но
Q(i-1,s,t)+Q(i-1,в+1,t)
>
о,
Q(i+1,8,t)
>
О,
то
также
с
вероятностью
р
имеем
Qks(i +
1,
В
+
1,
t +
1)
=
1.
Если
Qks(i,
В,
t)=
1
и
Q(i+
1,
s, t) =
О,
то
с
вероятностью
р
имеем
Qks(i+1,
s,
t+
1)
= 1
(АТС,
находящееся
на
"своей"
полосе,
передвигается
на
клетку
вперед).
Если
Qks(L,
В,
t) =
1,
Q(L+
1,
s, t) =
О,
то
с
вероятностью
р
имеем
Qks(L +
1,
s,
t + 1) =
1.
Если
Qks(L, s +
1,
t) = 1
и
Q(L-1,
В,
t) =
Q(L-1,
8+1, t) = Q(L,
В,
t) = Q(L+1,
s,
t) =
О,
TOQks(L+1,
s,
t+1) = 1
с
вероятностью
р
и
Qks(L,
В,
t+1) = 1
с
вероятностью
1 -
р.
Если
Qks(L,
В
+
1,
t)
=
1,
Q(L-1,
В,
t) +Q(L,
В
+
1,
t) >
О,
Q(L,
В,
t) = Q(L+ 1,
В,
t) =
О
,
то
Qks(L + 1,8, t +
1)
= 1
с
вероятностью
р.
Если
Q
ks
(L, 8 +
1,
t)
= 1,
Q(
L -
1,
s,
t)
+
Q(
L -
1,
В
+
1,
t) =
Q(L,
В,
t) =
О,
Q(L +
1,
В,
t)
>
О,
то
Qks(L,
8,
t + 1) =
1.
·
3.
Математич:ескан
169
:
Данные
правила
соответствую~
правилам
движения
те
в
зоне
II
(зоне
сегрегации)
имитационной
модели.
Если
Q(L,
1,
t)
= 2
и
Q(L,
2,
t) =
1,
то
будем
говорить,
в
момент
времени
t
система
находится
в
тупиковом
со
(в
состоянии
"клина").
Выход
из
тупикового
со
;i~
'-"ЛПZUl.
осуществляется
по
следующему
правилу
.
Пусть
момент
t
система
находится
в
тупиковом
состоянии
и
(L,
1, t) =
1,
Q(L+1,
1,
t) =
о.
Тогда
Qk2(L+1,
1,
t+1) =
1.
правило
соответствует
способу
2
выхода
из
тупикового
tIO<;ТС1ЯНИЯ
(с
выходом
А
те
на
"чужую"
полосу)
в
имитаци
I>ИIIОИ
модели.
Предлагаемый
приближенный
способ
вычи
~А<;;пп,л
среднего
времени
между
тупиковыми
состояниями
учитывает
правило
выхода
из
тупикового
состояния и
этот
способ
может
без
изменения
применяться
и
других
правилах
выхода
из
тупикового
состояния.
Вы'Чис.л.е-ние
стацио-нар-ных веро.ят-ностеЙ
состо.я-ниЙ
и
сред-него
'
време-ни
.между
туnи"овы.ми
состо.я-
Опишем
приближенный
способ
вычисления
среднего
: ....
jJ.~1VJ'vnz.
между
двумя
тупиковыми
состояниями.
Пусть
Ps(i,j,
t)
-
вероятность
того,
что
в
момент
вре
t
в
клетке
(i,
j)
находится
Ате
s-го
типа.
Данная
модель
может
рассматриваться
как
цепь
Мар
кова
с
конечным
мн:ожеством
состояний,
которая
удовле
.
'1'воряет
условиям
теоремы
эргодичности
[28].
Для
такой
.'
цепи
Маркова
существуют
предельные
вероятн:ости
состо-
ps(i,j) = lim Ps(i,j, t).
t--too
,
Пусть
p(i,j) = pl(i,j) + P2(i,j).
Буде.м
nриб.л.иже-н-но
с'Читать,
'Что
веро.ят-ность
состо
.я"u.я
фи"сированной
х:.л.ет"и
в
те"ущий
.мо.мент
вре.ме"и
"е
зависит
от
того,
в
"а"их
состо.я"u.яx
-наход.ятся
другие
Предложим
следующие
приближенные
формулы:
ps(i,
8)
=
Ps(i,
8)(1 -
(1
-
p(i
+
1,
8))Р)+
+Раи
- 1,8)(1 - p(i,
8))Р+
i ' .
i
i 1 ,
i
1 ,
170
Глава
7.
Сегрегация
АТП
+Ps(i
- 1,8 +
1)(1
-
p(i
- 1,8))(1 -
p(i,
8))Р+
+Ps(i,
8 + 1)(1 - p(i - 1,8))
Х
х(l
- p(i - 1,8 + 1))(1 - p(i, 8))(1 -
p(i
+ 1,8))(1 -
р)+
+Ps(i, 8 +
1)(1
-
p(i
- 1,8))(1 -
p(i
- 1,8 +
1))
х
х(l
- p(i, 8))p(i + 1,8),
8
= 1,2; i =
2,
...
, L;
Ps(i,
8 +
1)
=
Ps(i,
8 + 1)(1 -
(1
-
p(i
- 1,8))
х(l
-
p(i
- 1,8 +
1))(1-
p(i,
8))-
-(1
-
(1-
p(i
-1,8))(1-
p(i
-1,8
+
l)))х
х
(1
- p(i, 8))(1 - p(i +
1,
8))Р-
-
(1
-
(1
-
р(
i -
1,
8)
)( 1 -
р(
i -
1,
8 + 1)))
х
х(l
- p(i, 8))p(i + 1,8)(1 -
p(i
+ 1,8 +
l))р
-p(i,
8)(1
- p(i + 1,8 +
l))р)+
(1)
+p8(i
- 1,8 + 1)(1 -
(1
- p(i - 2,8))(1 -
p(i
- 2,8 + 1)))
х
х(l-
p(i
- 1,8))p(i,
8)Х
х(l
-
(1
- p(i, 8 +
l))р)+
+p,(i - 1,8 + l)p(i - 1,8)(1 -
p(i,
s +
l))р,
s = 1,2; i =
2,
...
, L -
1,
Ps(L,
s +
1)
=
Ps(L,
8 + 1)(1 -
(1
- p(L - 1,8))
Х
Х
(1
- p(L - 1,8 + 1))(1 -
p(L,
8))-
-
(1
-
(1
-
р(
L -
1,
8)
)( 1 -
р(
L -
1,
8 + 1)))
х
х(l
-
p(L,
8))(1 - p(L +
1,
в))р)
+Ps(L - 1,8 + 1)(1 -
(1
- p(L -
2,
8))Х
х(l
- p(L - 2,8 +
l)))х
(2)