Разработка и исследование динамической геоинформационной модели цепей поставок Савельева Марина Николаевна

Содержание к диссертации

Введение

1. Информационное моделирование цепей поставок 10

1.1. Структура и функции цепи поставок 10

1.2. Анализ и классификация геоинформационных моделей для поддержки принятия решений 18

1.3. Анализ информационных моделей для управления цепями поставок 30

1.4. Описание динамической геоинформационной модели цепей поставки 37

Выводы по разделу 1 и определение задач исследования 41

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

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

2.2. Процедурная модель маршрутизации при наличии темпоральных зависимостей с четкими параметрами 60

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

2.2.2. Пример реализации процедурной модели маршрутизации при условии задания всех параметров в четком виде 66

2.2.3. Оценка эффективности алгоритма маршрутизации с темпоральной зависимостью 73

2.3. Процедурная модель маршрутизации при нечетко заданном расстоянии с темпоральной зависимостью 74

2.3.1. Разработка процедурной модели маршрутизации при нечетко заданном расстоянии с темпоральной зависимостью 74

2.3.2. Пример реализации процедурной модели маршрутизации при нечетко заданном расстоянии с темпоральной зависимостью 83

2.4. Процедурная модель маршрутизации при нечетко заданном расстоянии и времени 92

2.4.1. Разработка процедурной модели маршрутизации при нечетко заданном расстоянии и времени 92

2.4.2. Пример реализации процедурной модели маршрутизации при нечетко заданном расстоянии и времени 104

Выводы по разделу 2 108

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

3.1. Особенности представления опыта наблюдения информационных потоков при

маршрутизации в динамической геоинформационной модели цепей поставок 110

3.2. Анализ особого метода описания опыта в виде образа необходимого для принятия решений в цепях поставок 119

3.3. Процедурная модель конструирования маршрутов динамической геоинформационной модели с использованием прецедентного анализа 126

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

Вывод по разделу 3 135

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

4.1. Постановка задачи 136

4.2. Описание реализации 137

4.3. Результаты эксперимента 144

Выводы по разделу 4 158

Заключение 159

Cписок литературы 161

• Анализ информационных моделей для управления цепями поставок
• Процедурная модель маршрутизации при наличии темпоральных зависимостей с четкими параметрами
• Пример реализации процедурной модели маршрутизации при нечетко заданном расстоянии и времени
• Процедурная модель конструирования маршрутов динамической геоинформационной модели с использованием прецедентного анализа

Введение к работе

Актуальность темы исследования.

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

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

В диссертационной работе поставленная задача решается разработкой новых концептуальных, информационных и процедурных моделей, использующих неполные, нечеткие пространственные, временные и семантические данные о состоянии цепи поставок. О практической значимости проблемы свидетельствует то, что в настоящее время разрабатываются и выпускаются программные продукты, которые реализуют ряд важных информационных моделей представления цепей поставок. К таковым относятся ERP-системы, APS-системы, SCEM-системы, а также геоинформационные системы и сервисы ArcGIS, AutoCad Map, MapInfo, Яндекс.Карты, Google.Maps, 2GIS, и другие.

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

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

К основным трудам в области управления цепями поставок относятся работы Кристофера М., Уотерса Д., Лукинского В.С., Иванова Д.А. В области разработки и применения геоинформационных систем и технологий – работы Бондура В.Г., Иванникова А.Д., Тикунова В.С., Берлянта А.М., Цветкова В.Я., и многих других. В области интеллектуальных систем – работы Поспелова Д.С., Осипова Г.С., Гавриловой Т.А., в области теории графов и нечетких множеств – работы Заде Л., Беллмана Р., Кристофидеса Н., Майника Э., Саати Т., Свами М., Берштейна Л.С., а также ряда других отечественных и зарубежных исследователей.

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

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

Для достижения поставленной цели решаются следующие задачи:

Построения обобщенной динамической геоинформационной модели для управления цепями поставок;

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

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

Объект исследования – информационные процессы управления в цепи поставок.

Предмет исследования – динамическая геоинформационная модель цепей поставок.

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

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

Научная новизна диссертационной работы:

1. Формальная динамическая геоинформационная модель цепи поставок. В отличие от известных модель включает в себя картографическое описание последовательностей операций цепи поставок и их изменчивости. Использование модели повышает достоверность принятия решений в условиях динамики внешней среды (п.3 паспорта специальности 05.25.05).

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

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

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

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

5. Формальная динамическая геоинформационная модель для управления цепями поставок;

6. Процедурная модель маршрутизации в темпоральных транспортных сетях цепей поставок;

7. Процедурные модели маршрутизации с нечеткими темпоральными зависимостями параметров;

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

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

тивного и долгосрочного планирования поставок, страхования от неблагоприятных природных и техногенных условий, и ряд других.

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в работе организаций ООО КС «Строитель-Юг», ООО «Элефант» и ООО «Центр комплексных систем безопасности», что подтверждается актами о внедрении.

Результаты диссертационной работы были использованы при выполнении грантов РФФИ: проект № 11-01-00011a «Решение оптимизационных задач в транспортных сетях в условиях нечеткости и частичной неопределенности», проект № 12-01-00032-а «Разработка принципов создания интеллектуальных геоинформационных систем для оптимизации поставок на основе нечётких темпоральных сетевых моделей», проект № 13-07-13103 офи_м_РЖД «Методы и средства образного представления знаний для принятия решений с использованием геоинформационных систем».

Апробация основных теоретических и практических результатов работы докладывались и обсуждались на научно-практических конференциях: VII Ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН (Ростов-на-Дону, 2011 г.); IX Всероссийская научная конференция молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2011 г.); 19^th East-West Zittau Fuzzy Colloquium (Циттау, Германия, 2012 г.); 19^th International Conference on Soft Computing “MENDEL 2013” (Брно, Чехия, 2013 г.); 20^th East-West Zittau Fuzzy Colloquium (Циттау, Германия, 2013 г.); II международный Поспеловский симпозиум ГИСИС’2014 «Гибридные и синергетические интеллектуальные системы» (Светлогорск, 2014); 12th IEEE International Conference on Industrial Informatics “INDIN 2014” (Порту-Алегри, Бразилия, 2014); IEEE INTELLIGENT SYSTEM’2014 (Варшава, Польша, 2014).

Публикации. Основные результаты диссертационного исследования отражены в 6 статьях, опубликованных в ведущих научных журналах и изданиях, рекомендованных ВАК Министерства образования и науки РФ, в 4 статьях, опубликованных в международных базах цитирования, 2 свидетельствах об официальной регистрации программ. Всего по теме диссертации имеется 19 публикаций.

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы. Основное содержание работы изложено на 171 страницах, содержит 48 рисунков, 13 таблиц, список литературы состоит из 124 наименования. В приложениях содержатся: программный код, реализующие решение проблемы маршрутизации с использованием прецедентного анализа; карты построенных маршрутов, использованных для экспериментального анализа; свидетельства о государственной регистрации программы для ЭВМ.

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

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

Данный класс моделей отражает исключительно визуализацию картографической информации с помощью растровых изображений или снимков. Примером является геоинформационная система ArcGIS Online (рисунок 1.4) [72-73]. Пользователь выбирает требуемый вид карт и производит поиск необходимых данных по наименованию карты, на основании которых производится принятие управленческих или производственных решений. Достоинством такого класса моделей является простота. Геоинформационные модели первого типа реализуются информационными системами различного назначения, не требуя специализированного программного обеспечения. Недостатками являются отсутствие встроенного анализа геопространственной информации, необходимость самостоятельного принятия решения. Данные недостатки усложняют процесс оперативного принятия решения.

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

Геоинформационные модели второго типа формально описываются следующим образом: где W2 - геоинформационная модель 2-го типа; а - множество картографических объектов и отношений; Q - набор процедур управления картографическим изображением; А - семантические атрибуты объекта или отношения; щ - картографический объект или отношение. Рисунок 1.6 – Иллюстрация геоинформационной системы ERDAS IMAGINE Данный класс моделей использует растровое и векторное представление картографических объектов и обладает процедурами их создания и редактирования. Особенностью модели является наличие процедур визуализации геопространственной информации, с помощью которых реализуется геопространственный анализ данных. Основа анализа – поиск объектов по заданным атрибутам и просмотр атрибутов выбранного объекта.

Примером использования подобного рода моделей выступают геоинформационные системы ERDAS IMAGINE (рисунок 1.6) [74], QGIS Desktop (рисунок 1.7) [75] и ProGIS [76] (рисунок 1.8). ERDAS IMAGINE обрабатывает растровую информацию. QGIS Desktop – это геоинформационная система с открытым кодом, обрабатывающая векторные данные. Достоинством этого типа моделей является наличие картографических объектов и отношений. Недостатками является то, что картографические объекты и отношения статичны и их атрибуты не отражают временных зависимостей. Данный класс геоинформационных систем из-за имеющихся недостатков не позволяется оперативно принимать решения.

Структурная схема геоинформационной системы, использующих данный класс моделей, представлена на рисунке 1.9. Отличительной ее особенностью является появление подсистемы диалога с пользователем, которая позволяет реализовать пространственный анализ через инструменты визуального управления Рисунок 1.7 – Иллюстрация геоинформационной системы QGIS Desktop изображением. Компонент работы с данными возникает ввиду усложнения

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

Алгоритм Эдмодса-Карпа [11,105] находит максимальный поток в транспортной сети. Является модификацией алгоритма Форда-Фалкерсона, но для решения этой проблемы используется построение дополняющего кратчайшего пути, но подразумевается, что путь единичной длины, поэтому применяется алгоритм поиска в ширину. Несмотря на то, что производится построение кратчайшего маршрута, но основной задачей этого алгоритма является получение максимального потока, следовательно, для решения нашей проблемы этот алгоритм не является приемлемым.

Генетический алгоритм

Генетический алгоритм [11,25-26,106] принадлежит к разновидности эвристических алгоритмов и решает задачи различного вида поиска, а также оптимизации, может находить как точные, так и приблизительные решения. Процесс моделирования определяется при помощи стохастических выбора, сопоставления и существования (создания) различных вариантов набора данных, основанных на естественном отборе. При использовании подобного рода алгоритмов решается оптимизации задачи при помощи таких природных процессов таких как наследование, мутация, отбор и кроссинговер. Отличительной чертой является процедура скрещивания, после чего и производятся все остальные процессы. Генетический алгоритм может решать огромное количество задач, одной из которых является построение кратчайшего пути [106]. Для того чтобы данный алгоритм давал хорошие результаты необходимо правильно определить целевую функцию для особей популяции и составить начальную популяцию.

Основными этапами при решении задачи является: инициализация популяции, выбор фитнесс-функции и оценка для каждой особи популяции, выбор лучших особей для воспроизведения, создание нового поколения с помощью кроссовера или мутации и рождение потомства, замена худшей части населения потомками, повторение этого процесса до достижения условия прекращения алгоритма. Решение задачи поиска кратчайшего маршрута показано в [106] и [107]. Только первый вариант ищет минимальный маршрут базируясь на параметре времени, а во втором случае, производится поиск минимального пути на основе основного дерева.

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

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

Муравьиный алгоритм

Муравьиный алгоритм [27-28] – это полиномиальный эвристический алгоритм решения оптимизационных задач. Давно применяется для решения задач на графах: задача коммивояжера, задача оптимизации движения грузовиков, задача раскраски графа и т.д. Данный алгоритм основан на имитации поведения муравьев, которые прокладывают путь от своего местонахождения к источнику питания. Основывается на том, что первый муравей прокладывает маршрут случайный образом, оставляя за собой след из феромонов, также случайный образом возвращается назад. Феромоны со временем выветриваются, поэтому чем больше муравью требуется времени для прохождения по маршруту, тем запах меньше, и, следовательно, следующие муравьи пойдут по тому пути, где запах феромонов более ярко выраженный, при этом каждый муравей, который проходит, оставляет также после себя след из феромонов. Важными моментами при реализации муравьиного алгоритма является количество муравьев, которое необходимо для прохождения по маршруту, равновесие между моментами обучения и непосредственного применения алгоритма, а также определение момента времени обновления феромона.

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

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

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

Пример реализации процедурной модели маршрутизации при нечетко заданном расстоянии и времени

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

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

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

Проблемы, возникающие при управлении цепью поставок, являются сложными, а их решения неоднозначными. Одной из главных проблем является маршрутизация. Поэтому из-за изменчивости, неопределенности условий транспортировки груза целесообразным способом является использование моделей адаптивной маршрутизации, ориентированных на знания. В этом направлении предлагались различные подходы, определяемые источником и формой представления знаний [41-43,117-119]. Но непосредственное применение невозможно.

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

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

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

На рисунке 3.2 приведен пример визуализации образа. Проиллюстрировано три независимые базы данных: о пространственной ситуации - информация о расположении элементов транспортной сети (Nk), о временной ситуации -информация о положении временных интервалов (Atk) и о семантической ситуации - информация о загруженности транспортной сети (vk). Элементы образа связаны ссылками. Наличие системы визуализации образов ситуаций играет решающую роль в адаптации системы в целом. Именно здесь обеспечивается необходимое качество знаний - полнота, непротиворечивость, отсутствие избыточности,

Далее предполагают, что в близких ситуациях применимы похожие решения и соответственным образом конструируют новое решение. Подобный механизм обладает недостатком: наблюдаемые ситуации фиксируются как точки признакового пространства А, а достоверность оценки их близости определяется исключительно логикой реализации метрики (по формуле (3.1)). В системах гибридного интеллекта имеется возможность повышать достоверность оценки близости ситуаций за счет расширения опытных знаний. Ситуации представляются не точками, а областями признакового пространства А [44]. Проиллюстрируем это на примере (рисунок 3.3 и 3.4). Пусть ситуации Sa,SblSc имеют временную привязку (рисунок 3.3). Очевидно, что по расстоянию на временной оси ситуации (Sb,Sc) более близки, чем (Sa Sb). Однако, предположим, что эксперт описал возможные отклонения временной привязки, которые возможны в реальности и при этом не меняют сути ситуаций. Этим отклонениям соответствуют области, показанные на рисунке 3.4. Близость ситуаций в таком случае отображается как степень перекрытия областей. Можно видеть, что (Sa, Sb) при таком подходе более близки, чем (Sb,Sc). Достоверность оценки близости повышается благодаря активности эксперта и расширению знаний о каждой ситуации.

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

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

Исходными данными для экспериментальной оценки является начальные и конечные пункты для построения множества из N маршрутов. Все пункты расположены в г. Ростове-на-Дону. Все разрабатываемые маршруты имеют расстояние [5 км; 22 км]. Также исходными данными являются N построенных маршрутов в геоинформационных сервисах: Google.Maps, 2GIS, Mail.Карты, Yandex.Карты. Основополагающим условием для каждого способа построения является стартовое время, которое для i-го маршрута из множества N является одинаковым.

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

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

Вероятность возникновения риска (в %) 0 - 20 21 - 40 41 - 60 61 - 80 81 - 100 Значение коэффициента риска (ri) 1 2 3 4 5 В соответствии с таким представлением о риске был рассмотрен каждый маршрут. По итогам анализа эксперта были сформированы таблицы с уровнем риска каждого маршрута R (Таблица 4.2 - 4.6). Уровень риска маршрута R лежит в интервале [0,2; 1].

Уровень риска R определяется по следующей формуле: R=tr5 i=l где at - доля маршрута, соответствующая определенному коэффициенту риска Если существует участок маршрута, который не определен экспертом, то он относится к коэффициенту с самым низким уровнем, а именно к г і. по построенному по разработанной модели маршруту.

На основании описанных в разделе 4.1 и 4.2 исходных данных и методики поведения были получены следующие данные и анализ их эффективности по параметру расстояние (по формуле 4.1), параметру время (по формуле 4.2), представленные в таблице 4.7. Вследствие получено следующие графические изображения (рисунок 4.3 и рисунок 4.4), отображающие разброс данных по расстоянию и времени на основании геоинформационных сервисов относительно усредненного маршрута и разработанного маршрута.

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

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

Количество произведенных измерений п = 22. Рассматриваемые данные являются не сгруппированной выборкой, поэтому частота их появления В = 1. Для расчета необходимо определить среднее значение относительной погрешности X и среднеквадратичное отклонение 5: Х = = 6,933,5= — = 6,343. п J п — 1 Для расчета функции нормального распределения необходимо определить коэффициент п К = - 2 = 6,936 Остальные данные и расчеты представлены в таблице 4.10. Таким образом, определено -распределение Х2 = 20,265. По таблице « -распределение (доверительные границы)» [58] Хо,05 = 32 67 для 5% при числе степеней свободы к = п — 1 = 21. Так как х2 Хо,о5, это означает, что принимается нулевая гипотеза, то есть выборка принадлежит нормальному распределение, следовательно, полученное решение по параметру расстояние не является случайным.

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

Количество произведенных измерений п = 22. Рассматриваемые данные являются не сгруппированной выборкой, поэтому частота их появления В = 1. Для расчета необходимо определить среднее значение относительной погрешности X и среднеквадратичное отклонение

Остальные данные и расчеты представлены в таблице 4.11. Таким образом, определено -распределение /2 = 14,43. По таблице « -распределение (доверительные границы)» [58] Хо,05 = 32 67 для 5% при числе степеней свободы к = п — 1 = 21. Так как х2 Хо,о5, это означает, что принимается нулевая гипотеза, то есть выборка принадлежит нормальному распределение, следовательно, полученное решение по параметру время не является случайным.

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

Количество произведенных измерений п = 22. Рассматриваемые данные являются не сгруппированной выборкой, поэтому частота их появления В = 1. Для расчета необходимо определить среднее значение относительной погрешности X и среднеквадратичное отклонение 5: