SOLUTION OF THE TASK OF MULTIPOLAR NETWORK WITH MAXIMUM BANDWIDTH IN THE GEOGRAPHICAL INFORMATION SYSTEMS
Authors:
1.
Astrakhan State Technical University
2.
Astrakhan State Technical University
3.
Astrakhan State Technical University
Type:
Article
Pages:
from 53
to 57
Status:
Published
Received:
05.04.2015
Accepted:
25.04.2015
Published:
25.04.2015
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK [656.135.073:004]:625.711/.712
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK [656.135.073:004]:625.711/.712
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
geographic information system, automobile transport, cargo transportation, multipolar network, network structure
Abstract (English):
The article describes the method for searching a cargo transportation route through solving the problem of a multipolar network with maximum bandwidth. Two types of the requirements (criteria of choosing optimal route) to cargo transportation are defined; they are mandatory (road bandwidth depending on car weight limits, number of road lanes, etc.) and desirable (the quality of road surface, the minimum accident statistics on cargo route, etc.). The geographic information system is taken as the supporting technology, where a set of routes can be presented as a linear geometrical high-level object - the network, presented as a graph, where edges are city road parts, but the nodes are the crossroads or the points of road state change. The article describes the algorithm for building graph structures using attribute data - spatial and qualitative characteristics of the road parts. The mechanisms of building a bandwidth matrix for each mandatory and desirable criteria, as well as the convolution of a set of criteria into super-criteria and building the resulting bandwidth matrix and matrix for optimal route are described. Software implementation of this method allows to extend the standard functionality of geographic information system search engines when working with network entities.
The article describes the method for searching a cargo transportation route through solving the problem of a multipolar network with maximum bandwidth. Two types of the requirements (criteria of choosing optimal route) to cargo transportation are defined; they are mandatory (road bandwidth depending on car weight limits, number of road lanes, etc.) and desirable (the quality of road surface, the minimum accident statistics on cargo route, etc.). The geographic information system is taken as the supporting technology, where a set of routes can be presented as a linear geometrical high-level object - the network, presented as a graph, where edges are city road parts, but the nodes are the crossroads or the points of road state change. The article describes the algorithm for building graph structures using attribute data - spatial and qualitative characteristics of the road parts. The mechanisms of building a bandwidth matrix for each mandatory and desirable criteria, as well as the convolution of a set of criteria into super-criteria and building the resulting bandwidth matrix and matrix for optimal route are described. Software implementation of this method allows to extend the standard functionality of geographic information system search engines when working with network entities.
Keywords:
geographic information system, automobile transport, cargo transportation, multipolar network, network structure
geographic information system, automobile transport, cargo transportation, multipolar network, network structure
Введение Рыночные отношения предъявляют к транспортной системе жесткие требования по ускорению доставки грузов при минимизации затрат на транспортировку, повышению качества и надежности перевозок. В условиях портового города возникает задача оптимизации внутренних автомобильных перевозок негабаритных и нестандартных грузов. Задача транспортировки груза состоит в определении оптимального маршрута между пунктами погрузки и выгрузки, с учетом ряда правил и ограничений, имеющихся в сети автомобильных дорог в городской черте и в области. Одним из эффективных способов решения данной проблемы является выбор оптимального пути следования груза из точки отправления в точку доставки, исходя из особенностей груза. Однако выбор соответствующего пути невозможен без учета всех характеристик участков дорог, составляющих маршрут, например, ширины дороги, допустимой тоннажности груза, количества полос движения и качества дорожного покрытия. Подобную информацию предоставляют дорожные службы города и области. Существует ряд косвенных характеристик, которые также необходимо учитывать при составлении маршрута следования негабаритных и тяжеловесных грузов, например, высота линий электроснабжения и рекламных растяжек над дорогой, высота подмостовых зазоров и т. п. [1]. Владельцем такой информации являются как частные собственники бизнеса, так и муниципальные и городские службы. Цель исследования - разработка методики нахождения оптимального пути перевозки негабаритного и тяжеловесного груза путем обобщения всех атрибутов участков дорог, полученных из гетерогенных сред, сравнение имеющейся атрибутивной информации и выработка оптимального пути. Методика нахождения оптимального пути грузоперевозки Автомобильные дороги городского и областного значения представляют собой сетевой объект, который подчиняется правилам построения и работы с этими объектами. Основными объектами любой сетевой структуры являются узел и дуга. Под узлом понимается точка в сетевой структуре, образованная на пересечении двух и более дуг, или образованная в месте значительной смены какой-либо качественной характеристики. Под дугой понимается отрезок дороги между соседними узлами, который идентифицируется образующими его узлами и обладает атрибутами. Все атрибуты данного участка дороги, или дуги, можно разделить на пространственные и качественные, причем пространственные определяют физическое расположение участка дороги, а качественные играют определяющую роль при решении задачи о нахождении оптимального пути. Таким образом, задача транспортировки негабаритного и нестандартного груза сводится к определению оптимального набора связанных между собой участков дороги в соответствии с заданными условиями перевозки. Сеть автомобильных дорог является геометрическим объектом высокого уровня, для которого следует учитывать две характеристики по критерию направления движения: одни участки дорог имеют направление движения «в оба конца» и являются ненаправленными, другие - только одно направление движения и являются направленными. Графически дорожная сеть строится с использованием разных соединительных дуг между узлами перевозки: если на дуге явно не указано направление движения, то это означает, что данный участок дороги является ненаправленным, в противном случае необходимо графически задать направление движения между смежными узлами (рисунок). Пример сети автомобильных дорог Если известен пункт отправления и пункт назначения груза, заданные пункты для сети автомобильных дорог, принимаются как начальный и конечный узел, а задача транспортировки сводится к определению внутри данных узлов маршрута передвижения, состоящего из n-участков дорог. При решении задачи о транспортировке конкретного груза выделяют 2 типа характеристик (требований): 1. Обязательные - это требования, указанные в нормативно-правовой базе регулирования данного вида деятельности [2, 3] (пропускная способность участка дороги в зависимости от тоннажа машины для грузоперевозки, количество полос движения и т. п.). 2. Желательные - дополнительные требования заказчика (качество дорожного покрытия, наименьшая аварийность пути следования груза и др.). На практике не исключены ситуации, когда выполнение всех желательных условий становится невозможным. В этом случае необходимо задать ранг каждому условию в зависимости от степени его важности. В итоге получаем множество значений , т. е. множество критериев выбора пути. Для решения поставленной задачи нахождения оптимального маршрута используем алгоритм решения задачи о многополюсной цепи с максимальной пропускной способностью [4, 5], согласно которой максимальному потоку между каждой парой узлов может соответствовать множество маршрутов из пункта отправки к пункту назначения груза. В целом, методику нахождения оптимального пути можно представить в виде следующих последовательных шагов. Шаг 1. Для дорог на исследуемой территории строится простая сеть с обозначенными максимальными пропускными способностями по каждому из критериев. На каждой дороге имеется величина пропускной способности дуги по каждому критерию mij. Шаг 2. Строится матрица пропускных способностей размером , элементы которой соответствуют пропускным способностям дуг между узлами i и j (где i, j=1, 2, … n) по конкретному критерию: Если заранее известны габариты перевозимого груза и ограничения по дорожному полотну, то очевидно, что в конечную матрицу пропускных способностей по конкретному критерию должны войти только те элементы, которые больше или равны ограничениям, установленным по каждому перевозимому грузу. Данное предположение не противоречит общей концепции решения задачи о многополюсной кратчайшей цепи, т. к. дуга с наименьшей пропускной способностью дает максимальную пропускную способность всей цепи. Таким образом, строим матрицу пропускных способностей по критерию, заменяя элементы, меньшие допустимого ограничения по конкретному критерию, на значения равные нулю. Шаг 3. Получив на n критериев n матриц пропускных способностей необходимо провести операцию умножения матриц. Шаг 4. Так как условия перевозки разделены на 2 группы, то необходимо комбинированно подходить к проблеме получения конечной матрицы пропускных способностей ( содержащий суперкритерий), к которой впоследствии будет применен алгоритм решения задачи о многополюсной кратчайшей цепи. Для начала необходимо найти произведение матриц пропускных способностей, соответствующих критериям первой группы, (обязательным): . В результате получаем матрицу, которая должна удовлетворять обязательному условию, т. е. для всех узлов переходов должна существовать хотя бы одна дуга перехода как минимум в одном направлении, в противном случае транспортировка указанного груза становится невозможной для автомобильного транспорта и необходимо будет принимать решение об использовании других видов транспорта. Шаг 5. Предположим, что существует матрица пропускных способностей обязательных условий . Тогда необходимо поочередно наложить условия второй группы, т. е. выбрать матрицу пропускных способностей желательного условия с наивысшим рангом. Производим операцию умножения матриц , где - промежуточная конечная матрица пропускных способностей; - матрица желательного условия с наивысшим рангом. После каждой итерации умножения матриц, составленных по второй группе критериев, необходимо проверять получившуюся промежуточную конечную матрицу пропускных способностей на соответствие обязательным условиям. Если после очередной операции перемножения матриц выяснится, что обязательные условия не выполняются, то необходимо взять результат предыдущего перемножения и считать его конечной матрицей пропускных способностей . Таким образом, может получиться, что заранее определенное конечное множество критериев перевозки сократится за счет исключения наименее важных (не обязательных, а желательных) критериев перевозки. В итоге получаем конечную матрицу пропускных способностей, содержащую в себе суперкритерий перевозки груза, который представляют собой результат мультипликативной свертки значений пропускных способностей каждой дуги по каждому из конечного множества отобранных критериев. Шаг 6. Далее делаем необходимые преобразования над конечной матрицей пропускных способностей, заменяя в случае отсутствия соединительной дуги между узлом i и j ранее имеющееся значение, равное нулю, на значение, равное . Нулевыми остаются только диагональные элементы результатной матрицы пропускных способностей. Далее решаем задачу о цепи с максимальным потоком между всеми парами узлов по полученному суперкритерию. Шаг 7. Строится матрица маршрутов , в которой все элементы столбцов заменяются одинаковыми числами, равными номеру столбца. Над результатной матрицей пропускных способностей необходимо выполнить следующие операции: Шаг 8. Для любых i, j=1, 2, … n исключить j-ю строку и i-й столбец матрицы (диагональные элементы тоже исключаются), производим тернарную операцию: (1) для всех j=1, 2,… n. Имеющаяся матрица маршрутов необходима для определения внутренних узлов каждой цепи. Матрица маршрутов имеет размер , где k-й элемент i-й строки первоначально равен k. Шаг 9. Вместе с вычислением значений элементов в матрице пропускных способностей вычисляется справочная матрица маршрутов: элемент (i-й, k-й) матрицы маршрутов предполагается сначала равным k, затем выполняется замена в соответствии с правилом Количество таких итераций над матрицами пропускных способностей и матрицами маршрутов необходимо провести j раз, где j = 1, 2, … n. В результате преобразования получаем оптимальное решение, выраженное в конечной матрице пропускных способностей и конечной матрице маршрутов . Данный метод расчета оптимального пути использует только 2 точки, однако, если рассматривать ситуацию, в которой происходит доставка груза нескольким адресам, то алгоритм расчета необходимо запустить для каждого адресата в соответствии с порядком доставки. Заключение Рассмотренный метод вычисления пути транспортировки позволяет включить его в информационную систему, функционал которой может дополнить стандартные методы поиска оптимальных путей, используемые в готовых типовых геоинформационных системах. Программная реализация данного метода в совокупности с методами гармонизации и структурирования входных данных об объектах дорожной сети, а также с методами визуализации и вывода выходной расчётной информации возможна в самостоятельном геоинформационном сервисе.
1. Kirichenko A. V. Perevozka eksportno-importnyh gruzov / A. V. Kirichenko // Organizaciya logisticheskih shem. SPb.: Piter, 2004. 505 s.
2. URL: http://www.orendor.ru/inst_perevoz_gruzov_po_20130213.htm.
3. URL: http://base.consultant.ru/cons/cgi/online.cgi?req=doc;base=LAW;n=168230.
4. Greshilov A. A. Matematicheskie metody prinyatiya resheniy / A. A. Greshilov. M.: Izd-vo MGTU im. N. E. Baumana, 2006. 586 s. // URL: http://baumanpress.ru/books/456/456.pdf.
5. Hu T. S. Celochislennoe programmirovanie i potoki v setyah / T. S. Hu. M.: Mir, 1973. 520 s.
