Программные продукты и системы, 2018, том 31, № 1

Научно-исследовательский институт

«Центрпрограммсистем»

Программные

продукты и системы

МЕЖДУНАРОДНЫЙ НАУЧНО-ПРАКТИЧЕСКИЙ ЖУРНАЛ

2018, том 31, № 1

(год издания тридцать первый)

Главный редактор

С.В. ЕМЕЛЬЯНОВ, академик РАН

Тверь

SOFTWARE & SYSTEMS

(PROGRAMMNYE PRODUKTY I SISTEMY)

International research and practice journal

2018, vol. 31, no. 1

Editor-in-Chief 

S.V. EMELYANOV, Academician of the Russian Academy of Sciences

Tver

Russian Federation

Research Institute CENTERPROGRAMSYSTEM

 ПРОГРАММНЫЕ ПРОДУКТЫ И СИСТЕМЫ

Международный научно-практический журнал 

2018. Т. 31. № 1
DOI: 10.15827/0236-235X.031

Главный редактор 

С.В. ЕМЕЛЬЯНОВ,
академик РАН (г. Москва, Россия)

Научные редакторы:

С.А. ПРОХОРОВ, д.т.н., профессор Самарского
университета (г. Самара, Россия)
А.В. ИВАЩЕНКО, д.т.н., профессор Самарского
университета (г. Самара, Россия)
Н.А. СЕМЕНОВ, д.т.н., профессор ТвГТУ 
(г. Тверь, Россия)

Издатель НИИ «Центрпрограммсистем»

(г. Тверь, Россия)

Учредители: МНИИПУ (г. Москва, Россия),
Главная редакция международного журнала 

«Проблемы теории и практики управления» (г. Москва, Россия),

Закрытое акционерное общество 

«Научно-исследовательский институт 

«Центрпрограммсистем» (г. Тверь, Россия)

Журнал зарегистрирован в Комитете Российской Федерации

по печати 26 июня 1995 г.

Регистрационное свидетельство № 013831

Подписной индекс в каталоге

Агентства «Роспечать» 70799

ISSN 0236-235X (печатн.)
ISSN 2311-2735 (онлайн)

МЕЖДУНАРОДНАЯ РЕДАКЦИОННАЯ КОЛЛЕГИЯ

Семенов Н.А. – д.т.н., профессор Тверского государственного технического университета, заместитель главного 
редактора (г. Тверь, Россия)
Решетников В.Н. – д.ф.-м.н., профессор Московского авиационного института 
(национального исследовательского университета), заместитель главного редактора (г. Москва, Россия)
Арефьев И.Б. – д.т.н., профессор Морской академии Польши (г. Щецин, Польша)
Афанасьев А.П. – д.ф.-м.н., профессор Московского физико-технического института (технического университета), 
заведующий Центром распределенных вычислений Института проблем передачи информации РАН (г. Москва, Россия)
Баламетов А.Б. – д.т.н., профессор Азербайджанского научно-исследовательского и проектно-изыскательского института 
энергетики (г. Баку, Азербайджан)
Батыршин И.З. – д.т.н., профессор Мексиканского института нефти (г. Мехико, Мексика)
Вагин В.Н. – д.т.н., профессор Московского энергетического института (технического университета) 
(г. Москва, Россия)
Голенков В.В. – д.т.н., профессор Белорусского государственного университета информатики и радиоэлектроники 
(г. Минск, Беларусь)
Еремеев А.П. – д.т.н., профессор Московского энергетического института (технического университета)
(г. Москва, Россия)
Котов А.С. – кандидат наук, ассистент профессора университета Уэйна (штат Мичиган) (г. Детройт, США)
Кузнецов О.П. – д.т.н., профессор Института проблем управления РАН (г. Москва, Россия)
Курейчик В.М. – д.т.н., профессор Инженерно-технологической академии Южного федерального университета 
(г. Таганрог, Россия)
Лисецкий Ю.М. – д.т.н., генеральный директор «S&T Ukraine» (г. Киев, Украина)
Мамросенко К.А. – к.т.н., доцент Московского авиационного института 
(национального исследовательского университета), руководитель Центра визуализации и спутниковых 
информационных технологий НИИСИ РАН (г. Москва, Россия)
Мейер Б. – доктор наук, профессор, заведующий кафедрой Высшей политехнической школы – ETH (г. Цюрих, Швейцария)
Нгуен Тхань Нги – д.ф.-м.н., профессор, проректор Ханойского открытого университета (г. Ханой, Вьетнам)
Николов Р.В. – доктор наук, профессор Университета библиотековедения и информационных технологий Софии
(г. София, Болгария)
Осипов Г.С. – д.ф.-м.н., профессор, заместитель директора Института системного анализа РАН (г. Москва, Россия)
Палюх Б.В. – д.т.н., профессор Тверского государственного технического университета (г. Тверь, Россия)
Рахманов A.A. – д.т.н., профессор, заместитель генерального директора Концерна «РТИ Системы» (г. Москва, Россия)
Серов В.С. – д.ф.-м.н., профессор Университета прикладных наук Оулу (г. Оулу, Финляндия)
Сотников А.Н. – д.ф.-м.н., профессор, Межведомственный суперкомпьютерный центр РАН (г. Москва, Россия)
Сулейманов Д.Ш. – академик АН Республики Татарстан, д.т.н., профессор Казанского государственного 
технического университета (г. Казань, Республика Татарстан, Россия)
Тарасов В.Б. – к.т.н., доцент Московского государственного технического университета им. Н.Э. Баумана (г. Москва, Россия)
Таратухин В.В. – доктор философии, управляющий директор Европейского исследовательского центра 
в области информационных систем (ERCIS) Вестфальского университета им. Вильгельма (г. Мюнстер, Германия)
Хорошевский В.Ф. – д.т.н., профессор Московского физико-технического института (технического университета) 
(г. Москва, Россия)
Язенин А.В. – д.ф.-м.н., профессор Тверского государственного университета (г. Тверь, Россия)

АССОЦИИРОВАННЫЕ ЧЛЕНЫ РЕДАКЦИИ

Московский энергетический институт (технический университет), г. Москва, Россия
Технологический институт Южного федерального университета, г. Таганрог, Россия
Тверской государственный технический университет, г. Тверь, Россия
Научно-исследовательский институт «Центрпрограммсистем», г. Тверь, Россия

АДРЕС РЕДАКЦИИ
Россия, 170024, г. Тверь, пр. 50 лет Октября, 3а
Телефон (482-2) 39-91-49
Факс (482-2) 39-91-00
E-mail: red@cps.tver.ru
Сайт: www.swsys.ru

Подписано в печать 22.02.2018 г.

Отпечатано ООО ИПП «Фактор и К»

Россия, 170028, г. Тверь, ул. Лукина, д. 4, стр. 1

Выпускается один раз в квартал.

Год издания тридцать первый. Формат 6084 1/8. Объем 228 стр.

Заказ № 7. Тираж 1000 экз. Цена 330,00 руб.

Автор статьи отвечает за подбор, оригинальность и точность приводимого фактического материала.
Авторские гонорары не выплачиваются. При перепечатке материалов ссылка на журнал обязательна.

 SOFTWARE & SYSTEMS 
(PROGRAMMNYE PRODUKTY I SISTEMY)
International research and practice journal

2018, vol. 31, no. 1
DOI: 10.15827/0236-235X.031

Editor-in-chief 
S.V. Emelyanov, Academician of the Russian Academy of Sciences
(Mosсow, Russian Federation)
Science editors:
S.A. Prokhorov, Dr.Sc. (Engineering), Professor, Samara University 
(Samara, Russian Federation)
A.V. Ivaschenko, Dr.Sc. (Engineering), Professor, Samara University 
(Samara, Russian Federation)
N.A. Semenov, Dr.Sc. (Engineering), Professor TvSTU
(Tver, Russian Federation)

Publisher Research Institute 
CENTERPROGRAMSYSTEM 

(Tver, Russian Federation)

The Founders: International Scientific 

and Research Institute for Management Issues 

(Moscow, Russian Federation),

the Chief Editorial Board 

of International Magazine Theoretical and practical 

issues of management (Moscow, Russian Federation),

Research Institute CENTERPROGRAMSYSTEM 

(Tver, Russian Federation)
The magazine is on record 

in Russian committee

on press 26th of June 1995

Registration certificate № 013831

ISSN 0236-235X (print)

ISSN 2311-2735 (online)

INTERNATIONAL EDITORIAL BOARD

Semenov N.A. – Dr.Sc. (Engineering), Professor of Tver State Technical University, Deputy Editor-in-Chief
(Tver, Russian Federation)
Reshetnikov V.N. – Dr.Sc. (Physics and Mathematics), Professor of Moscow Aviation Institute (National Research University), 
Deputy Editor-in-Chief (Mosсow, Russian Federation)
Arefev I.B. – Dr.Sc. (Engineering), Professor of Poland Szczecin Maritime Academy (Szczecin, Poland)
Afanasiev A.P. – Dr.Sc. (Physics and Mathematics), Professor of Moscow Institute of Physics and Technology, 
Head of Centre for Distributed Computing of Institute for Information Transmission Problems (Moscow, Russian Federation)
Balametov A.B. – Azerbaijan Scientific-Research & Design-Prospecting Power Engineering Institute (Baku, Azerbaijan)
Batyrshin I.Z. – Dr.Sc. (Engineering), Professor of Mexican Petroleum Institute (Mexico City, Mexico)
Vagin V.N. – Dr.Sc. (Engineering), Professor of Moscow Power Engineering Institute (Technical University) 
(Mosсow, Russian Federation)
Golenkov V.V. – Dr.Sc. (Engineering), Professor of Belarusian State University of Informatics and Radioelectronics 
(Minsk, Republic of Belarus)
Eremeev A.P. – Dr.Sc. (Engineering), Professor of Moscow Power Engineering Institute (Technical University) 
(Moscow, Russian Federation)
Kotov A.S. – Ph.D. (Computer Science), Assistant Professor, Wayne State University (Detroit, MI, USA)
Kuznetsov O.P. – Dr.Sc. (Engineering), Professor of the Institute of Control Sciences of the Russian Academy of Sciences
(Moscow, Russian Federation)
Kureichik V.M. – Dr.Sc. (Engineering), Professor of Academy of Engineering and Technology Southern Federal University 
(Taganrog, Russian Federation)
Lisetskiy Yu.M. – Dr.Sc. (Engineering), CEO of S&T Ukraine (Kiev, Ukraine)
Mamrosenko K.A. – Ph.D. (Engineering), Associate Professor of Moscow Aviation Institute (National Research University), 
Head of Center of Visualization and Satellite Information Technologies SRISA RAS (Moscow, Russian Federation)
Meyer B. – Dr.Sc., Professor, Head of Department in Swiss Federal Institute of Technology in Zurich, ETH 
(Zurich, Switzerland)
Nguyen Thanh Nghi – Dr.Sc. (Physics and Mathematics), Professor, Vice-Principal of Hanoi Open University (Hanoi, Vietnam)
Nikolov R.V. – Full Professor of the University of Library Studies and Information Technology (Sofia, Bulgaria)
Osipov G.S. – Dr.Sc. (Physics and Mathematics), Professor, Deputy of the Principal of Institute of Systems Analysis 
of the Russian Academy of Sciences (Mosсow, Russian Federation)
Palyukh B.V. – Dr.Sc. (Engineering), Professor of Tver State Technical University (Tver, Russian Federation)
Rakhmanov A.A. – Dr.Sc. (Engineering), Professor, Deputy of the CEO of Concern RTI Systems
(Mosсow, Russian Federation)
Serov V.S. – Dr.Sc. (Physics and Mathematics), Professor of the Oulu University of Applied Sciences (Oulu, Finland)
Sotnikov A.N. – Dr.Sc. (Physics and Mathematics), Professor, Joint Supercomputer Center of the Russian Academy 
of Sciences (Moscow, Russian Federation)
Suleimanov D.Sh. – Academician of TAS, Dr.Sc. (Engineering), Professor of Kazan State Technical University
(Kazan, Republic of Tatarstan, Russian Federation)
Tarassov V.B. – Ph.D. (Engineering), Associate Professor of Bauman Moscow State Technical University
(Mosсow, Russian Federation)
Taratoukhine V.V. – Ph.D. (Engineering), Dr.Ph., Managing Director of the Competence Centre ERP and ERCIS Lab
Russia of the ERCIS (Muenster, Germany)
Khoroshevsky V.F. – Dr.Sc. (Engineering), Professor of Moscow Institute of Physics and Technology
(Moscow, Russian Federation)
Yazenin A.V. – Dr.Sc. (Physics and Mathematics), Professor of Tver State University (Tver, Russian Federation)

ASSOCIATED EDITORIAL BOARD MEMBERS

Moscow Power Engineering Institute (Technical University), Moscow, Russian Federation
Technology Institute at Southern Federal University, Taganrog, Russian Federation
Tver State Technical University, Tver, Russian Federation
Research Institute CENTERPROGRAMSYSTEM, Tver, Russian Federation

EDITORIAL OFFICE ADDRESS
50 let Oktyabrya Ave. 3а, Tver, 170024, Russian Federation
Phone: (482-2) 39-91-49  Fax: (482-2) 39-91-00
E-mail: red@cps.tver.ru
Website: www.swsys.ru

Passed for printing 22.02.2018

Printed in printing-office “Faktor i K”

Lukina St. 4/1, Tver, 170028, Russian Federation

Published quarterly. 31th year of publication

Format 6084 1/8. Circulation 1000 copies

Prod. order № 7. Wordage 228 pages. Price 330,00 rub. 

Вниманию авторов

Международный журнал «Программные продукты и системы» публикует материалы научного и научно-практического 

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

Решением Президиума Высшей аттестационной комиссии (ВАК) Министерства образования и науки РФ международ
ный журнал «Программные продукты и системы» внесен в Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней 
кандидата и доктора наук.

Информация об опубликованных статьях по установленной форме регулярно предоставляется в систему Российского 

индекса научного цитирования (РИНЦ), в CrossRef и в другие базы и электронные библиотеки.

Условия публикации

К рассмотрению принимаются ранее нигде не опубликованные материалы, соответствующие тематике журнала 

(специализация 05.13.ХХ – Информатика, вычислительная техника и управление) и отвечающие редакционным требованиям.

Работа представляется в электронном виде в формате Word. При обилии сложных формул обязательно наличие 

статьи и в формате PDF. Формулы должны быть набраны в редакторе формул Word (Microsoft Equation или MathType). 
Объем статьи вместе с иллюстрациями – не менее 10 000 знаков. Диаграммы, схемы, графики должны быть доступными 
для редактирования (Word, Visio, Excel). Все иллюстрации для полиграфического воспроизведения представляются в 
черно-белом варианте. Цветные, тонированные, отсканированные, не подлежащие редактированию средствами Word рисунки и экранные формы следует присылать в хорошем качестве для их дополнительного размещения на сайте журнала в 
макете статьи с доступом по ссылке. (Публикация материалов с использованием гипертекста, графики, аудио-, видео-, 
программных средств и др. возможна в электронном издании «Программные продукты, системы и алгоритмы», сайт 
www.swsys-web.ru.) Заголовок должен быть информативным; сокращения, а также терминологию узкой тематики желательно в нем не использовать. Количество авторов на одну статью – не более 4, количество статей одного автора в номере, 
включая соавторство, – не более 2. Список литературы, наличие которого обязательно, должен включать не менее 10 пунктов.

Необходимы также содержательная структурированная аннотация (не менее 250 слов), ключевые слова (7–10) и 

индекс УДК. Название статьи, аннотация и ключевые слова должны быть переведены на английский язык (машинный 
перевод недопустим), а фамилии авторов, названия и юридические адреса организаций (если нет официального перевода), 
пристатейные списки литературы – транслитерированы по стандарту BGN/PCGN. 

Вместе со статьей следует прислать сопроводительное письмо-рекомендацию в произвольной форме, экспертное

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

Порядок рецензирования

Все статьи, поступающие в редакцию (соответствующие тематике и оформленные согласно требованиям к публи
кации), подлежат обязательному рецензированию в течение месяца с момента поступления. 

В редакции есть устоявшийся коллектив рецензентов, среди которых члены международной редколлегии журнала, 

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

Рецензирование проводится конфиденциально. Автору статьи предоставляется возможность ознакомиться с тек
стом рецензии. При необходимости статья отправляется на доработку.

Рецензии обсуждаются на заседаниях рабочей группы, состоящей из членов научного совета журнала. Заседания 

проводятся раз в месяц в НИИ «Центрпрограммсистем» (г. Тверь), где принимается решение о целесообразности публикации статьи.

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

Редакция международного журнала «Программные продукты и системы» в своей работе руководствуется сводом 

правил Кодекса этики научных публикаций, разработанным и утвержденным Комитетом по этике научных публикаций 
(Committee on Publication Ethics – COPE).

Программные продукты и системы / Software & Systems
1 (31) 2018

5

УДК 656.073.7
Дата подачи статьи: 12.12.17

DOI: 10.15827/0236-235X.031.1.005-011
2018. Т. 31. № 1. С. 005–011

ПРОГРАММНЫЕ СРЕДСТВА РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ 

РАЗМЕЩЕНИЯ ТРАНСПОРТНЫХ ОБЪЕКТОВ 

НА ОСНОВЕ АЛГОРИТМА КЛАСТЕРИЗАЦИИ С ПРОЕКЦИЕЙ

Б.А. Есипов 1, к.т.н., доцент, bobpereira@yandex.ru

1 Самарский национальный исследовательский университет им. академика С.П. Королева, 
Московское шоссе, 34, г. Самара, 443086, Россия

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

В статье предлагаются математическая модель и новый метод решения задачи оптимального размещения логисти
ческих центров двухуровневой сети перевозок на основе применения математического аппарата кластерного анализа. 
При заданных геоинформационных параметрах производств-поставщиков, а также заданной топологии дорог, станций или других объектов транспортной инфраструктуры ставится задача оптимального выбора логистических центров. Для сети железных дорог логистическими центрами могут быть, например, контейнерные пункты. Критерием 
оптимизации является минимизация общего суммарного объема перевозок в тонно-километрах от производств до контейнерных пунктов. Для этого в качестве оптимизационной математической модели используется модель разбиения 
объектов на кластеры. Искомыми кластерами являются подмножества точек-производств со своими центрами – контейнерными пунктами. Поскольку центры кластеров обязательно должны находиться на железнодорожных станциях, 
предложен новый алгоритм кластеризации с проекцией. Исследованы возможности такого алгоритма кластеризации, 
названного k-means pro.

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

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

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

Основной идеей для повышения эффективности 

транспортных сетей является создание многоуровневой инфраструктуры (см. рис. 1) с центрами обслуживания на каждом уровне [2]. 

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

Постановка задачи оптимального размещения 

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

основе переборных алгоритмов NP-сложности и не 
позволяет решать поставленные задачи для десятков тысяч предприятий и тысяч железнодорожных 
станций [2–4].

Классические задачи о кратчайшем расстоянии 

между точками и их центром на плоскости решаются, когда точки, для которых находится центр, 
заданы. В общем случае оптимизация расстояний 
от точек до центров подмножеств точек должна достигаться вариацией самих подмножеств точек, что 
приводит к задаче оптимальной кластеризации исходного множества точек и определения оптимальных центров кластеров. Известно, что при боль
Рис. 1. Двухуровневая сеть контейнерных перевозок 
(точки – производства, квадраты и треугольники –
логистические центры первого и второго уровней)

Fig. 1. A two-tier network of container transportations 

(points are production, squares and triangles are logistics 

centers of the first and second level)

Программные продукты и системы / Software & Systems
1 (31) 2018

6

ших n полный перебор таких вариантов определяется величиной порядка kn–1, где k – количество 
кластеров, а n – количество точек (производств). 
Поэтому для практических задач необходимы методы, радикально уменьшающие перебор вариантов [4, 5].

Математическая модель размещения 

транспортных объектов на основе 

кластерного анализа

В данной работе для оптимального выбора мест 

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

Геометрическая близость объектов от центра 

гарантирует минимизацию расстояний при перевозке, а учет веса каждого объекта, выражающего 
объем перерабатываемой объектом продукции, оптимизирует общие затраты на перевозки. Большое 
достоинство кластерного анализа и в том, что он 
позволяет производить разбиение объектов не по 
одному параметру, а по целому набору признаков. 
Анализ литературы по кластерному анализу и опыт 
использования стандартных программных средств 
кластерного анализа позволяют утверждать, что 
принципиально возможно решать поставленные 
задачи для практических задач большой размерности (для федеральных округов и всей страны в целом) [7, 8]. 

Однако при подходе к решению практических 

задач оптимизации местоположения КП и КНРЦ на 
основе идеи кластеризации возникла новая проблема, решение которой развивает сами методы 
кластерного анализа.

Так, при применении алгоритмов кластериза
ции по известному методу k-means [6] считается, 
что оптимальный центр может находиться в любой 
точке пространства параметров, определяющих 
объекты. Если параметры – это геометрические координаты центров производства, то центр лежит в 
любой точке плоскости. На практике следует рассмотреть случай, когда центр обязательно должен 
находиться в одной из заданных точек (например, 
на железнодорожной линии или станции). Таким 
образом, при решении задачи определения мест КП 
и КНРЦ приходится решать задачу кластеризации 
с проекцией на функцию, когда центр обязательно 
должен находиться на железнодорожной магистрали, или с проекцией на точки – на железнодорожной станции. 

В работе предлагается новый алгоритм класте
ризации с проекцией на множество точек, названный k-means pro, и исследуется возможность его 
применения в практических задачах проектирования транспортной инфраструктуры [4].

Входными данными алгоритма являются мно
жество объектов кластеризации X = {x1, …, xn}, их 
веса V = {v1, …, vn} и допустимое множество проекций Y = {y1, …, yp}. Каждый j-й объект и каждая 
допустимая точка-проекция заданы в G-мерном 
пространстве RG, то есть xj = (xj1, …, xjG) и yr = (yr1, 
…, yrG).

Единственным управляющим параметром явля
ется число кластеров k, на которые производится 
разбиение S = {S1, …, Sk} множества Х. В результате получается несмещенное разбиение S* = {S*1, 
…, S*k}, центры которого – это оптимальное множество проекций C*  Y.

Введем следующие обозначения: n – количе
ство объектов кластеризации; p – количество точек 
допустимого множества проекций; i, i’ – номер кластера;  j – номер объекта; r – номер точки множества проекций; l – номер координаты точки; m – номер текущей итерации; G – размерность пространства, в котором выполняется кластеризация.

Расстояние между точками в G-мерном про
странстве определяется по евклидовой метрике, 
где tl и t2 – две любые точки пространства RG:

2

1
2
1
2

1

( ,
)
(
) .

G

l
l

l

d t t
t
t







Алгоритм k-means pro.
1. Выберем начальное разбиение 

0
0
0

1
{
, ...,
}
k
S
S
S

,




0
0
0

1

0
0
0
'

1

, ...,
,

,
,
’.

i
i
in

k

i
i
i

i

S
x
x

S
X
S
i
i
S







 


2. Пусть построено m-е разбиение 

1
{
, ...,
}
m
m
m
k
S
S
S

.

Вычислим 
набор 
векторов 
средних 

1
{
, ...,
}

m
m
m
k
E
e
e

, то есть 
1
(
, ...,
)
m
m
m

i
i
iG
e
e
e

, 

где 

1

1

in

j
jl

j
m
il
n

j

j

v x

e

v





 



; ni – количество точек i-го 

кластера.

3. Определим множество проекций средних для 

текущего разбиения:

*

1
{
:
,
( ,
)
min
(
,
)}

m
m
m

i
r
i
r
p
C
y
Y
i
d
y e
d y e

 




.

4. Построим минимальное дистанционное раз
биение, порождаемое множеством Cm, и возьмем 
его в качестве 
1
1
1

1
(
, ...,
),

m
m
m
k
S
S
S





то есть




1

'
1
'
:
( ,
)
min
( ,
) , 1
.

m
m
m

i
i
i
i
k
S
x
X
d x c
d x c
i
k



 



 

Программные продукты и системы / Software & Systems
1 (31) 2018

7

5. Если Sm+1  Sm, то переходим к п. 2, заменив 

m на m+1; если Sm+1 = Sm, то полагаем Sm = S*, 
Cm = C* и заканчиваем работу алгоритма.

Поскольку на последовательности разбиений 

S0, S1, …, Sm, строящейся в алгоритме, функционал 

качества разбиений 
 
 

2

1
i

k

i

i
X
S

F S
X
e
S






 
не 

возрастает, причем F(Sm) = F(Sm+1), только если 
Sm=Sm+1, для любого начального разбиения S0 алгоритм через конечное число шагов заканчивает работу. Сложность вычислений по этому алгоритму 
оценивается как O(nkm), где n – количество кластеризуемых объектов; k – количество кластеров; m –
количество итераций.

Начальное разбиение 
0
0
0

1
{
, ...,
}
k
S
S
S

выбира
ется произвольным образом, например так: из 
всего множества координат объектов выбираются 
минимальное и максимальное число по x и по y, 
затем в этом диапазоне выбираются k точек 
(начальных центров кластеров). В данной работе 
координаты этих центров е0 получены как случайные числа, равномерно распределенные в прямоугольнике возможных координат исходных точек в 
диапазонах [xmin, xmax] и [ymin, ymax] соответственно. 
Затем для каждого объекта кластеризации выбирается ближайшая из этих точек, таким образом получается начальное случайное разбиение на непересекающиеся подмножества S0.

Для проверки устойчивости результатов и полу
чения различных зависимостей менялся выбор е0, 
получались 100 различных реализаций, из них выбиралась наилучшая, а также усреднялись полученные параметры для построения различных графиков. 

Исследование алгоритма k-means pro

Разработана программа, реализующая приве
денный алгоритм с возможностью визуализации 
получаемых кластеров и вычисления разнообразных параметров. Для сравнения взят классический 
алгоритм k-means Мак-Куина [6, 9, 10]. Сравнение 
производилось на тестовых выборках точек, распределенных равномерно на плоскости. На рисунке 2 показаны кластеры, полученные классическим k-means, а на рисунке 3 – алгоритмом k-means 
pro. В данном примере железнодорожная магистраль представлена в виде синусоиды (+ отмечены 
центры кластеров, o – железнодорожные станции). 
Из рисунков 2 и 3 следует, что оптимальное разбиение точек на кластеры для обычного алгоритма 
приводит к тому, что центры располагаются произвольно (рис. 2), в то время как с использованием 
алгоритма k-means pro оптимальная кластеризация 
допускает только центры, лежащие на железнодорожных станциях (рис. 3).

Разработанный алгоритм применен для реше
ния задачи оптимального выбора мест расположе
ния КП для заданных 900 производств и 137 железнодорожных станций Приволжского федерального 
округа (ПФО). Производства определялись географическими координатами и объемом контейнеропригодной продукции. Множество железнодорожных станций задано на сети 7 железных дорог, расположенных на территории ПФО. Результат при 
k = 42 показан на рисунке 4, где точками изображены заданные производства, малыми квадратиками – железнодорожные станции, большими квадратами – найденные станции-КП. Показаны кластеры производств.

Представляет интерес соотношение показате
лей качества кластеризации для обычного алгоритма и алгоритма кластеризации с проекцией. 
В первом случае центры кластеров определяются 
исключительно из свойств расположения объектов 
(точек) и критерия оптимальности кластеризации 
D. Такую кластеризацию в контексте данной работы можно назвать свободной.

В рассматриваемом случае центры кластеров 

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

Fig. 2. Free clustering

Рис. 3. Кластеризация с проекцией

Fig. 3. Clustering with a projection

Программные продукты и системы / Software & Systems
1 (31) 2018

8

ризации с проекцией и, очевидно, с другим значением критерия Dпр. 

Для классического алгоритма k-means

1
1

(
,
)

in
k

ij
i

i
j

D
d x
e




 
, 

2
2

1
1
2
2
(
,
)
(
)
(
)
ij
i
ij
i
ij
i
d x
e
x
e
x
e




.

Для k-means pro

*

1
1

(
,
),

in
k

пр
ij
i

i
j

D
d x
с




 

*
*
2
*
2

1
1
2
2
(
,
)
(
)
(
)
ij
i
ij
i
ij
i
d x
c
x
c
x
c




.

На рисунке 5 изображена зависимость D и Dпр

от k для вышеприведенного примера, а на рисунке 6 для ПФО. Видно, что суммарное расстояние 
сначала резко падает при увеличении числа кластеров, а затем меняется слабо.

Назовем дефектом проекции разницу критери
альных величин качества свободной кластеризации 
и кластеризации с проекцией: Δ = Dпр – D. Зависи
мость Δ /D от k для производств ПФО показана на 
рисунке 7.

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

Выбор оптимального 
количества кластеров

Выбор оптимального числа кластеров является 

проблемным вопросом кластерного анализа [5, 7]. 
Рассмотрим экономический подход к выбору оптимального количества кластеров k. В данном случае 
это число определяет количество логистических 
центров (КП).

Итак, пусть количество КП не задано (k неиз
вестно), но известна приведенная к одному году 

Рис. 4. Кластеризация предприятий ПФО

Fig. 4. Clustering of Volga Federal District companies