автореферат диссертации по документальной информации, 05.25.05, диссертация на тему:Разработка и исследование динамической геоинформационной модели цепей поставок

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

Савельева Марина Николаевна

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ДИНАМИЧЕСКОЙ ГЕОИНФОРМАЦИОННОЙ МОДЕЛИ ЦЕПЕЙ ПОСТАВОК

Специальность: 05.25.05 - Информационные системы и процессы

АВТОРЕФЕРАТ 4 0КТ 2015

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

Таганрог -2015

005563202

005563202

Работа выполнена в ФГАОУ ВО «Южный федеральный университет» Научный руководи- Беляков Станислав Леонидович,

тель: доктор технических наук, профессор, ФГАОУ ВО «Южный

федеральный университет», кафедра информационно-аналитических систем безопасности, профессор Официальные оппо- Карелин Владимир Петрович,

ненты: доктор технических наук, профессор, НОУ ВПО Таганрог-

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

Кобак Валерий Григорьевич,

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

Ведущая организация: ФГБОУ ВПО «Ростовский государственный университет путей сообщения», г. Ростов-на-Дону

Защита состоится «25» декабря 2015 г. в 14.00 на заседании диссертационного совета Д 212.208.25 при Южном федеральном университете по адресу: 347928, г. Таганрог, ул. Чехова, 2, ауд. И-409.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344103, г. Ростов-на-Дону, ул. Зорге, 21 Ж.

Диссертация в электронном виде доступна по адресу: http://hub.sfedu.ru/diss/announcement/

Автореферат разослан «02» октября 2015 г.

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

Брюхомицкий Ю.А.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предмет исследования - динамическая гепинфпрмяттгшняя мппрт. тт<»прй поставок.

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

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

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

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

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

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

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

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

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

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

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

4. Концептуальная модель образного прецедентного анализа.

Практическая значимость работы заключается в прикладном характере

разработанных информационных и процедурных моделей. На их основе могут

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

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

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

Апробация основных теоретических и практических результатов работы докладывались и обсуждались на научно-практических крнференциях:. VII Ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН (Ростов-на-Дону, 2011 г.); IX Всероссийская научная конференция молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2011 г.); 19th East-West Zittau Fuzzy Colloquium (Циттау, Германия, 2012 г.); 19th International Conference on Soft Computing "MENDEL 2013" (Брно, Чехия, 2013 г.); 20th 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 наименования. В приложениях содержатся: программный код, реализующие решение проблемы маршрутизации с использованием прецедентного анализа; карты построенных маршрутов, Использован-

ных для экспериментального анализа; свидетельства о государственной регистрации программы для ЭВМ.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы диссертационного исследования, представлены цели и задачи диссертации, используемые методы исследования, научная новизна, достоверность, теоретическая и практическая ценность исследования, сведения о реализации работы, апробации результатов, публикациях и структуре диссертации.

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

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

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

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

У/0 =< М,П,Д,() >,где М — представление цепи поставок в виде логистической сети; П — множество картографических объектов и пространственных отношений картографической базы данных геоинформационной системы; Я — привязка логистической сети к картографической основе, т.е. М х П -» Я,

Q = Qт^ Q^^} — набор процедур оценки показателей качества цепи поставки. Здесь (¿Р — затраты на выполнение запланированных поставок; (}т — время необходимое для выполнение запланированных поставок; — риск выполнения запланированных поставок; — затраты на модификацию цепи поставок из-за изменения внешних условий.

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

щСХЮ.Т.АСф е П,1 = 17п где и>1 — картографический объект или отношение; Х(Ь) - параметры пространственной привязки; Т — параметры временной привязки; — семантические атрибуты.

Таким образом, £ = Р (*(£), Г, Л (С)).

Рисунок 1 — Информационные модели цепей поставок, включающие динамическую геоинформационную модель Логистическую сеть, представляющую цепь поставки, предлагается описывать следующим образом:

М =< А, В,Л, Г, Т >, где. А — {Аг, Л1,0[, т/4}, £ = 1, п - это множество узлов (вершин) преобразования материального потока, в которых выполняются разнообразные логистические операции и, без совершения которых невозможна .транспортировка. {Аг}, £ = 1, п, - узел преобразования материального потока. Л1 = {Л}} Ф 0,1 — 1 ,п,_/ = 1,тп- подмножество логистических операций, совершаемых в узле преобразования материального потока А1 (возможно присутствиенескольких логистических операций в одном узле преобразования материального потока). В каждом узле преобразования материального потока су: ществует хотя бы одна логистическая операция: Одна й та же логистическая операция может выполняться несколько раз в узле преобразования маТериаль-'-ного потока. • .■--чV ■:;■■ • ......

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

{0^}, 1, п - свойства материального потока в узле Аг, которые изменятся после выполнения операций.

{т/4}» I = 1, я — общее время необходимое для выполнения всего подмножества логистических операций в узле А^.

В = {Ви„, Рии, Пии, и = 1,71,17 = 1,п- множество связей (дуг) между узлами преобразования материального потока. Каждая из связей представляет собой участок транспортной сети. Участок может быть самостоятельной сетью. На участке реализован какой-либо алгоритм маршрутизации. Алгоритм может не совпадать с алгоритмом, применяемым для всей сети.

{В иг}< и — 1, п, V — 1, п — дуга между узлами преобразования материального потока, где и, V — концевые узлы дуги из множества {Аг}, концевые узлы дуги не могут совпадать.

_ Ц А„, V = А„; Аи,А„ 6 А^; Аи Ф- А„.

{Ри„}, и = 1, п, V = 1, п - расстояние между узлами преобразования материального потока.

№ шЛ» и — 1,п,1> — 1,п — пропускная способность сети между узлами преобразования материального потока.

{Тцу}, и = 1, п, V = 1,71 - время, затрачиваемое для прохождения по дуге Ви„.

Л = {Л,},/ = 1,7п - множество логистических операций, используемых в динамической геоинформационной модели управления цепями поставок.

Т = {Тк}, к = 0,1- интервалы постоянства весов дуг.

ТкпТк+1 = 0,к = 0,1-1

Г = {Г5, Г'} - множество пространственных объектов геоинформационной модели.

{Г5} — подмножество статических пространственных объектов, не зависящие от времени.

{Г£} — подмножество динамических пространственных объектов, т.е. объектов, изменяющих свои атрибуты со временем.

Г5 П Г* = 0

Статические объекты не переходят в множество динамических объектов.

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

Проблема маршрутизации представлена следующим образом:

Необходимо найти кратчайший путь Ь из начальной точки 5 (источник) до конечной точки г (сток), используя дополнительный параметр - время.

1* = X; >), (ВД/< Хи X; >.), (ВД < Х],г >)}

где #(?) - расстояние между пунктами назначения при управлении цепью поставок.

Существуют дуги, которые отсутствуют в некоторый период времени (используется понятие «отсутствия дуги» означающее, что значение веса дуги в рассматриваемый момент времени стремится к бесконечности). Дуги являются нечеткими величинами. Время - дискретна^ величина, период времени прохождения по каждой дуге представлен в нечетком виде. Под периодом времени 7}, где у = 0, те, понимается временной интервал, который задает пользователь. Также пользователем задается количество временных периодов, определяемое множеством

_т = {То.П.....тт} = {7}в>7),7)г}

где = 0,771 — 1 - время отправления из начальной точки; {Ту},/' ='

1,771 — 1 - время движения, без учета времени отправление и прибытия; {Т,гцг = 1, т - время прибытия в пункт назначения.

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

где щ = (щ, ат, ау) - вес (длина) дуги нечеткого темпорального графа; ?г = \.Ч> ¿т> ~ время прохождения по дуге нечеткого темпорального графа, представленное в виде треугольного нечеткого числа; = [£0г, £0т(, £0т/, £:0/] -время отсутствия дуги нечеткого темпорального графа (длина дуги равна оо), представленное в виде трапециевидного нечеткого числа.

(а) (аь ат, <*/)[и, ¡т, Дй/, ¡0т1, (0т/, t0f ]-»К^В^)

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

Ситуация №1. Процедурная модель маршрутизации с-темпоральной зависимостью при заданном стартовом времени..

■ Шаг 1. Определено; что исходный нечеткий темпоральный граф на начальном этапегне зависит от времени. Находим для этого графа кратчайший путь Ь*. На начальном этапе все вершины и дуги графа не окрашены.,. .

Шаг 2; Всем вершинам в результате выполнения алгоритма происходит при-сваивание.нечеткого числа.а!(д^), равного длине кратчайшего пути из 5 в хь которое включает в себя только окрашенные вершины.

• Решено, что <?($) = 0 и &{х{) = <х> для всех хь отличных от у. Окрашиваем вершину 5 и принимаем у = 5 (у - последняя из окрашенных вершин).

Шаг 3. Пересчитываем величину для всех неокрашенных вершин X; следующим образом:

Л(*() = тт{5(хг), а(у) + а(у, х£)} (1) где а(у, XI) - длина дуги (у, хг).

Сравнение значений нечетких чисел производится, используя индекс центра тяжести нечеткого числа. Если для всех неокрашенных вершин х1 ¿0с£) = оо, то необходимо закончить выполнение алгоритма и полагать, что в исходном графе нет путей из 5 в неокрашенные вершины. В противном случае, произвести окрашивание той из вершин Х(, для которой значение величины а!(х;) является минимальным. И при этом еще пометить дугу, которая ведет в выбранную на дан. ном шаге вершину (для данной дуги получен минимум согласно выражению (1)). Принятьу= XI.

Шаг 4. Если у = г, прекратить процедуру: кратчайший путь V из вершины 5 в г, не учитывая параметр времени, определен. В противном случае перейти к шагу 3.

Шаг 5. Перейти к поиску кратчайшего пути на нечетком темпоральном графе, в котором дуги отсутствуют в определенные периоды времени. Для этого необходимо поэтапно строить граф, представляя его в статическом виде. Первоначально происходит построение кратчайшего пути V, полученного на шаге 4, который начинается в период времени = 0,т — 1,т - определяет

пользователь. При построении дуг осуществляется проверка их существования. Если дуга существует, то на первом этапе с начального времени {7}},/ = 0,т начинается движение и определяется время прохождения по дуге, которое будет составлять:

= Т,г + Цу.хЦ

где ?(*() - общее время прохождения до вершины дг£; 1(у,х{) - время прохождения по дуге.

На последующих этапах время определяется по следующей формуле: г(х1) = 1(у) + 1(у,х1) (2)

где 1{у) — общее время прохождения до вершины у.

Если же дуга не существует в рассматриваемый момент, то прекращаем проверку и переходим к следующему шагу.

Шаг 6. Начальная вершина 5 принадлежит периоду времени =

0,т — 1. Как указано на шаге 3, найти новое значение д.(х[) по формуле (1) и произвести проверку на существование дуги (у, х{) по параметру времени, следующим образом:

0 01 • Чти £фт/' ¿0/) £ (^1-¿12) и ({т1< ¿тг) и 0/1» */г) (3)

где (t01, t0mi, t0mf, Î0f) - нечеткое значение времени отсутствия дуги; tn - левый параметр нечеткого значения времени, принадлежащий началу рассматриваемой дуги; tI2 - левый параметр нечеткого значения времени, принадлежащий концу рассматриваемой дуги; tml - серединный параметр нечеткого значения времени, принадлежащий началу рассматриваемой дуги; tm2 - серединный параметр нечеткого значения времени, принадлежащий концу рассматриваемой дуги; tfi — правый параметр нечеткого значения времени, принадлежащий началу рассматриваемой дуги; tf2 - правый параметр нечеткого значения времени, принадлежащий концу дуги.

Если (3) не выполняется, следовательно, дуга (у, xi) существует в рассматриваемый период, то окрашиваем вершину хь наращиваем 7) = 7) на t(y, xi) по формуле (2) и принимаем Xi =у. Если выражение (3) выполняется, то дуга (у, отсутствует в данный период времени, следовательно, она не рассматривается и выбирается другая минимальная вершина. Если нет других дуг, то алгоритм не имеет решения при заданных условиях. Если все же необходимо найти какое-либо решение, то стартовый период js увеличивается на 1 и переход к шагу 5.

Шаг 7. Если у = г, закончить процедуру: кратчайший путь L* из вершины s в г найден. В противном случае перейти к шагу 6.

Шаг 8. Дефаззификация полученных кратчайших маршрутов.

Шаг 9. Просматриваются все кратчайшие пути из множества L = {Li, L2,..., Ln}, время отправления которых равно 7}*. Из данного множества кратчайших маршрутов выбирается минимальный маршрут после дефаззификации, т.е.

U = mintLi.Lz,...,^}

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

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

Шаг 11. Если оказывается, что существует несколько одинаковых маршрутов, то

1г (T/s) = L2(T/s) =...= Ln (Т?)

tnin = min{t (¿1(7};)), t (l2(t};)).....t (Ln(7};))} => i4w)'

где t = t(r) —Tjs- время прохождения маршрута из начального пункта в пункт назначения. Искомый путь L* найден.

Ситуация №2. Процедурная модель маршрутизации с темпоральной зависимостью и заданным временем прибытия.

Шаг 1—6 совпадает с ситуацией 1

Шаг 7. Если у = г, закончить процедуру: кратчайший путь V из вершины s в г найден. В противном случае перейти к шагу 6.

Шаг 8. Сравнить стартовое время 7}s с заданным пользователем временем прибытия в пункт назначения 7}*. Если TJs = 7}*, то закончить поиск маршрута

и перейти к шагу 9. Если 7}5 < 7}*, то начальный период 7} увеличивается на 1 и переход к шагу 5. Если Т^ > 7}*, то кратчайшего пути, в заданный начальный период времени не существует.

Шаг 9. Дефаззифицировать полученные кратчайшие маршруты. Шаг 10. Просматриваются все кратчайшие пути из множества/^ = /X/, ¿2,..., Ьп}, время прибытия которых равно 7}*. Из данного множества кратчайших маршрутов выбирается минимальный маршрут после дефаззификации, т.е.

V = шш {111121:.,1п} Подобное множество кратчайших маршрутов вознррикает из-за нечеткости начальных данных.

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

Шаг 12. Если оказывается, что существует несколько одинаковых маршрутов, то

ьЛт/г) = ^(т};) =...=ьп(т;г) _

СШп = тт{С (^(7);)), с (¿2(?};)).....I (¿п(7};))} >

где Ь = Т]г — {(г) — время прохождения маршрута из начального пункта в пункт назначения. Искомый путь V найден.

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

Шаг 1 - 4 совпадает с ситуацией 1.

Шаг 5. На основании полученного кратчайшего пути ¿'определить расчетное время £*, поэтапно суммируя дуги по параметру времени, не учитывая параметр времени, когда дуга отсутствует. Рассчитанное время будет минимально возможным временем передвижения

Шаг 6. Параметр С* дефаззифицировать, в результате получаем параметр Шаг 7. Сравнить полученный параметр С* с интервалом задаваемым пользователем. Если V < тогда переходим к шагу 8. Если С* > окончить выполнение алгоритма, данный алгоритм решения не имеет. Необходимо задать другой интервал.

Шаг 8. Перейти к поиску кратчайшего пути на нечетком темпоральном графе, в котором дуги отсутствуют в определенные периоды времени. Для этого • необходимо поэтапно строить граф, представляя его в статическом виде. Первоначально происходит построение кратчайшего пути V, полученного на шаге 4, который начинается в период времени {7)5},у5 = 0,т— 1 ,т - определяет пользователь. При построении дуг осуществляется проверка их существования. Если дуга существует, то на первом этапе с начального времени {7у}(/ = 0,т начинается движение и определяется время прохождения по дуге, которое будет составлять:

Í(*¡) = Th + i(y,Xi) где t(x¿) - общее время прохождения до вершины x¿; t(y, x¿) — время прохождения по дуге.

На последующих этапах время определяется по формуле (2).

Если же дуга не существует в рассматриваемый момент, то прекращаем проверку и переходим к шагу 9.

Шаг 9 соответствует Шагу 6 в ситуации 1.

Шаг 10. Если jy = г, закончить процедуру: кратчайший путь L* из вершины s в г найден. В противном случае перейти к шагу 9.

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

i = i(r)-TJs

Шаг 12. Дефаззифицировать полученное значение t на шаге 9.

Шаг 13. Если tu < t (где - время прохождения маршрута, заданное пользователем), то перейти к шагу 14. Если > t, то при найденных начальных и конечных условиях, нет решения, поэтому необходимо стартовый период js увеличивается на 1 и переход к шагу 8.

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

Шаг 15. Просматриваются все кратчайшие пути из множестваL = {L¡, L¡,..., Ln}, интервал прохождения которых равен Из данного множества кратчайших маршрутов выбирается минимальный маршрут после дефазификации, т.е.

V = min{L1,L2,...,¿n}

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

Шаг 16. Если существует несколько маршрутов, удовлетворяющих этому условию, то

— ¿2 = 1 • ■ — Lift

tmln = min{taii ta2).....tan)}=> ¿*(ímín)

L — искомый маршрут с заданными условиями.

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

0(Z((fc + 1 )(n2 + т) + (t - к)п)) « О ((.к + l)(n2 + т) + (t - к)п) где п - количество вершин; т - количество ребер; t - количество периодов времени; ¿ — количество периодов времени, когда все дуги на кратчайшем пути существуют; I - количество операций необходимое для дефаззификации временного параметра.

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

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

1р *>> где 13 - образ ситуации, 1а - образ решения.

В свою очередь,

=< Ры, Рт, Рс, РЕ, I, М$1 М3. >, где — пространственные свойства ситуации. К ним относят пространственные объекты ситуации прецедента на карте; Рт — временные свойства ситуации. Свойства отражают не только абсолютное время, но и длительность, периодичность, согласованность с другими событиями; Рс - семантические свойства ситуации. Таковыми являются наименование, оценки по различным классификациям, количественные и качественные значения параметров ситуации; РЕ — прагматические свойства ситуации, отражающие ее связь с различными прикладными задачами, полезность ее учета в их решении; £ - список существенно важных для идентификации образа ситуации экземпляров и классов объектов и отношений; М5, - методы расширения ситуации и методы-индикаторы.

Аналогичным образом описывается образ решения 1а, и =< Рп. Рт. Рс РЕ. Мм >, где РууРуу. Рт. Рс. Ре ~ пространственные, временные, семантические и прагматические свойства решения; Ма, Мпа - методы расширения решения и конструирования визуального представления области решения.

Прецедентный анализ при использовании предложенной концептуальной модели реализуется следующим образом:

1. Задается проблемная ситуация путем описания пространственно-временных, семантических и прагматических границ проблемной области 5.

2. Строится множество образов прецедентов {¡¡}, близких проблемной ситуации. В отличие от традиционного отбора прецедентов путем вычисления значений меры близости, отбор образов дополнительно требует оценку результата работы методов расширения ситуации М$. В множество анализируемых ситуаций могут попасть те, которые непосредственно «не имеют отношения» к текущей, но близки «по сути».

3. Вызовом методов-индикаторов М3- оценивается возможность применения решений из множества {/$}, в результате чего строится множество возможных решений {с^}.

4. Для {с^} с помощью методов Ма, Мы создаются варианты альтернатив решения в проблемной ситуации.

■". 5. Если геоинформационной системой не предложено полезных решений, ситуация 5 фиксируется как ситуация, для которой недостаточно накопленного опыта.

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

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

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

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

Шаг 1. Перед началом алгоритма все вершины и дуги не окрашены.

Шаг 2. Проверка принадлежит ли вершина xs какому-нибудь ребру гиперграфа. Если вершина принадлежит ребру xs е ёь то переход к шагу 7. Если вершина не принадлежит xs g ёг, то надо найти ближайшее ребро. Для этого необходимо произвести поиск в начале центра ребра. Центром кластера является среднее геометрическое место точек в пространстве переменных. Поэтому центр ребра можем определить следующим образом,

(п ч 1/п ]> '

где <7i - центр ребра, t - элементы, принадлежащие ребру ё£.

Шаг 3. Определить ближайшее к начальной вершине xs ребро:

bs = min у] (xs — gt)2

bs - расстояние между начальной вершиной и центром ребра.

Шаг 4. Проверить, существует ли ребро ё£ в момент времени t. Если данное ребро существует, то переходим в него, если нет, то новый поиск ребра.

Шаг 5. Определяется ближайшая вершинах к вершине xs,

bx = min V(xs-x)2.

Шаг 6. Строится путь из начальной вершины xs в вершину х, используя алгоритм Дейкстры. Переходим к шагу 8.

Шаг 7. Если начальная вершина принадлежит ребру xs 6 ёьто в начале производится проверка на нечеткую смежность вершин по моменту времени Vtifid > 0, xs, х е ё], далее производится проверка принадлежности конечной вершины найденному ребру, если xk е ёь то строится опытный маршрут, ребро окрашивается. Если хк g eh то переходим на шаг 8.

Шаг 8. Поиск смежного ребра с ё( среди неокрашенных ребер, т.е. ё[ П Щ Ф 0. Если такое ребро существует, то переход в ребро ёу, в котором прокладывается опытный маршрут через смежную по времени вершину, ребро окрашивается. Если ei П ej = 0, то переход к шагу 9.

Шаг 9. Нахождение ближайшего ребра ё;- к ребру

b = min (|gt — gj\) - расстояние между кластерами,

е ё£ - текущий центр ребра, д} е ё;- - искомый центр ребра.

Шаг 10. Проверить расстояние между центром ребра gt и конечной вершиной хк, и расстояние между новым центром gj и конечной вершиной хк. Если (gi,xk) > (gj,xk), то производится поиск маршрута между ребрами гиперграфа. Переход к шагу 4.

Шаг 11. Если (gi,xk) < (gj,xk), то производится поиск ближайшей вершины к вершине хк. Далее производится построение маршрута по алгоритму Дейкстры.

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

В заключении сформулированы основные выводы и результаты диссертационной работы.

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

В ходе проведенных в диссертационной работе исследований получены следующие научные и практические результаты:

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

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

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

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

5. Произведен экспериментальный анализ разработанной процедурной модели конструирования маршрутов, основанной на прецедентном анализе. В результате этого анализа было выявлено, что по следующим параметрам разработанный маршрут дает лучшие результаты, а именно: по параметру расстояние на 3,0%; по параметру время на 13,8%; по параметру затраты на 5,6%; по параметру риск на 10,4%.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Публикации в ведущих научных журналах и изданиях, рекомендованных ВАК Министерства образования и науки РФ:

1. Савельева, М.Н. Модель решения задачи маршрутизации в интеллектуальной геоинформационной системе. /С.Л. Беляков, Я.А. Коломийцев, И.Н. Розенберг, М.Н. Савельева. // Известия ЮФУ. Технические науки. — 2011. - № 5 (118).- С. 113-119.

2. Савельева, М.Н. Кластеризация при логистическом роутинге. / С.Л. Беляков, М.Н. Савельева. // Известия ЮФУ. Технические науки. - 2012. - № 4 (129). -С. 242-246.

3. Савельева, М.Н. Прецедентный анализ маршрутов на электронных картах. / С.Л. Беляков, М.Л. Белякова, И.Н. Розенберг, М.Н. Савельева // Известия ЮФУ. Технические науки. - 2012. - № 5 (130). - С. 47-51.

4. Савельева, М.Н. Прецедентный анализ образов в интеллектуальных геоинформационных системах. / С.Л. Беляков, М.Л. Белякова, М.Н. Савельева. // Информационные технологии. - 2013. - №7. - С. 22-25.

5. Савельева, М.Н. Оптимизация потоков в транспортных системах. / С.Л. Беляков, М.Л. Белякова, А.В. Боженюк, М.Н. Савельева. // Известия ЮФУ. Технические науки. -2014. -№ 5 (154). - С.161-167.

6. Савельева, М.Н. Образная модель представления опыта принятия решений с помощью геоинформационных систем. / С.Л. Беляков, М.Л. Белякова, М.Н. Савельева // Геоинформатика. - 2014. - №4. - С. 23-28.

Публикация в международных базах цитирования:

7. Savelyeva, М. The construction of the fiizzy route based on Case-Based Reasoning. / S. Belyakov, I. Rozenberg, M. Savelyeva. // In Proceeding "19л International Conference on Soñ Computing MENDEL 2013". - 2013. - pp. 273-276 (Scopus).

8. Savelyeva, Marina. Knowledge-based routing in mechanical transportation systems. / Stanislav Belyakov, Marina Savelyeva, Jeffrey Yan, Valeriy Vyatkin // In Proc. 2014 12th IEEE International Conference on Industrial Informatics (INDIN 2014). - 2014 - pp. 48-53 (Scopus).

9. Savelyeva, M. Fuzzy routing in supply chain management with temporal dependence. / M. Savelyeva, S.Beliacov // 20th International Conference on Soñ Computing: Evolutionary

Computation, Genetic Programming, Swarm Intelligence, Fuzzy Logic, Neural Networks, Fractals, Bayesian Methods, MENDEL 2014. - 2014 - pp. 195-200 (Scopus).

lO.Savelyeva, Marina. Solution of the Problem Supply Chain Management in Temporal Dependence. / Marina Savelyeva, Stanislav Belyakov // Intelligent Systems'2014. Advances in Intelligent Systems and Computing. - 2015 - Volume 323 - pp 489-496 (Springer, Scopus).

Свидетельства о государственной регистрации программы:

11. Савельева, М.Н. Визуализатор картографических данных транспортных сетей / C.J1. Беляков, А.В. Боженюк, М.Н. Савельева // Свидетельство о государственной регистрации программы для ЭВМ №2014610002. Зарегистрировано в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности РФ от 09.01.2014г.

12. Савельева, М.Н. Программа моделирования нечеткого темпорального гиперграфа / СЛ. Беляков, А.В. Боженюк, М.Н. Савельева // Свидетельство о государственной регистрации программы для ЭВМ №2014610007. Зарегистрировано в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности РФ от 09.01.2014г.

Публикации в других изданиях:

13. Савельева, М.Н. Маршрутизация в логистических проектах с неопределенностью. / М.Н. Савельева // Сборник тезисов докладов «VII Ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН». - 2011. -С. 150-151.

14. Савельева, М.Н. Маршрутизация в логистических системах при различных условиях задания времени / М.Н. Савельева. // Сборник материалов IX Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление». - 2011. — С. 219-223.

15. Savelyeva, М. Case Base Reasoning of the Route Based on Fuzzy Clusterization. / M. Savelyeva, S. Beliacov. // Proceeding "19th East West Zittau Fuzzy Colloquium". - 2012. - pp. 57-63.

16. Savelyeva, M. Fuzzy Images of Case in Intelligent Cartographic Analysis. / M. Savelyeva, S. Beliacov.//Proceeding "19th East West Zittau Fuzzy Colloquium". - 2012. -pp.64-69.

17. Сав'ельева, М.Н. Интеллектуальная визуализация при автоматическом картографировании. / СЛ. Беляков, МЛ. Белякова, М.Н. Савельева // Сборник материалов III Междунар. научн.-техн. конф. «Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2013)».-2013.-C. 413-416.

18. Savelyeva, M. The construction of fuzzy time-dependent route in geographic information system. / M. Savelyeva, S. Belyakov. // Proceeding "20th East West Zittau Fuzzy Colloquium". - 2013. - pp. 63-69.

.19. Савельева, М.Н. Образные геоинформационные модели опыта в управлении цепями поставок. / СЛ. Беляков, M.JI. Белякова, М.Н. Савельева // Гибридные и синер-гетические интеллектуальные системы: материалы II международного Поспеловского симпозиума ГИСИС'2014. -2014. - С. 39-44.

/

Соискатель (оУ Савельева М.Н.

Издательство Южного федерального университета ГСП 17А, Таганрог, 28, Некрасовский, 44 Типография Южного федерального университета ГСП 17 А, Таганрог, 28, Энгельса, 1