Эвристический алгоритм управления конфликтными нестационарными транспортными потоками
Рассмотрена модель сети, узлами которой являются однолинейные системы массового обслуживания. На вход некоторых систем поступают нестационарные пуассоновские потоки требований (транспортные потоки). Предложен алгоритм статистического моделирования, который позволяет выявлять наиболее проблемные учас...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2018 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/161427 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Эвристический алгоритм управления конфликтными нестационарными транспортными потоками / Н.Ю. Кузнецов // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 27-37. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-161427 |
|---|---|
| record_format |
dspace |
| spelling |
Кузнецов, Н.Ю. 2019-12-08T17:27:35Z 2019-12-08T17:27:35Z 2018 Эвристический алгоритм управления конфликтными нестационарными транспортными потоками / Н.Ю. Кузнецов // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 27-37. — Бібліогр.: 15 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/161427 519.873 Рассмотрена модель сети, узлами которой являются однолинейные системы массового обслуживания. На вход некоторых систем поступают нестационарные пуассоновские потоки требований (транспортные потоки). Предложен алгоритм статистического моделирования, который позволяет выявлять наиболее проблемные участки сети и сформулировать эвристический алгоритм управления потоками, способствующий уменьшению времени пребывания в очередях. Данный алгоритм проиллюстрирован на примере транспортной сети, состоящей из 20 перекрестков. Розглянуто модель мережі, вузлами якої є однолінійні системи масового обслуговування. На вхід деяких систем надходять нестаціонарні пуассонівські потоки вимог (транспортні потоки). Запропоновано алгоритм статистичного моделювання, який дозволяє виявити найбільш проблемні місця у мережі та сформулювати евристичний алгоритм керування потоками, який сприяє зменшенню часу перебування у чергах. Цей алгоритм проілюстровано на прикладі транспортної мережі, яка налічує 20 перехресть. The paper considers a model of the network with nodes being one-server queueing systems. The non-stationary Poisson flows are input flows to some queueing systems (transport flows). A statistical simulation algorithm is proposed. It identifies weak points of the network and allows formulating a heuristic flow control algorithm that reduces the total waiting time. This algorithm is illustrated by an example of a transport network with 20 crossroads. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Эвристический алгоритм управления конфликтными нестационарными транспортными потоками Евристичний алгоритм керування конфліктними нестаціонарними транспортними потоками Heuristic control algorithm for conflicting nonstationary transport flows Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Эвристический алгоритм управления конфликтными нестационарными транспортными потоками |
| spellingShingle |
Эвристический алгоритм управления конфликтными нестационарными транспортными потоками Кузнецов, Н.Ю. Системний аналіз |
| title_short |
Эвристический алгоритм управления конфликтными нестационарными транспортными потоками |
| title_full |
Эвристический алгоритм управления конфликтными нестационарными транспортными потоками |
| title_fullStr |
Эвристический алгоритм управления конфликтными нестационарными транспортными потоками |
| title_full_unstemmed |
Эвристический алгоритм управления конфликтными нестационарными транспортными потоками |
| title_sort |
эвристический алгоритм управления конфликтными нестационарными транспортными потоками |
| author |
Кузнецов, Н.Ю. |
| author_facet |
Кузнецов, Н.Ю. |
| topic |
Системний аналіз |
| topic_facet |
Системний аналіз |
| publishDate |
2018 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Евристичний алгоритм керування конфліктними нестаціонарними транспортними потоками Heuristic control algorithm for conflicting nonstationary transport flows |
| description |
Рассмотрена модель сети, узлами которой являются однолинейные системы массового обслуживания. На вход некоторых систем поступают нестационарные пуассоновские потоки требований (транспортные потоки). Предложен алгоритм статистического моделирования, который позволяет выявлять наиболее проблемные участки сети и сформулировать эвристический алгоритм управления потоками, способствующий уменьшению времени пребывания в очередях. Данный алгоритм проиллюстрирован на примере транспортной сети, состоящей из 20 перекрестков.
Розглянуто модель мережі, вузлами якої є однолінійні системи масового обслуговування. На вхід деяких систем надходять нестаціонарні пуассонівські потоки вимог (транспортні потоки). Запропоновано алгоритм статистичного моделювання, який дозволяє виявити найбільш проблемні місця у мережі та сформулювати евристичний алгоритм керування потоками, який сприяє зменшенню часу перебування у чергах. Цей алгоритм проілюстровано на прикладі транспортної мережі, яка налічує 20 перехресть.
The paper considers a model of the network with nodes being one-server queueing systems. The non-stationary Poisson flows are input flows to some queueing systems (transport flows). A statistical simulation algorithm is proposed. It identifies weak points of the network and allows formulating a heuristic flow control algorithm that reduces the total waiting time. This algorithm is illustrated by an example of a transport network with 20 crossroads.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/161427 |
| citation_txt |
Эвристический алгоритм управления конфликтными нестационарными транспортными потоками / Н.Ю. Кузнецов // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 27-37. — Бібліогр.: 15 назв. — рос. |
| work_keys_str_mv |
AT kuznecovnû évrističeskiialgoritmupravleniâkonfliktnyminestacionarnymitransportnymipotokami AT kuznecovnû evrističniialgoritmkeruvannâkonflíktniminestacíonarnimitransportnimipotokami AT kuznecovnû heuristiccontrolalgorithmforconflictingnonstationarytransportflows |
| first_indexed |
2025-11-26T01:39:43Z |
| last_indexed |
2025-11-26T01:39:43Z |
| _version_ |
1850603581670948864 |
| fulltext |
ÓÄÊ 519.873
Í.Þ. ÊÓÇÍÅÖÎÂ
ÝÂÐÈÑÒÈ×ÅÑÊÈÉ ÀËÃÎÐÈÒÌ ÓÏÐÀÂËÅÍÈß ÊÎÍÔËÈÊÒÍÛÌÈ
ÍÅÑÒÀÖÈÎÍÀÐÍÛÌÈ ÒÐÀÍÑÏÎÐÒÍÛÌÈ ÏÎÒÎÊÀÌÈ
Àííîòàöèÿ. Ðàññìîòðåíà ìîäåëü ñåòè, óçëàìè êîòîðîé ÿâëÿþòñÿ îäíîëèíåé-
íûå ñèñòåìû ìàññîâîãî îáñëóæèâàíèÿ. Íà âõîä íåêîòîðûõ ñèñòåì ïîñòóïà-
þò íåñòàöèîíàðíûå ïóàññîíîâñêèå ïîòîêè òðåáîâàíèé (òðàíñïîðòíûå ïîòî-
êè). Ïðåäëîæåí àëãîðèòì ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ, êîòîðûé ïîçâîëÿ-
åò âûÿâëÿòü íàèáîëåå ïðîáëåìíûå ó÷àñòêè ñåòè è ñôîðìóëèðîâàòü
ýâðèñòè÷åñêèé àëãîðèòì óïðàâëåíèÿ ïîòîêàìè, ñïîñîáñòâóþùèé óìåíüøå-
íèþ âðåìåíè ïðåáûâàíèÿ â î÷åðåäÿõ. Äàííûé àëãîðèòì ïðîèëëþñòðèðîâàí
íà ïðèìåðå òðàíñïîðòíîé ñåòè, ñîñòîÿùåé èç 20 ïåðåêðåñòêîâ.
Êëþ÷åâûå ñëîâà: ñèñòåìà îáñëóæèâàíèÿ, íåñòàöèîíàðíûé ïóàññîíîâñêèé
ïîòîê, ìåòîä ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ, öåïü Ìàðêîâà, óïðàâëåíèå
ïîòîêàìè.
ÂÂÅÄÅÍÈÅ
Ïðîáëåìà óïðàâëåíèÿ òðàíñïîðòíûìè ïîòîêàìè, îñîáåííî â ñîâðåìåííûõ ìå-
ãàïîëèñàõ, óæå íà ïðîòÿæåíèè íåñêîëüêèõ äåñÿòèëåòèé âåñüìà àêòóàëüíà. Âîç-
ðàñòàþùåå ñ êàæäûì ãîäîì êîëè÷åñòâî òðàíñïîðòíûõ ñðåäñòâ (êàê ëè÷íûõ,
òàê è îáùåñòâåííûõ) ïðèâîäèò ê ïåðåãðóçêàì òðàíñïîðòíîé ñåòè è ìíîãî÷àñî-
âûì ïðîáêàì. Ïî ñóòè òðàíñïîðòíûå ïîòîêè ÿâëÿþòñÿ, âî-ïåðâûõ, ñòîõàñòè-
÷åñêèìè, à âî-âòîðûõ, — íåñòàöèîíàðíûìè. Ïðè ýòîì íåñòàöèîíàðíîñòü ìî-
æåò ïðîÿâëÿòüñÿ íå òîëüêî â ñóòî÷íîì èçìåðåíèè, íî è â íåäåëüíîì, à òàêæå
â ñåçîííîì. Ïîñòðîåíèå àäåêâàòíîé ìàòåìàòè÷åñêîé ìîäåëè, ðàçðàáîòêà ìåòî-
äîâ îöåíêè îñíîâíûõ åå ñòàòèñòè÷åñêèõ õàðàêòåðèñòèê è âûðàáîòêà ðåêîìåí-
äàöèé äëÿ ðàöèîíàëüíîãî óïðàâëåíèÿ òðàíñïîðòíûìè ïîòîêàìè ÿâëÿþòñÿ íå
òîëüêî âåñüìà ñëîæíûìè, íî è ÷ðåçâû÷àéíî àêòóàëüíûìè çàäà÷àìè.
Ïåðâûå ðàáîòû îá èññëåäîâàíèè òðàíñïîðòíûõ ïîòîêîâ ïóáëèêîâàëèñü áîëåå
80 ëåò òîìó íàçàä. Ñ òåõ ïîð èíòåðåñ ê ýòîé òåìàòèêå íåèçìåííî âîçðàñòàë. Âñëåä-
ñòâèå ìíîãîãðàííîñòè ïðîáëåìû íå óäàëîñü äî ñèõ ïîð (è âðÿä ëè óäàñòñÿ â äàëü-
íåéøåì) ïîñòðîèòü íåêóþ «óíèâåðñàëüíóþ» ìîäåëü, ñïîñîáíóþ õîòÿ áû â ïåðâîì
ïðèáëèæåíèè ó÷åñòü îñíîâíûå îñîáåííîñòè îðãàíèçàöèè è îïòèìàëüíîãî óïðàâëå-
íèÿ òðàíñïîðòíûìè ïîòîêàìè. Îñîáîå âíèìàíèå â èññëåäîâàíèÿõ óäåëÿëîñü ÷àñò-
íûì ìîäåëÿì, ó÷èòûâàþùèì ëèøü îïðåäåëåííûå àñïåêòû îðãàíèçàöèè òðàíñïîð-
òíûõ ïîòîêîâ. Ïðè ýòîì íàèáîëåå ðàñïðîñòðàíåííûìè áûëè ñèñòåìû ìàññîâîãî
îáñëóæèâàíèÿ ñ õîðîøî ðàçâèòîé ìåòîäîëîãèåé èññëåäîâàíèÿ [1].
Çíà÷èòåëüíûå óñèëèÿ ïðåäïðèíèìàëèñü äëÿ ñîçäàíèÿ àíàëèòè÷åñêèõ ìåòî-
äîâ èññëåäîâàíèÿ êîíôëèêòíûõ òðàíñïîðòíûõ ïîòîêîâ [2–9]. Ðàçðàáàòûâàëñÿ ðÿä
÷àñòíûõ ìîäåëåé, îïèñûâàþùèõ âçàèìîäåéñòâèå òðàíñïîðòíûõ ïîòîêîâ, ïîñòó-
ïàþùèõ íà ïåðåêðåñòêè àâòîìîáèëüíûõ ìàãèñòðàëåé. Ïðè ýòîì ïîâåäåíèå ñèñ-
òåì îïèñûâàëîñü öåïüþ Ìàðêîâà âåñüìà ñëîæíîé ñòðóêòóðû. Äàëåå ïðèìåíÿëàñü
ýðãîäè÷åñêàÿ òåîðèÿ ìàðêîâñêèõ öåïåé. Ïðåäëàãàëñÿ èòåðàòèâíî-ìàæîðèòàðíûé
ìåòîä (ñì., íàïðèìåð, [2, 5, 8]), ïîçâîëÿþùèé óñòàíàâëèâàòü íåîáõîäèìûå è/èëè
äîñòàòî÷íûå óñëîâèÿ ýðãîäè÷íîñòè ðàñïðåäåëåíèÿ öåïè Ìàðêîâà. Èç ïîñëåäíèõ
ðàáîò ýòîãî íàïðàâëåíèÿ îòìåòèì [9–11], â êîòîðûõ ïîëó÷åíû íåîáõîäèìûå
óñëîâèÿ ñóùåñòâîâàíèÿ ñòàöèîíàðíîãî ðàñïðåäåëåíèÿ öåïè Ìàðêîâà, îïèñûâàþ-
ùåé ôóíêöèîíèðîâàíèå òàíäåìà èç äâóõ ïåðåêðåñòêîâ. Îáîáùåíèå äàííûõ
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 27
© Í.Þ. Êóçíåöîâ, 2018
ðåçóëüòàòîâ äëÿ íåñêîëüêèõ ïåðåêðåñòêîâ ñîïðÿæåíî ñ ñóùåñòâåííûìè òðóäíîñòÿ-
ìè, ñâÿçàííûìè ñ íåîáîçðèìûì ðàñøèðåíèåì ïðîñòðàíñòâà ñîñòîÿíèé öåïè Ìàð-
êîâà. Ïðåîäîëåòü âû÷èñëèòåëüíûå ñëîæíîñòè íå ïîçâîëÿþò äàæå ñîâðåìåííûå
ìíîãîïðîöåññîðíûå êîìïëåêñû.
Ïîýòîìó, êîãäà ðå÷ü èäåò î ðåøåíèè ðåàëüíûõ ïðàêòè÷åñêèõ çàäà÷, âñå ÷àùå
ïðèìåíÿåòñÿ ìåòîä ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ (èëè ìåòîä Ìîíòå-Êàðëî),
ðàçðàáîòàííûé ïðèáëèçèòåëüíî 70 ëåò òîìó íàçàä äëÿ ìîäåëèðîâàíèÿ ïðîöåññîâ
÷ðåçâû÷àéíîé ñëîæíîñòè. Ïî ìåðå ðàçâèòèÿ âû÷èñëèòåëüíîé òåõíèêè ñôåðà ïðè-
ìåíåíèÿ ìåòîäà Ìîíòå-Êàðëî ñóùåñòâåííî ðàñøèðèëàñü. Ââèäó ñëîæíîñòè âçàè-
ìîçàâèñèìûõ ñëó÷àéíûõ ïðîöåññîâ, èñïîëüçóåìûõ äëÿ îïèñàíèÿ êîíôëèêòíûõ
ïîòîêîâ â ñåòè èç n ïåðåêðåñòêîâ, ìåòîä ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ ÿâëÿåò-
ñÿ åäâà ëè íå åäèíñòâåííûì èíñòðóìåíòîì ÷èñëåííîãî èññëåäîâàíèÿ ïàðàìåòðîâ
ñåòè [12, 13].
 ðàáîòå [13] â êà÷åñòâå ìîäåëè, îïèñûâàþùåé ôóíêöèîíèðîâàíèå òðàíñïîð-
òíîé ñåòè, ïðåäëîæåíî èñïîëüçîâàòü ñåòü èç n îäíîëèíåéíûõ ñèñòåì ìàññîâîãî îá-
ñëóæèâàíèÿ ñî ìíîãèìè âõîäÿùèìè ïîòîêàìè òðåáîâàíèé è ñ îïðåäåëåííûìè âå-
ðîÿòíîñòíûìè çàêîíàìè ïåðåðàñïðåäåëåíèÿ òðåáîâàíèé âíóòðè ñåòè. Èìèòàöèîí-
íîå ìîäåëèðîâàíèå ïîçâîëèëî äîñòàòî÷íî ïîëíî è íàãëÿäíî ïîêàçàòü ïðîáëåìû,
âîçíèêàþùèå â îòäåëüíûõ óçëàõ ñåòè, è ñôîðìóëèðîâàòü àëãîðèòì óïðàâëåíèÿ ïà-
ðàìåòðàìè ñåòè äëÿ îáåñïå÷åíèÿ åå ìàêñèìàëüíî íàäåæíîãî è óñòîé÷èâîãî ôóíê-
öèîíèðîâàíèÿ íà ïðîòÿæåíèè áîëüøîãî ïðîìåæóòêà âðåìåíè.
Íàñòîÿùàÿ ñòàòüÿ — ïðîäîëæåíèå èññëåäîâàíèé, íà÷àòûõ â [13]. Ðàññìàòðè-
âàåòñÿ òà æå ñàìàÿ ìîäåëü ñåòè, óçëàìè êîòîðîé ÿâëÿþòñÿ îäíîëèíåéíûå ñèñòå-
ìû ìàññîâîãî îáñëóæèâàíèÿ. Ñóùåñòâåííîå îòëè÷èå ñîñòîèò â òîì, ÷òî íà âõîä
íåêîòîðûõ ñèñòåì ïîñòóïàþò íåñòàöèîíàðíûå ïóàññîíîâñêèå ïîòîêè òðåáîâàíèé
(òðàíñïîðòíûå ïîòîêè), ÷òî íå ïîçâîëÿåò èñïîëüçîâàòü ñòàöèîíàðíûé ðåæèì ðà-
áîòû ñåòè. Ðàçðàáîòêà ìåõàíèçìîâ óìåíüøåíèÿ î÷åðåäåé ïðè âîçðàñòàþùèõ èí-
òåíñèâíîñòÿõ âõîäÿùèõ ïîòîêîâ ÿâëÿåòñÿ öåëüþ íàñòîÿùåãî èññëåäîâàíèÿ.
Ïðåäëîæåí àëãîðèòì ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ, ïîçâîëÿþùèé âûÿâëÿòü
íàèáîëåå ïðîáëåìíûå ó÷àñòêè ñåòè è ñôîðìóëèðîâàòü ýâðèñòè÷åñêèé àëãîðèòì
óïðàâëåíèÿ ïîòîêàìè, ñïîñîáñòâóþùèé óìåíüøåíèþ âðåìåíè ïðåáûâàíèÿ â î÷å-
ðåäÿõ. Äàííûé àëãîðèòì ïðîèëëþñòðèðîâàí íà ïðèìåðå òðàíñïîðòíîé ñåòè, ñî-
ñòîÿùåé èç 20 ïåðåêðåñòêîâ. Ïðàêòè÷åñêîå ïðèìåíåíèå àëãîðèòìà óïðàâëåíèÿ
ïîòîêàìè ìîæíî ýôôåêòèâíî ïîääåðæàòü ñ ïîìîùüþ äàò÷èêîâ ñáîðà âñåõ
íåîáõîäèìûõ ñòàòèñòè÷åñêèõ äàííûõ, ðàçðàáîòàííûõ â Èíñòèòóòå êèáåðíåòèêè
èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû [14, 15].
ÎÏÈÑÀÍÈÅ ÌÎÄÅËÈ
Ðàññìàòðèâàåìàÿ äàëåå ìîäåëü îïèñûâàåò ôóíêöèîíèðîâàíèå ôðàãìåíòà ãîðîä-
ñêîé òðàíñïîðòíîé ñåòè, ñîñòîÿùåé èç âçàèìîñâÿçàííûõ ïåðåêðåñòêîâ. Î÷åâèä-
íî, ÷òî ïðåäëàãàåìàÿ ìîäåëü ïåðåêðåñòêà íå ìîæåò âêëþ÷àòü â ñåáÿ âñå âîç-
ìîæíûå àëãîðèòìû óïðàâëåíèÿ äâèæåíèåì. Â òî æå âðåìÿ ìîäåëü ÿâëÿåòñÿ
äîñòàòî÷íî îáùåé è ïîçâîëÿåò ó÷èòûâàòü îäíîñòîðîííåå äâèæåíèå, ðåæèì ïî-
âîðîòà «çåëåíàÿ ñòðåëêà», íåýêñïîíåíöèàëüíîñòü ðàñïðåäåëåíèÿ âðåìåíè ïðî-
õîæäåíèÿ ïåðåêðåñòêà è âðåìåíè ïåðåäâèæåíèÿ ìåæäó âçàèìîñâÿçàííûìè ïå-
ðåêðåñòêàìè. Êðîìå òîãî, âåðîÿòíîñòíûå ðàñïðåäåëåíèÿ äàþò âîçìîæíîñòü ïå-
ðåðàñïðåäåëÿòü ïîòîêè òðàíñïîðòà íà êàæäîì ïåðåêðåñòêå ñî ñâåòîôîðîì.
Ïîòîêè ìàøèí (òðåáîâàíèÿ), ïîñòóïàþùèå èçâíå ñåòè íà ðàçëè÷íûå åå óçëû,
ïðåäïîëàãàþòñÿ íåñòàöèîíàðíûìè ïóàññîíîâñêèìè. Ïðåäëàãàåìàÿ ìîäåëü
òðàíñïîðòíîé ñåòè îñíîâàíà íà òàêèõ ïîñòóëàòàõ.
28 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5
Çàäàåòñÿ ñòðóêòóðà ñåòè ïåðåêðåñòêîâ (îäíîëèíåéíûå ñèñòåìû îáñëóæèâàíèÿ):
� èìååòñÿ n âçàèìîñâÿçàííûõ ïåðåêðåñòêîâ (i n�1, ,� ), íà êàæäîì èç êîòî-
ðûõ ðàñïîëîæåí ñâåòîôîð;
� ìîäåëü êàæäîãî ïåðåêðåñòêà èìååò ïî ÷åòûðå âõîäà/âûõîäà ( j �1 2 3 4, , , ),
ïðîíóìåðîâàííûõ ïî ÷àñîâîé ñòðåëêå. Ñâåòîôîðû íà ïåðåêðåñòêàõ ðàáîòàþò
â öèêëè÷åñêîì ðåæèìå, à èìåííî 1 3� (çåëåíûé ñâåò), ïåðåêëþ÷åíèå (æåëòûé
ñâåò), 2 4� (çåëåíûé ñâåò), ïåðåêëþ÷åíèå (æåëòûé ñâåò), 1 3� (çåëåíûé ñâåò) è
ò.ä. (â äàëüíåéøåì çàïèñü «ïåðåêðåñòîê ( , )i j » îçíà÷àåò, ÷òî ðå÷ü èäåò î j-ì âõî-
äå/âûõîäå i-ãî ïåðåêðåñòêà);
� çàäàåòñÿ êîììóòàöèÿ ïåðåêðåñòêîâ ( , ) ( , )i j k l� , ò.å. ïîòîê òðåáîâàíèé
(òðàíñïîðòíûõ ñðåäñòâ) ñ j-ãî âûõîäà i-ãî ïåðåêðåñòêà ïîñòóïàåò íà l-é âõîä k-ãî
ïåðåêðåñòêà, àíàëîãè÷íî ïîòîê òðåáîâàíèé ñ l-ãî âûõîäà k-ãî ïåðåêðåñòêà ïîñòó-
ïàåò íà j-é âõîä i-ãî ïåðåêðåñòêà. Èíà÷å ãîâîðÿ, çàäàíî îòîáðàæåíèå íà ïðîñòðà-
íñòâå ïàð: h i j k l( , ) ( , )� è h k l i j( , ) ( , )� ;
� çàäàåòñÿ ìíîæåñòâî I i j� { }( , ) âõîäîâ ïåðåêðåñòêîâ, íà êîòîðûå èçâíå ñåòè
ïîñòóïàþò íåñòàöèîíàðíûå ïóàññîíîâñêèå ïîòîêè òðåáîâàíèé;
� çàäàåòñÿ ìíîæåñòâî O i j� { }( , ) âûõîäîâ ïåðåêðåñòêîâ, êîòîðûå îäíîâðå-
ìåííî ÿâëÿþòñÿ âûõîäàìè èç ñåòè (ïîñòóïèâøåå íà äàííûé âûõîä òðåáîâàíèå
ïîêèäàåò ñåòü);
� â íà÷àëüíûé ìîìåíò â ñåòè íå èìååòñÿ òðåáîâàíèé (ýòî óñëîâèå ìîæíî èç-
ìåíÿòü â çàâèñèìîñòè îò ðåàëüíîé ñèòóàöèè).
Çàäàþòñÿ ÷èñëåííûå õàðàêòåðèñòèêè ñåòè:
� äëÿ êàæäîãî ( , )i j I� çàäàåòñÿ èíòåíñèâíîñòü � ij t( ), t T�[ , ]0 , ïîòîêà òðå-
áîâàíèé, ïîñòóïàþùåãî íà j-é âõîä i-ãî ïåðåêðåñòêà â ìîìåíò t èç ïðîìåæóòêà
[ , ]0 T , â êîòîðîì èññëåäóåòñÿ ôóíêöèîíèðîâàíèå òðàíñïîðòíîé ñåòè;
� äëÿ êàæäîãî i n�1, ,� çàäàþòñÿ íà÷àëüíûå çíà÷åíèÿ âåëè÷èí � i
( )1 , � i
( )2 è
� i
( )0 — ïðîäîëæèòåëüíîñòè ðàáîòû i-ãî ñâåòîôîðà â ðåæèìàõ ïðîïóñêà ïîòîêîâ
1 3� , 2 4� (çåëåíûé ñâåò) è ïåðåêëþ÷åíèÿ ìåæäó ýòèìè ðåæèìàìè (æåë-
òûé ñâåò) ñîîòâåòñòâåííî. Âåëè÷èíû � i
( )1 , � i
( )2 è � i
( )0 ïðåäïîëàãàþòñÿ äåòåðìèíè-
ðîâàííûìè. Äëÿ óìåíüøåíèÿ îáùåé çàãðóæåííîñòè ñåòè âåëè÷èíû � i
( )1 è � i
( )2
ìîæíî èçìåíÿòü, îäíàêî ïðè ýòîì äîëæíû âûïîëíÿòüñÿ íåðàâåíñòâà
� � �
i i imin
( ) ( )
max
( )1 1 1� � , � � �
i i imin
( ) ( )
max
( )2 2 2� � ;
� ïðè ïîñòóïëåíèè íà âõîä ( , )i j ïîòîê ðàçäåëÿåòñÿ íà òðè: ëåâûé, ïðàâûé è
öåíòðàëüíûé. Ñîîòâåòñòâóþùèå âåðîÿòíîñòè ðàâíû pij
l( ) , pij
r( ) è pij
c( ) , ïðè÷åì
p p pij
l
ij
r
ij
c( ) ( ) ( )� � �1;
� òðåáîâàíèÿ ïðàâîãî ïîòîêà ïðîõîäÿò â ðåæèìå «çåëåíàÿ ñòðåëêà», ò.å. áåç
îæèäàíèÿ ðàçðåøàþùåãî ñèãíàëà ñâåòîôîðà. Âðåìÿ îáñëóæèâàíèÿ (ïðîõîæäåíèå
ïåðåêðåñòêà ( , )i j ) òðåáîâàíèé äàííîãî ïîòîêà èìååò ðàñïðåäåëåíèå F xij
r( ) ( ), x 0;
� òðåáîâàíèÿ ëåâîãî è öåíòðàëüíîãî ïîòîêîâ îáñëóæèâàþòñÿ òîëüêî ïðè ðàç-
ðåøàþùåì ñèãíàëå ñâåòîôîðà è âðåìÿ îáñëóæèâàíèÿ ýòèõ òðåáîâàíèé èìååò ðàñ-
ïðåäåëåíèÿ F xij
l( ) ( ), x 0, è F xij
c( ) ( ), x 0, ñîîòâåòñòâåííî;
� äëÿ êàæäîé ïàðû âçàèìîñâÿçàííûõ ïåðåêðåñòêîâ ( , ) ( , )i j k l� çàäàåòñÿ
ôóíêöèÿ ðàñïðåäåëåíèÿ F xij kl( ),( ) ( ), x 0, âðåìåíè ïðîõîæäåíèÿ òðåáîâàíèé —
îò âûõîäà îäíîãî èç íèõ äî âõîäà äðóãîãî.
Îïèñàííàÿ ìîäåëü èìååò äîñòàòî÷íî ñëîæíóþ ñòðóêòóðó, çàäàâàåìóþ ìíî-
ãî÷èñëåííûìè ïàðàìåòðàìè.  òåîðèè ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ øèðîêî
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 29
ïðèìåíÿþòñÿ äâà ïîäõîäà: ìåòîä óçëîâûõ ìîìåíòîâ è
t-ìåòîä. Ïåðâûé ìåòîä áî-
ëåå ïîïóëÿðíûé. Îí îñíîâàí íà ìîäåëèðîâàíèè èçìåíåíèé ñîñòîÿíèé ñèñòåìû, ïðî-
èñõîäÿùèõ â ìîìåíòû îêîí÷àíèÿ òåõ èëè èíûõ îïåðàöèé (îáñëóæèâàíèå è ïîñòóï-
ëåíèå òðåáîâàíèÿ, ïðîôèëàêòèêà è ò.ï.). Ýòîò ïîäõîä îñîáåííî ýôôåêòèâåí, êîãäà
÷àñòîòà óçëîâûõ ìîìåíòîâ íå î÷åíü âåëèêà. Âòîðîé ìåòîä ìîäåëèðóåò èçìåíåíèå
ñîñòîÿíèÿ ñèñòåìû çà ìàëûé ïðîìåæóòîê âðåìåíè
t (íàïðèìåð,
t � 1 ñ). Ýòî, ïî
ñóòè, äèñêðåòèçàöèÿ âðåìåíè, ïîçâîëÿþùàÿ îïèñûâàòü ïîâåäåíèå ñèñòåìû (à çàòåì
è ìîäåëèðîâàòü) ìíîãîìåðíîé öåïüþ Ìàðêîâà. Èìåííî âòîðûì ìåòîäîì âîñïîëüçó-
åìñÿ äëÿ ìîäåëèðîâàíèÿ ïîñòóïëåíèé òðåáîâàíèé â ñåòü è ïåðåäâèæåíèÿ èõ ìåæäó
óçëàìè. Áóäåì ñ÷èòàòü, ÷òî âñå âåëè÷èíû, îòíîñÿùèåñÿ êî âðåìåíè âûïîëíåíèÿ òîé
èëè èíîé îïåðàöèè, êðàòíû
t (âêëþ÷àÿ è ïðîäîëæèòåëüíîñòü T ðàññìàòðèâàåìî-
ãî ïðîìåæóòêà). Èíà÷å ãîâîðÿ, âñå íåïðåðûâíûå ñëó÷àéíûå âåëè÷èíû � çàìåíÿ-
åì m t�
, ãäå m m t
m
� � �arg min | |�
. Ââèäó ìàëîñòè
t òàêàÿ àïïðîêñèìàöèÿ íå
âíîñèò ñêîëü-íèáóäü çàìåòíîé ïîãðåøíîñòè â ðåçóëüòàò ìîäåëèðîâàíèÿ.
Îáîçíà÷èì w kij
l( ) ( ), w kij
r( ) ( ), w kij
c( ) ( ), k � 0 1, ,�, K T t� /
, ÷èñëî òðåáîâà-
íèé, íàõîäÿùèõñÿ â î÷åðåäè íà ïåðåêðåñòêå ( , )i j â ìîìåíò k t
ïðè ïîâîðîòå íà-
ëåâî, íàïðàâî è ïðè ïðÿìîëèíåéíîì äâèæåíèè ñîîòâåòñòâåííî. Åñëè ïðîñóììè-
ðîâàòü ïî âñåì âîçìîæíûì çíà÷åíèÿì ( , )i j è k , òî ïîëó÷èì íåêèé èíòåãðàëüíûé
ïîêàçàòåëü
W w k w k w kij
l
ij
c
ij
r
k
K
ji
n
� � �
���
[ ( ) ( ) ( )]( ) ( ) ( )
11
4
1
,
õàðàêòåðèçóþùèé îáùóþ çàãðóæåííîñòü ñåòè â ïðîìåæóòêå [ , ]0 T . Âîçíèêàåò
âîïðîñ, êàêèì îáðàçîì ñëåäóåò âûáèðàòü âåëè÷èíû { }� �i i i n( ) ( ), , , ,1 2 1� � ,
îïðåäåëÿþùèå ðåæèìû ðàáîòû ñâåòîôîðîâ, ÷òîáû ìèíèìèçèðîâàòü ñðåäíþþ
çàãðóæåííîñòü ñåòè MW.  íàñòîÿùåé ðàáîòå ïðåäëîæåí ýâðèñòè÷åñêèé àëãî-
ðèòì ðåøåíèÿ ïîñòàâëåííîé çàäà÷è. Íà ÷èñëåííîì ïðèìåðå äàëåå ïðîèëëþñ-
òðèðîâàíû âîçìîæíîñòè äàííîãî àëãîðèòìà.
ÏÎÑÒÐÎÅÍÈÅ ÖÅÏÈ ÌÀÐÊÎÂÀ, ÎÏÈÑÛÂÀÞÙÅÉ ÈÇÌÅÍÅÍÈÅ ÑÎÑÒÎßÍÈÉ ÑÅÒÈ
Ïðîâåäåííàÿ äèñêðåòèçàöèÿ âðåìåíè ïîçâîëÿåò îïèñûâàòü ôóíêöèîíèðîâàíèå
ñåòè áîëåå ïðîñòîé ìîäåëüþ ìíîãîìåðíîé öåïè Ìàðêîâà. Â êàæäûé ìîìåíò âðå-
ìåíè k t
ñîñòîÿíèå ñåòè îäíîçíà÷íî îïðåäåëÿåòñÿ ñîâîêóïíîñòüþ ïåðåìåííûõ:
� � i k
i
( )
,
�
1 åñëè íà -ì ïåðåêðåñòêå ãîðèò çåëåíûé ñâåò â íàïðàâëåíèè 1 3,
2, åñëè ãîðèò æåëòûé ñâåò, ïîñëå êîòîðîãî á
�
óäåò çåëåíûé
â íàïðàâëåíèè 2 4,
åñëè ãîðèò çåëåíûé ñâåò
�
3� â íàïðàâëåíèè 2 4,
åñëè ãîðèò æåëòûé ñâåò, ïîñëå êîòîðî
�
4 , ãî áóäåò çåëåíûé
â íàïðàâëåíèè 1 3�
�
�
�
�
�
�
�
�
�
— äèñêðåòíàÿ ïåðåìåííàÿ, õàðàêòåðèçóþùàÿ ñîñòîÿíèå ñâåòîôîðà íà i-ì ïåðå-
êðåñòêå (i n�1, ,� );
� � i k( ) — âðåìÿ, îñòàâøååñÿ äî ïåðåêëþ÷åíèÿ i-ãî ñâåòîôîðà;
� r kij
l( ) ( ), r kij
r( ) ( ), r kij
c( ) ( ) — ÷èñëî òðåáîâàíèé, îáñëóæèâàåìûõ èëè íàõîäÿ-
ùèõñÿ â î÷åðåäè íà ïåðåêðåñòêå ( , )i j (ïîâîðîòû íàëåâî, íàïðàâî è ïðÿìîëèíåé-
íîå äâèæåíèå). Ïîñêîëüêó ñèñòåìà îáñëóæèâàíèÿ ïðåäïîëàãàåòñÿ îäíîëèíåéíîé,
îáñëóæèâàåòñÿ íå áîëåå îäíîãî òðåáîâàíèÿ;
30 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5
� s kij
l( ) ( ) — âðåìÿ, íåîáõîäèìîå äëÿ çàâåðøåíèÿ ïîâîðîòà íàëåâî òðåáîâàíè-
åì, íàõîäÿùèìñÿ íà ïåðåêðåñòêå ( , )i j â ìîìåíò k t
(àíàëîãè÷íî îïðåäåëÿþòñÿ
s kij
r( ) ( ) è s kij
c( ) ( )), äàííàÿ ïåðåìåííàÿ çàäàåòñÿ ëèøü â ñëó÷àå r kij
l( ) ( ) � 0;
� r kij
( ) ( )0 — ÷èñëî òðåáîâàíèé, íàïðàâëÿþùèõñÿ ê ïåðåêðåñòêó ( , )i j ;
� s k m r kijm ij
( ) ( )( ), , , ( )0 01� � , — âðåìÿ, îñòàâøååñÿ äëÿ äîñòèæåíèÿ ïåðåêðåñ-
òêà ( , )i j m-ì ïî ñ÷åòó òðåáîâàíèåì (ïîñëå ÷åãî òðåáîâàíèå ïîñòóïàåò â îäíó èç
òðåõ î÷åðåäåé).
Ââåäåííûå ïåðåìåííûå îäíîçíà÷íî îïðåäåëÿþò òåêóùåå ñîñòîÿíèå ñåòè
è äàëüíåéøåå åå ôóíêöèîíèðîâàíèå. Ïîýòîìó
� � �( ) ( ( ), ( ), ( ), ( ), ( ),( ) ( ) ( )k k k r k r k r k si i ij
l
ij
r
ij
c
i� j
l
ij
r
ij
ck s k s k( ) ( ) ( )( ), ( ), ( ),
r k s k m r k i n jij ijm ij
( ) ( ) ( )( ), ( ), , , ( ), , , , ,0 0 01 1 1� � �� � � , ),4 0k ,
ÿâëÿåòñÿ öåïüþ Ìàðêîâà. Äëÿ îïðåäåëåííîñòè çàäàäèì íà÷àëüíîå ñîñòîÿíèå
ýòîé öåïè â âèäå
� � �i i i ij
l
ij
r
ij
cr r r( ) , ( ) , ( ) , ( ) ,( ) ( ) ( ) ( )0 1 0 0 0 0 01� � � � ( ) , ( ) ,( )0 0 0 00� �rij
i n j� �1 1 4, , , , ,� � .
Àëãîðèòì ìîäåëèðîâàíèÿ öåïè Ìàðêîâà { }�( ),k k 0 äåòàëüíî èçëîæåí â [13],
ïîýòîìó äàëåå îñíîâíîå âíèìàíèå óäåëèì àëãîðèòìó âûáîðà âåëè÷èí
{ }� �i i i n( ) ( ), , , ,1 2 1� � , ïîçâîëÿþùåìó ñíèçèòü ñðåäíþþ çàãðóæåííîñòü ñåòè MW.
ÀËÃÎÐÈÒÌ ÂÛÁÎÐÀ ÏÀÐÀÌÅÒÐÎÂ {� �
i i
i n
( ) ( ), , , , }1 2 1� �
Ðàññìàòðèâàåìàÿ ìîäåëü — ýòî ñåòü âçàèìîñâÿçàííûõ îäíîëèíåéíûõ ñèñòåì
ìàññîâîãî îáñëóæèâàíèÿ (êîíôëèêòíûå ïîòîêè òðåáîâàíèé). Îäíîëèíåéíîñòü
ñîîòâåòñòâóåò êîíêðåòíîìó íàïðàâëåíèþ (âëåâî, âïðàâî, ïðÿìî) íà êàæäîì èç
÷åòûðåõ âõîäîâ êàæäîãî ïåðåêðåñòêà. Åñëè åùå ó÷åñòü íåñòàöèîíàðíîñòü âõî-
äÿùèõ ïîòîêîâ òðåáîâàíèé, òî êîëè÷åñòâî ñîñòîÿíèé öåïè Ìàðêîâà ñòàíîâèò-
ñÿ îãðîìíûì, ÷òî ïîëíîñòüþ èñêëþ÷àåò èñïîëüçîâàíèå àíàëèòè÷åñêèõ ìåòîäîâ
(åñëè íå ðàññìàòðèâàòü ìàëîèíòåðåñíûå ñëó÷àè n �1 èëè n � 2). Ïîýòîìó ñòà-
òèñòè÷åñêîå ìîäåëèðîâàíèå ÿâëÿåòñÿ åäèíñòâåííûì äåéñòâåííûì èíñòðóìåí-
òîì äëÿ îöåíêè õàðàêòåðèñòèê ñåòè.
Ïóñòü N — ôèêñèðîâàííîå ÷èñëî ðåàëèçàöèé àëãîðèòìà ìîäåëèðîâàíèÿ
ñåòè. Îáîçíà÷èì � ( ; ) ( � ( ; )( ) ( )w k m w k mij
l
ij
r , � ( ; )( )w k mij
c ) îöåíêó ÷èñëà òðåáîâàíèé, íà-
õîäÿùèõñÿ â î÷åðåäè íà ïåðåêðåñòêå ( , )i j â ìîìåíò k t
ïðè ïîâîðîòå íàëåâî (ñî-
îòâåòñòâåííî íàïðàâî è ïðè ïðÿìîëèíåéíîì äâèæåíèè), â m-é ðåàëèçàöèè
àëãîðèòìà. Âåëè÷èíû
� ( ) [ � ( ; ) � ( ; ) � ( ;
( , ) ( ) ( ) ( )W m w k m w k m w k mi i
l
i
c
i
r1 3
1 1 1
� � � ) � ( ; )( )� �
�
w k m
i
l
k
K
3
1
� �� ( ; ) � ( ; )]( ) ( )w k m w k m
i
c
i
r
3 3
,
� ( ) [ � ( ; ) � ( ; ) � ( ;
( , ) ( ) ( ) ( )W m w k m w k m w k mi i
l
i
c
i
r2 4
2 2 2
� � � ) � ( ; )( )� �
�
w k m
i
l
k
K
4
1
� �� ( ; ) � ( ; )]( ) ( )w k m w k m
i
c
i
r
4 4
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 31
èñïîëüçóåì äëÿ îöåíêè ñóììàðíîãî ÷èñëà òðåáîâàíèé, íàõîäÿùèõñÿ â î÷åðå-
äÿõ íà ïåðåêðåñòêå íà âõîäàõ 1, 3 è 2, 4 ñâåòîôîðà i íà ïðîòÿæåíèè âñåãî
ïðîìåæóòêà [ , ]0 T (êàê è ðàíåå, m — òåêóùèé íîìåð ðåàëèçàöèè).  êà÷åñòâå
îöåíêè ñóììàðíîé çàãðóæåííîñòè ñåòè â [ , ]0 T âûáåðåì
� ( , ) [ � ( ) � ( )]( ) ( ) ( , ) ( , )
W
N
W m W mN i i
i
n
m
� �1 2 1 3 2 4
11
1
� �
��
N
, (1)
ãäå � � �( ) ( ) ( )( , , )l l
n
l�
1
� , l �1 2, . Öåëüþ èññëåäîâàíèÿ ÿâëÿåòñÿ ðàçðàáîòêà àëãî-
ðèòìà âûáîðà âåêòîðîâ ïàðàìåòðîâ � ( )1 è � ( )2 , äàþùåãî âîçìîæíîñòü öåëåíàï-
ðàâëåííî óìåíüøàòü � ( , )( ) ( )WN � �1 2 íà êàæäîì øàãå àëãîðèòìà. Äëÿ ýòîãî íåîá-
õîäèìî ðàçðàáîòàòü êðèòåðèé, ïîçâîëÿþùèé îïðåäåëÿòü, êàêèå èìåííî èç êîì-
ïîíåíò âåêòîðîâ � ( ),1 � ( )2 ñëåäóåò èçìåíÿòü è êàêèì îáðàçîì. Ïðåäëàãàåìûé
äàëåå êðèòåðèé îñíîâàí íà èäåå âûðàâíèâàíèÿ çàãðóæåííîñòè ïåðåêðåñòêà íà
âõîäàõ 1, 3 è 2, 4 êàæäîãî ñâåòîôîðà (åñëè íàãðóçêà ðàñïðåäåëåíà íåðàâíîìåð-
íî íà âõîäàõ ñâåòîôîðà, òî ýòî ïðèâîäèò ê íåîïðàâäàííîìó ðîñòó î÷åðåäè íà
îäíîì èç âõîäîâ è, ñëåäîâàòåëüíî, ê óâåëè÷åíèþ îáùåé çàãðóæåííîñòè).
Îáîçíà÷èì
� ( , ) � ( ), ,( ) ( ) ( ) ( , ) � �
iN
l
i
l l
m
N
N
W m l1 2 2
1
1
1 2� ��
�
, (2)
� ( , ) � ( , ) / � ( ,( ) ( ) ( ) ( ) ( ) ( ) ( ) (
� � � � � �iN iN iN
1 2 1 1 2 2 1� 2) ) , (3)
� ( , ) max � ( , ), / � ( ,( ) ( ) ( ) ( ) ( ) (� � �
� �
� �iN iN iN
1 2 1 2 11� { 2) )}. (4)
Î÷åâèäíî, ÷òî � ( , )( ) ( )� � �iN
1 2 1� . Îïòèìèçàöèîííóþ çàäà÷ó ìîæíî ñôîðìó-
ëèðîâàòü ñëåäóþùèì îáðàçîì:
� ( , ) max � ( , ) min( ) ( ) ( ) ( )
,
( ) (
� � � � � �
� �
N
i n
iN
1 2
1
1 2
1 2
� �
� � )
.
Ïîñêîëüêó ïîòîêè òðåáîâàíèé âçàèìîñâÿçàííûå, ëþáîå èçìåíåíèå ïàðàìåò-
ðîâ � ( )1 , � ( )2 ïðèâîäèò ê ïåðåðàñïðåäåëåíèþ ïîòîêîâ, â ðåçóëüòàòå ÷åãî óìåíü-
øåíèå çàãðóæåííîñòè íà îäíîì ïåðåêðåñòêå ìîæåò óâåëè÷èòü çàãðóæåííîñòü
äðóãîãî. Îäíàêî, êàê ïîêàçûâàþò ðàñ÷åòû äëÿ êîíêðåòíûõ òðàíñïîðòíûõ ñåòåé,
íà íà÷àëüíîì ýòàïå óäàåòñÿ ñóùåñòâåííî óìåíüøèòü � ( ,( )� �N
1 � ( ) )2 , ÷òî ïðèâî-
äèò ê óìåíüøåíèþ è ñóììàðíîé çàãðóæåííîñòè � ( , )( ) ( )WN � �1 2 . Â òî æå âðåìÿ
âçàèìíîå âëèÿíèå ïîòîêîâ íå ïîçâîëÿåò óìåíüøèòü � ( )( ) ( )� � � �N
1 2 äî åäèíèöû;
ïðè ýòîì íà î÷åðåäíîì ýòàïå àëãîðèòìà è � ( )( ) ( )WN � � �1 2 ïåðåñòàåò óìåíüøàòüñÿ.
Ýòî ÿâëÿåòñÿ ïðèçíàêîì òîãî, ÷òî ïîëó÷åííûé íàáîð � ( )1 , � ( )2 â îïðåäåëåííîì
ñìûñëå áëèçîê ê îïòèìàëüíîìó.
Ââåäåì íåêîòîðûå ïàðàìåòðû, èñïîëüçóåìûå â ñôîðìóëèðîâàííîì äàëåå àëãî-
ðèòìå:
— êâàíòèëü âðåìåíè, íà êîòîðûé âîçðàñòàþò/óáûâàþò { }� �i i
( ) ( ),1 2 ; R —
êîëè÷åñòâî ïåðåêðåñòêîâ ñ ìàêñèìàëüíûìè çíà÷åíèÿìè { }� ( , )( ) ( )� � �iN
1 2 , ó êî-
òîðûõ ìîãóò îäíîâðåìåííî èçìåíÿòüñÿ { }� �i i
( ) ( ),1 2 ; q (q �1) — âåëè÷èíà, îïðåäå-
ëÿþùàÿ, ñòîèò ëè èçìåíÿòü çíà÷åíèå ñîîòâåòñòâóþùåãî ïàðàìåòðà (�i
( )1 (èëè �i
( )2 )
èçìåíÿåòñÿ íà î÷åðåäíîì øàãå àëãîðèòìà ëèøü â ñëó÷àå, êîãäà � ( , )( ) ( )� � �iN q1 2 � );
32 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5
M — ÷èñëî øàãîâ àëãîðèòìà, òðåáóåìûõ äëÿ ïîäòâåðæäåíèÿ ìèíèìàëüíîñòè ïîëó-
÷åííîãî çíà÷åíèÿ � ( , )( ) ( )WN � �1 2 , ò.å. çà M øàãîâ àëãîðèòìà íå óäàåòñÿ ïîëó÷èòü
ìåíüøåãî çíà÷åíèÿ ñóììàðíîé çàãðóæåííîñòè.
Àëãîðèòì âûáîðà ïàðàìåòðîâ { }� �i i
( ) ( ),1 2 ôîðìóëèðóåòñÿ ñëåäóþùèì
îáðàçîì.
Øàã 1. Çàäàåì íà÷àëüíûå çíà÷åíèÿ � �i i
( ) ( )1
0
1� , � �i i
( ) ( )2
0
2� , i n�1, ,� . Êðîìå
òîãî, ïîëàãàåì �
minW �1010 (ïðîèçâîëüíîå î÷åíü áîëüøîå ÷èñëî, íåîáõîäèìîå
â äàëüíåéøåì äëÿ ñðàâíåíèÿ ñ � ( , )( ) ( )WN � �1 2 ) è m � 0 (ñ÷åò÷èê ÷èñëà ïîñëåäîâà-
òåëüíûõ çíà÷åíèé � ( , )( ) ( )WN � �1 2 , ïðåâûøàþùèõ �
minW ).
Øàã 2. Ìîäåëèðóÿ ôóíêöèîíèðîâàíèå òðàíñïîðòíîé ñåòè, ñòðîèì N ðåàëè-
çàöèé è óñðåäíåíèåì íàõîäèì � ( , )( ) ( )WN � �1 2 (ñì. (1)).
Øàã 3. Åñëè � ( , ) �( ) ( )
minW WN � �1 2 � , òî ïîëàãàåì � � ( , )min
( ) ( )W WN� � �1 2 , m � 0.
Äàëåå çàïîìèíàåì çíà÷åíèÿ � �i i
( ) ( )1 1� � , � �i i
( ) ( )2 2� � , i n�1, ,� , è ïåðåõîäèì
ê øàãó 4. Åñëè � ( , ) �( ) ( )
minW WN � �1 2 � , òî ïåðåõîäèì ê øàãó 9.
Øàã 4. Ñîãëàñíî (2)–(4) âû÷èñëÿåì { }� ( , )( ) ( ) ( ) � �
iN
l 1 2 , { }� ( , )( ) ( )
� �iN
1 2 è
{ }� ( , )( ) ( )� � �iN
1 2 .
Øàã 5. Óïîðÿäî÷èâàåì { }� ( , )( ) ( )� � �iN
1 2 â ïîðÿäêå óáûâàíèÿ, ò.å.
� ( , )( ) ( )� � �i N1
1 2 � � ( , )( ) ( )� � �i N2
1 2 ��
Øàã 6. Åñëè � ( , )( ) ( )� � �i N q
1
1 2 � , òî àëãîðèòì çàâåðøåí.  ýòîì ñëó÷àå ïî-
ëàãàåì � � � �i i i i
( ) ( ) ( ) ( ),1 1 2 2� �� � , i n�1, ,� .
Øàã 7. Ïóñòü � ( , )( ) ( )� � �i N q
1
1 2 � . Íàõîäèì
L
R q
l
i N
i N
R
l
�
�, � ( , ) ,
max : � ( ,
( ) ( )
( ) ( )
åñëè
{
� � �
� � �
1 2
1 2 ) , � ( , ) .( ) ( )� �
�
�
�
�� q qi NR
} åñëè � � �1 2
Øàã 8. Åñëè � ( , )( ) ( )
� �lN
1 2 1� , òî óâåëè÷èâàåì �
l
( )1 íà
.  ïðîòèâíîì ñëó÷àå
óâåëè÷èâàåì �
l
( )2 íà
. Ïðè ýòîì ó÷èòûâàåì âåðõíèå îãðàíè÷åíèÿ �
l max
( )1 è �
l max
( )2 ,
l L�1, ,� . Äàëåå ïåðåõîäèì ê øàãó 2.
Øàã 9. Óâåëè÷èâàåì m íà åäèíèöó. Åñëè m M� , òî àëãîðèòì çàâåðøåí.
 ïðîòèâíîì ñëó÷àå ïåðåõîäèì ê øàãó 2.
Ïðè íàéäåííûõ { }� i
( )1 � è { }� i
( )2 � ðåêîìåíäóåòñÿ ïðîâåðÿòü óñòîé÷èâîñòü ìîäå-
ëèðîâàíèÿ, çíà÷èòåëüíî óâåëè÷èâàÿ êîëè÷åñòâî ðåàëèçàöèé (íàïðèìåð, â 10 ðàç).
Ïîëó÷åííîå ðåøåíèå ìîæåò ñóùåñòâåííî çàâèñåòü îò íà÷àëüíûõ çíà÷åíèé { }�
i0
1( )
è { }�
i0
2( ) . Ïîýòîìó ðåêîìåíäóåòñÿ íàõîäèòü ðåøåíèå ïðè ðàçëè÷íûõ íà÷àëüíûõ
çíà÷åíèÿõ, âûáðàâ òî èç íèõ, êîòîðîå èìååò ìåíüøóþ ñóììàðíóþ çàãðóçêó.
×ÈÑËÅÍÍÛÉ ÏÐÈÌÅÐ
Ðàññìîòðèì ôðàãìåíò òðàíñïîðòíîé ñåòè, ñîñòîÿùåé èç n � 20 ïåðåêðåñòêîâ,
ðàñïîëîæåííûõ â âèäå ìàòðèöû ðàçìåðà 4 5� (ðèñ. 1). Ñòðåëêè íà ðèñ. 1 óêà-
çûâàþò íà îäíîñòîðîííåå äâèæåíèå. Êàê îòìå÷àëîñü ðàíåå, âõîäû/âûõîäû íó-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 33
ìåðóþòñÿ ïî ÷àñîâîé ñòðåëêå. Íîìåð 1 ïðèñâîèì çàïàäíîìó íàïðàâëåíèþ, òåì
ñàìûì îïðåäåëèì ìíîæåñòâà âõîäîâ I è âûõîäîâ O :
I � {( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( ,1 1 1 2 2 2 4 2 5 2 5 3 10 3 11 1 16 1 16 4), ( , ), ( , ),
( , ), ( , ), ( , ), ( , )18 4 19 4 20 3 20 4 },
O � {( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( ,1 2 3 2 4 2 5 2 5 3 6 1 15 3 16 1),
( , ), ( , ), ( , ), ( , ), ( , )16 4 17 4 19 4 20 3 20 4 }.
Ôóíêöèîíèðîâàíèå ñåòè ðàññìàòðèâàåì íà ïðîòÿæåíèè äâóõ ÷àñîâ, ò.å.
T � 7200 c. Èçìåíåíèå ñîñòîÿíèÿ ñåòè áóäåì îòñëåæèâàòü åæåñåêóíäíî, ò.å.
t �1 c.
Çàäàäèì ÷èñëîâûå õàðàêòåðèñòèêè. Ñ÷èòàåì, ÷òî âñå âõîäÿùèå ïîòîêè èìåþò
îäíó è òó æå èíòåíñèâíîñòü: åñëè ( , )i j I� , òî
L
t T t T
t T
�
� � �
� �
0 01 0 08 0 2
0 05 0 08 0 5
. . / , / ,
. . ( / . ),
åñëè
åñëè T t T/ .2 � �
�
�
�
Ïîëîæèì �
0
3( )i � , 1 � �i n (íà÷àëüíûå çíà÷åíèÿ âåêòîðîâ � ( )1 è � ( )2 îïðåäå-
ëåíû äàëåå). Âåðõíèå è íèæíèå ãðàíèöû çàäàäèì òàê: � �
i imin
( )
min
( ) ,1 2 10� �
� �i imax
( )
max
( )1 2 100� � ,1 � �i n. Âåðîÿòíîñòè ðàñùåïëåíèÿ ïîòîêà, âõîäÿùåãî íà ïå-
ðåêðåñòîê ( , )i j , íà ëåâûé, ïðàâûé è öåíòðàëüíûé çàäàþòñÿ ñëåäóþùèì îáðàçîì:
pij
l( ) � 0.2, pij
r( ) � 0.2 è pij
c( ) � 0.6. Åñëè îäíî èç íàïðàâëåíèé èñêëþ÷àåòñÿ ââèäó
îäíîñòîðîííåãî äâèæåíèÿ, òî ñîîòâåòñòâóþùàÿ âåðîÿòíîñòü ïîëàãàåòñÿ ðàâíîé
íóëþ, à îñòàëüíûå âåðîÿòíîñòè ïåðåðàñïðåäåëÿþòñÿ (íàïðèìåð, p r
12
0( ) � ,
p l
12
( ) � 0.25, p c
12
0 75( ) .� ).
 êà÷åñòâå ðàñïðåäåëåíèé F xij
l( ) ( ), F xij
r( ) ( ), F xij
c( ) ( ) è F xij kl( ), ( ) ( ) âûáåðåì óñå-
÷åííûå íîðìàëüíûå ðàñïðåäåëåíèÿ ñîîòâåòñòâåííî ñ ïàðàìåòðàìè aij
l( ) � 8,
� ij
l( )2
� 0.64, aij
r( ) � 4, � ij
r( )2
� 0.16, aij
c( ) � 6, � ij
c( )2
� 0.36 è a ij kl( ), ( ) � 60, �
( ),( )ij kl
2 36�
(óñëîâèåì óñå÷åíèÿ íîðìàëüíî ðàñïðåäåëåííûõ ñëó÷àéíûõ âåëè÷èí ÿâëÿåòñÿ èõ ïî-
ëîæèòåëüíîñòü).
34 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5
1 2 3
6
54
11
16
7
12
17
8
13
18
9
14
19
10
15
20
Ðèñ. 1
Êîíêðåòèçèðóåì ïàðàìåòðû, èñïîëüçóåìûå â ñôîðìóëèðîâàííîì àëãîðèòìå:
N �100,
� 5 ñ, R �10, q � 1.1 è M �10. Ðåçóëüòàòû ñòàòèñòè÷åñêîãî ìîäåëèðî-
âàíèÿ ïðè ðàçëè÷íûõ íà÷àëüíûõ äàííûõ ïðåäñòàâëåíû â òàáë. 1.
 ïðîöåññå ìîäåëèðîâàíèÿ ïðè íà÷àëüíûõ çíà÷åíèÿõ �
i0
1 10( ) � , �
i0
2 10( ) � ,
i n�1, ,� , îáùóþ çàãðóçæåííîñòü ñåòè óäàëîñü óìåíüøèòü ñ 1242024 äî 417209,
ò.å. ïî÷òè â òðè ðàçà. Ïðè ýòîì çíà÷åíèÿ {� ( , )}( ) ( )� � �iN
1 2� � íàõîäÿòñÿ â èíòåðâà-
ëå îò 1.00 (i � 3) äî 1.40 (i �13).
Ïðè íà÷àëüíûõ çíà÷åíèÿõ �
i0
1 20( ) � , �
i0
2 20( ) � , i n�1, ,� , ïðåäëîæåííûé àë-
ãîðèòì ïîçâîëèë óìåíüøèòü îáùóþ çàãðóæåííîñòü ñåòè ñ 671104 äî 398525. Ïðè
ýòîì çíà÷åíèÿ { }� ( , )( ) ( )� � �iN
1 2� � íàõîäÿòñÿ â èíòåðâàëå îò 1.00 (i �19 ) äî 1.18
( )i �12 . Äëÿ ïðîâåðêè óñòîé÷èâîñòè ìîäåëèðîâàíèÿ ïðè íà÷àëüíûõ çíà÷åíèÿõ
� �
i i0
1 1( ) ( )� � , � �
i i0
2 2( ) ( )� � , i n�1, ,� , ïðîâîäèëîñü äîïîëíèòåëüíîå ìîäåëèðîâàíèå
îáùåé çàãðóæåííîñòè ñåòè. Îêàçàëîñü, ÷òî � ( , )( )* ( )*WN � �1 2 � 401587 ïðè
N �1000, ò.å îòêëîíåíèå çíà÷åíèé ïðè N �100 è N �1000 íå ïðåâûøàåò 0.8 %.
Èíà÷å ãîâîðÿ, ðåçóëüòàòû ìîäåëèðîâàíèÿ ïðè îòíîñèòåëüíî íåáîëüøîì ÷èñëå
ðåàëèçàöèé N �100 îáåñïå÷èâàþò äîñòàòî÷íî òî÷íûå îöåíêè.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 35
Ò à á ë è ö à 1. Ðåçóëüòàòû ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ ïðè íà÷àëüíûõ çíà-
÷åíèÿõ �
i0
1( ) , �
i0
2( ) , i n�1, ,�
Ñôåòîôîð,
i
Âðåìÿ ðàáîòû ñôåòîôîðîâ, ñ
íà÷àëüíûå çíà÷åíèÿ
�
i0
1
10
( ) � , �
i0
2
10
( ) �
íà÷àëüíûå çíà÷åíèÿ
�
i0
1
20
( ) � , �
i0
2
20
( ) �
íà÷àëüíûå çíà÷åíèÿ
�
i0
1
30
( ) � , �
i0
2
30
( ) �
äëèòåëüíîñòü ðåæèìîâ äëèòåëüíîñòü ðåæèìîâ äëèòåëüíîñòü ðåæèìîâ
�
i
( )1 �
�
i
( )2 �
�
i
( )1 �
�
i
( )2 �
�
i
( )1 �
�
i
( )2 �
1 25 30 20 25 30 35
2 40 20 45 25 55 30
3 20 35 25 45 30 50
4 30 35 30 35 40 45
5 20 15 25 20 45 35
6 30 25 25 25 45 45
7 55 45 40 35 50 45
8 40 55 30 45 35 55
9 40 35 30 25 50 45
10 25 40 25 40 30 45
11 20 45 25 50 35 60
12 40 65 50 75 50 80
13 70 45 45 30 70 40
14 35 20 35 20 50 30
15 40 20 40 20 60 30
16 15 15 25 25 30 30
17 30 30 30 30 35 35
18 40 25 40 25 50 30
19 15 20 20 30 30 40
20 15 15 20 20 30 30
Ïðè íà÷àëüíûõ çíà÷åíèÿõ �
i0
1 30( ) � , �
i0
2 30( ) � , i n�1, ,� , èñïîëüçîâàíèå àë-
ãîðèòìà îïòèìèçàöèè ïîçâîëèëî óìåíüøèòü îáùóþ çàãðóæåííîñòü ñåòè ñ 566071
äî 425164. Ïðè ýòîì çíà÷åíèÿ { }� ( , )( ) ( )� � �iN
1 2� � íàõîäÿòñÿ â èíòåðâàëå îò 1.00
( )i �1 äî 1.15 (i �13).
Ñðàâíåíèå íàáîðîâ { }� �( ) ( ),1 2� � äëÿ âñåõ òðåõ ñëó÷àåâ ïîêàçûâàåò èõ ñîãëà-
ñîâàííîñòü. Èíà÷å ãîâîðÿ, åñëè ïðè êàêîì-ëèáî ðåæèìå ñâåòîôîðà îïðåäåëåííîå
íàïðàâëåíèå ïðèîðèòåòíîå (çåëåíûé ñâåò ãîðèò äîëüøå), òî ýòà òåíäåíöèÿ
ïðîñëåæèâàåòñÿ â êàæäîì âàðèàíòå.
ÇÀÊËÞ×ÅÍÈÅ
Òðàíñïîðòíàÿ ñåòü — ýòî ñåòü ïåðåêðåñòêîâ, íà êàæäîì èç êîòîðûõ íàõîäèòñÿ
ñâåòîôîð. Ïðîâåäåííûå èññëåäîâàíèÿ ïîçâîëèëè âûäåëèòü èíòåãðàëüíûé ïîêà-
çàòåëü, îïòèìèçàöèÿ êîòîðîãî ñïîñîáñòâóåò ñíèæåíèþ îáùåé çàãðóæåííîñòè
ñåòè â çàäàííîì ïðîìåæóòêå [ , ]0 T . Ïðåäëîæåí ýâðèñòè÷åñêèé àëãîðèòì ìèíè-
ìèçàöèè ñðåäíåé çàãðóæåííîñòè ñåòè, îñíîâàííûé íà ïåðåðàñïðåäåëåíèè ïîòî-
êîâ òðåáîâàíèé íà êàæäîì ñâåòîôîðå. Ïðèìåíåíèå àëãîðèòìà äëÿ ñåòè èç
20 ïåðåêðåñòêîâ ïîçâîëèëî äîáèòüñÿ òðîåêðàòíîãî óìåíüøåíèÿ ñóììàðíîãî
âðåìåíè ïðåáûâàíèÿ òðåáîâàíèé â ñåòè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ãíåäåíêî Á.Â., Êîâàëåíêî È.Í. Ââåäåíèå â òåîðèþ ìàññîâîãî îáñëóæèâàíèÿ. Ìîñêâà: ËÊÈ,
2007. 400 ñ.
2. Ôåäîòêèí Ì.À. Ïðîöåññû îáñëóæèâàíèÿ è óïðàâëÿþùèå ñèñòåìû. Ìàòåìàòè÷åñêèå âîïðîñû
êèáåðíåòèêè. Ìîñêâà: Íàóêà, 1996. Ñ. 51–70.
3. Ëèòâàê Í.Â., Ôåäîòêèí Ì.À. Âåðîÿòíîñòíàÿ ìîäåëü àäàïòèâíîãî óïðàâëåíèÿ êîíôëèêòíûìè
ïîòîêàìè. Àâòîìàòèêà è òåëåìåõàíèêà. 2000. ¹ 5. Ñ. 67–76.
4. Çîðèí À.Â., Ôåäîòêèí Ì.À. Îïòèìèçàöèÿ óïðàâëåíèÿ äâàæäû ñòîõàñòè÷åñêèìè íåîðäèíàðíû-
ìè ïîòîêàìè â ñèñòåìàõ ñ ðàçäåëåíèåì âðåìåíè. Àâòîìàòèêà è òåëåìåõàíèêà. 2005. ¹ 7.
Ñ. 102–111.
5. Ñåìåíîâ Â.Â. Ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå òðàíñïîðòíîãî ïîòîêà íà íåðåãóëèðóåìîì ïå-
ðåñå÷åíèè. Ìàòåì. ìîäåëèðîâàíèå. 2008. Ò. 20, ¹ 10. Ñ. 14–22.
6. Afanaseva L., Bulinskaya E. Stochastic models of transport flows. Proc. of the XIII Int. Conf.
“Applied Stochastic Models and Data Analysis” (Vilnius, 2009). P. 320–324.
7. Ôåäîòêèí Ì.À., Ôåäîòêèí À.Ì. Àíàëèç è îïòèìèçàöèÿ âûõîäíûõ ïðîöåññîâ ïðè öèêëè÷åñêîì
óïðàâëåíèè êîíôëèêòíûìè òðàíñïîðòíûìè ïîòîêàìè Ãíåäåíêî–Êîâàëåíêî. Àâòîìàòèêà è
òåëåìåõàíèêà. 2009. ¹ 12. Ñ. 92–108.
8. Ôåäîòêèí Ì.À., Ôåäîòêèí À.Ì. Èçó÷åíèå ñâîéñòâ ïîòîêà Ãíåäåíêî–Êîâàëåíêî. Âåñò. Íèæå-
ãîðîäñêîãî ãîñ. óí-òà èì. Í.È. Ëîáà÷åâñêîãî. 2008. ¹ 6. Ñ. 156–160.
9. Zorin A.V. Stability of a tandem of queueing systems with Bernoulli noninstantaneous transfer of
customers. Theory of Probability and Mathematical Statistics. 2012. P. 173–188.
10. Çîðèí À.Â. Ñòîõàñòè÷åñêàÿ ìîäåëü ñîîáùàþùèõñÿ ñèñòåì ìàññîâîãî îáñëóæèâàíèÿ ñ ïîâòîð-
íûìè âûçîâàìè è öèêëè÷åñêèì óïðàâëåíèåì â ñëó÷àéíîé ñðåäå. Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. 2013. ¹ 6. Ñ. 100–109.
11. Çîðèí À.Â., Êóçíåöîâ Í.Þ., Êóçíåöîâ È.Í. Àíàëèç ñòîõàñòè÷åñêîé ìîäåëè ñîîáùàþùèõñÿ
ñèñòåì ìàññîâîãî îáñëóæèâàíèÿ ñ ïîâòîðíûìè âûçîâàìè è öèêëè÷åñêèì àëãîðèòìîì óïðàâëå-
íèÿ â ñëó÷àéíîé ñðåäå. Âåñò. Íèæåãîðîäñêîãî ãîñ. óí-òà èì. Í.È. Ëîáà÷åâñêîãî. 2013. ¹ 5.
Ñ. 54–65.
12. Balsys K., Valinevicius A., Zilys M. Crossroads load modeling. Proc. of the ITI. The 30th Int. Conf.
on Information Technology Interfaces. 2008. P. 685–690.
36 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5
13. Êóçíåöîâ Í.Þ., Ôåäîòêèí Ì.À. Ìîäåëèðîâàíèå êîíôëèêòíûõ òðàíñïîðòíûõ ïîòîêîâ. Êèáåð-
íåòèêà è ñèñòåìíûé àíàëèç. 2013. ¹ 6. Ñ. 32–39.
14. Boyun V. Intelligent selective perception of visual information in vision systems. Proc. of the 6-th
IEEE Int. Conf. on Intelligent Data Acquisition and Advanced Computing Systems: Technology and
Application (Prague, 2011). Vol. 1. P. 412–416.
15. Boyun V. Directions of development of intelligent real time video systems. Application and Theory
of Computer Technology. 2017. Vol. 2, N 3. P. 48–66.
Íàä³éøëà äî ðåäàêö³¿ 10.10.2017
Ì.Þ. Êóçíºöîâ
ÅÂÐÈÑÒÈ×ÍÈÉ ÀËÃÎÐÈÒÌ ÊÅÐÓÂÀÍÍß ÊÎÍÔ˲ÊÒÍÈÌÈ ÍÅÑÒÀÖ²ÎÍÀÐÍÈÌÈ
ÒÐÀÍÑÏÎÐÒÍÈÌÈ ÏÎÒÎÊÀÌÈ
Àíîòàö³ÿ. Ðîçãëÿíóòî ìîäåëü ìåðåæ³, âóçëàìè ÿêî¿ º îäíîë³í³éí³ ñèñòåìè
ìàñîâîãî îáñëóãîâóâàííÿ. Íà âõ³ä äåÿêèõ ñèñòåì íàäõîäÿòü íåñòàö³îíàðí³
ïóàññîí³âñüê³ ïîòîêè âèìîã (òðàíñïîðòí³ ïîòîêè). Çàïðîïîíîâàíî àëãîðèòì
ñòàòèñòè÷íîãî ìîäåëþâàííÿ, ÿêèé äîçâîëÿº âèÿâèòè íàéá³ëüø ïðîáëåìí³
ì³ñöÿ ó ìåðåæ³ òà ñôîðìóëþâàòè åâðèñòè÷íèé àëãîðèòì êåðóâàííÿ ïîòîêà-
ìè, ÿêèé ñïðèÿº çìåíøåííþ ÷àñó ïåðåáóâàííÿ ó ÷åðãàõ. Öåé àëãîðèòì
ïðî³ëþñòðîâàíî íà ïðèêëàä³ òðàíñïîðòíî¿ ìåðåæ³, ÿêà íàë³÷óº 20 ïåðå-
õðåñòü.
Êëþ÷îâ³ ñëîâà: ñèñòåìà îáñëóãîâóâàííÿ, íåñòàö³îíàðíèé ïóàññîí³âñüêèé
ïîò³ê, ìåòîä ñòàòèñòè÷íîãî ìîäåëþâàííÿ, ëàíöþã Ìàðêîâà, êåðóâàííÿ ïî-
òîêàìè.
N.Yu. Kuznetsov
HEURISTIC CONTROL ALGORITHM FOR CONFLICTING NONSTATIONARY
TRANSPORT FLOWS
Abstract. The paper considers a model of the network with nodes being
one-server queueing systems. The non-stationary Poisson flows are input flows
to some queueing systems (transport flows). A statistical simulation algorithm is
proposed. It identifies weak points of the network and allows formulating a
heuristic flow control algorithm that reduces the total waiting time. This
algorithm is illustrated by an example of a transport network with 20 crossroads.
Keywords: queueing system, nonstationary Poisson flow, Monte Carlo method,
Markov chain, flow control.
Êóçíåöîâ Íèêîëàé Þðüåâè÷,
÷ëåí-êîð. ÍÀÍ Óêðàèíû, äîêòîð òåõí. íàóê, çàâåäóþùèé îòäåëîì Èíñòèòóòà êèáåðíåòèêè
èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, Êèåâ; ïðîôåññîð êàôåäðû Íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåð-
ñèòåòà Óêðàèíû «Êèåâñêèé ïîëèòåõíè÷åñêèé èíñòèòóò èìåíè Èãîðÿ Ñèêîðñêîãî»,
e-mail: kuznetsov2016@icloud. com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 37
|