РЕШЕНИЕ ЗАДАЧИ О МНОГОПОЛЮСНОЙ ЦЕПИ С МАКСИМАЛЬНОЙ ПРОПУСКНОЙ СПОСОБНОСТЬЮ В ГЕОИНФОРМАЦИОННЫХ СИСТЕМАХ
Авторы:
1.
Астраханский государственный университет
2.
Астраханский государственный университет
3.
Астраханский государственный университет
Тип:
Статья
Страницы:
с 53
по 57
Статус:
Опубликован
Получено:
05.04.2015
Одобрено:
25.04.2015
Опубликовано:
25.04.2015
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК [656.135.073:004]:625.711/.712
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК [656.135.073:004]:625.711/.712
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
геоинформационная система, автомобильный транспорт, грузоперевозки, многополюсная цепь, сетевая структура
Аннотация (русский):
Описана методика поиска маршрута грузоперевозок на основе решения задачи о многополюсной сети с максимальной пропускной способностью. Выделяют два типа требований к организации грузоперевозки (критериев выбора оптимального маршрута): обязательные (пропускная способность участка дороги в зависимости от тоннажа машины, количество полос движения и т. д.) и желательные (качество дорожного покрытия, наименьшая аварийность пути следования груза и т. д.). В качестве обеспечивающей технологии принята технология геоинформационных систем, где совокупность маршрутов может быть рассмотрена как геометрический линейный объект высокого уровня - сеть, представленная в виде графа, ребрами которого являются участки городских автодорог, а узлами - перекрестки либо точки изменения состояния дороги. Описан алгоритм формирования графовых структур на основе атрибутивных данных - пространственных и качественных характеристик участков дороги. Рассмотрены механизм построения матрицы пропускных способностей в соответствии с обязательными и желательными критериями, а также свёртка набора критериев в суперкритерий, построение результатной матрицы пропускных способностей и матрицы оптимального конечного маршрута. Программная реализация предлагаемой методики позволит расширить стандартный функционал поисковых механизмов геоинформационных систем при работе с сетевыми объектами.
Описана методика поиска маршрута грузоперевозок на основе решения задачи о многополюсной сети с максимальной пропускной способностью. Выделяют два типа требований к организации грузоперевозки (критериев выбора оптимального маршрута): обязательные (пропускная способность участка дороги в зависимости от тоннажа машины, количество полос движения и т. д.) и желательные (качество дорожного покрытия, наименьшая аварийность пути следования груза и т. д.). В качестве обеспечивающей технологии принята технология геоинформационных систем, где совокупность маршрутов может быть рассмотрена как геометрический линейный объект высокого уровня - сеть, представленная в виде графа, ребрами которого являются участки городских автодорог, а узлами - перекрестки либо точки изменения состояния дороги. Описан алгоритм формирования графовых структур на основе атрибутивных данных - пространственных и качественных характеристик участков дороги. Рассмотрены механизм построения матрицы пропускных способностей в соответствии с обязательными и желательными критериями, а также свёртка набора критериев в суперкритерий, построение результатной матрицы пропускных способностей и матрицы оптимального конечного маршрута. Программная реализация предлагаемой методики позволит расширить стандартный функционал поисковых механизмов геоинформационных систем при работе с сетевыми объектами.
Ключевые слова:
геоинформационная система, автомобильный транспорт, грузоперевозки, многополюсная цепь, сетевая структура
геоинформационная система, автомобильный транспорт, грузоперевозки, многополюсная цепь, сетевая структура
Введение Рыночные отношения предъявляют к транспортной системе жесткие требования по ускорению доставки грузов при минимизации затрат на транспортировку, повышению качества и надежности перевозок. В условиях портового города возникает задача оптимизации внутренних автомобильных перевозок негабаритных и нестандартных грузов. Задача транспортировки груза состоит в определении оптимального маршрута между пунктами погрузки и выгрузки, с учетом ряда правил и ограничений, имеющихся в сети автомобильных дорог в городской черте и в области. Одним из эффективных способов решения данной проблемы является выбор оптимального пути следования груза из точки отправления в точку доставки, исходя из особенностей груза. Однако выбор соответствующего пути невозможен без учета всех характеристик участков дорог, составляющих маршрут, например, ширины дороги, допустимой тоннажности груза, количества полос движения и качества дорожного покрытия. Подобную информацию предоставляют дорожные службы города и области. Существует ряд косвенных характеристик, которые также необходимо учитывать при составлении маршрута следования негабаритных и тяжеловесных грузов, например, высота линий электроснабжения и рекламных растяжек над дорогой, высота подмостовых зазоров и т. п. [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. Кириченко А. В. Перевозка экспортно-импортных грузов / А. В. Кириченко // Организация логистических схем. СПб.: Питер, 2004. 505 с.
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. Грешилов А. А. Математические методы принятия решений / А. А. Грешилов. М.: Изд-во МГТУ им. Н. Э. Баумана, 2006. 586 с. // URL: http://baumanpress.ru/books/456/456.pdf.
5. Ху Т. С. Целочисленное программирование и потоки в сетях / Т. С. Ху. М.: Мир, 1973. 520 с.
