Інтеграція ГІС-технологій і методів розв'язання неперервних задач оптимального мультиплексного розбиття множин
The article presents а review of software and technologies of geographic information systems in the context of applying them to solve practical problems of the territorial segmentation, mathematical models of which are reduced to continuous problems of optimal multiplex-partitioning of sets. In this...
Saved in:
| Date: | 2017 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2017
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/103015 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1867334280917549056 |
|---|---|
| author | Koriashkina, Larysa S. Cherevatenko, Antonina Pavlovna Koriashkina, E. O. |
| author_facet | Koriashkina, Larysa S. Cherevatenko, Antonina Pavlovna Koriashkina, E. O. |
| author_institution_txt_mv | [
{
"author": "Larysa S. Koriashkina",
"institution": "Кафедра системного анализа и управления Государственного высшего учебного заведения \"Национальный горный университет\", Днепр"
},
{
"author": "Antonina Pavlovna Cherevatenko",
"institution": "Кафедра системного анализа и управления Государственного высшего учебного заведения \"Национальный горный университет\", Днепр"
},
{
"author": "E. O. Koriashkina",
"institution": "Учебно-научный комплекс \"Институт прикладного системного анализа\" Национального технического университета Украины \"Киевский политехнический институт имени Игоря Сикорского\", Киев"
}
] |
| author_sort | Koriashkina, Larysa S. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-04-04T16:37:16Z |
| description | The article presents а review of software and technologies of geographic information systems in the context of applying them to solve practical problems of the territorial segmentation, mathematical models of which are reduced to continuous problems of optimal multiplex-partitioning of sets. In this case, service zone models are understood as geometry-based procedures for creating theoretical service zones using characteristics of the service center and assumptions about the customer behavior. The basic requirements to the data used in developed software, that includes methods for solving problems of multiplex-partitioning of sets and GIS technologies, are described. The results of segmentation of the city area into zones that are served by several service centers are given, taking into account the possibility of zones overlapping. An approach to solving problems of the optimal placement of service centers in a limited nonconvex incoherent region with a simultaneous segmentation is proposed. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2017.4.08 |
| first_indexed | 2025-07-17T10:21:01Z |
| format | Article |
| fulltext |
Л.С. Коряшкина, А.П. Череватенко, Е.О. Коряшкина, 2017
Системні дослідження та інформаційні технології, 2017, № 4 97
УДК 519.8
DOI: 10.20535/SRIT.2308-8893.2017.4.08
ИНТЕГРАЦИЯ ГИС-ТЕХНОЛОГИЙ И МЕТОДОВ РЕШЕНИЯ
НЕПРЕРЫВНЫХ ЗАДАЧ ОПТИМАЛЬНОГО
МУЛЬТИПЛЕКСНОГО РАЗБИЕНИЯ МНОЖЕСТВ
Л.С. КОРЯШКИНА, А.П. ЧЕРЕВАТЕНКО, Е.О. КОРЯШКИНА
Аннотация. Представлен обзор программного обеспечения и технологий гео-
информационных систем в контексте применения их к решению практических
задач территориальной сегментации рынка услуг, математические постановки
которых сводятся к непрерывным задачам оптимального мультиплексного
разбиения множеств. Под моделями зон обслуживания понимаются основан-
ные на геометрии процедуры создания теоретических зон обслуживания с ис-
пользованием характеристик сервисного центра и предположений о поведении
клиента. Описаны основные требования к наборам данных, используемых в
разработанном программном обеспечении, включающем методы решения за-
дач мультиплексного разбиения и ГИС-технологии. Приведены результаты
сегментации территории города на зоны обслуживания несколькими центрами
услуг с учетом возможности перекрытия зон. Предложен подход к решению
задач оптимального размещения сервисных центров в ограниченной невыпук-
лой несвязной области с одновременной сегментацией рынка услуг.
Ключевые слова: непрерывные задачи оптимального мультиплексного раз-
биения множеств, геоинформационные системы, ГИС-технологии, территори-
альная сегментация рынка услуг.
ВВЕДЕНИЕ
Непрерывные задачи оптимального мультиплексного разбиения множеств
(ОМРМ) состоят в разбиении ограниченного множества из пространства nE
на такие подмножества точек, каждое из которых отвечает (в соответствии с
определенным критерием) одному и тому же набору k точек из N сущест-
вующих, называемых центрами )( Nk [1, 2]. Как отмечено в работе [2],
выбор критерия оптимальности мультиплексного разбиения определяется
спецификой самих центров. Чаще всего это или минимизация суммарного
взвешенного расстояния от центров до всех точек, им соответствующих, или
оптимизация наихудшего варианта, когда минимизируется максимальное
расстояние от центров до самой отдаленной точки соответствующего им
подмножества. Вопросам, связанным с теоретическим обоснованием мето-
дов решения непрерывных линейных задач ОМРМ в различных постанов-
ках, а также исследованию свойств решений и практических приложений
таких задач, посвящены работы [3–6].
В работах [5, 6] показано, что при 2E непрерывные задачи ОМРМ
могут выступать в качестве математических моделей задач территориальной
сегментации рынка услуг, в особенности когда зоны могут перекрываться.
При этом необходимо учитывать такие факторы, как спрос и предложение
на рынке услуг, количество и расположение уже существующих сервисных
Л.С. Коряшкина, А.П. Череватенко, Е.О. Коряшкина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 98
центров, неохваченные предложением территории, места наибольшей кон-
центрации потенциальных клиентов. Кроме того, планирование размещения
новых сервисных центров предполагает учет и других факторов, таких как
наличие коммуникаций в местах предполагаемого размещения центров, воз-
можные дополнительные расходы на строительство собственных комму-
никаций, налог на землю и т.п. При моделировании реальных задач сегмен-
тации возникают также вопросы, связанные с описанием границ
сегментируемых территорий, вычислением фактических расстояний между
сервисными центрами и их клиентами.
Приведенные выше данные, а также развитые средства автоматизации
процесса поиска кратчайшего пути между конкретными объектами (точками
на карте) предоставляют современные геоинформационные системы (ГИС)
и технологии. Данная работа посвящена вопросам, связанным с расширени-
ем функциональных возможностей компьютерной программы «Optimal
Multiplex-Partitioning of Sets» (OMPS-2015) [7] за счет ее интеграции с сов-
ременными ГИС-технологиями. Некоторые аспекты применения ГИС при
решении задач ОМРМ затронуты в работах [8, 9].
ОБЗОР СОВРЕМЕННЫХ ГИС-ТЕХНОЛОГИЙ
В КОНТЕКСТЕ ВОЗМОЖНОСТИ ИХ ПРИМЕНЕНИЯ
ПРИ РЕШЕНИИ НЕПРЕРЫВНЫХ ЗАДАЧ ОМРМ
Всеобщий интерес к использованию геоинформационных систем в различ-
ных областях практической деятельности вызвало такое их преимущество
перед другими информационными системами, как возможность объедине-
ния разнородных данных на основе географической информации. В настоя-
щее время ГИС широко используются для решения задач корпоративных
пользователей, например, в градостроительной деятельности, природополь-
зовании и многих других областях, предоставляя пользователям возможно-
сти решения задач пространственного анализа, планирования и прогнозиро-
вания. Геоинформационные системы нередко выступают как инструмент
интеграции разнородных информационных систем предприятия, поэтому
программное обеспечение ГИС часто является интегрированным сегментом
корпоративной информационной среды [10].
Интернет-услуги в области геоданных постоянно расширяются и тех-
нологически совершенствуются, затрагивая все более глубокие пласты гео-
информационной деятельности: производство и распространение цифровых
геоданных, их стандартизацию и классификацию, создание ГИС с возмож-
ностями удаленного доступа для широкого круга пользователей посредством
«открытых» сетей, осуществление комплексных научно-исследовательских
ГИС-проектов. Дальнейшее совершенствование развития ГИС-индустрии
связано с созданием специализированных ГИС-технологий. Уже в настоя-
щее время предлагаемые и реализованные технологические решения до-
статочно разнообразны. Это разнообразие диктуется желанием учесть, по
возможности, широкий спектр функциональных и пользовательских требо-
ваний, предъявляемых к интернетовским ГИС-приложениям, таким как ско-
рость формирования, передачи и выполнения запросов, набор геоинформа-
ционных услуг, предоставляемых сервером, возможность доступа и обработки
больших массивов географической информации и т.д. Формируется новое
Интеграция ГИС-технологий и методов решения непрерывных задач оптимального …
Системні дослідження та інформаційні технології, 2017, № 4 99
технологическое направление работы с геопространственными данными в
сетевом режиме, получившее название WebGIS-системы. Разрабатываемые
интегрированные информационно-технологические решения называют
WebGIS-технологиями. Главное их достоинство заключается в том, что эта
технология «связывает» между собой и делает доступными для широкого и
совместного использования геоданные, рассредоточенные по различным
точкам земного шара. Важнейшим свойством разрабатываемых в настоящее
время WebGIS-технологий является то, что, применяя их, пользователи Ин-
тернет получают возможность активной работы с геоданными (вплоть до
реализации собственных ГИС-проектов), не приобретая для этого геоинфор-
мационные программные средства (ГИС-оболочки). Основным инструмен-
том работы остаются только интернет-навигаторы/браузеры, оснащенные
некоторыми стандартными или специализированными программными при-
ложениями, распространяемыми, как правило, в сети Интернет бесплатно.
Таким образом, WebGIS-технологии позволяют добавить геоинформацион-
ные функции к широкому спектру приложений, основанных на сетевом до-
ступе и используемых в бизнесе, управлении, образовании.
Далее рассмотрим вопросы совместного использования ГИС-
технологий и методов решения задач оптимального мультиплексного разби-
ения множеств для территориальной сегментации рынка услуг, т.е. модели-
рования зон сервисного обслуживания на заданной территории. По аналогии
с работами [11–13], где были введены понятия торговых зон Вороного, под
моделями зон обслуживания будем понимать основанные на геометрии
процедуры создания теоретических зон обслуживания с использованием
характеристик сервисного центра и предположений о поведении клиента.
Выделение таких зон наиболее полезно в случаях, если подробные данные о
предпочтениях клиентов отсутствуют либо считаются слишком дорогосто-
ящими, или требуется большое количество времени для их получения. Та-
кие модели могут быть использованы не только для описания, но и для про-
гнозирования зон обслуживания, для определения потенциальных мест
расположения новых сервисных центров, оценивания воздействия этих и
других изменений на существующем множестве центров.
Приведем кратко математическую постановку непрерывной линейной
задачи оптимального мультиплексного разбиения множеств евклидова про-
странства 2E на подмножества k -го порядка с неизвестными заранее коор-
динатами центров, программную реализацию алгоритма решения которой
будем расширять возможностями ГИС.
НЕПРЕРЫВНАЯ ЗАДАЧА ОПТИМАЛЬНОГО МУЛЬТИПЛЕКСНОГО
РАЗБИЕНИЯ МНОЖЕСТВ И ИДЕЯ МЕТОДА ЕЕ РЕШЕНИЯ
Пусть — ограниченное, измеримое по Лебегу, замкнутое множество из
пространства 2E ; ),( )2()1(
iii , для всех Ni ,1 — некоторые точки,
называемые «центрами», координаты которых неизвестны заранее и подле-
жат определению, N
N
N
N ...),...,( 1 .
Будем использовать следующие обозначения: },...,2,1{ NN — набор
всех индексов центров; ),( kΝΜ — множество всех k -элементных под-
Л.С. Коряшкина, А.П. Череватенко, Е.О. Коряшкина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 100
множеств множества Ν , LCkΝΜ k
N ),( ; },...,,{ 21
l
k
ll
l jjj , ,,1 Ll —
элементы из ),( kΝΜ .
С каждым элементом l множества ),( kΝΜ будем ассоциировать
подмножество
l точек из , а с подмножеством
l связывать набор
центров },...,,{
21
l
k
ll jjj
, Ll ,1 .
Пусть kN ,
— класс всех возможных разбиений k -го порядка множе-
ства на его непересекающиеся подмножества
L ,...,,
21
:
;0)(mes,:},...,{
1
,
1 jilL
L
l
kN
LjijikΝΜji ,1,,),,(, .
Непрерывная линейная задача оптимального мультиплексного разбие-
ния множества 2E при ограничениях с размещением центров формули-
руется следующим образом [3, 4].
Задача А. Найти, минимизировав функционал
,min),(
;, NNkN
NF
,)()/) ,((),(
1
L
l i
iii
N
l l
dxxawxcF (1)
где ),( )2()1( xxx ; ),( ixc , Ni ,1 — ограниченные, определенные на
декартовом произведении функции, измеримые по аргументу x при
любом фиксированном векторе ),( )2()1(
iii . Функция )(x — ограничен-
ная, измеримая, неотрицательная на множестве ; ,,0 ii aw ,,1 Ni —
заданные числа.
Оптимальным решением задачи А2- k называется пара ),( ** N , при
которой достигается минимальное значение функционала F .
Метод решения задачи А2- k предполагает переход к эквивалентной
задаче, сформулированной относительно характеристических вектор-
функций подмножеств
l , Ll ,1 , составляющих разбиение k -го поряд-
ка множества , обозначаемых ))(),...,(()( 1 xxx l
N
ll , Ll ,1 , опреде-
ленных на множестве , с координатами, вычисляемыми по следующей
формуле
l
x :
.случаепротивномв0
,&,1
)(
ll
i
ix
x
l
,,1 Ni Ll ,1 ,
Задача Б. Найти ,),( N которые обеспечивают
Интеграция ГИС-технологий и методов решения непрерывных задач оптимального …
Системні дослідження та інформаційні технології, 2017, № 4 101
dxxxawxc
L
l
N
i
l
iiiiNkN
)()()/) ,((min
1 1)),(( 0
,
,,1, 10)(:))(),...,(()( 10 Nixxl
i
l
N
llk ,,1 Ll
.для вездепочти,,1,)(
1
xLlkxl
i
N
i
В работах [3, 4] показано, что оптимальное решение задачи В2- k имеет
следующий вид: для LlNi ,1,,1 и почти всех x
случаях,остальных в 0
,\,
,/),(/),( если ,1
)(
**
* ll
jjjiii
l
i Νji
awxcawxc
x
в качестве N*1* ,..., выбирается оптимальное решение задачи
NN
G
min)( , (2)
где
dxxawxcG
ll i
iii
Ll
k
)(]/),([min)(
,1
),(
. (3)
Решение непрерывной задачи ОМРМ сводится к решению конечномер-
ной задачи (2) с недифференцируемой функцией (3) любым известным ме-
тодом негладкой оптимизации [14].
ИНТЕГРАЦИЯ ГИС-ТЕХНОЛОГИЙ И КОМПЬЮТЕРНОЙ ПРОГРАММЫ
РЕШЕНИЯ МУЛЬТИПЛЕКСНЫХ ЗАДАЧ
ОПТИМАЛЬНОГО РАЗБИЕНИЯ МНОЖЕСТВ
Геоинформационная система хранит информацию о реальном мире в виде
набора тематических слоев, которые объединены на основе географического
положения. Этот простой, но очень гибкий подход доказал свое преимуще-
ство при решении разнообразных реальных задач. Электронные карты, как
правило, содержат полную информацию о протяженности дорог, их связно-
сти и условиях перемещения по ним (скоростные режимы, запрещенные
съезды, наличие перевалочных пунктов и т.д.).
В процессе исследования возможности применения ГИС-технологий
при решении непрерывных задач ОМРМ выбор платформы ГИС был ориен-
тирован на наличие функционала поиска кратчайшего пути и расчета его
длины. Данный функционал является базовым в программных продуктах
семейства ArcGIS. Однако ArcGIS является платным и для его использова-
ния следует приобрести лицензию. Альтернативой платному программному
обеспечению является свободная кроссплатформенная геоинформационная
система QGIS с открытым кодом, которая предоставляет возможность ис-
пользовать инструменты анализа, выборки, геопроцессинга, управления
Л.С. Коряшкина, А.П. Череватенко, Е.О. Коряшкина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 102
геометрией и базами данных. Система QGIS включает в себя и функционал
поиска кратчайшего пути, необходимый при решении практических задач
оптимального мультиплексного разбиения множеств.
Возможны два варианта использования геоинформационных техноло-
гий при решении задач ОМРМ. В первом варианте на этапе расчета длины
пути между точками на карте и выделенными центрами предполагается вы-
зов внешней программы — ГИС. В другом варианте можно расширить фун-
кционал уже существующей ГИС-системы, реализовав в нем методы реше-
ния непрерывных задач ОМРМ. В обоих вариантах требуется провести
некоторый подготовительный этап, который заключается в процессе поиска
и загрузки электронных карт из базы OSM в выбранную ГИС-систему. OSM
(Open Street Map) — ресурс для получения бесплатных данных с открытой
лицензией. База данных OSM содержит информацию о дорогах, улицах, ка-
фе, вокзалах и многих других объектах по всему миру. Получение доступа к
данным OSM в ГИС-формате интегрировано в QGIS.
Несмотря на широкую функциональность упомянутых выше систем
выяснилось, что они позволяют определить путь лишь между точками, ко-
торые принадлежат сети дорог. Для расчета расстояний между двумя произ-
вольными точками на карте требуется дополнительная возможность ГИС-
подпрограммы поиска ближайшей дороги для любой точки. Такой функ-
циональностью обладает сервис Google Maps AP, используемый в миллио-
нах web-сайтов и приложений для расширения возможностей работы с ме-
стоположениями. Сервисы Google Maps API распределены по категориям в
зависимости от платформы: web, Android и iOS. В частности, Google Maps
Distance Matrix API — служба, которая предоставляет информацию о длине
маршрута между начальной и конечной точками. Эти точки могут быть за-
даны как словесно (в виде адреса), так и географическими координатами.
При отправке адреса в виде строки служба выполнит геокодирование строки
и преобразует ее в координаты широты/долготы для расчета расстояний.
Возвращаемая информация основывается на рекомендованном (минималь-
ном) маршруте в соответствии с расчетами Google Maps API. Кроме того,
Google Maps Distance Matrix API позволяет учитывать дополнительные па-
раметры, такие как способ передвижения, ограничения (объекты, которых
следует избегать) и др.
Google Maps API предоставляются бесплатно для широкого спектра
использования, хотя и имеют ограничения на использование API и фиксиро-
ванную плату за превышение этих ограничений. Для получения возможно-
сти использования API Карт необходим ключ, который можно получить,
имея аккаунт Google. Приведенные выше доводы и обусловили выбор биб-
лиотеки Google Maps Distance Matrix API в качестве инструментария, ис-
пользуемого для интеграции ГИС-технологий и программы, реализующей
алгоритмы решения непрерывных задач оптимального мультиплексного
разбиения множеств [7]. При этом ГИС используется для поиска кратчай-
шего пути между любыми двумя точками региона, учитывая дорожный граф.
Не рассматривая детально численный алгоритм решения непрерывных
задач ОМРМ, остановимся лишь на особенностях его реализации совместно
с ГИС-технологиями, возникающих при этом трудностях и способах их пре-
одоления.
Интеграция ГИС-технологий и методов решения непрерывных задач оптимального …
Системні дослідження та інформаційні технології, 2017, № 4 103
1. Подготовительный этап обработки электронных карт состоит в уда-
лении с рисунка карты рек и суши, не принадлежащих территории региона.
Это осуществляется с помощью любого графического редактора. Получен-
ная допустимая область вписывается в прямоугольник , который,
в свою очередь, покрывается прямоугольной сеткой. В каждой точке сетки
определяется функция плотности:
.\,0
;),(
)(
xx
x
2. Ключевой составляющей программы решения непрерывной задачи
оптимального мультиплексного разбиения множества с размещением центров
является r-алгоритм Шора, который, как известно, разработан для решения
задач безусловной недифференцируемой оптимизации. Так как практиче-
ские задачи территориальной сегментации предполагают размещение сер-
висных центров в ограниченной области, зачастую невыпуклой, а иногда и
несвязной, имеющей запретные территории (например, при наличии в облас-
ти водоемов, промышленных зон, рек и т.п.), то приходится решать вопросы,
связанные с тем, чтобы не допустить размещения центра на недопустимой
территории. Для учета «невыхода» за пределы допустимой (разбиваемой)
области размещаемых центров предлагается следующий подход: на каждой
итерации r-алгоритма Шора проверять принадлежность текущих координат
центров допустимой области. В случае, если какой-либо центр попадает в
запретную зону — находить его «псевдопроекцию» на разбиваемое множе-
ство. Под псевдопроекцией точки 2Ez на замкнутое множество 2E
будем понимать точку )(zDv , такую что ),(distmin),(dist
)(
xzvz
zDx
,
где множество ,,{)( RwzvzD }},{ 21 eew ; 21,ee — орты осей
координат, ),(dist vz — расстояние между двумя точками.
3. С целью сокращения количества обращений к библиотеке Google
Maps Distance Matrix API, а, следовательно, и количества задействованных
вычислительных ресурсов – объема оперативной памяти и времени, требуе-
мого на выполнение как одного запроса, так и в целом всех запросов, реше-
ние задачи ОМРМ с размещением центров производится в два этапа. На
первом этапе решается задача А2- k , в которой в качестве функций ),( ixc ,
Ni ,1 , выступает одна из известных метрик – манхэттенская, евклидова,
Минковского, Чебышева. При этом выбор метрики осуществляется путем
предварительного сравнения результатов мультиплексного разбиения кон-
кретного региона на основе расстояний между точками, вычисляемых тео-
ретически и с помощью ГИС. На втором этапе подключением ГИС для поис-
ка фактического расстояния между найденными центрами и точками региона
определяется оптимальное разбиение k -го порядка заданного региона.
ПРИМЕРЫ РЕАЛИЗАЦИИ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ОМРМ
С ИСПОЛЬЗОВАНИЕМ ГИС-ТЕХНОЛОГИЙ
Приведем результаты работы разработанного программного продукта с ис-
пользованием ГИС для решения модельной задачи территориальной сегмен-
Л.С. Коряшкина, А.П. Череватенко, Е.О. Коряшкина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 104
тации рынка услуг на примере города Днепра. В качестве сервисных цен-
тров выбраны существующие отделения грузоперевозок «Новой почты». На
рис. 1, а показано триплексное разбиение города на зоны обслуживания
в предположении, что клиент для того, чтобы воспользоваться почтовыми
услугами, полагает k ближайших центров одинаково привлекательными
(а это означает, что в функционале (1) центры i — фиксированы, 1iw ,
0ia , Ni ,1 ). Расстояния от центров до точек города определены с по-
мощью ГИС. Для сравнения на рис. 1, б, в, г приведены результаты разбие-
ния 3-го порядка той же территории, но полученные на основе теоретиче-
ских расстояний между двумя точками на карте города (разбиение
с использованием на рис. 1, б манхэттенской метрики, на рис. 1, в — эвкли-
довой метрики и на рис. 1, г — метрики Минковского, 10p ).
Рис. 1. Оптимальное триплексное разбиение города Днепра для 15 сервисных цен-
тров, полученное с использованием: а — ГИС-технологий, б — манхэттенской
метрики, в — эвклидовой метрики, г — метрики Минковского (р=10)
Соответствие цвета ближайшим центрам Соответствие цвета ближайшим центрам
а б
Соответствие цвета ближайшим центрам Соответствие цвета ближайшим центрам
в г
Интеграция ГИС-технологий и методов решения непрерывных задач оптимального …
Системні дослідження та інформаційні технології, 2017, № 4 105
При анализе результатов этих и других вычислительных экспериментов
был сделан вывод о том, что адекватнее всего расстояние между двумя точ-
ками на карте города описывает манхэттенская метрика. Поэтому в даль-
нейшем при решении задачи ОМРМ с размещением центров использовалась
именно эта метрика.
На рис. 2 показаны результаты решения модельной задачи дуплексного
разбиения )2( k города с размещением сервисных центров на его террито-
рии: рис. 2, а — оптимальное размещение центров и разбиение на основе
манхэттенской метрики, рис. 2, б — оптимальное разбиение второго поряд-
ка для тех же центров с учетом фактического расстояния между точками
города).
Отметим, что представленные модели мультиплексного разбиения
множеств позволяют получить перекрытие сервисных зон. Так, на рис. 3, 4
показаны зоны обслуживания для конкретных центров при разбиении 2-го и
3-го порядков. Полученные в результате сервисные зоны не являются взаи-
моисключающими и в большей степени соответствуют реальности, напри-
мер, по сравнению с моделями, которые приводят к разбиению первого по-
рядка и определяют сервисные зоны как пространственные монополии.
Как видно на рис. 3, д, з, а также на рис. 4, е, зоны влияния определен-
ных центров могут представлять собой несвязные подмножества разбивае-
мого множества. Этот факт является еще одной характерной особенностью
применения методов решения задач мультиплексного разбиения несвязного
множества совместно с ГИС-технологиями и показывает, насколько важно
при оптимальной сегментации рынка услуг на конкретной территории учи-
тывать реальные транспортные развязки и подъездные пути для каждой
точки рассматриваемой области.
Соответствие цвета ближайшим центрам Соответствие цвета ближайшим центрам
а б
Рис. 2. Отпимальное дуплексное разбиение города Днепра с размещением девяти
центров: а — оптимальное размещение центров и разбиение на основе
манхэттенской метрики; б — оптимальное разбиение для тех же центров с учетом
фактического расстояния между точками города
Л.С. Коряшкина, А.П. Череватенко, Е.О. Коряшкина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 106
а б в
г д е
Рис. 4. Разбиение 3-го порядка. Зоны обслуживания сервисных центров: а — пер-
вого, б — второго, в — третьего, г — тринадцатого, д — четырнадцатого, е —
пятнадцатого
а б в
ж з и
г д е
Рис. 3. Дуплексное разбиение. Зоны обслуживания сервисных центров: а — перво-
го, б — второго, в — третьего, г — четвертого, д — пятого, е — шестого, ж —
седьмого, з — восьмого, и — девятого
Интеграция ГИС-технологий и методов решения непрерывных задач оптимального …
Системні дослідження та інформаційні технології, 2017, № 4 107
ВЫВОДЫ
В работе продемонстрирована возможность применения ГИС-технологий
при решении непрерывных задач оптимального мультиплексного разбиения
множеств. Представленный в работе подход к территориальной сегментации
региона обеспечивает разумные приближения реальных зон обслуживания
сервисных центров быстро и без больших затрат, а также без необходимости
проведения детальной экспертизы зон влияния центров со стороны ана-
литика.
С учетом того, что непрерывные задачи ОМРМ могут выступать в ка-
честве математических моделей реальных задач территориальной сегмента-
ции (например, при разделении рынка услуг или при диагностике конку-
рентной среды, для сегментации карт и геопространственного
интеллектуального анализа данных), использование ГИС-технологий при
разработке алгоритмов решения таких задач представляет собой актуальное
направление научных исследований и требует дальнейшего развития.
ЛИТЕРАТУРА
1. Коряшкіна Л.С. Розширення одного класу нескінченновимірних
оптимізаційних задач / Л.С. Коряшкіна // Вісн. Черкаськ. ун-ту. Сер. Прикл.
матем. Інф. — 2015. — № 18(351). — С.28–36.
2. Коряшкина Л.С. О способах задания функционала качества в задачах мультип-
лексного разбиения множеств / Л.С. Коряшкина // Вычислительные методы,
модели и образовательные технологии: сб. материалов Междунар. науч.-
практ. конф., Брест, 22–23 окт. 2015 г. / Брест. гос. ун-т им. А.С. Пушкина ;
под общ. ред. О.В. Матысика. — Брест: БрГУ, 2015. — С. 40–41.
3. Koriashkina L.S. Continuous problems of optimal multiplex-partitioning of sets
without constraints and solving methods / L.S. Koriashkina, А.Р. Cherevatenko //
Journal of Computational & Applied Mathematics. — 2015. — N 2 (119). —
P. 15–32.
4. Коряшкина Л.С. Непрерывные линейные задачи оптимального
мультиплексного разбиения множеств с ограничениями / Л.С. Коряшкина,
А.П. Череватенко // Вісн. Харків. нац. ун-ту ім. В. Н. Каразіна. Серія «Ма-
тематичне моделювання. Інформаційні технології. Автоматизовані системи
управління». — 2015. — Вип. 28. — С. 77–91.
5. Коряшкина Л.С. Об одном подходе к территориальной сегментации рынка
услуг / Л.С. Коряшкина, А.П. Череватенко // Современные информацион-
ные и коммуникационные технологии на транспорте, в промышленности и
образовании: сб. материалов Междунар. науч.-практ. конф., 16–17 дек.
2015 г. — Дн-ск: ДНУЖТ им. В.А. Лазаряна, 2015. — С. 81.
6. Koriashkina L. The continuous problems of the optimal multiplex partitioning an ap-
plication of sets / L. Koriashkina, A. Cherevatenko, O. Mykhalova // Power En-
gineering and Information Technologies in Technical Objects Control – Pivnyak,
Beshta & Alekseyev (eds). — Taylor & Francis Group, London. — 2016. —
P. 233–239.
7. Коряшкіна Л.С. Свідоцтво 64326 Україна про реєстрацію авторського права на
твір «Комп’ютерна програма «Optimal Multiplex-Partitoning of Sets» (OMPS-
2015) / Л.С. Коряшкіна, А.П. Череватенко (Україна). — № 64838; заявл.
31.12.15; зареєстровано 01.03.16 в Державному реєстрі свідоцтв про
реєстрацію авторського права на твір.
Л.С. Коряшкина, А.П. Череватенко, Е.О. Коряшкина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 108
8. Коряшкина Л.С. Использование ГИС-инструментария при решении практиче-
ских задач мультиплексного разбиения множеств / Л.С. Коряшкина,
А.П. Череватенко // Вычислительные методы, модели и образовательные
технологии: сб. материалов Междунар. науч.-практ. конф., Брест, 21 окт.
2016 г. / Брест. гос. ун-т им. А.С. Пушкина; под общ. ред. О.В. Матысика.
— Брест: БрГУ, 2016. — С. 63–64.
9. Коряшкина Л.С. О программной реализации алгоритмов оптимального муль-
типлексного разбиения множеств совместно с ГИС- технологиями при ре-
шении задач сегментации рынка услуг / Л.С. Коряшкина, А.П. Череватенко
// Современные информационные и коммуникационные технологии на
транспорте, в промышленности и образовании: тезисы Х Междунар. науч.-
практ. конф., Днипро, 14–15 дек. 2016 г. — Д.: ДИИТ, 2016. — С. 52.
10. Павлов С.В. Сервис-ориентированная архитектура программного обеспечения
корпоративных геоинформационных систем / С.В. Павлов, Т.М. Усов,
Р.А. Шкундина // Управление, вычислительная техника и информатика:
вестн. УГАТУ. — Уфа: УГАТУ, 2010. — Т. 14, № 5 (40). — С. 163–169.
11. Lee I. Map segmentation for geospatial data mining through generalized higher-order
Voronoi diagrams with sequential scan algorithms / I. Lee, C. Torpelund-Bruin,
K. Lee // Expert Systems with Applications. — 2012. — Vol. 39, Issue 12. —
P. 11135–11148.
12. Boots B. Modeling Retail Trade Areas Using Higher-Order, Mukiplicatively
Weighted Voronoi Diagrams / B. Boots, R. South. // Journal of Retailing 73(4).
— 1997. — P. 519–536.
13. Okabe A. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams /
A.Okabe, B. Boots, K. Sugihara, S. Chiu. — Chichester, West Sussex: John
Wiley & Sons, 2000. — 696 p.
14. Киселева Е.М. Непрерывные задачи оптимального разбиения множеств и
r -алгоритмы / Е.М. Киселева, Л.С. Коряшкина. — К.: Наук. думка, 2015.
— 400 с.
Поступила 16.06.2017
|
| id | journaliasakpiua-article-103015 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:21:01Z |
| publishDate | 2017 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/a1/a7dfacda20b2a70f9bd65dc8a34ec2a1.pdf |
| spelling | journaliasakpiua-article-1030152018-04-04T16:37:16Z Integration of GIS technologies and methods of solving continuous problems of optimal multiplex-partitioning of sets Интеграция ГИС-технологий и методов решения непрерывных задач оптимального мультиплексного разбиения множеств Інтеграція ГІС-технологій і методів розв'язання неперервних задач оптимального мультиплексного розбиття множин Koriashkina, Larysa S. Cherevatenko, Antonina Pavlovna Koriashkina, E. O. continuous problems of optimal multiplex-partitioning of sets geographic information systems GIS technologies territorial segmentation непрерывные задачи оптимального мультиплексного разбиения множеств геоинформационные системы ГИС-технологии территориальная сегментация рынка услуг неперервні задачі оптимального мультиплексного розбиття множин геоінформаційні системи ГІС-технології територіальна сегментація ринку послуг The article presents а review of software and technologies of geographic information systems in the context of applying them to solve practical problems of the territorial segmentation, mathematical models of which are reduced to continuous problems of optimal multiplex-partitioning of sets. In this case, service zone models are understood as geometry-based procedures for creating theoretical service zones using characteristics of the service center and assumptions about the customer behavior. The basic requirements to the data used in developed software, that includes methods for solving problems of multiplex-partitioning of sets and GIS technologies, are described. The results of segmentation of the city area into zones that are served by several service centers are given, taking into account the possibility of zones overlapping. An approach to solving problems of the optimal placement of service centers in a limited nonconvex incoherent region with a simultaneous segmentation is proposed. Представлен обзор программного обеспечения и технологий геоинформационных систем в контексте применения их к решению практических задач территориальной сегментации рынка услуг, математические постановки которых сводятся к непрерывным задачам оптимального мультиплексного разбиения множеств. Под моделями зон обслуживания понимаются основанные на геометрии процедуры создания теоретических зон обслуживания с использованием характеристик сервисного центра и предположений о поведении клиента. Описаны основные требования к наборам данных, используемых в разработанном программном обеспечении, включающем методы решения задач мультиплексного разбиения и ГИС-технологии. Приведены результаты сегментации территории города на зоны обслуживания несколькими центрами услуг с учетом возможности перекрытия зон. Предложен подход к решению задач оптимального размещения сервисных центров в ограниченной невыпуклой несвязной области с одновременной сегментацией рынка услуг. Подано огляд програмного забезпечення та технологій геоінформаційних систем у контексті застосування їх до вирішення практичних проблем територіальної сегментації ринку послуг, математичні постановки яких зводяться до неперервних задач оптимального мультиплексного розбиття множин. Під моделями зон обслуговування слід розуміти засновані на геометрії процедури створення теоретичних зон обслуговування з використанням характеристик сервісного центру і припущень про поведінку клієнта. Описано основні вимоги до наборів даних, що використовуються у розробленому програмному забезпеченні, до складу якого входять методи розв’язання задач мультиплексного розбиття і ГІС-технології. Наведено результати сегментації території міста на зони обслуговування декількома центрами послуг з урахуванням можливості перекриття зон. Запропоновано підхід до вирішення завдань оптимального розміщення сервісних центрів на обмеженій неопуклій незв'язній області з одночасною сегментацією ринку послуг. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2017-12-15 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/103015 10.20535/SRIT.2308-8893.2017.4.08 System research and information technologies; No. 4 (2017); 97-108 Системные исследования и информационные технологии; № 4 (2017); 97-108 Системні дослідження та інформаційні технології; № 4 (2017); 97-108 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/103015/114235 Copyright (c) 2021 System research and information technologies |
| spellingShingle | неперервні задачі оптимального мультиплексного розбиття множин геоінформаційні системи ГІС-технології територіальна сегментація ринку послуг Koriashkina, Larysa S. Cherevatenko, Antonina Pavlovna Koriashkina, E. O. Інтеграція ГІС-технологій і методів розв'язання неперервних задач оптимального мультиплексного розбиття множин |
| title | Інтеграція ГІС-технологій і методів розв'язання неперервних задач оптимального мультиплексного розбиття множин |
| title_alt | Integration of GIS technologies and methods of solving continuous problems of optimal multiplex-partitioning of sets Интеграция ГИС-технологий и методов решения непрерывных задач оптимального мультиплексного разбиения множеств |
| title_full | Інтеграція ГІС-технологій і методів розв'язання неперервних задач оптимального мультиплексного розбиття множин |
| title_fullStr | Інтеграція ГІС-технологій і методів розв'язання неперервних задач оптимального мультиплексного розбиття множин |
| title_full_unstemmed | Інтеграція ГІС-технологій і методів розв'язання неперервних задач оптимального мультиплексного розбиття множин |
| title_short | Інтеграція ГІС-технологій і методів розв'язання неперервних задач оптимального мультиплексного розбиття множин |
| title_sort | інтеграція гіс-технологій і методів розв'язання неперервних задач оптимального мультиплексного розбиття множин |
| topic | неперервні задачі оптимального мультиплексного розбиття множин геоінформаційні системи ГІС-технології територіальна сегментація ринку послуг |
| topic_facet | continuous problems of optimal multiplex-partitioning of sets geographic information systems GIS technologies territorial segmentation непрерывные задачи оптимального мультиплексного разбиения множеств геоинформационные системы ГИС-технологии территориальная сегментация рынка услуг неперервні задачі оптимального мультиплексного розбиття множин геоінформаційні системи ГІС-технології територіальна сегментація ринку послуг |
| url | https://journal.iasa.kpi.ua/article/view/103015 |
| work_keys_str_mv | AT koriashkinalarysas integrationofgistechnologiesandmethodsofsolvingcontinuousproblemsofoptimalmultiplexpartitioningofsets AT cherevatenkoantoninapavlovna integrationofgistechnologiesandmethodsofsolvingcontinuousproblemsofoptimalmultiplexpartitioningofsets AT koriashkinaeo integrationofgistechnologiesandmethodsofsolvingcontinuousproblemsofoptimalmultiplexpartitioningofsets AT koriashkinalarysas integraciâgistehnologijimetodovrešeniânepreryvnyhzadačoptimalʹnogomulʹtipleksnogorazbieniâmnožestv AT cherevatenkoantoninapavlovna integraciâgistehnologijimetodovrešeniânepreryvnyhzadačoptimalʹnogomulʹtipleksnogorazbieniâmnožestv AT koriashkinaeo integraciâgistehnologijimetodovrešeniânepreryvnyhzadačoptimalʹnogomulʹtipleksnogorazbieniâmnožestv AT koriashkinalarysas íntegracíâgístehnologíjímetodívrozvâzannâneperervnihzadačoptimalʹnogomulʹtipleksnogorozbittâmnožin AT cherevatenkoantoninapavlovna íntegracíâgístehnologíjímetodívrozvâzannâneperervnihzadačoptimalʹnogomulʹtipleksnogorozbittâmnožin AT koriashkinaeo íntegracíâgístehnologíjímetodívrozvâzannâneperervnihzadačoptimalʹnogomulʹtipleksnogorozbittâmnožin |