Нечіткі моделі та алгоритми для оптимізації маршрутів і траєкторій в умовах невизначеності

Размещено на http://www.allbest.ru/

Одеський національний політехнічний університет

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

05.13.06 - Автоматизовані системи управління та прогресивні інформаційні технології

Нечіткі моделі та алгоритми для оптимізації маршрутів і траєкторій в умовах невизначеності

Кондратенко Галина Володимирівна

Одеса - 2003

Дисертацією є рукопис.

Робота виконана в Українському державному морському технічному університеті імені адмірала Макарова Міністерства освіти і науки України на кафедрі комп'ютеризованих систем управління.

Науковий керівник Заслужений діяч науки і техніки України чл.-кор. Академії педагогічних наук України доктор технічних наук, професор Малахов Валерій Павлович, Одеський національний політехнічний університет, ректор, зав. кафедри комп'ютерних систем

Офіційні опоненти:

Заслужений діяч науки і техніки України Лауреат Державної премії України доктор технічних наук, професор Богаєнко Іван Миколайович, Науково-виробнича корпорація "Київський інститут автоматики", заступник генерального директора з наукової роботи

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

Вчений секретар спеціалізованої вченої ради Д 41.052.01 Ямпольський Ю.С.

Анотація

Кондратенко Г.В. Нечіткі моделі та алгоритми для оптимізації маршрутів і траєкторій в умовах невизначеності. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - Автоматизовані системи управління та прогресивні інформаційні технології. - Одеський національний політехнічний університет, Одеса, 2003.

Дисертація присвячена розробці нечітких моделей, алгоритмів оптимізації та програмного забезпечення для підвищення ефективності маршрутів і траєкторій рухомих об'єктів в умовах невизначеності. Розроблено стохастичні імітаційні моделі прогнозних та реальних параметрів вузлів для моделювання та оптимізації маршрутів і траєкторій в умовах невизначеності; узагальнені алгоритми фаззифікації відносних якісних сигналів, що характеризують нечіткі параметри вузлів; комбіновані алгоритми для прийняття рішень щодо включення вузлів-претендентів до відповідної траєкторії; структури баз правил нечітких експертних систем для формування значень рівня сатисфакції параметрів вузлів на траєкторіях; методи підвищення ефективності процесів оптимізації маршрутів і траєкторій в умовах невизначеності шляхом настроювання критичного рівня сатисфакції та глибини пошуку найближчих вузлів-претендентів в конфліктних ситуаціях; критерії оцінки ефективності планування маршрутів і траєкторій в умовах невизначеності; уніфіковане програмно-алгоритмічне забезпечення СППР на основі об'єктно-орієнтованих інформаційних технологій.

Ключові слова: нечіткі моделі, алгоритми, нечітка логіка, оптимізація, інформаційна технологія, СVRP-моделі, маршрут, траєкторія, бункерування суден.

Аннотация

Кондратенко Г.В. Нечеткие модели и алгоритмы для оптимизации маршрутов и траекторий в условиях неопределенности. - Рукопись.

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

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

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

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

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

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

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

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

Ключевые слова: нечеткие модели, алгоритмы, нечеткая логика, оптимизация, информационная технология, СVRP-модели, маршрут, траектория, бункерование судов.

Annotation

Kondratenko G.V. Fuzzy models and algorithms for optimization of routes and trajectories in uncertainty. - Manuscript.

The thesis is presented for submitting of scientific degree of the candidate of technical science in speiality 05.13.06 - Automated control system and progressive information technologies. - Odessa national politechnical university, Odessa, 2003.

The thesis is devoted to development of fuzzy models, optimization algorithms and software for increasing efficiency of moveable objects' routes and trajectories in uncertainty. The main research results are: stochastic simulation models of prognoses and real nodes' parameters for modeling and optimization of routes and trajectories in uncertainty; general fuzzyfication algorithms for relatively quality input signals as fuzzy parameters of nodes; combined algorithms for decision making about including node-claimant to corresponding trajectory; rule bases' structure of fuzzy expert system for determination of satisfaction level of node's fuzzy parameters at the planned trajectory; methods for increasing efficiency of optimization processes in uncertainty for routes and trajectories by adjusting critical value of satisfaction level and search's deep for nearest node-claimants in conflict situations; criteria's estimation of route and trajectory planning in uncertainty; unification software for decision making systems based on the object-oriented information technologies.

Keywords: fuzzy models, algorithms, fuzzy logic, optimization, information technology, СVRP-models, route, trajectory, ship's bunkeribg.

1. Загальна характеристика роботи

невизначеність математичний програмний алгоритмічний

Актуальність теми. Проблеми створення високоефективних систем підтримки прийняття рішень (СППР) для оптимізації процесів планування маршрутів та траєкторій суттєво впливають на ефективність функціонування рухомих об'єктів управління, зокрема на ефективність транспортних перевезень, бункерувальних операцій, а також на ефективність робототехнічних систем, маніпулятори яких відтворюють складні траєкторії в процесі виконання технологічних операцій, та ін. Задачі такого типу значно ускладнюються при їх розв'язанні в умовах невизначеності апріорної і поточної інформації. До цього класу відноситься і (одна з найважливіших на морському транспорті) задача планування економічних маршрутів суден з точки зору забезпечення мінімізації їх подовженості, зменшення часової тривалості та зниження витрат палива на реалізацію маршруту. Її розв'язок часто ускладнюється високим ступенем невизначеності апріорної і поточної інформації в вузлах маршрутів та траєкторій, зокрема, при плануванні маршрутів танкерів-бункерувальників, які мають доставляти паливо суднам, розміщеним в різних портах (вузлах дислокації). Замовлення портів на етапі попереднього планування маршрутів, як правило, є нечіткими, наприклад, "біля 500 т", "в середньому 300 т", "не менше 200 т" і т.п., тобто розмитою або нечіткою є інформація про обсяг вантажу, що має бути доставленим в кожний з вузлів на маршруті. Математична формалізація задач такого класу з врахуванням умов невизначеності апріорної інформації є досить складною проблемою. Для аналізу та оптимізації морських перевезень, взаємодії суден та розв'язання інших задач планування в морській логістиці найефективнішими, з точки зору математичної формалізації задач і шляхів їх розв'язання, є методи дослідження операцій, теорії нечітких множин, нечіткої логіки та теорії прийняття рішень.

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

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

Робота виконувалася у відповідності до пріоритетних напрямків науково-дослідних робіт Українського державного морського технічного університету імені адмірала Макарова згідно координаційних планів Міністерства освіти та науки України, зокрема, в рамках наукових досліджень за держбюджетними темами: "Основи теорії суднових нечітких експертних систем для управління процесами передачі рідинних вантажів в нестаціонарних умовах" (№ держ. реєстр. 0102U005205), “Розробка теорії синтезу алгоритмів прийняття рішень та моделей управління суднами в екстремальних умовах на основі нечіткої логіки і нечітких множин” (№ держ. реєстр. 0100UKR001903), "Розробка методів проектування інтерактивних сенсорних систем для оптимізації режимів роботи об'єктів з умовами функціонування, що змінюються випадковим чином (№ держ. реєстр. 0196UKR023263).

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

Досягнення мети здійснюється розв'язанням таких основних задач:

аналіз існуючих методів планування маршрутів і траєкторій в умовах невизначеності;

синтез комбінованих алгоритмів оптимізації маршрутів та траєкторій в умовах невизначеності на основі нечітких математичних моделей, евристично-пошукових механізмів та нечітких експертних систем;

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

розробка структури, компонентів і параметрів нечітких експертних систем, що забезпечують прийняття ефективних рішень в конфліктних ситуаціях при оптимізації процесів формування маршрутів і траєкторій на основі формування поточних значень рівня сатисфакції нечітких замовлень в вузлах-претендентах;

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

розробка критеріїв та методів оцінки ефективності спланованих в умовах невизначеності маршрутів і траєкторій;

розробка інформаційних моделей семантичних взаємовідношень між класами та об'єктами при оптимізації маршрутів і траєкторій в умовах невизначеності та ресурсних обмежень.

Об'єкт дослідження: система автоматизованого планування маршрутів та траєкторій в умовах апріорної та поточної невизначеності і ресурсних обмежень рухомих об'єктів.

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

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

Наукова новизна одержаних результатів полягає в розвитку і поглибленні теоретичних і методологічних основ формування нечітких моделей та алгоритмів для підвищення ефективності процесів формування маршрутів і траєкторій в умовах невизначеності. Новизна наукових результатів полягає в наступному:

для моделювання процесів оптимізації маршрутів і траєкторій в умовах невизначеності отримали подальший розвиток імітаційні моделі нечітких (прогнозних) та реальних параметрів вузлів на основі стохастичного характеру процедури їх формування з урахуванням різнорідності транспортних одиниць з точки зору ресурсних обмежень;

для підвищення ефективності обробки нечіткої інформації удосконалено методи і алгоритми фаззифікації сигналів якісного характеру з функціями належності (ФН) трикутної форми та відносних якісних сигналів з гіперболічними ФН LR-форми на основі вперше запропонованих узагальнених аналітичних залежностей, що забезпечують суттєве зниження обчислювальної складності та похибок обчислень в процесах фаззифікації;

вперше запропоновано нечіткі моделі поведінки людини-оператора (ЛПР) при розв'язанні конфліктних ситуацій на основі відносних якісних параметрів вузлів-претендентів, а також відповідні структури баз правил нечітких експертних систем, що формують значення рівня можливої сатисфакції вузлів на поточній траєкторії (маршруті);

для оптимізації маршрутів і траєкторій в умовах невизначеності вперше запропоновано концепцію та комбінований алгоритм почергового аналізу ранжованих вузлів-претендентів і методи підвищення ефективності автоматизованого прийняття рішень стосовно включення вузла-претендента до траєкторії (маршруту) в конфліктних ситуаціях шляхом настроювання критичного рівня сатисфакції та глибини пошуку найближчих вузлів-претендентів;

отримав подальший розвиток комплекс критеріїв ефективності процесів планування маршрутів і траєкторій в умовах невизначеності за рахунок введення додаткового критерію, що ґрунтується на мінімізації ресурсних залишків транспортних одиниць після обслуговування всіх вузлів на відповідному маршруті;

для автоматизації процесів планування морських бункерувальних програм (БП) вперше запропоновано семантичні об'єктно-орієнтовані моделі взаємодії інформаційних агентів при формуванні маршрутів танкерів в умовах невизначеності.

Практичне значення отриманих результатів полягає в тому, що розроблені алгоритми та моделі можуть бути використані для оптимізації маршрутів та траєкторій широкого класу рухомих об'єктів, які функціонують в умовах апріорної та поточної невизначеності (стосовно параметрів вузлів). Алгоритми та моделі для розв'язання задач планування маршрутів танкерів при здійсненні бункерувальних операцій в умовах нечітких замовлень портів, планування запасів бункерувального палива та визначення оптимальної кількості танкерів для ефективного виконання бункерувальних програм в умовах невизначеності впроваджено в морських компаніях “Укрбункер” та “Нафтасервіс Шиппінг”. Результати досліджень також впроваджено в навчальний процес УДМТУ. Запропоновані моделі та алгоритми для управління робототехнічними системами в умовах невизначеності та методи фаззифікації якісних сигналів використано іншими авторами при виданні наукової та навчальної літератури.

Особистий внесок здобувача. Всі основні результати, що виносяться на захист, отримані здобувачем самостійно та опубліковані в 14 наукових працях. При цьому роботи [2, 3, 5, 7, 8, 10, 12] опубліковані здобувачем особисто. У роботах, опублікованих у співавторстві, здобувачу належать: в роботі [1] - імітаційні моделі та блок-схеми алгоритмів на основі НЕС; [4] - аналіз та класифікація задач типу VRP; [6] багатокритеріальний підхід на основі критеріїв оптимізації бункерувальних операцій в умовах невизначеності; [14] - програмно-алгоритмічне забезпечення комп'ютеризованої системи управління.

Апробація результатів дисертації. Основні результати дисертаційних досліджень доповідалися та обговорювалися на: наук.-техн. семінарі "Застосування обчислювальної техніки і математичного моделювання в прикладних наукових дослідженнях", Одеса, 1995; Міжн. школі-семінарі "Проблемні питання автоматизації виробничих процесів", Севастополь, 1996; 3-й, 4-й Укр. конф. з автоматичного управління, Севастополь, 1996, Черкаси, 1997; Міжн. семінарі "Автоматизація: проблеми, ідеї, рішення", Тула, 1996; Міжн. конф. "Проблеми суднобудування: стан, ідеї, рішення", Миколаїв, 1997; 1-й - 7-й Міжн. школі з моделювання, Алушта, 1996-1999, 2001, 2002, Шацьк, 2000; Міжн. конф. "Проблеми автоматизації технічних об'єктів і технологічних процесів в машинобудуванні, енергетиці і на транспорті", Севастополь, 1999; Міжн. конф. з управління роботами "Robot Control", SYROCO'00, Відень, Австрія, 2000; Щорічній наук.-метод. конф. "Могилянські читання", Миколаїв, 2001, 2002; 2-й Міжн. конф. "Management and Control of Production and Logistic", IFAC, Гренобль, Франція, 2000; 3-й Міжн. конф. "Проблеми енергозбереження і екології в суднобудуванні"; Миколаїв, 2002; Міжн. конф. "Кораблебудування: освіта, наука, виробництво", Миколаїв, 2002; наук.-техн. конф. професорсько-викладацького складу УДМТУ, 1996, 1998, 2000, 2002.

Публікації. Основні результати дисертаційної роботи опубліковано в 14 друкованих працях, в тому числі в 6 наукових працях [1-3, 5,7,10] у виданнях, що входять до переліків ВАК України, 2 опублікованих доповідях та 6 тезах Міжнародних та Всеукраїнських конференцій.

Структура дисертації. Дисертація складається з вступу, 5 розділів та 3 додатків. Загальний обсяг дисертації складає 278 сторінок, обсяг тексту - 146 сторінок, додатків - 73 сторінки. Дисертація містить 62 рисунки, 22 таблиці та посилання на 181 літературних джерел.

2. Основний зміст роботи

У вступі стисло представлені об'єкт і предмет дослідження, обґрунтовано актуальність дисертаційної роботи, наведено відомості про зв'язок обраного напрямку досліджень з державними науковими програмами та з планами організації, в якій виконано роботу, відзначено наукову новизну та практичну значимість, наведено дані про публікацію та апробацію отриманих результатів.

У першому розділі розглянуто основні методи планування маршрутів та траєкторій рухомих об'єктів (транспортних одиниць), проаналізовано існуючі підходи до оптимізації маршрутів та траєкторій на основі точних та евристичних моделей і алгоритмів, виділено для дослідження клас задач планування маршрутів типу CVRP (з ресурсними обмеженнями на вантажомісткість транспортних одиниць) та співставні класи типу DVRP (з обмеженнями на загальну довжину або час реалізації кожного з маршрутів), проаналізовано вплив розмірності задач планування маршрутів на вибір алгоритмів, їх обчислювальну складність та ефективність. Визначено відповідний клас рухомих об'єктів, що функціонують в умовах невизначеності, проаналізовано основні джерела нечіткості апріорної та поточної інформації, зокрема для задач бункерування суден в умовах нестаціонарного морського середовища при нечітких параметрах замовлень палива в портах та інших місцях дислокації суден, для яких формуються маршрути танкерів при реалізації відповідних БП. Детально проаналізовано шляхи корекції математичних моделей при плануванні траєкторій рухомих об'єктів з врахуванням невизначеності (нечіткості або стохастичності) апріорної інформації та можливості виникнення конфліктних ситуацій. На основі аналізу та узагальнення широкого класу об'єктів, що функціонують в умовах невизначеності, обґрунтовано доцільність розробки універсальних математичних моделей та комбінованих алгоритмів оптимізації для успішної формалізації задач CVRP та планування маршрутів і траєкторій із застосуванням теорії нечітких множин, точних та евристичних методів оптимізації, нечіткої логіки та засобів об'єктно-орієнтованого програмування.

У другому розділі на основі теорії нечітких множин розроблено математичні моделі для автоматизації морських транспортних перевезень, детально досліджено вплив невизначеності апріорної і поточної інформації та нестаціонарного характеру морського середовища на параметри цільових функцій, параметричні та координатні обмеження та нечіткі вхідні дані, які можуть бути представлені нечіткими множинами з функціями належності (ФН) трикутної або узагальненої LR-форми. Досліджено різні математичні моделі на основі декомпозиції нечіткої цільової функції, на основі використання "чітких-нечітких" перетворень для побудови чітких компромісно-цільових моделей, в т.ч. при використанні метода середньо-інтервальних значень, на основі застосування нечітких множин типу 2 та на основі формування позитивних і негативних ідеальних рішень.

Для оцінки ефективності та вибору найкращих алгоритмів формування маршрутів і траєкторій в умовах невизначеності при розв'язанні задач класу CVRP розроблено ряд імітаційних моделей, що дозволяють досліджувати процес планування і реалізації маршрутів та траєкторій в умовах різної інтенсивності зовнішніх збурень та наявності декількох джерел невизначеності апріорної інформації. Розробка таких імітаційних моделей дозволяє здійснювати апробацію алгоритмів планування маршрутів та траєкторій і приймати ефективні рішення на основі дослідження властивостей алгоритмів в умовах невизначеності та нестаціонарних збурень.

Як один з найбільш узагальнюючих прикладів, детально розглянуто процес формування імітаційних моделей та дослідження нечітких алгоритмів прийняття рішень при плануванні маршрутів і траєкторій в задачах оптимізації бункерувальних процесів на морському транспорті. Імітаційні моделі нечітких замовлень представлено у вигляді нечітких множин з трикутною формою ФН (рис. 1). Нечіткі замовлення як параметри ФН для різних портів визначаються при цьому на основі моделі (1):

, , , 1

де - верхня межа нечіткої множини; - нижня межа нечіткої множини; - параметр нечіткої множини, для якого значення ФН ; , , - випадкові величини з відповідним законом розподілу, ; D - вантажомісткість танкеру; j - номер порта-замовника, для якого формується модель нечітких замовлень .

При використанні однотипних танкерів для виконання БП () та при відсутності апріорної інформації про типи суден-замовників в імітаційних моделях.

При формуванні імітаційних моделей реальних замовлень стохастичний підхід, що характеризує нестаціонарний характер зовнішніх збурень для бункерувальних процесів, реалізується наступним чином:

Крок 1. Визначається для j-го порту параметр

Крок 2. Визначається значення ФН за алгоритмом

Крок 3. Формується випадкове число (для першої ітерації k=1).

Крок 4. Перевіряється умова при виконанні якої значення приймається як модель фактичного значення замовлення j-го порту. Якщо ж зазначена умова не виконується, то поточний параметр не фіксується і процедура формування моделі чіткого замовлення для j-го порту повторюється, починаючи з Кроку 1.

Крім того, розроблено блок-схему та алгоритми формування комплексної імітаційної моделі, в якій нечіткі замовлення та реальні замовлення формуються одночасно при виконанні умови (4) на основі залежностей.

Для ієрархічної структури задач формування маршрутів і траєкторій наведено характеристики умов невизначеності при плануванні та реалізації морських БП, оптимізація яких пов'язана з наступними критеріями та обмеженнями: мінімально можлива кількість танкерів для реалізації БП; мінімальна сумарна довжина маршрутів танкерів в рамках БП; обов'язкове обслуговування всіх портів-замовників; максимально можлива кількість розвантаженого палива при реалізації кожного маршруту в умовах нечітких замовлень портів.

Обґрунтовано необхідність розробки нечіткої експертної системи (НЕС), що дозволяє автоматизувати процес прийняття рішення відносно можливості включення порта-претендента до відповідного маршруту на основі, наприклад, нечіткої інформації про замовлення (j1)-го порту та нечіткого значення залишкового бункерувального палива на танкері у випадку виникнення конфліктної ситуації (рис.2). Конфліктна ситуація характеризується перетином нечітких множин та .

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

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

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

Крім того, розроблено аналітичний алгоритм фаззифікації відносних якісних сигналів з гіперболічними ФН LR-форми, що формуються в результаті застосування операції ділення до нечітких множин з ФН трикутної форми.

При виникненні конфліктних ситуацій в процесі прийняття рішень ступінь перетину нечітких множин та характеризується рівнем можливої сатисфакції.

В розділі сформульовано принципи побудови НБП. Структура та кількість правил залежать від: кількості вхідних змінних,; кількості вихідних змінних,; кількості лінгвістичних термів, вхідних змінних; кількості лінгвістичних термів, вихідних змінних; кількості ієрархічних рівнів НБП; застосування процедур мінімізації кількості правил на етапах попереднього навчання НЕС. Проектування НБП здійснюється спеціалістами-експертами в даній предметній області. При = 3 лінгвістичні терми, вибираються з множини, тобто, а при = 5 лінгвістичні терми, вибираються з множини, де лінгвістичні терми позначено: L -"Низький", LM - "Нижче середнього", M - "Середній", HM - "Вище середнього", H - "Високий".

Для правила IF AND AND THEN відповідний алгоритм агрегації за методом Л. Заде.

Сформовано варіанти НБП НЕС на основі попередньо обраної кількості лінгвістичних термів якісних вхідних та вихідного сигналів та проаналізовано синтезовані за підходами Л. Заде, Б. Вернерс та Г. Циммермана алгоритми агрегації з урахуванням ступеня оптимізму позицій спеціалістів-експертів. Аналіз наведених результатів моделювання процесів планування маршрутів і траєкторій для БП, що включає 27 портів, підтверджує ефективність та працездатність розроблених нечітких моделей та алгоритмів прийняття рішень для розв'язку задач типу CVRP.

Четвертий розділ присвячено дослідженню шляхів та методів підвищення ефективності процесів прийняття рішень при плануванні маршрутів і траєкторій в умовах невизначеності. Досліджуються методи оцінки ефективності маршрутів і траєкторій на основі використання імітаційних моделей реальних вхідних параметрів, що характеризують невизначеність апріорної інформації при розв'язку CVRP з урахуванням наступних вимог: а) сумарна довжина маршрутів має бути мінімізована; б) танкер на маршруті заходить в кожний порт тільки один раз (крім базового порту BASE); в) початком і кінцем кожного маршруту є BASE; г) замовлення всіх портів мають бути обов'язково виконаними.

При використанні евристичних методів оптимізації (у випадку великої кількості портів в БП) пропонується здійснювати наступну послідовність алгоритмічних процедур: побудова гамільтонового циклу для всієї кількості N вузлів без урахування ресурсних обмежень (аналог реалізації БП одним танкером з необмеженою вантажомісткістю) з метою визначення послідовності обходу, тобто ранжування портів; розв'язок задачі CVRP для N портів на основі застосування НЕС в конфліктних ситуаціях з урахуванням вантажомісткості танкерів та імітаційних моделей (3), (7) реальних замовлень; оптимізація сформованих маршрутів шляхом побудови гамільтонових циклів в рамках кожного з синтезованих на попередньому етапі маршрутів.

Використання запропонованих імітаційних моделей при реалізації інтерактивного режиму взаємодії ЛПР-СППР дозволяє попередньо “програвати” різні ситуації, як при варіації параметрів СППР, так і при варіації параметрів імітаційних моделей, що можуть відображати різні думки експертів з точки зору формування параметрів моделей реальних замовлень, зокрема, постійного значення опорної величини в моделі (8) та законів розподілу стохастичних параметрів в імітаційних моделях (4) та (8). Порівняльний аналіз результатів моделювання попередньо запланованих маршрутів та оцінка їх ефективності дозволяє визначати найкращий варіант з гами альтернативних варіантів. Подальший аналіз апостеріорних оцінок дозволяє здійснювати корекцію стратегії прийняття рішень для підвищення їх ефективності. При цьому накопичення досвіду ЛПР та експертів, як і корекція параметрів СППР, дозволяють підвищувати ефективність процесів формування маршрутів і траєкторій в умовах невизначеності.

В інтерактивному режимі взаємодії ЛПР з розробленою СППР людина-оператор в разі виникнення непередбачених перешкод (бойові навчання військових кораблів, наявність мін, погіршення погодних умов та ін.) може коригувати значення відстаней між портами, а також встановлювати індивідуальні значення параметру , для кожного порту або для особливо відповідальних портів, повторний захід в які пов'язаний з підвищенням можливості виникнення аварійних ситуацій або з можливістю порушення обмежень на часовий термін БП ().

В загальному випадку довжина -го маршруту визначається наступним чином враховуючи, що. Для оцінки ефективності попередньо запланованих маршрутів необхідно порівняти наступні параметри: загальну довжину попередньо запланованих маршрутів; загальну довжину додаткових маршрутів при реалізації реальних замовлень портів; повну довжину основних і додаткових маршрутів танкерів при успішному завершенні БП.

Глобальний екстремум (мінімум) залежності відповідає оптимальному критичному значенню, тобто при забезпечується виконання умови. При дослідженні НЕС з критичним значенням для CVRP на основі 27 портів значення загальної довжини основних маршрутів складає = 3658 миль, додаткових маршрутів - = 142 милі, а повної довжини всіх маршрутів - 3800 миль, що є мінімальним значенням в порівнянні з аналогічним параметром при інших критичних значеннях рівня сатисфакції. Досліджено вплив параметрів нечітких та реальних замовлень портів на вибір значення . Наведено усереднену функцію, що побудована за результатами моделювання задачі бункерування суден з 32 вузлами на основі 248 стохастичних імітаційних моделей нечітких замовлень та більше стохастичних імітаційних моделей реальних замовлень при реалізації 8-ми БП з.

Запропоновано метод зниження ступеня невизначеності апріорної інформації шляхом збільшення кількості пріоритетних факторів та формування відносної якісної інформації на входах НЕС.

Для підвищення ефективності планування маршрутів розроблено алгоритми поглибленого пошуку (з глибиною 1 та 2) вузлів-претендентів при неможливості розв'язання конфліктної ситуації для поточного вузла-претендента. Для НЕС з відносними вхідними якісними сигналами (9) розроблено НБП. Результати моделювання задачі бункерування суден з 32 вузлами підтверджують ефективність запропонованих нечітких моделей та алгоритмів за критеріями мінімальної сумарної довжини всіх маршрутів та максимально можливої кількості розвантаженого вантажу (8) на кожному з маршрутів в рамках відповідної БП. Зокрема, застосування НЕС до аналізу конфліктних ситуацій в рамках 8-ми БП забезпечує зменшення параметра на 5…10%; введення глибини 2 для пошуку порта-претендента забезпечує зменшення усередненого параметра на 0…8% та підвищення (для БП №4) на 7%. Оптимізація попередньо запланованих маршрутів шляхом побудови додаткових гамільтонових циклів забезпечує зниження параметра на 2%, а при реалізації БП (з додатковими маршрутами) знижує на 10…25%.

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

У п'ятому розділі наведено програмно-алгоритмічне забезпечення СППР у вигляді інформаційної інтелектуальної системи для планування маршрутів на основі об'єктно-орієнтованої технології з розробкою та реалізацією об'єктних моделей: НЕС, побудови гамільтонових циклів (алгоритми Clark та Wright, моделювання процесів випалювання), формування оптимальних маршрутів з урахуванням невизначеності замовлень та ресурсних обмежень (CVRP). Крім того, сформовано об'єктні моделі інформаційних агентів даних, зокрема, бази замовлень, бази замовників, бази можливих дислокацій замовників (рис. 8) тощо. Розглянуто можливість використання розробленої інформаційної системи для розв'язання в різних постановках задач планування маршрутів мобільних та підводних роботів, маніпуляційних систем з рухомою основою, транспортно-технологічних систем та інших рухомих об'єктів, що функціонують в умовах невизначеності.

Загальні висновки

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

1. Розроблено нечіткі математичні моделі для розв'язку задач планування та оптимізації маршрутів і траєкторій при невизначеності вхідних даних, параметрів цільових функцій та обмежень. Запропоновано алгоритми і моделі для представлення і обробки нечіткої інформації на основі застосування ФН трикутної та LR-форм, спеціальних перетворень розмитих змінних та параметрів.

2. Сформовано стохастичні імітаційні моделі вхідної нечіткої інформації для тестування алгоритмів планування та оптимізації маршрутів і траєкторій в умовах невизначеності. Запропоновано комплекс критеріїв для оцінки ефективності процесів планування на основі мінімізації загальної довжини маршрутів, кількості маршрутів та ресурсних залишків транспортних одиниць після обслуговування всіх вузлів відповідного маршруту.

3. На основі застосування нечіткої логіки розроблено узагальнену структуру багатокрокових алгоритмів планування та оптимізації маршрутів і траєкторій з використанням процедур ранжування вузлів та побудови множини гамільтонових циклів. Обґрунтовано ієрархічний підхід до класифікації CVRP та сформульовано відмінні ознаки задач верхнього, середнього та нижнього рівнів.

4. Обґрунтовано і розроблено структуру СППР, бази знань НЕС для прийняття рішень в конфліктних ситуаціях шляхом прогнозування рівня сатисфакції нечітких замовлень в вузлах-претендентах та процедуру вибору критичного значення рівня сатисфакції на основі мінімізації загальної довжини маршрутів.

5. Розроблено узагальнений алгоритм фаззифікації вхідної інформації НЕС при застосуванні нечітких моделей вхідних сигналів та лінгвістичних термів у вигляді нечітких множин з трикутними та гіперболічними LR-формами ФН. Запропоновано алгоритми поглибленого пошуку вузлів-претендентів в конфліктних ситуаціях та алгоритми зниження ступеня невизначеності вхідної інформації шляхом збільшення кількості пріоритетних факторів і використання відносних величин нечітких вхідних сигналів.

6. Шляхом моделювання процесів бункерування суден для CVRP з 32 вузлами, 248 імітаційних моделей нечітких замовлень та більше як 2 моделей реальних замовлень підтверджено ефективність розроблених нечітких моделей та алгоритмів згідно відповідного комплексу критеріїв. Введення НЕС в СППР для аналізу конфліктних ситуацій зменшує значення усередненого критерію на 5…10%; введення глибини 2 для пошуку порта-претендента знижує на 0…8% та підвищує значення критерію (для БП №4) на 7%. Оптимізація сформованих маршрутів шляхом побудови додаткових гамільтонових циклів забезпечує зниження параметра на 2%, а при реалізації БП (з додатковими маршрутами) знижує значення на 10…25%.

7. На основі об'єктно-орієнтованих технологій розроблено програмне забезпечення СППР для оптимізації маршрутів і траєкторій в умовах невизначеності, що забезпечує інтеграцію в існуючі автоматизовані системи управління бункерувальними компаніями, узгодженість з чинними стандартами в області організаційного управління підприємствами та ергономіки, поширення області застосування на більш широкий клас задач логістики, що характеризуються нечіткими параметрами вузлів в умовах ресурсних обмежень, та задач управління, зокрема, маніпуляційними системами з рухомою основою, підводними роботами в динамічному середовищі, нестаціонарними транспортно-технологічними системами тощо. Результати дисертаційних досліджень впроваджено в морських компаніях “Укрбункер” та “Нафтасервіс”, в навчальному процесі Українського державного морського технічного університету.

Список опублікованих праць за темою дисертації

1. Імітаційні моделі та алгоритми формування маршрутів і траєкторій на основі нечіткої логіки // Праці Одеського політехнічного університету, Одеса, 2002. - Вип. 2 (18). - С. 72-80.

2. Кондратенко Г.В. Алгоритмы оценки эффективности процессов планирования маршрутов и траекторий на основе нечетких моделей принятия решений // Моделювання та інформаційні технології. - К.: ІПМЕ НАНУ, 2002. - Вип. 12.- С. 40-47.

3. Кондратенко Г.В. Проблемы управления манипуляционными системами с подвижным основанием // Збірник наукових праць УДМТУ. - Миколаїв, УДМТУ, 1999. - Вип. 4., С. 135-151.

4. Малахов В.П., Кондратенко Г.В. Аналіз задач класу VRP і алгоритми формування та оптимізації маршрутів рухомих об'єктів // Proceeding, 7-th International Modelling School, Alushta, Crimea, 2002. - С. 21-24.

5. Кондратенко Г.В. Фаззифікація якісних сигналів в нечітких системах підтримки прийняття рішень // Вісник ХГТУ. - Херсон, № 14, 2002. - С. 74-81.

6. Сидоренко С., Кондратенко Г., Полторак К. Імітаційне моделювання нечітких алгоритмів для формування характеристик нелінійних функціональних перетворювачів // Proc. of 4-th International Modelling School of AMSE-UAPL (Alushta, Crimea, Sept. 12-17, 2000), Rzeszov, Poland, 2000. - С. 233-236.

7. Кондратенко Г.В. Оптимізація маршрутів суден в умовах невизначеності // Вісник технол. ун-ту Поділля. - Хмельницький, 2002. - № 3, Том. 2. - С. 23-27.

8. Кондратенко Г.В. Формування цільових функцій при оптимізації процесів управління в умовах невизначеності // Матеріали міжнародної конференції з управління Автоматика - 2002, Донецьк, ДонНТУ, 2002. - С. 125-127.

9. Ткаченко А.Н., Кондратенко Г.В. Метафильтрация в линейных динамических системах // Тез. докл. ІІ гор. семинара "Применение выч. техники и математического моделирования в прикладных научных исследованиях", Одесса, 1995.-С. 22-23.

10. Кондратенко Г.В. Математичні моделі для оптимізації процесів планування маршрутів та траєкторій // Комп'ютерна інженерія та інформаційні технології. - Львів, Вісник НУ "Львівська політехніка", № 450, 2002. - С. 56-60.

11. Malakhov V.P.,Kondratenko G.V. Information-support system based on the decision-making algorithms for marine uncertain functioning conditions//Proc. Int. Conf. "Shipbuilding: education, science, production", Mykolaiv, USMTU, 2002.- Vol. 2.- P. 216-217.

12. Кондратенко Г.В. Проблеми моделювання електроприводів підвищеної швидкодії // Proc.:1-st Int. Modelling School (Krym,Alushta'96).- Rzeszow,1996. - С. 42.

13. Кондратенко Г.В., Тимченко В.Л. Критерії ефективності маршрутів танкерів при плануванні бункерувальних операцій // Мат. 3-й Межд. н.-т. конф. "Проблемы энергосбережения и экологии в судостроении".- УГМТУ, Николаев.- 2002. - С. 164.

14. Бочаров Р.Н., Кондратенко Г.В. Компьютеризированное управление температурными режимами печи для производства глинозема // Проблемы автоматизации технических объектов и технологических процессов в машиностроении, энергетике и на транспорте. Материалы межд. конф. - Севастополь, 1999. - С. 21.

Размещено на Allbest.ru