НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ ІМЕНІ ІГОРЯ СІКОРСЬКОГО
Факультет інформатики та обчислювальної техніки .
(назва факультету, інституту)
Кафедра автоматизованих систем обробки інформації і управління .
(назва кафедри)
"На правах рукопису"
УДК 004.94: 519.876.5
«До захисту допущено»
Завідувач кафедри __________ О.А.Павлов . (підпис) (ініціали, прізвище)
“ ” 20 19 р.
МАГІСТЕРСЬКА ДИСЕРТАЦІЯ
на здобуття ступеня магістра
за спеціальністю . 126 Інформаційні системи та технології ..
(код та назва спеціальності)
ОПП Інформаційні управляючі системи та технології .
(код та назва спеціалізації)
на тему: Cистема моделювання транспортних перевезень матеріальних засобів у військових підрозділах
Виконав : студент VI курсу групи ІС-81мп
(шифр групи)
Бовда Владислав Едуардович
(прізвище, ім’я, по батькові) (підпис)
Науковий керівник проф., д.т.н., проф. Стеценко І.В.
(посада, науковий ступінь, вчене звання, прізвище та ініціали) (підпис)
Консультант проф., д.т.н., проф. Томашевський В.М.
(науковий ступінь, вчене звання, прізвище, ініціали) (підпис)
Рецензент начальник каф., д.т.н., с.н.с. Сова О.Я.
(посада, науковий ступінь, вчене звання, прізвище та ініціали) (підпис)
Засвідчую, що у цій магістерській дисертації немає запозичень з праць інших авторів без відповідних посилань.
Студент
(підпис)
Київ – 2019
«КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ ім. ІГОРЯ СІКОРСЬКОГО»
Факультет інформатики та обчислювальної техніки
(повна назва)
Кафедра автоматизованих систем обробки інформації та управління
(повна назва)
Рівень вищої освіти другий (магістерський) за освітньо-професійною програмою
Спеціальність 126 Інформаційні системи та технології
(код і назва)
ОПП Інформаційні управляючі системи та технології
(код і назва)
ЗАТВЕРДЖУЮ Завідувач кафедри
__________ О.А.Павлов .
(підпис) (ініціали, прізвище)
« » грудня 2019 р.
ЗАВДАННЯ
на магістерську дисертацію студенту Бовді Владиславу Едуардовичу
(прізвище, ім’я, по батькові)
1. Тема дисертації Система моделювання транспортних перевезень матеріальних засобів у військових підрозділах
науковий керівник дисертації Стеценко Інна В’ячеславівна, проф., д.т.н.
(прізвище, ім’я, по батькові, науковий ступінь, вчене звання)
затверджені наказом по університету від “ 28 ” жовтня 20 19 р. № 3770-с
2. Строк подання студентом дисертації “ 2 ” грудня 20 19 р.
3. Об’єкт дослідження Іноформаційні процеси поставок ресурсів для військових підрозділів.
4. Перелік завдань, які потрібно розробити 1. Виконати формалізацію задачі Транспортних перевезень матеріальних засобів у військових підрозділах.
2. Розробити Петрі-об’єктну модель для транспортних перевезень матеріальних засобів у військових підрозділах. 3.Розробити систему моделювання транспортних
перевезень матеріальних засобів у військових підрозділах.
5. Орієнтовний перелік ілюстративного матеріалу 1. Схема структурних
варіантів виконання. 2. Діаграма діяльності створення маршрутів та статистики витрат ресурсів на перевезення. 3. BPWIN діаграма. 4. Схема структурних станів системи для пошуку маршрутів доставки. 5. Схема структурна класів
програмного забезпечення. 6. Схема структурних компонентів. 7. Ілюстрація інтерфейсу. 8. Ілюстрація прикладу транспортних сполучень між автопарком та військовими частинами.9. Ілюстрація представлення мережею Петрі
транспортних сполучень між автопарком та військовими частинами.
6. Орієнтовний перелікпублікацій Чотири публікації: дві статті у фахових журналах та дві тези доповіді на наукових конференціях
7. Консультанти розділів дисертації
Розділ Прізвище, ініціали та посада
консультанта
Підпис, дата завдання
видав завдання
прийняв
8. Дата видачі завдання “ 28 ” жовтня 20 19 р.
Календарний план
№
з/п Назва етапів виконання
магістерської дисертації Строк виконання етапів
магістерської дисертації Примітка 1 Систематизація результатів огляду
літератури 17.09.2019
2 Аналіз існуючих методів розв’язання задачі 01.10.2019 3 Постановка та формалізація математичної
моделі задачі 08.10.2019
4 Розробка алгоритмів розв’язання задачі 15.10.2019 5 Розробка інформаційного та програмного
забезпечення 12.11.2019
7 Проведення експериментальних досліджень
розроблених алгоритмів 16.11.2019
8 Оформлення документації 19.11.2019
9 Подання роботи на попередній захист 20.11.2019 10 Подання роботи на основний захист 02.12.2019
Студент В.Е. Бовда
(підпис) (ініціали, прізвище)
Науковий керівник І.В. Стеценко
(підпис) (ініціали, прізвище)
РЕФЕРАТ
Магістерська дисертація: 99 с., 30 рис., 27 табл., 34 джерел, 9 додатків.
Актуальність. Армія - основа оборонної функції будь-якої країни. Від стану армії залежить імідж країни на міжнародній арені, впевненість громадян у власній безпеці, можливість протистояти зовнішнім загрозам і навіть здатність попереджати війни і конфлікти. І саме тому витрати на армію у переважної більшості країн є найбільшою статтею витрат. Величезні поставки військових ресурсів по всій країні вимагають великих витрат на перевезення. Планування маршрутів перевезень, які б забезпечили вчасну доставку та економію загальних витрат на доставку становить складну задачу для військового логіста.
Тому на даний момент існує необхідність у створенні програмного забезпечення для військових логістів, що дозволяло би швидко та ефективно планувати поставки військових ресурсів, які б забезпечували вчасну доставку та економили витрати на перевезення.
Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась на кафедрі автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» в рамках теми «Методи візуального програмування Петрі-об'єктних моделей.» (№ ДР 0117U000918).
Мета дослідження – підвищення якості процесу доставки військових ресурсів та зниження витрат на їх доставку за рахунок інформаційної системи моделювання транспортних перевезень матеріальних засобів у військових підрозділах.
Для досягнення мети необхідно виконати наступні завдання:
виконати огляд існуючих методів та засобів транспортних задач;
здійснити порівняльний аналіз різних методів та моделей транспортних задач;
формалізувати транспортну задачу перевезень матеріальних засобів у військових підрозділах;
розробити Петрі-об’єктну модель транспортних перевезень матеріальних засобів у військових підрозділах;
розробити алгоритм пошуку оптимальної кількості транспортних засобів для кожного військового складу та їх маршрути, що зменшує витрати палива на доставку та загальний час запізнення;
розробити програмну реалізацію розробленого алгоритму;
виконати аналіз отриманих результатів.
Об’єкт дослідження – іноформаційні процеси поставок ресурсів для військових підрозділів.
Предмет дослідження – методи та інформаційні технології оптимізації витрат на доставку ресурсів у військові підрозділи.
Наукова новизна отриманих результатів
Cистема моделювання транспортних перевезень матеріальних засобів у військових підрозділах дозволяє оперувати різними ресурсами військового устаткування. Також система дозволяє проводити налаштування вантажопідйомності для кожного транспортного засобу. Перевагою системи є стохастичність, що в свою чергу наближає моделювання транспортних перевезень матеріальних засобів до реальних значень. Деталізація процесів дозволяє проводити більш адекватне відображення станів та дій, які відбуваються у реальній системі. Використання генетичного алгоритму дає можливість визначити необхідну кількість транспортних засобів та їх вантажопідйомність для кожного складу та маршрути, які зменшують час запізнення замовлень та загальні витрати пального на доставку. Також використання генетичного алгоритму дозволяє генерувати широкий набір рішень та не дозволяє попадати в локальні екстремуми.
Система дозволяє проводити моделювання транспортних перевезень у складних багаторівневих ієрархічних системах.
Публікації. Матеріали роботи опубліковані в Збірнику наукових праць ВІТІ 2019 №3,4 та на ІІІ всеукраїнській науково-практичній конференції молодих вчених та студентів «Інформаційні системи та технології управління» (ІСТУ-2019).
ВІЙСЬКОВА ЛОГІСТИКА, ТРАНСПОРТНА ЗАДАЧА, ГЕНЕТИЧНИЙ АЛГОРИТМ, ЕКЗЕМПЛЯР ПОПУЛЯЦІЇ, СЕЛЕКЦІЯ ЕКЗЕМПЛЯРІВ ПОПУЛЯЦІЇ, СТОХАСТИЧНА МЕРЕЖА ПЕТРІ, ПЕТРІ-ОБ’ЄКТНА МОДЕЛЬ, ІМІТАЦІЙНЕ МОДЕЛЮВАННЯ, АЛГОРИТМ ОПТИМІЗАЦІЇ
ABSTRACT
Master's Thesis: 99 pp., 30 figs., 27 tables., 34 sources, 9 supplements.
Topicality. The army is the basis of any country's defense function. The image of the country in the international arena depends on the state of the army, citizens' confidence in their own security, their ability to withstand external threats, and even their ability to prevent wars and conflicts. This is why military spending in the vast majority of countries is the largest cost item. Huge supplies of military resources across the country require high transportation costs. Planning transportation routes that will ensure timely delivery and save on overall shipping costs is a difficult task for the military logistician.
Therefore, there is a need at present for the creation of software for military logistics, which would allow the rapid and efficient planning of deliveries of military resources that would ensure timely delivery and save on transportation costs.
Relationship with working with scientific programs, plans, topics. The work was performed at the Department of Automated Information Processing and Management Systems of the National Technical University of Ukraine «Kyiv Polytechnic Institute.
Igor Sikorsky» within the topic "Methods for Visual Programming of Petri-Object Models." 0117U000918.
The purpose of the study is to improve the quality of the delivery of military resources and reduce the cost of their delivery.
To achieve this goal, you must complete the following tasks:
review existing methods and means of transport tasks;
to carry out comparative analysis of different methods and models of transport problems;
formalize the transport task of transportation of material in military units;
to develop a petri-object model of transportation of material in military units;
to develop an algorithm for finding the optimal number of vehicles for each military unit and their routes, which reduces the cost of fuel for delivery and the total delay time;
to develop software implementation of the developed algorithm;
to analyze the results obtained.
Object of study - information processes for supplying resources to military units..
The subject of the study - methods and information technologies for optimizing the cost of resource delivery.
Scientific novelty of the obtained results
The system of modeling transportation of material transportation in military units allows to operate various resources of military equipment. The system also allows you to adjust the load capacity for each vehicle. The advantage of the system is stochasticity, which in turn brings the modeling of transportation of material to real values. The detailing of the processes allows for a more adequate reflection of the states and actions occurring in the real system. The use of a genetic algorithm makes it possible to determine the required number of vehicles and their load capacity for each warehouse and routes, which reduce order delay and overall fuel costs for delivery. Also, using a genetic algorithm allows you to generate a wide range of solutions and does not allow you to get into local extremes. The system allows modeling of transportation in complex multilevel hierarchical systems.
Publications. The materials of the work are published in the Collection of scientific works of VITI 2019 № 3,4 and at the III All-Ukrainian scientific-practical conference of young scientists and students "Information systems and technologies of management"
(ISTU-2019).
MILITARY LOGISTICS, TRANSPORTATION PROBLEMS, GENETIC ALGORITHM, COPIES POPULATION SELECTION COPIES POPULATION STOCHASTIC PETRI NET, PETRI-OBJECT MODEL, SIMULATION, OPTIMIZATION ALGORITHM
ЗМІСТ
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ ... 11
ВСТУП ... 12
1 ПРОЕКТНІ РІШЕННЯ З РОЗРОБКИ СИСТЕМИ МОДЕЛЮВАННЯ ТРАНСПОРТНИХ ПЕРЕВЕЗЕНЬ МАТЕРІАЛЬНИХ ЗАСОБІВ У ВІЙСЬКОВИХ ПІДРОЗДІЛАХ ... 14
1.1 Опис бізнес – процесів ... 14
1.1.1 Опис процесу діяльності ... 15
1.1.2 Актори і функції ... 18
1.1.3 Структура бізнес-процесів ... 20
1.2 Схема функціональної структури ... 22
1.3 Опис постановки задачі ... 22
1.4 Рішення з інформаційного забезпечення ... 23
2 МОДЕЛІ ТА МЕТОДИ СИСТЕМИ МОДЕЛЮВАННЯ ТРАНСПОРТНИХ ПЕРЕВЕЗЕНЬ МАТЕРІАЛЬНИХ ЗАСОБІВ У ВІЙСЬКОВИХ ПІДРОЗДІЛАХ ... 25
2.1 Змістовна постановка задачі ... 25
2.2 Математична модель ... 26
2.3 Огляд методів розв’язання ... 28
2.4 Розробка методу розв’язання задачі ... 37
2.5 Розробка алгоритму розв’язання... 46
2.6 Результати досліджень ефективності методу ... 47
Висновки до розділу ... 48
3 ОПИС ПРОГРАМНОГО ТА ТЕХНІЧНОГО ЗАБЕЗПЕЧЕННЯ ... 50
3.1 Засоби розробки ... 50
3.2 Архітектура програмного забезпечення ... 54
3.3 Інструкція користувача ... 57
3.4 Опис технічного забезпечення ... 64
Висновки до розділу ... 65
4 РОЗРОБКА СТАРТАП-ПРОЕКТУ ... 66
1. Опис ідеї проекту ... 66
2. Технологічний аудит ідеї проекту ... 69
3. Аналіз ринкових можливостей запуску стартап-проекту ... 70
4. Розроблення ринкової стратегії проекту ... 79
5. Розроблення маркетингової програми стартап-проекту ... 81
6. Висновки до розділу ... 83
ВИСНОВКИ ... 84
ПЕРЕЛІК ПОСИЛАНЬ ... 87
ДОДАТОК А ... 91
Схема структурних варіантів виконання ... 92
Діаграма діяльності створення маршрутів та статистики витрат ресурсів на перевезення ... 93
BPWIN діаграма ... 94
Схема структурних станів системи для пошуку маршрутів доставки ... 95
Схема структурна класів програмного забезпечення ... 96
Схема структурних компонентів ... 97
Головне вікно програми ... 98
Приклад транспортних сполучень між автопарком та військовими частинами ... 99
Представлення мережею Петрі транспортних сполучень між автопарком та військовими частинами ... 100
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ
VRP – vehicle routing problem
MDVRPTW – multi-depot vehicle routing problem GAPN – genetic algorithm and petri net
GA – genetic algorithm
ЕОМ – електронна обчислювальна машина СМО – система масового обслуговування JVM – Java Virtual Machine
JIT – Just-in-time compilation
ВСТУП
Логістика має велике значення як для клієнтів і постачальників підприємства, так і для власників і акціонерів. Головними показниками значущості логістики є час і місце. У товарів і послуг практично немає ніякої цінності, якщо вони не знаходяться саме в той час і в тому місці, де в них виникає потреба.
Протягом багатьох років робилися спроби дослідити і оцінити питому вагу логістики як на макроекономічному, так і на мікроекономічному рівні. Згідно з дослідженнями Міжнародного валютного фонду, витрати на логістику складають приблизно 12% світового валового продукту, а на рівні підприємств - від 4% до більш ніж 30% доходів.
Ще задовго до того, як підприємці стали цікавитися логістикою, ця галузь була широко поширена в військовій справі. Під час будь-яких військових дій необхідно доставити військовослужбовців, боєприпаси, запаси їжі в потрібне місце. По суті, логістика підприємницької діяльності виникла з військової логістики, тільки у військовій логістиці клієнтами є військовослужбовці, і керівництву армією потрібно зробити все, щоб забезпечити їх усім необхідним.
Завдання маршрутизації автотранспорту (Vehicle Routing Problems, VRP) - це великий клас задач дослідження операцій, що має пряме відношення до проблем побудови нових ефективних засобів логістики. Завдання маршрутизації автотранспорту може бути описано, як завдання знаходження оптимального (мінімального за витратами) плану перевезень будь-якого товару від постачальника до клієнтів, за умови додаткових обмежень. Додаткові обмеження можуть накладатися на кількість транспортних засобів, на час прибуття і час відправлення, на вантажопідйомність, тривалість маршруту і т.д[1].
Критерієм ефективності плану вантажоперевезень є сумарні витрати на перевезення вантажів транспортом.
Сучасні технічні, технологічні та інформаційні системи мають високий рівень складності, а саме велику кількість взаємопов’язаних елементів, різнорідні процеси функціонування елементів та підсистем. Методи дискретно-подієвого моделювання найбільш пристосовані для опису таких систем. В залежності від
опису моделі розрізняють аналітичне та імітаційне моделювання. Аналітичні моделі надають можливість здійснювати дослідження властивостей систем в залежності від параметрів системи в узагальненому вигляді. Імітаційні моделі, на відміну від аналітичних, здатні враховувати специфічні деталі функціонування елементів системи. Кожний метод має свої переваги моделювання, тому важливо мати таку формалізацію системи, яка б дозволяла застосовувати обидва підходи[2].
Розроблена технологія Петрі-об’єктного моделювання орієнтована на використання стохастичної мережі Петрі з багатоканальними та конфліктними переходами, з інформаційними зв’язками для опису динаміки системи.
Математичні рівняння станів такої мережі Петрі розроблені в роботі. Алгоритм імітації Петрі-об’єктної моделі, побудований у відповідності до математичного опису, підтверджує його коректність, дозволяє оцінити складність алгоритму та запобігти помилкам при його програмуванні. Отже, технологія Петрі-об’єктного моделювання надає можливість поєднати переваги аналітичного та імітаційного моделювання систем, а також розширити клас систем, що можуть бути формалізовані стохастичною мережею Петрі. Використання технології з візуальними засобами представлення моделі дозволяє перейти від програмування алгоритму до програмування моделі[2].
Вкладені мережі Петрі є одним із зручних формалізмів для моделювання та аналізу поведінки розподілених мультиагентних систем. Вони природним чином представляють структуру мультиагентних систем, так як фішки в системній мережі самі є класичними мережами Петрі і можуть мати автономну поведінку.
Мультиагентні системи є системами з високим рівнем паралелізму [3].
Сьогодні підхід GAPN (генетичні алгоритми і мережі Петрі) набуває все більшої популярності в вирішенні багатьох складних задач. Він поєднує в собі потужність моделювання мереж Петрі з можливістю оптимізації генетичних алгоритмів (GA) для планування виробничих систем. Цей підхід використовує як мережі Петрі для формулювання завдання планування, так і GA для планування.
Його основною перевагою є його здатність моделювати широкий спектр виробничих систем без змін ні в структурі мережі, ні в поданні хромосом [4].
1 ПРОЕКТНІ РІШЕННЯ З РОЗРОБКИ СИСТЕМИ МОДЕЛЮВАННЯ ТРАНСПОРТНИХ ПЕРЕВЕЗЕНЬ МАТЕРІАЛЬНИХ ЗАСОБІВ У ВІЙСЬКОВИХ ПІДРОЗДІЛАХ
1.1 Опис бізнес – процесів
Величезні поставки військових ресурсів по всій країні вимагають великих витрат на перевезення. Планування маршрутів перевезень, які б забезпечили вчасну доставку та економію загальних витрат на доставку становить складну задачу для військового логіста. Тому на даний момент існує необхідність у створенні програмного забезпечення для військових логістів, що дозволяло би швидко та ефективно планувати поставки військових ресурсів, які б забезпечували вчасну доставку та економили витрати на перевезення. Для розв’язання задачі обрано генетичний алгоритм, тому що він невразливий до потрапляння у локальний екстремум та виконується за відносно менший час ніж інші алгоритми.
Запропоновано нове рішення, що дозволяє зменшити витрати на доставку замовлень у транспортній системі матеріального забезпечення військових підрозділів
Військове устаткування та ресурси для доставки товарів представляються у вигляді “позицій” (ресурсів) мереж Петрі. Зв’язки між військовими складами та частинами представляються у вигляді “переходів” мереж Петрі. Ці переходи мають пріоритет, який буде геном у нашому генетичному алгоритмі. Екземпляр популяції являє собою список пріоритетів для всіх переходів у моделі. Селекція екземплярів популяції здійснюється через порівняння кількості витрат палива та загального часу затримки, що були отримані у результаті моделювання моделі екземпляру.
Чим менша витрата палива та загальний час затримки, тим кращий екземпляр.
Завдяки деталізації процесів доставки у мережі Петрі можна отримувати кращі маршрути доставки для транспортних засобів.
1.1.1 Опис процесу діяльності
Мережі Петрі є засобом формального опису процесів функціонування дискретних систем. У дискретній системі зміни її стану трапляються в особливі моменти часу, коли виникають умови для здійснення події. Здійснення події означає зміну стану системи, а значить, виникнення або не виникнення умов для інших подій. Процес функціонування дискретної системи – це упорядкована в часі послідовність подій [14].
Процес функціонування мережі Петрі може бути наочно представлений графом досяжних маркувань. Стан мережі однозначно визначає її маркуванням - розподілом фішок по позиціях. Вершинами графа є допустимі маркування мережі Петрі, дуги позначені символом спрацьовуючого переходу. Дуга будується для кожного збудженого переходу. Умовою запуску переходу є наявність маркерів у його вхідних позиціях в кількості рівній кількості зв’язків. Якщо умова запуску переходу виконана, здійснюється вхід маркерів до переходу і запам’ятовується момент виходу маркерів з переходу. Потім обирається перехід, для якого момент виходу маркерів з переходу найменший, і здійснюється вихід маркерів з обраного переходу. Вихід маркерів з переходу змінює маркування мережі Петрі, тому знову перевіряється умова запуску переходу і т.д. Процес продовжується, доки запускається хоч один перехід, або, доки вичерпаний час спостереження мережі Петрі.
Якщо в мережі Петрі одночасно виконана умова запуску декількох переходів, то такі переходи називають конфліктними.
Існують наступні способи розв’язування конфлікту[14]:
пріоритетний (явний та неявний спосіб завдання пріоритету);
ймовірнісний (з рівною та указаною ймовірністю).
При пріоритетному способі указується пріоритет запуску переходів і першим запускається перехід, що має вищий пріоритет. Наприклад, якщо один із пристроїв, що обслуговує об’єкти, основний, а інший – резервний, то для переходу
«обслуговування основним пристроєм» повинен бути указаний пріоритет запуску вищий, ніж для переходу «обслуговування резервним пристроєм».
У мережі Петрі з конфліктними переходами спочатку перевіряється умова запуску усіх її переходів, потім розв’язується конфлікт для конфліктних переходів і тільки потім здійснюється запуск переходу, що «виграв» конфлікт.
Для того, щоб представити систему засобами мереж Петрі потрібно[14]:
виділити події, що виникають в системі, і поставити у відповідність кожній події перехід мережі Петрі;
з’ясувати умови, при яких виникає кожна з подій, і поставити у відповідність кожній умові позицію мережі Петрі;
визначити кількість фішок у позиції мережі Петрі, що символізує виконання умови;
з’єднати позиції та переходи відповідно до логіки виникнення подій у системі : якщо умова передує виконанню події, то з’єднати в мережі Петрі відповідну позицію з відповідним переходом; якщо умова являється наслідком виконання події, то з’єднати в мережі Петрі відповідний перехід з відповідною позицією;
з’ясувати зміни, які відбуваються в системі при здійсненні кожної події, і поставити у відповідність змінам переміщення визначеної кількості фішок із позицій в переходи та з переходів у позиції;
визначити числові значення часових затримок в переходах мережі Петрі;
визначити стан мережі Петрі на початку моделювання.
Стохастичні мережі Петрі добре підходять для вирішення конфліктних ситуацій, оскільки часові затримки являють собою випадкові величини з заданим законом розподілу [14].
Імітаційні моделі зв'язані не з аналітичним поданням, а з принципом імітації за допомогою інформаційних та програмних засобів складних процесів і систем в найскладнішому аспекті – динамічному [6].
Пристрій - виробничий ресурс, який займає чітке місце в моделі, займає певний час та потребує використання модельних ресурсів. (Наприклад: верстат, який обробляє деталь та потребує електроенергію для роботи). Також пристрої поділяються на:
одноканальні, які обслуговують одночасно одну заявку;
багатоканальні, які дозволяють одночасно обслуговувати кілька заявок.
Модельний ресурс – кількісний ресурс, який займає чітке місце в моделі та являє собою атрибут моделі, який може змінюватись. (Наприклад: електроенергія для верстату).
Завдання – об’єкти, над якими необхідно провести дію на пристрої.
Черга – список завдань для певного пристрою.
Події пов'язані зі зміною стану системи та її об'єктів. Події забезпечують дискретність процесу. Процес представляється набором активностей та пасивностей. Початок кожної активності пов'язано з виникненням події в системі.
Механізми обліку системного часу[6]:
час змінюється рівномірно з певною дискретністю (лічильник часу спрацьовує при певній кількості одиниць, при кожному спрацьовуванні виникають події, які поміщаються в спеціальний список майбутніх подій. Якщо час події, що знаходиться в списку менше або дорівнює часу спрацьовування лічильника, то подія запускається на виконання) . - неефективно для більшої частини систем (лічильник спрацьовує вхолосту);
просування модельного часу у відповідності до моментів виникнення подій.
Список майбутніх подій - кожна подія має параметр часу виникнення.
Алгоритм імітації перевіряє список майбутніх подій і витягує найближчу подію:
зміну значення лічильника часу (часу настання даної події);
запуск на виконання даної події.
Джерела появи випадкових факторів можуть бути зовнішніми і внутрішніми.
Для моделювання випадкових факторів необхідно знати закон, за яким змінюються випадкові чинники. Даний закон зазвичай задається за допомогою відповідних теоретичних або емпіричних функцій розподілу. При цьому необхідно використовувати генератори псевдовипадкових чисел для імітації випадковості тих чи інших подій.
У магістерській роботі розглядається система, що дозволяє моделювати роботу військової логістики. Військовий логіст наносить на глобальну карту військові об’єкти та зв’язки між ними. Потім він вводить військові ресурси для
кожного складу. Наступним кроком є додавання військових замовлень, які необхідно доставити у встановлений час. Військовий логіст моделює роботу системи військової логістики та отримує маршрути для перевезень, які мінімізують витрату палива на доставку та загальний час запізнення замовлень. Також військовий логіст може переглянути звітність по вчасній доставці усіх замовлень та використанню людських ресурсів палива. Оптимізація використання ресурсів для перевезення залежить від кількості ітерацій генетичного алгоритму.
1.1.2 Актори і функції
На рисунку 1.1 наведено схему структурних варіантів виконання.
Рисунок 1.1 Схема структурних варіантів виконання.
У таблиці 1.1 наведено опис структурних варіантів виконання.
Таблиця 1.1 Опис структурних варіантів виконання
Назва прецеденту Опис
Створення моделі Система дозволяє створювати нову або редагувати стару модель і використовувати її в моделюванні для пошуку кращих маршрутів для перевезень та економії ресурсів, що використовуються для перевезень. Модель включає в себе: військові об’єкти; зв’язки між ними (дороги); військове устаткування, що знаходиться на цих об’єктах і може
бути передано військовій частини у користування; автопарк та водії, що можуть використовуватися для перевезень вантажу; військові замовлення у частини, які мають бути доставлені вчасно
Додавання військових об’єктів Система дозволяє додавати військовий об’єкт у модель шляхом нанесення відповідного маркеру на глобальну карту Додавання зв’язків між військовими
об’єктами
Система дозволяє додавати маршрути між військовими об’єктами до моделі
Введення доступного військового устаткування для доставки
Система дозволяє додавати військове устаткування на військових об’єктів, яке доступне для замовлень
Продовження таблиці 1.1
1.1.3 Структура бізнес-процесів Редагування даних про військове устаткування для доставки
Система дозволяє змінювати військове устаткування на військових об’єктів, яке доступне для замовлень
Назва прецеденту Опис
Введення ресурсів для доставки Система дозволяє додавати доступний автопарк військових об’єктів до моделі Редагування ресурсів для доставки Система дозволяє змінювати доступний
автопарк військових об’єктів до моделі Введення замовлень Система дозволяє додавати замовлення
військових частин у модель
Редагування замовлень Система дозволяє змінювати замовлення військових частин у моделі
Моделювання військової логістики Система дозволяє моделювати роботу військової логістики
Отримання маршрутів та звітності про використані ресурси
Система видає готові списки маршрутів для виконання військових замовлень та загальну кількість ресурсів, витрачених на перевезення
Налаштування глибини генетичного алгоритму та кількості транспортних засобів
Система дозволяє змінювати глибину генетичного алгоритму для отримання кращих маршрутів для економії ресурсів на перевезення. Система дозволяє редагувати кількість транспортних засобів та їх вантажопідйомність.
На рисунку1.2 зображено діаграму діяльності створення маршрутів та статистики витрат ресурсів на перевезення.
Рисунок 1.2 Діаграма діяльності створення маршрутів та статистики витрат ресурсів на перевезення
У таблиці 1.2 наведено опис процесів діяльності створення маршрутів та статистики витрат ресурсів на перевезення
Таблиця 1.2 Опис процесів діяльності створення маршрутів та статистики витрат ресурсів на перевезення
Назва процесу Опис
Редагування моделі Користувач розміщує військові об’єкти, зв’язки між військовими об’єктами, доступний автопарк, військове устаткування, військові замовлення
Відображення моделі Система відображає модель на карті з відповідними маркерами та інформацією
про внутрішні ресурси об’єктів та їх зв’язки
Продовження таблиці 1.2
Назва процесу Опис
Ввести глибину генетичного алгоритму
Користувач обирає точність генетичного алгоритму
Моделювання системи Система моделює процес роботи військової логістики та знаходить кращі рішення доставки військових замовлень, використовуючи генетичний алгоритм Створення маршрутів та статистики
витрат ресурсів
Система знаходить краще рішення маршрутів та рахує витрати ресурсів на доставку замовлень
Перегляд маршрутів та статистики витрат ресурсів
Користувач переглядає кращий варіант маршрутів та витрати ресурсів на доставку 1.2 Схема функціональної структури
На рисунку 1.3 зображено BPWIN діаграма, що відображає структуру підсистем програмного продукту.
Рисунок 1.3 BPWIN діаграма 1.3 Опис постановки задачі
Метою створення системи є планування перевезень яким відповідають мінімальні витрати на доставку військового устаткування та забезпечення вчасної доставки за рахунок знаходження кращих маршрутів, використовуючи моделювання. Призначенням системи є пошук маршрутів, які б забезпечили вчасну доставку та мінімізували витрати на доставку замовлень.
Для реалізації мети необхідно виконати такі завдання:
1. Розробка глобальної карти та інструментів
2. Нанесення військових об’єктів на глобальну карту 3. Реалізація моделі
3.1. Генерація мережі Петрі, що відповідає військовим об’єктам
4. Складання плану, якому відповідає мінімальне використання палива та людських ресурсів та мінімізація часу затримки доставки
4.1. Реалізація генетичного алгоритму для мінімізації витрат ресурсів на доставку
4.2. Видача маршрутів доставки
1.4 Рішення з інформаційного забезпечення Вхідні дані:
військова частина (фрагмент PetriNet);
оперативний склад (PetriNet);
тактичний склад (PetriNet);
стратегічний склад (PetriNet);
дороги між військовими об’єктами (PetriT, ArcIn, ArcOut);
час моделювання;
кількість транспортних засобів для кожного складу;
вантажопідйомність транспортного засобу (кількість маркерів у PetriP);
кількість ресурсів у складах (кількість маркерів у PetriP);
замовлення ресурсів у військові частини (кількість маркерів у PetriP).
Клас PetriNet описує роботу стохастичної мережі Петрі.
Клас PetriP описує позицію мережі Петрі у PetriNet.
Клас PetriT описує перехід у PetriNet.
Клас ArcIn описує вхідну дугу з переходу у позицію у PetriNet.
Клас ArcOut описує вихідну дугу з позиції у перехід у PetriNet.
Вихідні дані:
маршрути транспортних засобів (список військових об’єктів, які відвідає транспортний засіб);
загальні витрати палива;
загальний час затримки замовлень.
Опис структури бази даних База даних відсутня.
Структура масивів інформації
Програма зберігає створену ієрархію військових об’єктів у форматі .pns.
В цьому файлі зберігаються об’єкт типу PetriNet (з бібліотеки PetriObjLib), який містить інформацію про ресурси військових складів, транспортні засоби військових складів, дороги між військовими складами та військовими частинами, замовлення у військові частини.
Ресурси військових складів – позиції, які позначають багатоканальне завантаження військових ресурсів у транспортні засоби.
Транспортні засоби військових складів – мережа Петрі, яка відображає курсування і доставку замовлень між військовими об’єктами.
Замовлення у військові частини – позиції та переходи, які позначають багатоканальну доставку транспортними засобами військові ресурси.
Дороги – переходи позначають переїзд з одного військового об’єкту в інший за певний проміжок часу.
2 МОДЕЛІ ТА МЕТОДИ СИСТЕМИ МОДЕЛЮВАННЯ
ТРАНСПОРТНИХ ПЕРЕВЕЗЕНЬ МАТЕРІАЛЬНИХ ЗАСОБІВ У ВІЙСЬКОВИХ ПІДРОЗДІЛАХ
2.1 Змістовна постановка задачі
Військовий логіст наносить на карту військові частини та військові склади трьох рівнів: стратегічний, тактичний, оперативний. Стратегічні склади є найбільшими складами, вони доставляють ресурси у тактичні склади. Тактичні склади є середніми складами, вони доставляють ресурси у оперативні склади.
Оперативні склади є найменшими складами, вони доставляють ресурси у військові частини, які в свою чергу є кінцевими споживачами ресурсів. Кожен склад має в своєму розпорядженні транспортні засоби, які забезпечують перевезення військових ресурсів у менші склади або частини. Кожен транспортний засіб може відвідати один або більше складів (частин). Кожен рівень складів відрізняється обсягом військових ресурсів, які можуть на ньому зберігатися та розміром транспортних засобів. Постає задача у пошуку необхідної кількості транспортних засобів для кожного складу та множини маршрутів перевезення, які мінімізують сумарний час затримки та витрати палива на доставку до військових частин та складів.
Вхідні дані:
координати військових складів різних рівнів;
координати військових частин;
військове устаткування, що зберігається на складах;
автопарк, що знаходиться біля військових складів;
замовлення у військові частини;
дороги між військовими складами та частинами;
глибина генетичного алгоритму (точність).
Вихідні дані:
списки маршрутів для виконання військових замовлень;
загальні витрати палива;
загальний час затримки замовлень.
2.2 Математична модель Дано:
B1 – кількість оперативних складів;
B2 – кількість тактичних складів;
B3 – кількість стратегічних складів;
B4 – кількість військових частин;
G – список зв’язків між складами різних рівнів та військовими частинами;
N1 i – кількість замовлень для оперативних складів ; N2 i – кількість замовлень для тактичних складів ; N3 i– кількість замовлень стратегічних складів ; N4 i – кількість замовлень для військових частин ;
M1 i – кількість маршрутів для i-ого оперативного складу ; M2 i – кількість маршрутів для i-ого тактичного складу ; M3 i – кількість маршрутів для i-ого стратегічного складу ;
E1 i – кількість транспортних засобів для i-ого оперативного складу ; E2 i – кількість транспортних засобів для i-ого тактичного складу ;
E3 i – кількість транспортних засобів для i-ого стратегічного складу ; C1 i,j
– вміст i-ої машини по вазі для j-ого оперативного складу, ;
;
C2 i,j – вміст i-ої машини по вазі для j-ого оперативного складу, ;
;
C3 i,j – вміст i-ої машини по вазі для j-ого оперативного складу, ;
;
W1 i,j,– загальна вага i-ого замовлення для j-ого оперативного складу,
;
W2 i,j,– загальна вага i-ого замовлення для j-ого тактичного складу,
;
W3 i,j,– загальна вага i-ого замовлення для j-ого стратегічного складу,
;
O1 j,i –кількість замовлень для i-ого маршруту, j-ого оперативного складу ;
;
O2j,i – кількість замовлень для i-ого маршруту, j-ого тактичного складу ;
;
O3 j,i – кількість замовлень для i-ого маршруту, j-ого стратегічного складу
; ;
O4 j,i – кількість замовлень для i-ого маршруту, j-ого стратегічного складу
; ;
ti– директивний час доставки i-ого замовлення, ; Ti - фактичний час доставки i-ого замовлення, ;
ki – пройдений шлях i-ого маршруту , ; α – коефіцієнт важливості витрат палива;
(1- α) – коефіцієнт важливості вчасної доставки замовлень;
zi – час затримки i-ого замовлення, (Якщо ti ≥ Ti , то zi = 0, інакше ).
Обмеження:
- обмеження для замовлень оперативних складів.
- обмеження для замовлень тактичних складів.
- обмеження для замовлень стратегічних складів.
- кількість маршрутів для оперативних складів може бути більшою за кількість доступних транспортних засобів.
; - кількість маршрутів для тактичних складів може бути більшою за кількість доступних транспортних засобів.
- кількість маршрутів для стратегічних складів може бути більшою за кількість доступних транспортних засобів.
Тоді цільова функція рішення задачі транспортних перевезень матеріальних засобів у військових підрозділах буде виглядати таким чином:
(2.1)
Цільова функція моделювання цієї задачі можна представити в формальному вигляді:
(2.2) де – , є цільовою функцією;
F – алгоритм імітації;
X – змінні моделі:
P – вхідні параметри:
2.3 Огляд методів розв’язання
Дана задача належить до класу NP-повних, а це означає, що обчислювальна складність залежить від розмірів вхідних даних експоненціально.
Усі алгоритми які здатні вирішувати NP-повні задачі поділяються на точні підходи, евристичні методи та мета-евристичні методи.
Точні підходи перебирають всі можливі рішення, поки не буде знайдено оптимальне. У евристичних методах здійснюється відносно обмежений пошук по простору рішень, і зазвичай знаходяться хороші рішення за прийнятний час. У мета-евристичних методах акцент робиться на ретельному вивченні найбільш перспективних частин простору рішень. Якість одержуваних рішень виходить вище, ніж у отриманих класичними евристиками, однак час пошуку рішення може бути набагато більшим.
