Russian Federation
Russian Federation
Russian Federation
The article considers the problem of segmenting the interrelated terminals of a transport network into a fixed number of relatively autonomous transport hubs when solving transport technical problems. There has been proposed a most common and simple option for solving the graph partition problems - a problem of segmenting the transport network by r-partitioning. Useful practical approaches to solving the problem are studied. There has been proposed an assessing version for developing the transport network segmentation procedures and their content-richness. A heuristic procedure for the transport network segmentation by separation property for building the transportation hub system is defined. For the considered heuristic procedures of solving the set problem there is conducted the study of heuristic procedure properties and assessed the worst scenarios. It is found that the segmentation of the regional transport network into separate transport hubs using the described procedures can be carried out for the subclass of separable tiling or separable on average tiling, if no further possible improvements could be assessed. The considered procedures of the regionʼs transport network graph segmentation have one common feature: these procedures preserve some beneficial properties in tiling obtained in the course of building the transportation hub. It has been stated that the procedures can serve as a ground in the synthesis of a hierarchical group represented as a chain of inner tilings, each being “good” in terms of cluster analysis. The assessment richness of the transport network partitioning into the transport hubs is analyzed using a computational experiment.
transport hub, transport network partitioning, transport network, transport network segmentation, terminal
Введение
При решении технических проблем, связанных с проектированием и анализом деятельности транспортных сетей и транспортных узлов, может возникнуть задача оптимального разбиения транспортной сети того или иного региона на множество взаимосвязанных систем транспортных узлов, которые в свою очередь являются относительно автономными подмножествами терминалов. В математической постановке эта задача может быть сведена к известной задаче разрезания сети (графа) [1–3]. На практике для решения обозначенной задачи обычно используются эвристические методы разбиения, что объясняется значительной сложностью и трудоемкостью точных алгоритмов разбиения. В связи с этим актуальной является проблема изучения свойств различных эвристических процедур разбиения и оценки их эффективности [3]. В данном случае рассматривается распространенный и достаточно простой вариант задач разрезания графа – задача r-разрезания – и изучаются полезные с практической точки зрения процедуры решения данной задачи. Кроме того, в статье предложен вариант оценки наихудшего развития упомянутых процедур сегментации транспортной сети, их содержательности [4, 5].
Постановка задачи
Пусть задана транспортная сеть какого-либо региона, модель которой представлена в виде взвешенного графа G с множеством вершин (терминалов) N = {l, 2, ..., n}. Каждое разбиение – транспортный узел р – может состоять из взаимно непересекающихся множеств терминалов N1, N2, ... , Nr(p), каждый из которых будем характеризовать величиной внутреннего веса IW, заданного как
где ωik – вес ребра (i, k) в графе G, равный грузообороту между терминалами i и k, причем если ребро графа (i, k) отсутствует, то следует принимать ωik = 0.
В данном варианте сегментации транспортной сети требуется найти разбиение множества вершин графа сети N на r непустых подмножеств (узлов), имеющих наибольшее значение внутреннего веса. Для этой цели введем ряд дополнительных обозначений. Пусть:
– суммарный вес ребер графа
– внешний вес разбиения
– суммарный вес ребер подмножества вида
если
где вес связей подмножеств K и M Ì N;
– средний вес ребер множества
Если множество М состоит только из одной вершины (|M| = 1), то необходимо принимать величину q(M) = ∞, а средний вес связей между множествами Nj и Nl определять через значение
ljl (p) = W(Nj, Nl) / njnl.
Здесь и далее ns = |Ns| – мощность множества Ns, причем число внутренних связей в разбиении p определяется как
а число внешних связей в разбиении p определяется следующим образом:
.
Используя введенные обозначения, опишем первый вариант эвристической процедуры решения задачи по формированию в транспортной сети региона систем транспортных узлов (процедура П1). Для этой цели будем считать, что число п кратно числу r, или n = rh. В противном случае множество N можно дополнить необходимым числом изолированных вершин. Затем произвольным образом построим исходное разбиение множества N на r подмножеств по h элементов (терминалов) и на каждом последующем шаге (итерации) некоторым образом будем выбирать пары вершин графа из различных подмножеств I Î Ns, j Î Nt, причем такие, чтоб
(1)
Далее в процедуре будем производить обмен, при котором вершина i включается в множество Nt, а вершина j – в множество Ns, который увеличивает внутренний вес разбиения. Если пары вершин, удовлетворяющей выражению (1), не существует, то эвристическая процедура сегментации вершин графа прекращается.
В качестве второй процедуры (процедуры П2) формирования в транспортной сети региона систем транспортных узлов можно рассмотреть такую схему сегментации, при которой на нулевом шаге множество N рассматривается как набор из одноэлементных подмножеств, а на каждом последующем шаге по определенному правилу выбирается пара подмножеств Ns и Nt и производится их объединение. На шаге (n – r) получаем искомое разбиение вершин графа на r подмножеств.
Очевидно, что как в первой, так и второй процедуре для полного описания конкретного процесса сегментации достаточно указать только используемое правило выбора или правило выбора и метод дихотомии соответственно.
Условия отделимости структуры транспортного узла от транспортной сети региона
Для описания процедуры сегментации допустим, что IА – значение внутреннего веса разбиения, полученного с помощью одной из вышеописанных процедур сегментации транспортной сети региона П, а величина I* – оптимальное значение внутреннего веса полученных разбиений. В описанных выше эвристических процедурах или их конкретизациях можно найти нижние оценки вида IП Î cSW, где с < 1, при этом очевидно, что 1П > сI*.
Полученные оценки обусловлены свойствами кластерного анализа. С учетом этих свойств можно сформулировать предположение о правиле отделимости для множества терминалов транспортной сети, обладающего свойством транспортного узла [6, 7]. Так, разбиение терминалов р = (N1, N2, ..., Nr) будет являться отделимым от транспортной сети региона, если существует неотрицательное число α (порог отделимости), причем такое, чтоб
для любых i, s, t = 1, r.
Отделимое разбиение терминалов транспортного узла компактно в смысле [1], а каждый терминал из подмножеств транспортного узла можно назвать сгущением в среднем [1].
Введем еще один ослабленный вариант свойства отделимости разбиения терминалов от транспортной сети. Так, разбиение р = (N1, N2, ..., Nr) можно называть отделимым в среднем, если выполняется условие, записанное как
(2)
то есть средний вес внутренних связей терминалов больше среднего веса внешних связей этих же терминалов. Величину, равную
можно принять в качестве порога отделимости разбиения в среднем, причем это свойство эквивалентно некоторой нижней оценке для величины IW(p).
Разбиение терминалов р будет отделимо в среднем только тогда, когда выполняется условие вида
(3)
Это утверждение достаточно просто подтвердить. Если записать неравенство (2) в виде
то, подставляя выражение
и учитывая, что
получим отношение
которое является эквивалентным выражению (3).
Здесь следует заметить, что все применяемые преобразования являются тождественными, и поэтому из выражения (3) всегда можно получить отношение (2). Кроме того, оценка (3) достижима как в классе отделимых в среднем для разбиений, так и в более узком подклассе отделимых разбиений. Любое разбиение р полного графа транспортных сетей региона с единичными весами ребер отделимо с порогом, равным α = 1, при этом выполняется равенство
Таким образом, сегментация транспортной сети региона на отдельные транспортные узлы по вышеописанным процедурам может быть осуществлена для подкласса отделимых или отделимых в среднем разбиений, если будет реализовываться оценка вида (3), которую в принципе уже нельзя улучшить.
Оценка отделимости транспортного узла от транспортной сети региона
Для процедуры сегментации графа транспортной сети П1 разбиение, получаемое по окончании действий этой процедуры, отделимо в среднем. Очевидность этого заключения следует из свойства различимости подмножеств I Î Ns, j Î Nt при выполнении неравенства
Тогда, суммируя эти неравенства, можно получить условие для реализации процесса сегментации транспортной сети на отдельные транспортные узлы вида (1).
Заметим, что разбиения, получаемые по окончании работы процедуры П1, отделимы от транспортной сети региона в среднем, и для них будет иметь место оценка (3). Кроме того, нетрудно показать, что
где h = [n / r].
Поэтому для отделимого в среднем разбиения имеет место неравенство
Отсюда следует
(4)
Оценка (4) достигается в произвольной процедуре П1 при решении задачи разрезания полного графа Kп с единичными весами ребер с правилом выбора: для обмена выбирается пара вершин, максимизирующая разность левой и правой частей неравенства (1).
Перейдем к оценке свойств разбиений транспортной сети, получаемых в ходе использования эвристической процедуры П2. Процедурой П2 будем называть любой вариант сегментации графа транспортной цепи, в котором выбор пары подмножеств Ns и Nt на каждом шаге сегментации производится с соблюдением условия вида [8–10]
(5)
При этом любая конкретная процедура П2 будет порождать на каждом шаге сегментирования графа транспортной сети отделимое разбиение.
Заметим, что для соблюдения условия (5) на нулевом шаге следует объединить пару вершин, связанных ребром максимального веса. На очередном k-м шаге возможность выбора пары подмножеств, удовлетворяющих условию (5), получается из отделимости полученного на предыдущем шаге разбиения рk. Пусть
С учетом отделимости ph имеем
а уже с учетом этих неравенств получим
то eсть
Другим интересным вариантом процедуры П2 является процедура типа П2*, в которой при выборе пары Ns и Nt на каждом шаге процедуры соблюдается условие
(6)
Тогда процедура сегментации графа транспортной сети П2* порождает на каждом шаге отделимое в среднем разбиение терминалов.
При решении практической задачи сегментации графа транспортной сети можно рекомендовать процедуру П2 со следующими правилами выбора:
(7)
При сегментации графа транспортной сети Kn с единичными весами ребер в рамках процедур П2 и П2* можно использовать оценку (4). При этом легко видеть, что правило выбора (7) обеспечивает выполнение условий (5) и (6) одновременно, поэтому оценка (4) не является улучшаемой как в процедуре П2, так и в процедуре П2*.
Итак, рассмотренные выше процедуры П1, П2 и П2* сегментации графа транспортной сети региона связаны одной общей чертой. Эти процедуры обеспечивают сохранение некоторых полезных свойств разбиениями, получаемыми в ходе формирования транспортного узла. Кроме того, процедуры могут служить обоснованием при синтезе иерархической группировки, представленной в виде цепочки вложенных разбиений, каждое из которых является «хорошим» в смысле требований кластерного анализа [3].
Обсуждение полученного результата
С практической точки зрения оценка IП > сSW тем положительней и содержательней, чем меньше ее относительная погрешность вида
,
усредненная по всему множеству процедур возможных сегментаций графа транспортной сети.
С целью анализа поведения усредненной относительной погрешности оценки <εП> в зависимости от числа подмножеств r и разброса элементов
в матрице W = ||ωik||. Вычислительный эксперимент проводился по процедуре П2 с правилом выбора (7) и по процедуре П1. В качестве элементов матрицы W выбирались случайные числа, равномерно распределенные на некотором целочисленном отрезке [А, В], причем разброс измерялся коэффициентом, равным величине
.
Для каждого конкретного значения числа подмножеств r и коэффициента разброса k счет проводился на 40 случайно сгенерированных матрицах размером 48 × 48. Результаты счета приведены в табл. 1 и 2. На основании полученных результатов можно сделать выводы. Для малого числа подмножеств (r = 4) и небольшого коэффициента разброса (k = 1/3 и 2/3) погрешность оценки невелика, кроме того, погрешность оценки для процедуры П1 существенно меньше погрешности для процедуры П2. Погрешность оценки возрастает, если увеличивается коэффициент разброса и если увеличивается число транспортных узлов.
Таблица 1
Table 1
Относительная погрешность оценки отделимости транспортного узла от транспортной сети региона
по процедуре П2 <εП2>
Relative error of assessment of the transport junction separability from the regional transport network
by the procedure П2 <εП2>
|
k |
r |
|||
|
4 |
6 |
8 |
12 |
|
|
1 |
0,53 |
0,64 |
0,73 |
0,91 |
|
2/3 |
0,41 |
0,48 |
0,41 |
0,55 |
|
2/5 |
0,11 |
0,17 |
0,22 |
0,36 |
Таблица 2
Table 2
Относительная погрешность оценки отделимости транспортного узла от транспортной сети региона
по процедуре П1 <εП1>
Relative error of assessment of the transport junction separability from the regional transport network
by the procedure П1 <εП1>
|
k |
r |
|||
|
4 |
6 |
8 |
12 |
|
|
1 |
0,31 |
0,47 |
0,52 |
0,65 |
|
2/3 |
0,17 |
0,23 |
0,25 |
0,31 |
|
1/3 |
0,07 |
0,09 |
0,10 |
0,12 |
|
– |
– |
– |
– |
– |
Для процедуры П1 рост погрешности выражен более четко, однако во всех приведенных случаях он не превышает единицы.
Заключение
Предложенные эвристические процедуры сегментации графа транспортной сети региона обеспечивают, во-первых, сохранение некоторых полезных свойств всеми разбиениями, получаемыми в ходе формирования транспортного узла. Кроме того, эти процедуры могут служить обоснованием для составления иерархической группировки, составленной из цепочки вложенных разбиений, каждое из которых является «хорошим» в смысле требований кластерного анализа. Процесс сегментации транспортной сети региона на отдельные транспортные узлы по предложенным эвристическим процедурам может быть осуществлен для подкласса отделимых или отделимых в среднем разбиений, причем этот процесс будет реализовываться, если привлекать оценку отделимости, которую в принципе уже нельзя улучшить.
Рассмотренные выше процедуры сегментации графа транспортной сети региона связаны одной общей чертой. Эти процедуры обеспечивают сохранение некоторых полезных свойств разбиениями, получаемыми в ходе формирования транспортного узла. Кроме того, процедуры могут служить обоснованием при синтезе иерархической группировки, представленной в виде цепочки вложенных разбиений, каждое из которых является «хорошим» в смысле требований кластерного анализа.
1. Melihov A. N., Bershteyn L. S., Kureychik V. M. Primenenie grafov dlya proektirovaniya diskretnyh ustroystv. M.: Nauka, 1974. 303 s.
2. Kupershoh V. L., Mirkin B. G., Trofimov V. A. Summa vnutrennih svyazey kak pokazatel' kachestva klassifikacii // Avtomatika i telemehanika. 1976. № 3. S. 133-141.
3. Dyuran B., Odel P. Klasternyy analiz / per. s angl. E. Z. Demidenko. M.: Statistika, 1977. 127 s.
4. Germeyer Yu. B., Vatel' I. A. Igry s ierarhicheskim vektorom interesov // Tehnicheskaya kibernetika. 1974. № 3. S. 54-69.
5. Neyman D., Morgenshtern O. Teoriya igr i ekonomicheskoe povedenie / per. s angl. N. N. Vorob'eva. M.: Nauka, 1970. 707 s.
6. Eglit Ya. Ya., Eglite K. Ya., Artem'ev A. V. Transportnye sistemy dostavki gruzov. SPb.: Feniks, 2005. 300 s.
7. Eglit Ya. Ya., Eglite K. Ya., Prokof'ev V. A. Upravlenie transportnymi sistemami. SPb.: Izd-vo Akad. transp. Rossii, 2004. 423 s.
8. Braverman E. M., Levin M. I. Identifikaciya effektivnyh sostoyaniy setey proizvodstvennyh elementov. I // Avtomatika i telemehanika. 1978. № 6. S. 67-82.
9. Braverman E. M., Levin M. I. Identifikaciya effektivnyh sostoyaniy setey proizvodstvennyh elementov. II // Avtomatika i telemehanika. 1978. № 7. S. 79-86.
10. Braverman E. M. Model' potrebitel'skogo vybora pri fiksirovannyh cenah // Avtomatika i telemehanika. 1976. № 5. S. 100-111.
