автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Совершенствование процедур поддержки принятия решений в логистических системах на основе геоинформационных технологий

На правах рукописи

Макарян Александр Самвелович

СОВЕРШЕНСТВОВАНИЕ ПРОЦЕДУР ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ В ЛОГИСТИЧЕСКИХ СИСТЕМАХ НА ОСНОВЕ ГЕОИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (информационные и технические системы)

Автореферат

диссертации на соискание ученой степени кандидата технических наук

2 Я НОЯ 2013

Краснодар-2013

005541082

Работа выполнена в ФГБОУ ВПО «Кубанский государственный технологический университет»

Научный руководитель: кандидат технических наук, профессор

Кучер Виктор Алексеевич

Официальные оппоненты: доктор технических наук, профессор,

профессор кафедры специальной связи Филиал Военной академии связи (город Краснодар)

Хисамов Франгиз Гильфанстдинович

кандидат физико-математических наук, доцент, начальник кафедры информатики и математики Краснодарского университета МВД России

Старостенко Игорь Николаевич

Ведущая организация: ФГБОУ ВПО «Кубанский государственный

аграрный университет»

Защита диссертации состоится «25» декабря 2013 года в 1400 часов на заседании диссертационного совета Д212.100.04 в ФГБОУ ВПО «Кубанский государственный технологический университет» по адресу: 350072, г. Краснодар, ул. Московская, 2, корпус «Г», аудитория Г-248

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Кубанский государственный технологический университет» Автореферат разослан «22» ноября 2013 г.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

А.В. Власенко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

б) аналитическое сопровождение штатных процессов логистики;

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

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

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

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

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

Особый интерес представляет круг вопросов, связанный с разработкой, формализацией и совершенствованием математического и алгоритмического обеспечения логистических СППР при решении задач различного класса.

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

Объект исследования. Система поддержки принятия решений для задач транспортной логистики.

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

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

1. Анализ существующих методов решения задач транспортной логистики.

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

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

4. Разработка модели функционирования транспортной логистической СППР с совершенствованием процедур оптимизации, учитывающих различные типы исходной информации.

5. Разработка специального математического и алгоритмического обеспечения транспортной логистической СППР на основе ГИТ.

6. Оценка эффективности разработанных моделей, алгоритмов и программного обеспечения.

Научная новизна.

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

2. Разработана модель функционирования транспортной логистической СППР на основе ГИТ.

3. Разработан алгоритм двухфазной оптимизации для управления транспортной логистической системой.

4. Разработана архитектура транспортной логистической СППР на основе ГИТ.

5. Разработано специальное математическое и программное обеспечение для функционирования транспортной логистической системы на основе ГИТ. Основные положения, выносимые на защиту:

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

2. Принципы построения и структура транспортной логистической СППР на основе ГИТ.

3. Алгоритмическая реализация основных методов и этапов поддержки принятия решений для управления функционированием транспортной логистической системы на основе ГИТ.

4. Алгоритм двухфазной оптимизации транспортной логистической системы.

5. Программное обеспечение транспортной логистической СППР на основе ГИТ.

Практическая ценность. Практическая значимость работы заключается в разработке специализированного программного комплекса, позволяющего решать прикладные задачи в различных областях с использованием алгоритмов транспортной логистической СППР на основе ГИТ.

Апробация работы. Основные результаты диссертационной работы докладывались на 3 всероссийских и 3 международных конференциях и конкурсах:

1. Всероссийская конференция молодых ученых и студентов. «Современное состояние и приоритеты развития фундаментальных наук в регионах», Краснодар, 1-5 октября 2011 г.

2. III Международная научная конференция «TTC — 11», Краснодар, 5-7 октября 2011 г.

3. XIII Международная научно-практическая конференция «Перспектива развития информационных технологий», Новосибирск, 24 июня 2013г.

4. II Конкурс молодежных научных и инновационных проектов «InnoTech 2012», Краснодар, 7-9 ноября 2012 г. (доклад отмечен дипломом победителя).

5. II Всероссийская молодежная конференция «Перспектива-2012», ТТИ ЮФУ, Таганрог,25-29 июня 2012 г,

6. Десятый Международный симпозиум «Интеллектуальные системы» (1ЫТЕЬ8'2012), г. Вологда, Вологодский государственный технический университет 25 - 29 июня 2012 г.

Результаты работы докладывались также на научно-технических семинарах, проводимых в Институте информационных технологий и безопасности ФГБОУ В ПО «Кубанский государственный университет» в 2011 -2013 гг. Публикации. Основные результаты научных исследований по теме диссертации содержатся в 9 публикациях: из них 1 публикация в журналах, входящих в перечень рецензируемых журналов ВАК РФ при Минобрнауки России, Зсвидетельства о государственной регистрации программ для ЭВМ. Список публикаций приведен в конце автореферата.

Внедрение результатов работы. Разработанное математическое и алгоритмическое обеспечение было использовано при создании программного комплекса поиска оптимальных радиусов логистики в системе СППР по логистическим задачам, и в настоящее время эксплуатируется в администрации МО г. Краснодар. Лнчный вклад. В работе [1] автором предложена оптимизационная математическая модель решения задачи автоматизированного планирования транспортного обеспечения в условиях чрезвычайкой ситуации. В работах [5], [б] и [8] предложена математическая постановка и имитационная модель, а также процедура выбора альтернатив в СППР по транспортному обеспечению на основе модифицированного алгоритма решения задачи «коммивояжера». В [7] показана структура СППР, а также варианты повышения эффективности деятельности органов управления за счет совершенствования взаимодействия и связей блоков системы. В [9] предложена математическая модель принятия решения для управления логистической транспортпой системой на основе двухфазного модифицированного алгоритма решения задачи «коммивояжера», а также алгоритм поиска оптимальных радиусов логистики для принятия управленческих решений. Структура и объем работы. Работа состоит из введения, 4-х глав, заключения, приложений и содержит 164 страницы, 31 рис., 13 табл., список литературы из 156 названия.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первом разделе проведен системный анализ организации функционирования логистических систем, включающий с себя анализ: необходимости создания и совершенствования транспортной логистической системы поддержки принятия решений (ТЛСППР) на основе ГИТ, путей создания транспортных логистических СППР, правил, приемов и методов поддержки принятия логистических решений, методов оптимизации транспортных маршрутов в задачах логистики, программных средств оптимизации и планирования логистических мероприятии, а также программного обеспечения геоинформационных систем (ГИС).

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

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

В соответствии с этим задача принятия логистических решений состоит из трех компонентов:

- оценка состояния внешней среды;

- установка логистических целей;

- поиск вариантов решений.

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

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

В общем виде схема поддержки принятия решения включает следующие этапы:

- выявление проблемы;

- формулировка задач;

- формализация;

- анализ ресурсов;

- сбор данных и их анализ;

- синтез решений и формирование альтернатив;

- анализ альтернатив.

Стандартная структурная схема ТЛСППР представлена на рисунке 1. В ее состав входят: ЛПР, интерфейс взаимодействия, модуль организации диалога, подсистема данных и знаний, подсистема моделей, подсистема расчетов, блок ввода параметров объектов, эксперты и оператор.

Основой моделирования оптимизации транспортных маршрутов в задачах транспортной логистики является решение классической задачи «коммивояжера». Причем, в качестве алгоритма решения задачи был выбран метод «ветвей и границ», который дает более точные результаты по сравнению с другими известными алгоритмами.

Рисунок 1 - Структурная схема ТЛСППР

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

- использование масштабируемых карт и транспортных схем;

- выбор оптимального маршрута по заданным характеристикам;

- предоставление информации о транспортных средствах, их загруженности и состоянии транспортной сети;

- предоставление данных о зонах и областях действий, их изменений и характеристик;

- расчет времени транспортных мероприятий.

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

1. Использование ГИС не только в качестве средства визуализации, но и в качестве подсистемы, связанной с моделями, расчетами, базами данных.

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

3. Анализ складывающейся ситуации и выдача управленческих решений на основе совместной работы подключаемого экспертного модуля, ГИС, подсистемы данных и расчетов.

Настольные или пользовательские ГИС представляют собой картографическое программное обеспечение, предназначенное для установки и запуска на персональном компьютере, позволяющее отображать, обновлять и анализировать данные о географических объектах и связанную с ними атрибутивную информацию. Анализ ГИС показал, что наиболее целесообразно для ТЛСППР использовать ГИС GRASS. Данная ГИС обладает хорошей совместимостью со средой разработки, картографическими данными и позволяет настраивать свои функции под любые геоинформациоппые задачи. Она реализует возможности записи и

чтения векторных данных (SHP, GML, DFX), записи и чтения растровых данных (JPEG, GeoTIFF,ECW), поддержки стандартов разработки геосервисов (WMS, WFS, SFS, GML), записи и чтения систем баз геоданных (PostGfS, ArcSDE, Oracle). В заключении главы сформулироваиы выводы, цели и задачи исследования. Второй раздел посвящен разработке математической модели и алгоритма оптимизации поддержки принятия решений для управления транспортной сетью в логистических системах. Общий алгоритм процедуры принятия решения по логистическому транспортному обеспечению, состоящий из последовательных этапов системного анализа, приведен в виде [DEFO-диаграммы па рисунке 2. Из диаграммы следует, что переход к последующему этапу затруднен без реализации предыдущего, но возможны итерации для достижения наиболее эффективного результата.

Рисунок 2 — Общий алгоритм процедуры принятия решений по логистическому транспортному обеспечению

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

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

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

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

критерии и ограничения:

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

- общее время процесса Т (минимизация);

- время ожидания обслуживания одного пункта сбора / (минимизация);

- транспортные ресурсы и ГСМ (минимизация). параметры:

N = хп,х12,... ,х1п- совокупность пунктов сети (ПС), которые должны быть обслужены / -той сборной областью сети (СО() (узлы); /-узел-источник, е Л/; — узел-назначение, е Ы\ 1 < I < р- число СО, закрепленных за данной сетью;

- расстояние от узла / к узлу/; \?ц — скорость на участке от узла /' к узлу у; переменные:

- время движения от узла / к узлу у;

Сц- бинарная переменная, показывающая присутствие или отсутствие связи между узлами;

Т - общее время процесса.

/¿(*а. — Хы) - значение целевой функции, характеризующей процесс транспортировки объектов в СО¡и представляющий собой решение задачи «коммивояжера» для закрепленной совокупности ПС.

поправочные переменные:

- состояние транспортной сети (заторы, вид дорожного полотна и т.д.);

- метеоусловия.

В задаче «коммивояжера» стоимость между узлом /и узлом/ - это расстояние 5\ Таким образом, учитывая, что Уу - самая высокая скорость па участке от узла /' к узлу /', время движения представлено как:

В качестве значения функции ¡\ принято время выполнения задачи по обслуживанию в сопоставимых единицах (часы, минуты):

При достижении оптимального Т, будет достигаться оптимальность /?„,„, который можно будет наблюдать на карте сети.

Совокупность ПС, которые находятся в зоне обслуживания СО, представлено как подмножество множества ПС данной сети. Причем на множество пунктов сети установлено отношение эквивалентности: обслуживание /-ой СО, что обеспечивает разбиение множества на непересекающиеся подмножества.

Таким образом, находим:

(1)

(2)

где Т{ьг, ..., ¿р}и Х{Х11,Х12, ...,х|п}- непустые множества.

тттах Т =1Ч=,^кмТиСи,

(3)

при условии

1 Afi = l,

О, иначе.

при матричном ограничении элементов множества ПС, где строки матрицы соответствуют СО, а столбцы - ПС.

Х1 х2 хз ••■ Хп

СО 1 /Эц а12 а13 С02 I

СОр \api ap2 ар3

(5)

Зрп

(6)

Элементы матрицы определяются следующим образом:

.. || f 1, если XjeiaiioueiieMapiupym i — ойСО-, " (О, впротивоположномслучае.

Значения функции /¡ получают при решении задачи оптимизации для отдельной СО с помощью программного модуля, аргументы функции имеют дискретно-матричный вид, поэтому целесообразно для решения задачи (3) применение метода «ветвей и границ», который резко сократит вычислительную сложность.. Разработаем специальный алгоритм, позволяющий получить суб-опгималыюе решение задачи (3) с ограничениями (4, 5, 6), использующий модифицированный алгоритм решения задачи «коммивояжера».

Для получения суб-оптимального решения проводится целенаправленное изменение первоначального разбиения множества ПС по закрепленным СО.

Связи между подмножествами ПС, принадлежащим зонам обслуживания соседних СО представлены в виде ме га-матрицы (7).

COI С02 COI ... СОр

/си

с12 с13

С02

С21 с22

СО р \С|

pi

'-рг

рз

!Р\

2р

г 1, еслиСО;иСОусоседпие;

гда|кч11 = |п"--------.........." (8)

" 111 10, впротивоположномслучае. В модели задачи для соседних СО допустим перераспределение ПС. Передаем пункты сбора между соседними СО, при этом значения нелевых функций также изменяются:

- значение ... Х(п) уменьшается,

- значение — х]-п) увеличивается.

С

Погрешность йТ, Точность

Рисюфовалие значений функпий /¡<*ц. ... по убыванию

Определение СО,,, имеющей ишенмшнм )Н9Ч«КНе фуНКШШ Ми {Д(*и. ...»Ьп»

Выявление всея соселких областей к СО,, имеющих максимхтьное значенззе функции ДОц. •••**„)

Определение СО,, имеющей

минимальное значение функции /¡(гг1, среди

областей соседних к СОк

Полмножества СО, увеличивается. а подмножество СОк уменьшается ка одну единицу

Ранжирование финальных значений функции ...х(п) по убыванию

Определение максимального к минимального финального значения функтти

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

Рисупок 3-Алгоритм оптимизационной задачи кий. Процесс протекает

поэтапно, мощности подмножеств СО[ (увеличивается) и СОк (уменьшается) изменяются до тех пор, пока не будет выполнено:

1/К*(1. -хщ)-Мхк...хкп)\ < М\ (9)

Шаги повторяются пока существует пара соседних СО для которых выполнено:

Шхп, ...х1п) ~/к(хк1, | > Д£; (10)

Определяются максимальное и минимальное финальные значения функций, и если выполнено (11), то задача решена:

1/тах - /т!п1 < (И)

В случае, если неравенство (9) не выполнено, то задаются новое уменьшенное значение точности вычислений Д£ и процессы повторяются.

В случае, если и в этой итерации неравенство (9) не выполняется, то следует задать новую пару значений допустимой погрешности решения задачи ДТ и точности вычислений АС.

Если физические условия: пропускная способность маршрутов, технические характеристики материального обеспечения СО и топология соединений будут таковы, что величину Д£ можно сделать удовлетворяющую неравенству:

Л? < ^/р, (р- количество СО, данного объекта) (12)

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

В случае непрерывных функций /¡, алгоритм завершается, когда выполнено равенство: А = /2 = • ■ • = /р (13)

Третий раздел посвящен структуре, составу, алгоритмической и программной реализации ТЛСППР на основе ГИС. На рисунке 4 представлены этапы создания логистической транспортной системы с использованием процедур поддержки принятия решений на основе ГИТ.

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

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

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

Рисунок 4 — Этапы создания ТЛСППР на основе ГИС

Основу данной системы составляет комплекс взаимосвязанных моделей с соответствующей информационной поддержкой исследования, ГИС, экспертные и интеллектуальные системы, включающие опыт решения задач управления и обеспечивающие участие коллектива экспертов в процессе выработки рациональных решений.

Ядром ТЛСППР является ГИС, которая отвечает за интерактивный ввод и редактирование данных, визуализацию результатов процесса, а также за предоставление достоверных геоданных из web — геосерверов. Сделан выбор системы управления базами данных в пользу Microsoft SQL Server 2012 (технологии Data Warehousing), в которой реализована поддержка создания хранилищ данных (Data Warehousing, BI Development Studio, OLAP, Data Mining). Проведен выбор языка программирования, а также платформы функционирования экспертного модуля. Выяснилось что, платформа Exsys Corvid, предназначенная для разработки и развертывания базы знаний экспертов и построения экспертных систем, функционирующих в режиме on-line, и язык программирования Delphi хорошо совместимы и позволяют работать друг с другом с помощью HTML — шаблонов. ГИС GRASS, которая была выбрана для создания системы, содержит более трехсот модулей для визуализации карг и изображений, управления растров и векторными данными, в том числе vector сетями. Система позволяет обрабатывать многозональные изображения данных и создавать, управлять и хранить пространственные данные.ГИС GRASS поддерживает многопользовательские рабо-

чие группы благодаря возможности настройки на совместное использование данных с установкой по NFS (Network File System) или CIFS. В четвертой разделе представлены результаты испытаний программного комплекса. Для апробации и испытания системы была исследована следующая ситуация: в муниципальном образовании город Краснодар произошло чрезвычайное происшествие природного характера (подтопление одного из районов), в районе находится четыре пункта посадки сбора населения, к которым стягиваются люди из пострадавшего района в соответствии с правилами поведения населения в режиме ЧС природного характера. Задачей системы является определение ближайшего эвакуационного пункта, расчет и обеспечение транспортных эвакуационных мероприятий. Оператор системы берет на себя управление процессом: он определяет, с помощью экспертного модуля, данных ГИС и аналитической информации, город, район, критерии и ограничения для расчетов.

После настройки аналитического блока и расчетных значений, оператор может переходить к расчету мероприятий, при этом JUIF по данному процессу не видит всего процесса расчета результатов, сравнения альтернатив и т.д. Процесс вывоза населения в безопасную зону 5, начинается с формирования транспорта и анализа сети дорог, в соответствии с этим, происходит расчет обхода пунктов сбора 3, 2, 5, 6 транспортом, вышедшим из пункта 5 (эвакуационный пункт). В данном случае непринципиально направление обхода пунктов, так как заданные ограничения и критерии позволяют производить обход в любую удобную сторону (время процесса одинаково), но если добавить ограничения, такие как пробки, метеоусловия и т.д., то направление обхода будет иметь первоочередное значение. При этом четыре пункта сбора охватывают область ЧС. Они пересекаются и образуют зону эвакуации, в которой ведется объезд пунктов сбора. У каждого пункта есть свой Ropl, который задает система (рис. 6).

Оператор должен утвердить решение в соответствии с решением выработанным системой и запустить процесс, либо пересчитать зоны и сам процесс в соответствии с новыми условиями.

Рисунок 6 - Зоны эвакуации с Яор,

На данном этапе, процесс моделирования переходит в реальный процесс, и ЛПР может с помощью системы наблюдать эвакуацию по карте с констатацией временных данных (время Т = 43 мин. 11 сек.) (рис. 7).

Л 0!ГИ1?««вМ€ И

Рисунок 7 — Процесс эвакуации

Оценка эффективности применения ТЛСППР проведена в соответствии с критериям:

— минимизация общего времени процесса Т\

— минимизация времени ожидания обслуживания одного ПС (;

— минимизация транспортных ресурсов и ГСМ.

Общего времени процесса с применением ТЛСППР уменьшилось на 20-22 %. Использование ТЛСППР сокращает общее количество участвующих в процессе специалистов, что приводит к сокращению ошибок в процессе принятия решения. Также сокращается время ожидания обслуживания одного ПС на 15-17 % и количество транспортных ресурсов на 10-15 %.

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

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

В заключении приводится обобщение основных результатов диссертационной работы. В приложениях приводятся: листинг программы ТЛСППР и свидетельства об официальной регистрации программ для ЭВМ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

В результате проведённой работы можно говорить о найденном решении поставленных задач и достижении поставленной цели. Предложенные методы, алгоритмы и функциональная схема ТЛСППР на основе ГИТ позволили решить следующие задачи:

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

2. Усовершенствованы процедуры аппарата генерации альтернатив при принятии решений в логистической системе, и на основе их сформулирован ал-

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

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

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

5. Построена структура ТЛСППР, отвечающая требования многозадачности и интеллектуальности рассматриваемых задач. Представлены этапы создания транспортной логистической системы поддержки принятия решений с использованием геоинформационных технологий, где после каждого этапа передается управляющее воздействие последующему этапу, описанное перечнем выходных лингвистических указаний. Архитектура многозадачной ТЛСППР обеспечивает оперативное конфигурирование модулей системы при решении задач, относящихся к различным предметным областям.

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

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

В результате проведённых исследований достигнута цель работы: усовершенствованы процедуры поддержки принятия решений в логистических системах на основе геоинформационных технологий, разработано математическое и алгоритмическое обеспечения логистических СПГТР.

СПИСОК ПУБЛИКАЦИЙ Публикации в журналах, входящих в список рецензируемых изданий ВАК при Минобрнауки России

1. Кучер В.А., Макарян A.C. Оптимизационная математическая модель решения задачи автоматизированного планирования транспортного обеспечения в условиях чрезвычайной ситуации [Текст] / В.А.Кучер, А.С.Макарян // «Вестник адыгейского государственного университета». Издательство «АГУ» Технические науки.-2013.-Вып. 1(116).-Майкоп. 126.-С 100- 105.

Свидетельства о государственной регистрации программ для ЭВМ

2. Макарян A.C. «Информационно - аналитическая система планирования транспортного обеспечения в условиях ограниченных ресурсов. Модуль планирования и мониторинга транспортных колонн» [Текст] / В.С.Симанков, Т.Т.Зангиев, Т.А.Чурсина, А.С.Макарян; - № 2012619080; заявка № 2012616739. от 07.08.2012; зарегистрировано в реестре программ для ЭВМ 05.10.13.

3. Макарян A.C. «Информационно-аналитическая система планирования транспортного обеспечения в условиях ограниченных ресурсов. Модуль расчета и мониторинга мероприятий в условиях ограниченных ресурсов» [Текст] / В.С.Симанков, В.А.Кучер, Т.А.Чурсина, А.С.Макарян; -№ 2012619087; заявка № 2012616729. от 07.08.2012; зарегистрировано в реестре программ для ЭВМ 05.10.13.

4. Макарян A.C. «Информационно-аналитическая система планирования транспортного обеспечения в условиях ограниченных ресурсов. Модуль анализа и графической визуализации пространственных данных» [Текст] / В.С.Симанков, В.А.Кучер, Т.А.Чурсина, А.С.Макарян; - № 2012619086; заявка № 2012616728. от 07.08.2012; зарегистрировано в реестре программ для ЭВМ 05.10.13.

Статьи в научных журналах и материалы конференций

5. Макарян A.C. Имитационная модель системы поддержки принятия решений по транспортному обеспечению мероприятий в условиях ЧС [Текст] / В.А.Кучер, А.С.Макарян //Труды всероссийской конференции молодых ученых и студентов.

«Современное состояние и приоритеты развития фундаментальных наук в регионах» / Краснодар: ООО «Просвещение-ЮГ», 2011 - С. 176 - 178.

6. Макарян A.C. Математическая постановка задачи выбора альтернатив в СППР по транспортному обеспечению мероприятий в условиях чрезвычайной ситуации [Текст] / В.А.Кучер, А.С.Макарян // Труды всероссийской конференции молодых ученых и студентов. «Современное состояние и приоритеты развития фундаментальных наук в регионах»/Краснодар:000 «Просвещение-ЮГ»,2011-С. 178-180.

7. Макарян A.C. Повышение эффективности деятельности органов управления ГОИЧС за счет совершенствования взаимодействия систем оперативно — диспетчерского управления и повышения качества принятия решений [Текст] / В.А.Кучер, А.С.Макарян // «Сборник научных трудов студентов и аспирантов Института информационных технологий и безопасности» / Краснодар: ООО «Кубаньпечать», 2011 - С. 22 - 25.

8. Макарян A.C. Математическая постановка задачи выбора альтернатив в СППР по транспортному обеспечению мероприятий в условиях чрезвычайной ситуации [Текст] / В.А.Кучер, А.С.Макарян // Материалы Третьей международной научной конференции «TTC - 11»./ Краснодар: Филиал ВУНЦ ВВС «ВВЛ», 2011-С. 297-301.

9. Макарян A.C. О построении оптимальных маршрутов эвакуации в условиях ограничения ресурсов [Текст] / Т.Т.Зангиев, А.С.Макарян // «Перспективы развития информационных технологий». Сборник материалов 13 - ой международной научно - практической конференции. / Новосибирск: «СИБПРИНТ», 2013 - С. 15-19.

Подписано в печать 18.11.2013. Печать трафаретная. Формат 60x84 '/)б. Усл. печ. л. 1,35. Тираж 100 экз. Заказ № 1003. ООО «Издательский Дом-Юг» 350072, г. Краснодар, ул. Московская 2, корп. «В», оф. В-120 тел. 8-918-41-50-571 e-mail: olfoinenko@vandex.ru Сайт: http://id-yug.com

04201 455703

ФГБОУ ВПО «КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ»

У

правах рукописи

Макарян Александр Самвелович

СОВЕРШЕНСТВОВАНИЕ ПРОЦЕДУР ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ В ЛОГИСТИЧЕСКИХ СИСТЕМАХ НА ОСНОВЕ ГЕОИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

05.13.01 - Системный анализ, управление и обработка информации (информационные и технические системы) Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: кандидат технических наук, профессор Кучер В.А.

Краснодар - 2013

Сокращения

В диссертационной работе применены следующие сокращения:

ГИС - геоинформационная система;

СУБД - система управления базами данных;

Jill? - лицо, принимающее решение;

ТЛСППР - транспортная логистическая система поддержки принятия решений;

ЭС - экспертная система; БЗ - база знаний; ЗК - задача «коммивояжера»; ПО - программное обеспечение; ПК - программный комплекс; БД - база данных.

СОДЕРЖАНИЕ

Сокращения............................................................................................................................................................2

Введение..................................................................................................................................................................5

1 ОБОСНОВАНИЕ НЕОБХОДИМОСТИ РАЗРАБОТКИ ТРАНСПОРТНОЙ ЛОГИСТИЧЕСКОЙ СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ НА ОСНОВЕ ГЕОИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ..............................................................................................................................................10

1.1 Основные положения организации функционирования логистических систем..............................................................................................................................................................................................................10

1.2 Анализ правил, приемов и методов поддержки принятия логистических решений..................................................................................................................................................................14

1.2.1 Общая схема процесса поддержки принятия решений..............................15

1.2.2 Структурная схема СППР и классификация методов поддержки

принятия логистических решений............................................................................................18

1.3 Анализ методов оптимизации транспортных маршрутов в задачах логистики................................................................................................................................................................20

1.3.1 Постановка задачи «коммивояжера»..........................................................................20

1.3.2 Алгоритмы решения задачи «коммивояжера»..................................................21

1.4 Оценка эффективности методов оптимизации ..................................................................41

1.5 Анализ программных средств оптимизации и планирования логистических мероприятий................................................................................................................44

1.5.1 «БИТ: Управление транспортной логистикой»................................................45

1.5.2 SIGMA Transport Monitoring................................................................................................47

1.5.3 Система мониторинга транспортных средств «Навстат»..........................49

1.5.4 Система Qguar TMS....................................................................................................................49

1.5.5 Системы PSItms..............................................................................................................................51

1.5.6 «1С: Предприятие 8. Управление автотранспортом»....................................53

1.6 Анализ программного обеспечения геоинформационных систем........................54

1.7 Постановки задачи исследования......................................................................................................60

Выводы......................................................................................................................................................................61

2 РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ И АЛГОРИТМА ОПТИМИЗАЦИИ ПРОЕКТИРУЕМОЙ СИСТЕМЫ............................................63

2.1 Алгоритм поддержки принятия решений для управления транспортной

сетью в логистических системах..........................................................................................................63

2.1.1 Анализ электронной карты логистической сети и определение

проблемы............................................................................................................................................................66

2.1.2 Формулировка начальной и конечной точки процесса, а также

цели и предоставление сопроводительной информации........................................68

2.1.3 Определение множества ограничивающих факторов и критериев.. 70

2.1.4 Генерация множества решений по транспортному обеспечению.. 73

2.1.5 Анализ решений................................................................................................................................75

2.1.6 Формирование управляющего воздействия............................................................77

2.2 Разработка классификации задач логистических систем и методов

принятия решений на основе ГИС ................................................................................................83

2.3 Математическая модель принятия решения для управления логистической транспортной системой на основе двухфазного

модифицированного алгоритма решения задачи «коммивояжера»..................88

Выводы........................................................................................................................................................................97

3 СТРУКТУРА, СОСТАВ, АЛГОРИТМИЧЕСКАЯ И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ТРАНСПОРТНОЙ ЛОГИСТИЧЕСКОЙ СППР НА ОСНОВЕ ГИС..........................................................99

3.1 Общие принципы построения и функциональная схема ТЛСППР....................99

3.2 Язык разработки................................................................................................................................................107

3.3 Система управления базами данных и знаний........................................................................108

3.4 Геоинформационная система для отображения транспортной инфраструктуры и управления потоками....................................................................................111

3.5 Платформа для построения экспертного модуля системы..........................................ИЗ

3.6 Интерфейс функционирования системы....................................................................................116

Выводы........................................................................................................................................................................117

4 ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА РАЗРАБОТАННОГО ПРОГРАММНОГО И МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ............119

4.1 Результаты испытаний программного комплекса..............................................................119

4.2 Сравнение логистической системы с аналогами..................................................................123

4.3 Оценка эффективности использования транспортной логистической

системы поддержки принятия решений......................................................................................127

Выводы........................................................................................................................................................................132

Заключение............................................................................................................................................................134

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

Приложение А......................................................................................................................................................152

Приложение Б......................................................................................................................................................153

Приложение В......................................................................................................................................................154

Приложение Г......................................................................................................................................................155

Приложение Д......................................................................................................................................................156

ВВЕДЕНИЕ

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

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

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

б) аналитическое сопровождение штатных процессов логистики докладов;

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

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

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

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

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

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

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

6

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

Объектом исследования является система поддержки принятия решений для задач транспортной логистики.

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

Целью исследования является совершенствование методов и алгоритмов поддержки принятия решений логистических систем на основе геоинформационных технологий для различного класса задач.

Задачи исследования:

1. Анализ существующих методов решения задач транспортной логистики.

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

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

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

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

6. Оценка эффективности разработанных моделей, алгоритмов и программного обеспечения.

Методы исследования

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

Научная новизна работы

В результате проведенного в работе системного исследования получены следующие новые научные результаты:

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

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

3. Разработан алгоритм двухфазной оптимизации для управления транспортной логистической системой.

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

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

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

Практическая значимость

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

логистической системы поддержки принятия решений на основе геоинформационных технологий.

Основные положения, выносимые на защиту

К основным положениям, выносимым на защиту, относятся:

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

2. Принципы построения и структура транспортной логистической системы поддержки принятия решений на основе геоинформационных технологий.

3. Алгоритмическая реализация основных методов и этапов поддержки принятия решений для управления функционированием транспортной логистической системы на основе геоинформационных технологий.

4. Алгоритм двухфазной оптимизации транспортной логистической системы.

5. Программное обеспечение транспортной логистической системы поддержки принятия решений на основе геоинформационных технологий.

Структура и объем работы.

Работа состоит из введения, 4-х глав, заключения, приложений и содержит 164 страницы, 31 рис., 13 табл., список литературы из 156 названия.

1. ОБОСНОВАНИЕ НЕОБХОДИМОСТИ РАЗРАБОТКИ ТРАНСПОРТНОЙ ЛОГИСТИЧЕСКОЙ СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ НА ОСНОВЕ ГЕОИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

1.1 Основные положения организации функционирования

логистических систем

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

Рисунок 1.1.1- Схема логистической системы

Элементом логистической системы является информационная логистическая система [1, 57 - 61] как организованная совокупность взаимосвязанных средств вычислительной техники, средств программирования, алгоритмов и моделей, обеспечивающая решение различных логистических задач.

Логистические информационные системы можно разделить на две основные группы по уровням: микроуровень и макроуровень (рисунок 1.1.2 ).

г .______________

Логистические i информационные

системы

Информационные системы на микроуровне (предприятия, организации и т.д.)

¡¡РИИШИ^^Ш!!.

Плановые системы

Диспозитивные системы (диспетчеры)

Информационные системы на макроуровне (регион, страна и т.д.)

Исполнительные системы

Рисунок 1.1.2 - Логистические информационные системы

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

- MRP - Materials Requirements Planning (планирование потребности в материалах) - система планирования потребностей в материалах; эта логистическая система - одна из самых популярных в мире. В России концепцию представляют различные программные продукты иностранного производства. Но развитие и появление более успешных концепций построения систем привело к тому, что программные продукты класса MRP можно встретить очень редко, например, в составе устаревших информационных систем предприятий и учреждений.

- DRP - Distribution Requirements Planning (