Введение. Актуальность разрешения конфликтов на транспортных сетях является одной из наиболее важных задач инфраструктуры различных населенных пунктов. Использование теоретико-игрового подхода для данного класса задач обусловлено следующими факторами:
- наличие конфликта между сторонами;
- дефицит информации о стратегиях конкурентов;
- увеличение “выгоды” в случае создания коалиции между игроками.
Нахождение эффективных путей поиска оптимального распределения выигрыша для каждой стороны конфликта, с учетом всех вышеперечисленных факторов, позволяет использовать математический аппарат теории игр для успешного разрешения конфликтов.
Универсальность методов теории кооперативных игр позволяет задействовать их в различных конфликтных ситуациях. Так, в статье [1] предметом исследования выступает транспортная сеть. Автор предлагает наиболее оптимальный способ дележа издержек между участниками. Математическим аппаратом в этой экономической постановке выступает теория кооперативных игр.
Исследование [3] посвящено сетевой игре, в которой N игроков пытаются попасть в определенную точку сети. Данная постановка задачи является оптимизационной, так как затраты игроков минимизируются. Несмотря на сложность, вызванную тем, что траектории игроков не должны пересекаться (не имеют общих дуг), найдено множество равновесных состояний, в котором и достигается минимум расходов на перемещение в нужный пункт.
При решении задач, связанных с транспортным конфликтом, не всегда применяются теоретико-игровые методы. Например, в исследовании [4] представлены подходы к решению транспортных проблем. Базой являются игры Штакельберга. Они некооперативные, однако являются, своего рода, инструментом для принятия решений в конфликтной ситуации, заданной на транспортном узле.
Авторы в работе [5] в качестве модели исследования рассматривают транспортную сеть г. Пекин. Учитывая взаимосвязи между районами города, транспортной структурой, инфраструктурой и другими факторами, авторы выдвигают предположение по оптимизации транспортного узла.
В предложенной статье также предлагается исследование части транспортного узла населенного пункта с учетом конкуренции перевозчиков.
Предмет исследования — модель ориентированного взвешенного графа, представляющего собой транспортную сеть района города Апатиты, Мурманская область. Вес каждой дуги представляет собой максимальный поток пассажиров транспортного средства, которое может осуществить перевозку по данному элементу пути. В конфликте участвуют три игрока (три автомобильные компании), перед каждым из которых стоит задача перевести наибольшее число пассажиров из начального пункта в конечный.
Объектом исследования является теоретико-игровые методы.
Целью работы является исследование конкретного транспортного узла для нахождения оптимального результирующего вектора, компонентами которого являются наиболее выгодное распределение пассажиропотока для каждого перевозчика (конкурента) с использованием методов из теории кооперативных игр.
Задачи:
- Построить модель графа по существующему району города Апатиты.
- Написать программу на языке C++, позволяющую автоматизировать получение основных характеристик.
- Найти векторы, определяющие С – ядро.
- Получить значения вектора Шепли.
- Проанализировать полученные результаты.
Постановка задачи. На рис. 1 представлен транспортный узел, являющийся частью транспортной сети г. Апатиты, Мурманской области.
Рис.1 Граф транспортного узла г. Апатиты
На этой развязке действуют три конкурирующих перевозчика, представляющие множество игроков V = (1, 2, 3). Вершинами обозначены остановки, дуги — это участки дорог, соединяющие их, веса дуг — это максимальный пассажиропоток на данной части транспортной сети. Между перевозчиками пути распределяются следующим образом:
I = {(s, 1), (2, 4), (4, 7), (7, t)}, II = {(s, 6), (3, 4), (6, 7), (1, 3)},
III = {(s, 2), (6, 2), (2, 1), (3, 5), (5, t)}.
Значения характеристической функции для любой коалиции по отдельно взятому конкуренту принимают нулевые значения, так как ни одному игроку-конкуренту не принадлежит последовательный набор дуг, чтобы он смог добраться от начальной до конечной вершины.
Далее были рассмотрены коалиции конкурентов по два, и выписаны все доступные им пути.
Коалицию первых двух v(1, 2) определяют следующие пути:
(s, 1)→(1, 3)→(3, 4)→(4, 7)→(7, t);
(s, 6)→(6, 7)→(7, t).
Соответственно для первого и третьего и второго и третьего:
v(1, 3):
(s, 2)→(2, 4)→(4, 7)→(7, t).
v(2, 3):
(s, 6)→(6, 2)→(2, 1)→(1, 3)→(3, 5)→(5, 7);
(s, 2) →(2, 1)→(1, 3)→(3, 5)→(5, 7).
Для нахождения значений характеристической функции коалиций по паре перевозчиков был использован алгоритм поиска максимального потока на ориентированном взвешенном графе. Таким образом, исходный граф преобразуется в подграф для коалиции ⟨1, 2⟩, изображенный на рисунке 2.
Рис. 2 Преобразованный граф транспортной развязки для объединения игроков 1 и 2.
Согласно алгоритму Форда - Фалкерсона определяется характеристическая функция:
(s, 1)→(1, 3)→(3, 4)→(4, 7)→(7, t)
a1 = min{35, 35, 35, 60, 43} = 35
(s, 6)→(6, 7)→(7, t)
a2 = min{51, 20, 8} = 8
a1+a2 = 35+8 = 43
Следовательно, v(1, 2) = 43. Это означает, что коалиция первого и второго дают выигрыш больший, чем они могли бы получить в случае, если бы перевозили пассажиров без объединения усилий.
Для игроков коалиции ⟨1, 3⟩ возможен лишь один путь, поэтому v(1, 3) = min{50, 45, 60, 43} = 43.
На рисунке 3 изображен преобразованный исходный граф, определяющий пути коалиции ⟨2, 3⟩.
Рис. 3 Преобразованный граф транспортной развязки для объединения игроков 2 и 3.
Определим характеристическую функцию:
(s, 6)→(6, 2)→(2, 1)→(1, 3)→(3, 5)→(5, t)
a1 = min{51, 36, 35, 35, 40, 40} = 35
Больше путей нет, так как вес дуги в пути до итоговой вершины принимает нулевое значение.
Наконец, рассмотрим коалицию ⟨1, 2, 3⟩, которая определена на всем графе:
(s, 1)→(1, 3)→(3, 5)→(5, t)
a1 = min{35, 35, 40, 40} = 35
(s, 2)→(2, 4)→(4, 7)→(7, t)
a2 = min{50, 45, 60, 43} = 43
a1+a2 = 35+43 = 78
Таким образом, была получена система, определяющая выигрыши рассматриваемой
кооперативной игры.
Вектор a=(a1, a2, a3) – вектор неизвестных, представляющий оптимальное распределение количества человек в пассажиропотоке на всех игроков в условиях конкуренции.
До этапа вычисления векторов С–ядра необходимо осуществить его проверку на пустоту.
При проверке пустоты ядра была использована теорема Бондаревой–Шепли [2], согласно которой для игры трех лиц С–ядро не пусто тогда и только тогда, когда:
v(N) ≥ max{v[1]+v[2]+v[3];
v[1]+v[2,3];
v[2]+v[1,3];
v[3]+v[1,2];
1/2(v[1,2]+v[1,3]+v[2,3])}.
Действительно, 78 ≥ max{0; 43; 43; 35; 60.5}.
Для того, чтобы некоторый дележ a принадлежал С–ядру, необходимо и достаточно соблюдение следующих условий для каждого элемента результирующего вектора:
Преобразуя систему, получим ограничения значений дележа сверху и снизу:
Для представления С–ядра в геометрической интерпретации необходимо определить вершины. Были составлены и решены следующие системы:
Решения имеют вид: (8, 35, 35), (43, 0, 35), (43, 35, 0).
Вектор Шепли определяется следующим образом [2]:
φ_i (v) = ∑〖(k - 1)!(n - k)!/n! (v(K) - v(K - i)) 〗
В результате решения найдены следующие компоненты вектора Шепли:
Вектор Шепли имеет вид:
Таким образом, объединение всех трех перевозчиков является наиболее «выгодным» с точки зрения перевозки пассажиров, а значит и получения прибыли.
Выводы. Результаты исследовательской работы, позволяет сделать ряд выводов.
Применение такого математического аппарата, как кооперативная теория игр, позволяет значительно упростить вычислительный этап разрешения транспортного конфликта.
Для конкретного графа, который был построен для транспортной развязки г. Апатиты построена модель ориентированного взвешенного графа для рассматриваемого конфликта, а также вычислены вектора, определяющие С – ядро, и найдены значения вектора Шепли.
Полученные характеристики, а именно С–ядро – точный процесс вычисления множества недоминируемых дележей, а также вектор Шепли позволяют определить оптимальный результирующий вектор выигрыша игроков в кооперативной игре.
Применение теоретико-игрового подхода при решении конкретной транспортной конфликтной задачи вполне приемлем, так как полученные результаты не противоречат постановке задачи и логике процесса.
Всем перевозчикам, задействованным на данной транспортном узле, гораздо выгоднее сотрудничать вместе, действуя на правах одной коалиции, состоящей из всех участников.
Объединение перевозчиков позволит увеличить их прибыль в процессе.
Важно подчеркнуть, что все полученные данные были результатом работы программы на языке С++.
Полученные в ходе исследования данные в перспективе могут оказаться хорошей отправной точкой для автоматизации поиска решений различных конфликтов в транспортных задачах. Применяя изученные материалы, можно рассматривать сценарии на более крупных инфраструктурных развязках с использованием большего числа входных данных, влияющих на исход игры.
Список литературы
Мовсесян В. А. Теоретико-игровой подход распределения затрат между участниками транспортной сети / В. А. Мовсесян // Фундаментальные и прикладные исследования в современном мире. 2015. – № 10. – С. 80-85.
Бондарева О. Н. Некоторые применения методов линейного программирования к теории кооперативных игр // Проблемы кибернетики. – 1963. – № 10. – С. 119–139.
Петросян Л. А. Одна транспортная теоретико-игровая модель на сети / Л. А. Петросян // МТИП. – 2011. – № 3(4). – С. 89-98.
The applicability of non-cooperative game theory in transport analysis / Y. Hollander, J. Prasher // Transportation. – 2006. – №33. – p. 481-496.
The Optimization and Adjustment of Passenger Transport Hub Based on the Urban Spatial Evolution / W. Qiao, Z. Zhang, C. He [etc] // 17th COTA International Conference on Transportation Professionals. – 2018. – p. 3177-3184.