Методы и алгоритмы интеллектуального анализа процесса организации транспортной системы

|Выпуск 2

4. Конвенция ООН по морскому праву. — 1982.

5. Кузнецов А. Л. Механизмы рационализации маршрутов наземного распределения и выбора видов транспорта / А. Л. Кузнецов // Транспорт: наука, техника, управление. — 2011. — № 6.

УДК 656;004.83,164.2 С. А. Селиверстов,

науч. сотрудник,

Федеральное государственное бюджетное учреждение науки «Институт проблем транспорта им. Н. С. Соломенко»

МЕТОДЫ И АЛГОРИТМЫ ИНТЕЛЛЕКТУАЛЬНОГО АНАЛИЗА ПРОЦЕССА ОРГАНИЗАЦИИ ТРАНСПОРТНОЙ СИСТЕМЫ

METHODS AND ALGORITHMS FOR MINING THE PROCESS OF ORGANIZING THE TRANSPORT SYSTEM

В статье рассматривается применение методов автоматической группировки объектов к задачам организации транспортных сетей.

The article deals with the application of auto-grouped method to the transport networks organizing task.

Ключевые слава: методы автоматической группировки, методы кластеризации, методы организации транспортных сетей, интеллектуальный анализ транспортных сетей, транспортная система, транспортные сети, интеллектуальный анализ транспортных систем.

Key words: auto-grouped methods, clustering methods, transport networks organizing methods, intelligent analysis of transport networks, transport systems, transport networks, intelligent analysis of transport systems.

Введение

В Российской Федерации транспорт является одной из крупнейших базовых отраслей народного хозяйства, неотъемлемой составной частью логистической инфраструктуры. Транспортные коммуникации связывают страну с мировым сообществом, являясь материальной основой обеспечения внешнеэкономических связей России и ее интеграции в глобальную экономическую систему.

Сегодня совокупные расходы, связанные с организацией торговли на международных рынках и выполнением соответствующих транспортно-логистических мероприятий, постоянно возрастают. Растущий спрос на грузовые перевозки сдерживается неразвитостью транспортно-логистической системы страны, которая, в свою очередь, опирается на инфраструктурную составляющую транспортного комплекса, структура которой рассматривалась в [1-3]. Сегодня важнейшей задачей, обозначенной в Транспортной стратегии РФ на период до 2030 г. [4], является формирование единого транспортного пространства России на базе сбалансированного развития ее транспортной инфраструктуры и построения единой евразийской транспортной сети (ЕТС).

Здесь возникает проблема выбора способа формального представления ЕТС, позволяющего не только осуществлять необходимые для ресурсосбережения оптимизационные преобразования, но и определять наиболее слабые с коммуникационной точки зрения участки сети.

Традиционное представление сети взвешенным графом G = (V, E), как не раз обсуждалось в [5], с множествами вершин V и дуг E, отождествляемыми соответственно с населенными пунктами и с существующими транспортными коммуникациями (ТК) заданной протяженности между

ВЕСТНИКД

ПОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

ШРОЯТО И РЕЧНОГО ФЛОТА ИМЕНИ АДМИРАЛА С. 0. МАКАРОВА,

ними, или эквивалентной ему матрицей М естественно и наглядно. Но существуют и недостатки. Такое представление затрудняет выполнение указанных выше преобразований ввиду большой размерности матрицы, а также не позволяет учитывать внутренние свойства транспортных коммуникаций (водных, воздушных, наземных), характеристики среды, в которых они используются (геофизические, климатические, биологические, экологические), экономические, транспортные и иные показатели населенных пунктов, соединенных транспортными коммуникациями. Также не представляется возможным анализировать, улучшать и изменять параметры таких соединений и осуществлять моделирование с целью выявления наиболее эффективной структуры организации транспортного пространства.

Для решения описанной проблемы предлагается применить метод кластерного анализа, принцип работы которого более подробно освещен в [7; 8]. Данный метод исследования относится к интеллектуальному анализу и статистической обработке данных. Представляется целесообразной интерпретация сети совокупностью кластеров Е, связанная с разрезанием графа G на подграфы и с решением задачи оптимального покрытия [5; 6] ими графа ЕТС, формулируемая как задача линейного программирования:

т К п

G=YpixvK при Zv^eZv<; Е>

i=i i=i /-1

где vK — кластеризованное множество объектов; n. — количество кластеров; v . — группируемые объекты; n — общее количество группируемых объектов; Ек — показатель эффективности кластеризованной транспортной системы; Eg — показатель эффективности некластеризованной транспортной системы.

Введем определения кластера. Кластером £. (рис. 1) в среде S будем называть сгруппированное в определенной области s . е S и обладающее набором свойств q . е Q множество объектов v е V по закону группировки Z, таким образом, е Е — множество кластеров, в т. ч. Е е S; S(Q) — каждая область s. е S характеризуется набором свойств {q.} е Q; V(A) — каждый объект обладает множеством свойств {а.} е A; Z(Q, A) — процесс образования кластера зависит от свойств Q и A.

Тогда решение нашей задачи сводится к нахождению центров кластеризации (ЦК) v , труп-

ci

пировке объектов к ЦК с последующей прокладкой межкластерных связей в. при условии повышения эффективности социально-экономических и транспортных (СЭТ) показателей.

Содержательная постановка задачи

Объектами анализа является множество населенных пунктов на выделенной территории, которые характеризуются своим месторасположением (определяемым двумя или тремя географическими координатами), показателями среды территории (климатические, геофизические, экологические) и СЭТ показателями населенных пунктов. Требуется провести группировку населенных пунктов с укрупнением на выделенной территории по совокупности указанных показателей с их последующим объединением транспортными коммуникациями и тем самым сбалансировать структурные диспропорции ТС и устранить неравномерность в развитии транспортной системы России.

Выпуск 2

Выпуск 2

Математическая постановка задачи

Пусть исследуемая транспортная система T, T е S задана взвешенным графом G = (V, E) и множеством свойств A: T е A, зависимых от Q, где S — среда существования системы, определяемая множеством свойств Q среды, воздействующих на T. При этом для T, S соблюдаются постулаты существования и функционирования сложных систем, рассмотренные, например, в [1; 2]; следовательно, при переходе от системы к ее элементу выполняется условие целостности: (Vr,*S,)[3!i2(5') = Щ (S) };i = l,n; Qt гэ Qr = 0, где r ер — r-й вариант членения из множества ц возможных; Qr — множество свойств подсистем при r-й декомпозиции; множество V = {vp ..., v} обозначает n1 объектов (вершин), a E = (E1, ..., E ) — конечное множество связей (дуг графа). Предполагается, что существует определенное множество наблюдаемых показателей или характеристик A = (A1, ..., A )T которыми обладает каждый объект из V, то есть V е A, причем каждому признаку множества A ставится в соответствие конечное качественное подмножество АП/, е|ар”*,..., а^Циз качественного множества (A1, ..., A^), из которого соответственно и производится выбор определенной качественной величины признака, которым обладает рассматриваемый элемент (v1, ..., v ) е V.

Результат измерения /-й характеристики V. объекта будем обозначать символом х., тогда век-торX. = [Ху] размерностиp я n будет отвечать каждому ряду измерений (дляJ-го объекта). Следовательно, множество векторов, описывающих множество объектов V, обозначим какX = {X X ..., Xn}.

Множество X может быть представлено как n точек в p-мерном евклидовом пространстве Ep.

Пусть Lb (v1) Lb (v2), ._, Lb (vn) — географические координаты объектов (ГКО) (v1, ..., v ), Lb — матрица ГКО размером р я 2 или р я 3, тогда исходные данные представляют собой блочную матрицу типа объект-свойство, представленную в виде табл. 1.

Таблица 1

Матрица «объект-свойство»

Объект № объекта Признаки

V N Lb (ГКО) А Л А n

Процесс расширения базового пространства признака (пространство ГКО) до многомерного пространства признаков (МПП) A, представляющего собой многомерную систему координат, реа-

лизуется дополнением базового уровня Lb уровнями определенных признаков L L2

L.

L

Таким образом, уровню L1 соответствует признак A L2 — A ..., Ln — An), при этом: R2 и т. д.

Аналитически этот процесс можно представить в виде табл. 2, а графически — рис. 2.

Таблица 2

R ^ L, е L,

1b

Процесс расширения базового пространства пространствами признаков

Расширение измерений Расширение пространства уровней Расширение пространства объект (ГКО) — признак

R5 Lb L1 L2 L3 (х; у) (l1 ) (l2i) Ю

R4 Lb L1

R3 Lb

R2 Lb

Регистрационный номер объекта Мм или условные координаты R,*M.yu)

Рис. 2. Графический процесс расширения базового пространства пространствами признаков

Каждый объект может быть представлен точкой, координаты которой задаются на базовом уровне Lb, а свойства описываются в МПП, тогда положение этой точки будет определяться набором значений (координат) в базовом пространстве Lb и величиной (набором) признаков в соответствующих ПП. Каждую такую точку мы будем называть многомерным вектором.

Для решения задачи кластеризации необходимо:

1) осуществить группировку анализируемых исходных данных;

2) осуществить выбор центров кластеризации, описать процесс формирования центров кластеризации и свойств, общих для всех объектов отдельного кластера (меру сходства между объектами);

3) задать способ образования кластеров;

4) указать критерий качества кластеризации;

5) организовать движение к максимуму (минимуму) критерия качества (при этом определяется и число реально существующих кластеров).

Решение задачи кластеризации предлагается производить в два этапа. На первом этапе осуществляется метод выбора центров кластеризации v опираясь на анализ множества качественных признаков, на втором разрабатывается метод самой кластеризации.

Исследуемые данные

Множество свойств Q среды S, воздействующих на T, предлагается сформировать, опираясь на следующие существующие системы показателей, а именно:

1) данные геолого-сейсмических показателей (ГОСТ Р 22.1.06-99, ГОСТ 22.0.03-97/ГОСТ Р 22.0.03-95), данные районирования территории РФ по геологическим характеристикам, данные районирования по рельефу и по поверхности геоида территории РФ, тектонические карты и карты сейсмического районирования территории РФ;

2) показатели районирования территории РФ по геофизическим характеристикам: карты полезных ископаемых, топливно-энергетических ресурсов и показатели геохимического районирования территории РФ;

3) данные климатических показателей (ГОСТ 16350-80, ГОСТ 25870-83, ГОСТ Р 53614- 2009 (МЭК 60721-2-3:1987), ГОСТ 24482-80, ГОСТ 24728-81), показатели районирования территории РФ по климатическим характеристикам, карты районирования территории РФ по среднемесячной температуре воздуха в январе, по отклонениям средней температуры воздуха наиболее холодных суток от среднемесячной температуры в январе, по среднемесячной температуре воздуха в июле, по давлению, скорости и направлению ветра;

4) эколого-биологические данные, карты растительности РФ, карта заповедников и национальных парков РФ, карта радиоактивных территорий РФ.

Выпуск 2

Выпуск 2

Множество наблюдаемых СЭТ показателей (свойств) A, которыми обладает каждый объект из множества V, предлагается сформировать, используя:

— основные социально-экономические и транспортные показатели городов России [9; 10];

— транспортные показатели России [10].

Анализ исходных данных

На этапе анализа решается задача группировки ИД, при этом выделяются два вида группировок: типологические и структурные [11]. Типологической группировкой (ТГ) называется разбиение совокупности на качественно однородные группы, характеризующие некоторые классы свойств (например, множество свойств Q: 1-4 и свойств A: 5-6). Структурной группировкой (СГ) называется расчленение качественно однородной совокупности на количественно однородные группы, характеризующие строение совокупности, ее структуру (например, данные сейсмического районирования структурированы по 12-балльной шкале MSK-64). При анализе нашей проблемы выбор типологических ИД проистекает из целеполагания ТС (наличие востребованного ресурса и др.) и условий ее существования (СНиП, ТУ и другие категории стандартов), поэтому

Определяется структура распространения каждого признака из Q в среде R2 ^ Lb в зависимости от его СГ, путем присваивания каждой величине признака (в зависимости от его СГ) определенных координат Lb (точечных или интервальных, рис. 3) и строится матрица «объект-свойство» (табл. 1).

Процедура группировки величины каждого признака с учетом его пространственного положения может осуществляться как алгоритмом простой группировки [8], что позволяет автоматически определить распределение признака (с учетом СГ) в пространстве (рис. 4), так и методами минимальной дисперсии [7; 8]. В качестве целевой функции целесообразно использовать внутригрупповую сумму квадратов отклонений (ВГСКО) W величин рассматриваемых признаков, вычисляемую как

предполагается, что задача СГ уже решена.

п

w = £(а - *)2.

1=1

Оптимальное значение достигается, когда ВГСКО внутри каждой группы кластеризованных величин рассматриваемого признака достигает нулевого значения, что соответствует разбиению на группы с равной величиной признака внутри каждого кластера.

Рис. 4. Пример группировки

Такая структура анализа ИД (свойств Q и A) позволяет определить зависимость процесса развития объектов из множества V (населенных пунктов) и произвести оценку эффективности таких объектов от вида тех или иных выбранных свойств Q и A, например методами, рассмотренными в [7]. Параллельно реализуется решение другой важной задачи — прокладка ТК между объектами и участками ТС. Идея построения соответствующей модели опирается на сопоставление каждому участку пространства (элемент ландшафта географической территории, определяемого величиной соответствующего признака) величины некоторого потенциала р. Тогда разность потенциалов исследуемых участков (или групп), превышающая заданное пороговое значение, и создает предпосылки для прокладки новой ТК, осуществляемой по пути наименьшего значения р элементов ландшафта рассматриваемой территории.

Нахождение центров кластеризации

На этом этапе решается задача рационального выбора объектов ЦК из множества заданных. В нашем случае задача осложняется, если объекты характеризуются показателями, измеренными в различающихся единицах, а иногда и шкалах. При решении таких задач требуется аппарат, позволяющий сравнивать объекты, характеризующиеся целым набором признаков (многомерные объекты), с учетом всех этих признаков. Для решения таких задач предлагается использовать методы многокритериального анализа, рассмотренные, например, в [7; 8], с целью упрощения процесса автоматической обработки данных предлагается использовать модифицированный метод, который разработан, опираясь на метод многомерной средней.

Тогда алгоритмическое нахождение ЦК с использованием ММС будет следующим.

Шаг 1. Каждой вершине v ставится в соответствие численное значение определенного признака из множества A, рис. 5.

Шаг 2. Вычисляется среднее значение величины по качественным множествам (1), соответствующим качественным признакам, и реализуется процедура отбора (рис. 6) каждого элемента множества V:

Количественное значение признака

Рис. 5. Таблица «объект-свойство»

а

1

1ср

= — ТХУ’

S i=i

Рис. 6. Отображение процедуры отбора

качественные величины признаков которых превышают среднее значение по качественному множеству признака, из которого происходит выбор, причисляются к множеству P — множество потенциальных центров кластеризации (2), каждому из которых с соответствует множество признаков, выраженных качественной величиной (рис. 7).

Рис. 7. Формирование потенциальных центров кластеризации

•* к > к.

1 1 1ср

P

' Л

v2: к2 < к2

2 2 2ср

v2 i P.

*3нак «:» читается как «такое что».

Шаг 3. Вычисляется среднее значение по всем вершинам vp качественной величины для каждого признака (3) и реализуется процедура отбора каждого элемента множества P:

1 ^

а" =

1=1

v

v

v

p

Выпуск 2

|Выпуск 2

Элементы, качественные величины признаков которых превышают среднее значение по элементам р, причисляются к множеству C — множество активных центров кластеризации vc (рис. 8).

, еС^с, ->v.,

v. : к. > к,

Р1 J 1ср

Vp2 : к2 < к2ср

V2 Ч C.

Рис. 8. Процесс отбора активных центров кластеризации

Шаг 5. Вычисляются начальные положения активных центров кластеризации центров v

Шаг 6. Реализуется процесс присвоения каждого элемента и его качественных признаков к ближайшему активному центру.

Шаг 7. Осуществляется перерасчет качественных признаков.

Шаг 8. Осуществляется оценка кластеризации: усреднение межкластерных расстояний. Таким образом, на первом этапе метода вычисляются активные центры кластеризации, а на следующем шаге реализуется процесс присвоения второстепенных вершин v. к его ближайшему центру v

В качестве меры расстояния D примем квадрат евклидовой метрики d2, вычисляемый как

или

^=^Z(v(c)i-vWi)2

doj = i(Xc-Xj)2 +(Ус-У j)2 ,

где c и i — объекты в пространстве R2, то есть n = 2, v(c)i и v.). — координаты точек vc и v.

Мера D = {dy} может варьироваться в зависимости от функциональной особенности центров кластеризации. Аналитическая запись такого процесса будет представлять собой матрицу

(vAf.

Рис. 9. Процесс образования кластера с учетом меры близости

Пример: пусть d. = а, тогда все v. , для которых мера d2. < а, причисляются к vc<E v, в случае d2a > a, va Ч. v. Процесс образования кластера с учетом меры близости d. показан на рис. 9.

На третьем этапе происходит пересчет признаков и характеристик кластеров с учетом новых элементов. Также существует возможность реализовать функцию сжатия кластеризуемых объектов к центру кластеризации. В нашем случае для этого можно использовать удельные социально-экономические показатели, такие как плотность населения на единицу площади, коэффициент Энгеля, коэффициент транспортной обеспеченности и др.

ЕЭ

Оценка кластеризации

Среди критериев качества кластеризации [7; 8; 12] целесообразно применить следующие:

— среднее внутрикластерное расстояние должно быть как можно меньше О. :

dint

QdM = Z Z d(x,y)->Taan

i x,ysX,

при К. ^ max,

где К — множество коэффициентов качества кластеризуемых объектов;

— среднее межкластерное расстояние должно быть равным Qd :

Qdea = Z Z d(x>y) ->max;

i xaXj, yeXj

Тогда функцию ошибки кластеризации можно определить как отношение среднего внутрикластерного и среднего межкластерного расстояния Qm:

Qm

.05

Ol

->min.

В результате будет получено оптимальное количество кластеров, осуществлена их внутренняя организация и реализован процесс распределения и прокладки транспортных коммуникаций между кластерами. Это позволит повысить полную организацию транспортной системы T в среде S.

Исключительное преимущество состоит в том, что данный процесс анализа применим к исследованию динамического процесса развития транспортной системы с учетом глубины исторической информации, то есть зависимости показателей Q и A от времени, что позволит рассматривать предложенный интеллектуальный анализ процесса организации как одну из ступеней интеллектуальной системы прогнозирования [13, с. 43-49] и управления процессом развития транспортных сетей и систем страны.

Вывод

Предложенный кластерный подход к организации транспортных сетей позволит:

1) использовать математические методы, методы компьютерного моделирования и модельно-предсказательную методологию для оптимизации и систематизации транспортного пространства, что с трудом удавалось до сегодняшнего времени при структурировании столь сложных объектов. При дифференцированном уровне детализации в качестве кластеров могут выступать объекты и более высокого уровня сложности, такие как страны и континенты;

2) сбалансировать структурные диспропорции ЕТС и устранить неравномерность в развитии транспортной системы России;

3) осуществить процесс оптимального перераспределения связей между кластерами и внутри них, привязав их к видам транспортной инфраструктуры.

Список литературы

1. Проблематика сложных систем (концептуальные основы модельных представлений) / под общ. ред. С. А. Попова; В. М. Дубов [и др.]. — СПб.: Элмор, 2006. — 184 с.

2. Белый О. В. Архитектура и методология транспортных систем / О. В. Белый, О. Г. Кокаев, С. А. Попов. — СПб.: Элмор, 2002.

3. Кокаев О. Г. О технологии анализа транспортных процессов в современных условиях хозяйствования / О. Г. Кокаев, О. Ю. Лукомская, С. А. Селиверстов // Транспорт Российской Федерации. — 2012. — № 2 (39).

4. Транспортная стратегия на период до 2030 г.: утв. распоряжением Правительства Рос. Федерации № 1734-р от 22 ноября 2008 г.

5. Кристофидес Н. Теория графов. Алгоритмический подход / Н. Кристофидес. — М.: Мир, 1978. — 432 с.

6. Сигал И. X. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: учеб. пособие / И. X. Сигал, А. П. Иванова. — М.: Физматлит, 2002. — 240 с.

Выпуск 2

|Выпуск 2

7. ОлдендерферМ. С. Кластерный анализ. Факторный, дискриминантный и кластерный анализ / М. С. Олдендерфер, Р. К. Блэшфилд. — М.: Финансы и статистика, 1988. — 215 с.

8. Дюран Б. Кластерный анализ / Б. Дюран, П. Оделл. — M.: Статистика, 1977. — 128 с.

9. Регионы России. Основные характеристики субъектов Российской Федерации. 2012: стат. сб. / Росстат. — М., 2012. — 662 с.

10. Основные показатели транспортной деятельности в России. 2010: стат. сб. / Росстат. — M., 2010.

11. Общая теория статистики / Г. С. Кильдишев [и др.]. — М.: Статистика, 1980. — 423 с.

12. Оптимальная группировка взаимосвязанных объектов / М. И. Рубинштейн. — М.: Наука, 1989. — 166 с.

13. Селиверстов Я. А. Моделирование процессов распределения и развития транспортных потоков в мегаполисах / Я. А. Селиверстов // Известия СПбГЭТУ «ЛЭТИ». — 2013. — № 1.

УДК 629.5.064.2:656.614.3.073.434 Т. Б. Маликова,

канд. техн. наук, доцент, Морской государственный университет имени адмирала Г. И. Невельского;

М. А. Москаленко,

д-р техн. наук, профессор, Морской государственный университет имени адмирала Г. И. Невельского

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ МОРСКОЙ ПЕРЕВОЗКИ ТРУБ БОЛЬШОГО ДИАМЕТРА НА ПАЛУБЕ СУДНА

INCREASING THE EFFICIENCY OF DECK LARGE DIAMETER TUBES

CARRIAGE BY SEA TRANSPORT

Статья посвящена вопросам безопасной перевозки смещающихся грузов на палубе судна. В частности, рассматривается возможность перевозки труб большого диаметра с использованием технологии регулирования смещаемости штабеля при помощи пневморегуляторов амортизационного типа.

The paper covers issues of safe deck shipment of goods liable to shifting. In particular, an option of carrying large diameter tubes using a technique of adjusting stack shifting by means of air bags of amortization type is given a thorough consideration.

Ключевые слова: штабель труб, пневморегулятор, регулирование смещаемости грузов, устойчивое состояние штабеля, формирование штабеля, укладка.

Key words: stack of tubes, pneumatic controller, adjustment of goods shifting, stack stabilized condition, stack making up, stowage.

ПРУБЫ большого диаметра (ТБД) занимают одно из ведущих мест среди внешнеторговых грузов морского транспорта. Склонность к смещению такого груза при перевозке требует от перевозчика большого опыта и специальных знаний при решении вопросов, связанных с выполнением технологических операций в порту при погрузоразгрузочных работах, а также в процессе самой транспортировки груза морем.