Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2016
Hauptverfasser:	Жихаревич, В.В., Мацюк, Н.О.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут економіки промисловості НАН України 2016
Schriftenreihe:	Вісник економічної науки України
Schlagworte:	Наукові статті
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/105895
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму / В.В. Жихаревич, Н.О. Мацюк // Вісник економічної науки України. — 2016. — № 1 (30). — С. 49–54. — Бібліогр.: 12 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-105895
record_format	dspace
spelling	irk-123456789-1058952016-09-13T03:02:44Z Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму Жихаревич, В.В. Мацюк, Н.О. Наукові статті В даній роботі продемонстрована принципова можливість використання модифікованого мурашино- клітинно-автоматного алгоритму при оптимізації маршрутів руху транспортних засобів оптового торговельного підприємства у процесі розвезення продукції. Вирішення цієї проблеми сприятиме зниженню непродуктивних витрат ресурсів підприємств, а значить - підвищенню їх конкурентоспроможності. Для реалізації моделі було використано тестовий приклад з вісьма пунктами-споживачами вантажу та двома транспортними засобами необмеженої вантажопідйомності, які рухаються по дорогах деякого міста. В данной работе продемонстрирована принципиальная возможность использования модифицированного муравьино-клеточно-автоматного алгоритма при оптимизации маршрутов движения транспортных средств оптового торгового предприятия в процессе развозки продукции. Решение этой проблемы будет способствовать снижению непроизводительных затрат ресурсов предприятий, а значит - повышению их конкурентоспособности. Для реализации модели было использован тестовый пример с восемью пунктами-потребителями груза и двумя транспортными средствами неограниченной грузоподъемности, движущимися по дорогам некоторого города. The principal potentiality of using the ant colony optimization algorithm in optimizing the vehicle routs in the process of products delivery was demonstrated in this research. Solution of this problem will contribute to decrease of non-productive resources consumption of enterprises and thus - to increase of their competitiveness. To realize this model the test example with eight locations-consumers of the fright and two transportation means of unlimited carrying capacity moving about a certain city was used. 2016 Article Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму / В.В. Жихаревич, Н.О. Мацюк // Вісник економічної науки України. — 2016. — № 1 (30). — С. 49–54. — Бібліогр.: 12 назв. — укр. 1729-7206 http://dspace.nbuv.gov.ua/handle/123456789/105895 uk Вісник економічної науки України Інститут економіки промисловості НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Наукові статті Наукові статті
spellingShingle	Наукові статті Наукові статті Жихаревич, В.В. Мацюк, Н.О. Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму Вісник економічної науки України
description	В даній роботі продемонстрована принципова можливість використання модифікованого мурашино- клітинно-автоматного алгоритму при оптимізації маршрутів руху транспортних засобів оптового торговельного підприємства у процесі розвезення продукції. Вирішення цієї проблеми сприятиме зниженню непродуктивних витрат ресурсів підприємств, а значить - підвищенню їх конкурентоспроможності. Для реалізації моделі було використано тестовий приклад з вісьма пунктами-споживачами вантажу та двома транспортними засобами необмеженої вантажопідйомності, які рухаються по дорогах деякого міста.
format	Article
author	Жихаревич, В.В. Мацюк, Н.О.
author_facet	Жихаревич, В.В. Мацюк, Н.О.
author_sort	Жихаревич, В.В.
title	Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму
title_short	Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму
title_full	Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму
title_fullStr	Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму
title_full_unstemmed	Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму
title_sort	розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму
publisher	Інститут економіки промисловості НАН України
publishDate	2016
topic_facet	Наукові статті
url	http://dspace.nbuv.gov.ua/handle/123456789/105895
citation_txt	Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму / В.В. Жихаревич, Н.О. Мацюк // Вісник економічної науки України. — 2016. — № 1 (30). — С. 49–54. — Бібліогр.: 12 назв. — укр.
series	Вісник економічної науки України
work_keys_str_mv	AT žiharevičvv rozvâzannâzadačímaršrutizacíízvikoristannâmmodifíkovanogomurašinoklítinnoavtomatnogoalgoritmu AT macûkno rozvâzannâzadačímaršrutizacíízvikoristannâmmodifíkovanogomurašinoklítinnoavtomatnogoalgoritmu
first_indexed	2025-07-07T17:36:21Z
last_indexed	2025-07-07T17:36:21Z
_version_	1837010551677386752
fulltext	ЖИХАРЕВИЧ В. В., МАЦЮК Н. О. 2016/№1 49 трясінь, яких вона зазнала внаслідок економічної та політичної кризи в Україні. Список використаних джерел 1. Кузьменко Р.В. Організаційни та структурні чинники зміни пріоритетів / Р.В. Кузьменко // Стру- ктурні реформи економіки: світовий досвід, інститути, стратегії для України. — Тернопіль: Економічна думка ТНЕУ, 2011. — 848 с. 2. Колодинський С.Б. Структурні трансформації старопромислових регіонів / С.Б. Колодинський, Л.М. Кузьменко, И.В. Хаджинов // Структурні реформи економіки: світовий досвід, інститути, стратегії для України. — Тернопіль: Економічна думка ТНЕУ, 2011. — 848 с. 3. Василенко В.Н. Многомерность параметров региона: территории, системы, пространство: моно- графия / В.Н. Василенко. — Дружковка: ІЕПД НАН України, «ЮГО - ВОСТОК», 2016. — 408 с. 4. Василенко В.Н. Диагностика развития регио- нов: виды, подходы, приемы: могнография / В.Н. Ва- силенко, А.И. Благодарний, А.И. Ватченко и др.; под науч. ред. В.Н. Василенко. — Донецк: «ЮГО- ВОСТОК», 2012. — 558 с. 5. Медвідь В.Ю. Економічне регулювання регіо- нального розвитку: теорія, методологія, практика: мо- нографія / В.Ю. Медвідь: наук. ред. В.Н. Василенко; НАН України Ун-т економіко-правових досліджень. — К.: вид- во «Діса плюс», 2015. — 282 с. 6. Просторовий ровиток регіону: соціально-еко- номічні можливості, ризики і перспективи: моногра- фія / за ред. д.е.н., проф. Л.Т. Шевчук. — Львів: ІРД НАН України, 2011. — 256 с. 7. Смирнов В.В. Парадигма и концепция эффе- ктивного социально — экономического развития ре- гиона / В.В. Смирнов // Регионология. — 2011. — №2. — С.56-63. 8. Кухарская Н.А. Стратегические приоритеты трансформации экономики регионов Украины: тен- денции, формы, механизмы: монография / Н.А Кухар- ская. — Одесса: ИПРЭЭИ НАН Украины, 2010. — 519 с. 9. Монастирський Г.Л. Модернізаційна пара- дигма управління економічним розвитком територіа- льних спільнот базового рівня: монографія / Г.Л. Мо- ностирський. — Тернопіль: Економічна думка ТНЕУ, 2010. — 464 с. 10. Чухно А.А. Становлення еволюційної паради- гми економічних теорій: Твори: У трьох томах / А.А. Чухно. — К.: 2007. — Т. 3. — 217 с. 11. Дубницкий В.И. Парадигма функционирова- ния рыночных процессов в условиях трансформации регионов / В.И. Дубницкий // Трансформация про- мышленного комплекса региона: проблемы управле- ния развитием / под ред. В.И. Дубницкого, И.П. Бу- леева. — Донецк: ДЭГИ, ООО «Юго-Восток, Лтд», 2008. — 548 с. [3.2. — С. 105-130] 12. Пепа Т.В. Сучасна парадигма регіонального розвитку продуктивних сил економічного простору України / Т.В. Пепа. — Черкаси: Вертикаль, 2012. — 526 с. 13. Лазарева Т.С. Обоснование необходимости выравнивания региональных различий (диспропор- ций) / Т.С. Лазарева // Структурные трансформации старопромышленных регионов Украины / ИЭП НАН Украины. — Донецк, 2013. — 412 с. В. В. Жихаревич канд. фіз.-мат. наук Чернівецький національний університет ім. Ю. Федьковича, м. Чернівці, Н. О. Мацюк Буковинський державний фінансово-економічний університет, м. Чернівці РОЗВ’ЯЗАННЯ ЗАДАЧІ МАРШРУТИЗАЦІЇ З ВИКОРИСТАННЯМ МОДИФІКОВАНОГО МУРАШИНО-КЛІТИННО-АВТОМАТНОГО АЛГОРИТМУ Постановка проблеми. Задача маршрутизації транспорту (Vehicle Routing Problem, VRP) представ- ляє собою задачу комбінаторної оптимізації, яка по- лягає у пошуку набору найкоротших маршрутів руху парку транспортних засобів, що розташовані в одному або кількох депо, у процесі розвезення продукції точ- кам-споживачам. При цьому, можуть бути накладені обмеження щодо кількості та вантажопідйомності транспортних засобів, обсягів потреб споживачів, часу доставки тощо. Очевидно, що VRP є узагальненим випадком до- сліджуваної нами раніше [1] задачі комівояжера (Travelling Salesman Problem, TSP), коли попит спожи- вачів приймається ненульовим та існує декілька аген- тів, що рухаються. Такі задачі належать до класу NP- складних, розв’язання яких вимагає значних обчислю- вальних ресурсів, а час пошуку оптимального роз- в’язку залежить від розмірності задачі експоненційно. У зв’язку з цим, при розв’язанні конкретних практич- них завдань такого роду, коли розмірність може дося- гати 100 пунктів і більше, рекомендується застосову- вати наближені методи [2]. Тому на сучасному етапі актуальною є розробка та вдосконалення метаеврис- тичних методів розв’язання комбінаторних задач, до яких належать в тому числі генетичні алгоритми (GA), клітинні автомати (СА) та метод мурашиних колоній (ACO). Дані методи будують свою роботу аналогічно з процесами, які відбуваються у живій природі. Тому в ЖИХАРЕВИЧ В. В., МАЦЮК Н. О. 50 ВІСНИК ЕКОНОМІЧНОЇ НАУКИ УКРАЇНИ деяких джерелах можна зустріти назву «біоінспіровані алгоритми» [3], що з англійської означає — натхненні природою. Аналіз останніх досліджень і публікацій. Незважа- ючи на те, що вказані метаевристичні методи об’єд- нані в один науковий напрям, що має назву «природні обчислення» (Natural Computing), та дозволяють зна- ходити наближені до оптимальних розв’язки комбіна- торних задач за прийнятний час, вони відрізняються як за якістю розв’язків, так і за швидкістю роботи. По- рівняння ефективності використання різноманітних метаевристичних методів для розв’язання комбінатор- них задач здійснене у багатьох працях. І хоча у [4] до- ведено вищу ефективність методів ройового інтелекту (мурашиних та бджолиних алгоритмів) порівняно із GA для розв’язання більшості NP-складних задач, у [5] зазначено, що саме TSP ефективніше розв’язується за допомогою ACO та GA. Дозволимо собі не погоди- тись з цим, оскільки виходячи із своєї природи, му- рахи прагнуть потрапляти в одні і ті самі пункти, тоді як комівояжер не повинен повторно відвідувати жоден пункт, окрім початкового. Такі протиріччя стали при- чиною появи останніми роками все більшої кількості різноманітних комбінацій існуючих методів. Напри- клад, у [6] розроблено гібридний GA розв’язку VRP з обмеженою вантажопідйомністю, який ґрунтується на використанні двох популяцій, деякі особини яких пе- ріодично мігрують. У наведеній роботі зазначається, що такий гібридний GA за своєю ефективністю може змагатися із найкращим методом — пошуком з відмо- вою. Ідея застосування багатопопуляційних GA також розвинена у [7], проте в даній праці якість роботи GA підвищена за допомогою АСО. Аналогічно, у [8] для розв’язання TSP розроблено гібридний алгоритм, суть якого полягає у послідовному використанні операто- рів GA і АСО та інтеграції генетичної інформації у процес побудови шляху агентом АСО, а також дове- дено, що даний алгоритм дозволяє знаходити більш якісні розв’язки, ніж АСО, за той самий час. Мета статті. Огляд існуючої літератури з даної те- матики доводить, що найбільш перспективним є ви- користання не чистих, а комбінованих метаевристич- них методів для розв’язання таких задач, як TSP та VRP. Це логічно, зважаючи на специфіку VRP, яка фактично складається з двох підзадач — задачі пошуку найкоротших відстаней між кожною парою пунктів призначення та задачі комівояжера. Тому метою даної роботи є розробка модифікованого мурашино-клі- тинно-автоматного алгоритму розв’язання VRP з ура- хуванням якості доріг та реальної дорожньої ситуації. Виклад основного матеріалу дослідження. VRP ле- жить на перетині двох добре вивчених задач — TSP та задачі про упакування рюкзаку (Bin Packing Problem, BPP). Існує щонайменше 7 різновидів VRP [9], які відрізняються між собою за ступенем деталізації. Ми розглянемо найбільш загальну варіацію задачі марш- рутизації — Capacitated VRP (CVRP). Вона є розшире- ною версією класичної VRP та ураховує додатковий параметр — обмежену вантажопідйомність транспорт- ного засобу. Тут і далі CVRP будемо згадувати як зви- чайну VRP. Модель VRP включає такі параметри: n — кількість споживачів (пунктів, до яких необ- хідно доставити вантаж); K — вантажопідйомність кожного транспорт- ного засобу; { } 1,i i n D d = = — вектор попиту (обсягу замовлення) споживачів; { } , 0,ij i j n C c = = — матриця вартостей транспорту- вання вантажу між споживачами i та j . Сутність VRP полягає в наступному. Однакові транспортні засоби обмеженої вантажопідйомності K здійснюють доставку продукції з депо 0n до спожива- чів 1 , nn n . Завдання полягає у мінімізації загальних витрат на доставку продукції (або відстаней, що про- ходять всі транспортні засоби). Тобто, необхідно ви- значити набір маршрутів мінімальної загальної варто- сті, що відповідають таким вимогам: − кожен маршрут починається і закінчується у депо; − кожен споживач включається лише в один з маршрутів, оскільки може обслуговуватися лише од- ним транспортним засобом; − сумарний попит споживачів кожного марш- руту не перевищує вантажопідйомності транспортного засобу. Ураховуючи усі введені позначення, VRP може бути формалізована у вигляді зваженого орієнтованого графу ( , )G N A= . Множина вершин N включає множину споживачів C (вершини 1 , nn n ), а також депо 0n . Множина ребер A формується з можливих зв’язків між вершинами. Кожному ребру ( , )i jn n відпо- відає певна вартість перевезень між споживачами i та j , вартість перевезень з будь-якого пункту до цього ж пункту, зрозуміло, нульова 0i ic = . Матриця вартостей (відстаней) є симетричною, коли i j j ic c= . В реальних умовах частіше зустрічаються несиметричні матриці, що пов’язано, наприклад, з існуванням шляхів з одно- стороннім рухом. Множину однакових транспортних засобів, що характеризуються певною вантажопідйом- ністю K , позначимо як V . Кожен споживач, в свою чергу, має певну величину попиту (обсяг його замов- лення) id . Змінною виступає лише одна величина v i jX , яка може набувати двох значень: 1 — якщо транспортний засіб v переїжджає з пункту i до пункту j , 0 — в іншому випадку. Цільова функція VRP виглядає таким чином [10]: ( , ) m in ;v i j i j v V i j A c X ∈ ∈ →  (3) А обмеження, відповідно: 1; ,v i j v V j N X i C ∈ ∈ = ∀ ∈ (4) ; ,v i i j i C j N d X K v V ∈ ∈ ≤ ∀ ∈  (5) 0 1; ,v j j C X v V ∈ = ∀ ∈ (6) 0; ,v v i k k j i N j N X X k C , v V ∈ ∈ − = ∀ ∈ ∀ ∈  (7) { }0 ,1 ,v i jX ∈ ( ), ,i j A∀ ∈ .v V∀ ∈ (8) Обмеження (4) означає, що кожен споживач по- винен бути обслужений лише одним транспортним за- ЖИХАРЕВИЧ В. В., МАЦЮК Н. О. 2016/№1 51 собом. Нерівність (5) встановлює обмеження на ван- тажопідйомність транспортних засобів. Сумарне за- мовлення споживачів, що обслуговуються одним транспортним засобом, не повинне перевищувати його номінальної вантажопідйомності. Обмеження (6) фіксує, що кожний транспортний засіб може виїхати з депо лише один раз. А обмеження (7) означає, що кількості транспортних засобів, що в’їхали та виїхали від споживача чи депо, повинні бути однаковими. Така задача розв’язується у два етапи: − розбиття множини вершин N на m підмно- жин (маршрутів); − визначення послідовності відвідування вер- шин у кожному маршруті. Розв’язок VRP можна зобразити у вигляді графа, що є об’єднанням m орієнтованих циклів вихідного графа G , що мають єдиний перетин у точці 0n (рис. 1). Рис. 1. Представлення розв’язку задачі маршрутизації Під час розв’язання VRP, що описує реальні ви- падки, часто потрібна більша деталізація. Додатко- вими параметрами, що включаються в модель, можуть бути асиметрична матриця відстаней, декілька депо, неоднорідні транспортні засоби, різне часове вікно для кожного споживача. Врахування подібних факторів робить розв’язання даної задачі ще важчим. Двоетапність VRP зумовлює специфічний вибір методів її розв’язання. Зокрема, для розв’язання пер- шого етапу — розбиття множини вершин на підмно- жини та знаходження найкоротших відстаней між усіма вершинами — найбільш ефективним виступає АСО у зв’язку зі здатністю мурах вишукувати оптима- льні шляхи між пунктами. Проте, для розв’язання дру- гого етапу — визначення послідовності відвідування вершин у кожному маршруті, що фактично представ- ляє собою розв’язання TSP, — АСО є малоефектив- ним, що пов’язано із природою мурах, які прагнуть потрапляти в одні і ті самі пункти, в той час, як комі- вояжер не повинен відвідувати один пункт двічі за ви- ключенням депо. Тому, для розв’язання VRP ми про- понуємо використати модифікований мурашино-клі- тинно-автоматний алгоритм. Роботу пропонованого модифікованого мура- шино-клітинно-автоматного алгоритму можна зобра- зити у вигляді блок-схеми (рис. 2). Він працює у два етапи: 1) знаходження наближених до оптимальних шляхів між пунктами, ґрунтуючись на мережі доріг, за допомогою модифікації АСО по аналогії з процесами росту гриба-слизовика; 2) розв’язання задачі відвідування усіх пунктів в межах сформованих маршрутів методом СА. Мурашино-клітинно-автоматний алгоритм роз- в’язання VRP було удосконалено на основі аналогії з процесами росту гриба-слизовика виду Physarum polycephalum [11], який під час пошуку джерела їжі за- вдяки процесу селективного посилення бажаних мар- шрутів і одночасного видалення надлишкових зв’язків здатний формувати ефективні з точки зору вартості, продуктивності та відмовостійкості транспортні ме- режі. Саме цей механізм і став основою модифікації мурашиного алгоритму [12], сутність якої полягає в тому, що мурахи не бігають, як в класичному алго- ритмі, залишаючи за собою феромон, а вишикуються в ланцюжки. Таким чином відтворюється клітинно- автоматний підхід при реалізації алгоритму. Спочатку, за аналогією зі слизовиком, вибудову- ється суцільна мережа мурах, які починають переда- вати одна одній порції «поживних речовин». Імовірність передачі товару від однієї мурахи до іншої визначається так: [ ] [ ] , , , , , ( ) ( ) ( ) , ( ) 0, l k i j i j i j k i l i l i k l J i j k i k t P t t , i f j J P t i f j J , α β α β ∈     τ ⋅ η    = τ ⋅ η ∈   = ∉  (9) де α та β — параметри, які визначаються експеримен- тальним чином. Потім відбувається відмирання неефективних му- рах, тобто таких з них, які більше простоюють без діла, ніж передають порцію товарів (аналог «випаровування феромону»). Визначення ступеня ефективності роботи k-тої мурахи відбувається за такою формулою: , , ( , ) ( ), ( )( ) 0, ( , ) ( ), k ki j k k Q if i j T t L tt i f i j T t  ∈Δτ =   ∉ (10) де ( )kT t — маршрут, що k-та мураха пройшла на t -тій ітерації, довжиною ( )kL t ; Q — регульований пара- метр, значення якого одного порядку із довжиною оп- тимального маршруту. Чим частіше передається товар, тим мураха ефективніше і корисніше. Тобто в ній ніби підвищу- ється рівень феромону, як у класичному мурашиному алгоритмі. Швидкість відмирання не ефективних мурах фо- рмалізується так: ( 1) (1 ) ( ) ( ) ,i j i j i jt p t tτ + = − ⋅ τ + Δ τ (11) де [ ]0,1p ∈ — коефіцієнт випаровування феромону, , 1 ( ) ( ) m ij i j k k t t = Δτ = Δτ , m — кількість мурах в колонії. Тобто, чим менше у мурахи феромону, тим більша ймовірність її смерті. Таким чином відбувається зву- ження широкої мережі в окремі найбільш оптимальні транспортні ланцюжки. Депо Споживачі ЖИХАРЕВИЧ В. В., МАЦЮК Н. О. 52 ВІСНИК ЕКОНОМІЧНОЇ НАУКИ УКРАЇНИ Рис. 2. Блок-схема роботи модифікованого мурашино-клітинно-автоматного алгоритму Результати обчислювального експерименту. Для реалізації модифікованого мурашино-клітинно-авто- матного алгоритму розв’язання VRP було прийнято низку припущень: кількість пунктів призначення, розташованих ви- падковим чином, дорівнює 8; увесь вантаж розвозиться двома транспортними засобами; вантажопідйомність транспортних засобів є дос- татньою, щоб за один маршрут перевезти увесь товар; сумарне замовлення споживачів не перевищує номінальної вантажопідйомності двох транспортних засобів; витрати часу, окрім часу на транспортування, ну- льові, зокрема це час на розвантажувальні роботи та час на обідню перерву (витрати часу на розвантажу- вання продукції можна урахувати шляхом додавання до загального часу деяких усереднених значень цього часу, помножених на кількість пунктів). Зазначені спрощення не виходять за межі основ- ної мети нашого дослідження, якою є демонстрація можливостей мурашино-клітинно-автоматного алго- ритму при розв’язанні VRP. Реалізація мурашино-клітинно-автоматного алго- ритму розв’язання VRP, у нашому випадку, перш за все передбачає представлення транспортної інфра- структури міста у деякому мережевому вигляді (рис.3). Таким чином, задача оптимізації транспортування де- яких вантажів зводиться до пошуку мінімальних від- станей між заданими вузлами мережі. Окрім врахування відстаней між вузлами, в ре- альних ситуаціях, більш корисною є інформація, яка дозволяє мінімізувати час, що витрачається на подо- лання цієї відстані. Він визначається наступними факторами: якість дорожнього покриття; наявність світлофорів та регулярність їх переключення; кількість смуг руху (пропускна спроможність дороги); кількість сторонніх машин у конкретні періоди часу (форму- вання заторів); середній час, який витрачається для здійснення повороту. Окрім перелічених, можна навести ще низку фа- кторів, що залежать від багатьох суб’єктивних та об’єктивних причин (пори року, час доби тощо). У кі- нцевому випадку всі ці фактори можна звести до се- реднього часу подолання конкретної ділянки дороги, що залежить від середньої швидкості на цій ділянці та її довжини. Крім цього, іноді має місце односторонній рух деякою ділянкою дороги, що однозначно впливає на траєкторії руху транспортних засобів. Для аналізу ефективності мурашино-клітинно- автоматного алгоритму при розв’язанні VRP, було зге- неровано модельну інфраструктуру доріг деякого фрагменту міста та пункти, до яких необхідно доста- вити вантаж (рис. 4). Ширина фрагменту — 10 км, ви- сота — 5 км. Окрім цього, прийнято три типи доріг із різними середніми швидкостями їх подолання — 10, 20 Початок Кінець Ініціалізація параметрів та заповнення вузлів мережі мурахами Чи є два неідентичні шляхи між пунктами? ні так Ініціалізація лічильника кількості ітераційних циклів Вибір довільної мурахи та мо- дифікація її стану згідно алго- ритму транспортування Лічильник вичерпано? ні так Заповнення матриці від- станей та якості доріг між пунктами. Формування списків пу- нктів призначення для перевізників Виведення результатів Чи є зміни у списках? ні так Ініціалізація лічильника кількості ітераційних циклів Модифікація списків згідно алго- ритму оптимізації Лічильник вичерпано? ні так ЖИХАРЕВИЧ В. В., МАЦЮК Н. О. 2016/№1 53 та 30 км/год відповідно від світло-сірого до чорного кольорів. Середній час правостороннього повороту для моделі прийнято 10 с, а лівостороннього — 20 с. Також деякі ділянки доріг є дорогами з одностороннім рухом (на рисунках не відмічено цей факт, щоб не пе- ревантажувати зображення). Рис. 3. Приклад формування мережевої структури доріг міста Усі вузли мережевої структури доріг мають свої індекси, а також індекси та типи доріг до найближчих сусідніх вузлів. Пункти призначення згідно розробле- ної моделі розподіляються між двома транспортними засобами найбільш оптимальним чином, а траєкторія руху деякого транспортного засобу зводиться до пере- лічення порядку слідування вузлів мережі. На рисунку 4 показано приклад траєкторій руху двох транспортних засобів за умов мінімальної довжини шляху. Ліва тра- єкторія має загальну довжину 12,25 км із часом подо- лання шляху 1,05 години, а права — 10,45 км із часом 0,85 години. Рис. 4. Приклад траєкторій руху двох транспортних засобів за умов мінімальної довжини шляху (велике коло — депо, дрібні — споживачі) Висновки. Таким чином, в даній роботі була про- демонстрована принципова можливість використання мурашино-клітинно-автоматного алгоритму при роз- в’язанні задачі маршрутизації. Оптимізація маршрутів руху транспортних засобів під час розвезення продук- ції дозволить знизити непродуктивні витрати, що по- зитивно впливатиме на конкурентоспроможність під- приємств. Для реалізації моделі було використано тестовий приклад з вісьма пунктами-споживачами вантажу та двома транспортними засобами необмеже- ної вантажопідйомності, які рухаються по дорогах де- якого міста. Розроблена модель може бути в подаль- шому деталізована шляхом урахування різноманітних параметрів, зокрема обмежень на вантажопідйомність, кількість транспортних засобів, тривалість робочого дня, обсяг замовлення споживачів, час на навантажу- вально-розвантажувальні роботи тощо. Список використаних джерел 1. Мацюк Н.О. Особливості розв’язання задачі комівояжера для підприємств гуртової торгівлі / Н. О. Мацюк // Вісник ХНУ. Економічні науки. — 2013. — №5. — Т.2. — С. 95-100. 2. Bell J. E. Ant Colony Optimization Techniques for the Vehicle Routing Problem / John E. Bell, Patrick R. McMullen // Advanced Engineering Informatics. — 2004. — No.18. — P.41—48. 3. Курейчик В.В. Концепция эволюционных вычислений инспирированных природными вычисле- ниями / В.В. Курейчик, В.М. Курейчик, С.И. Родзин ЗАЙЦЕВ В. Є. 54 ВІСНИК ЕКОНОМІЧНОЇ НАУКИ УКРАЇНИ // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». — Таганрог : Изд- во ТТИ ЮФУ, 2009. — № 4(93) — 256 с. 4. Курейчик В. М. Использование роевого ин- теллекта в решении NP-трудных задач / В. М. Курей- чик, А. А. Кажаров // Известия ЮФУ. Технические науки. — 2011. — №7. — С.30-36. 5. Курейчик В. М. Использование пчелиных ал- горитмов для решения комбинаторных задач / В. М. Курейчик, А. А. Кажаров // Штучний інтелект. — 2010. — №3. — С.583-589. 6. Berger J. A New Hybrid Genetic Algorithm for the Capacitated Vehicle Routing Problem. / J. Berger and M. Barkaoui // Journal of the Operational Research Society. — 2003. — №41(2). — Р. 179-194. 7. Бегляров В. В. Гибридный многопопуля- ционный муравьиный генетический алгоритм / Бе- гляров В. В., Берёза А. Н., Стороженко А. С.// Извес- тия ЮФУ. Технические науки. — 2010. — №7. — С.39- 45. 8. Мартынов А. В. Гибридный алгоритм реше- ния задачи коммивояжера / А. В. Мартынов, В. М. Курейчик // Известия ЮФУ. Технические науки. — 2015. — №4 (165). — С.36-44. 9. Кочегурова Е.А. Оптимизация составления маршрутов общественного транспорта при создании автоматизированной системы поддержки принятия решений / Е.А. Кочегурова, Ю.А. Мартынова // Изве- стия Томского политехнического университета. — 2013. — Т. 323. — № 5. — C.79-84. 10. Bjarnadottir A. S. Solving the Vehicle Routing Problem with Genetic Algorithms / Aslaug Soley Bjarnadottir. — Technical University of Denmark, 2004. — 127 p. 11. Tero A. Rules for Biologically Inspired Adaptive Network Design / Atsushi Tero, Seiji Takagi, Tetsu Saigusa, Kentaro Ito, Dan P. Bebber, Mark D. Fricker, Kenji Yumiki, Ryo Kobayashi, Toshiyuki Nakagaki // Science. — 2010. — Vol. 327. — P. 439—442. 12. Штовба С.Д. Муравьиные алгоритмы / С.Д. Штовба // Exponenta Pro. Математика в приложениях. — 2003. — № 4. — С. 70-75. В. Є. Зайцев канд. екон. наук Університет митної справи та фінансів, м. Дніпропетровськ ВИКОРИСТАННЯ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ ЯК ОСНОВА ЕФЕКТИВНОЇ ІННОВАЦІЙНОЇ ДІЯЛЬНОСТІ ТА ПІДВИЩЕННЯ КОНКУРЕНТНОГО ПОТЕНЦІАЛУ ПІДПРИЄМСТВ Постановка проблеми. Сучасний етап розвитку світової економіки ґрунтується на випереджувальному використанні інформації, знань та технологій. Одним з найвпливовіших користувачів даних складових явля- ється підприємницький сектор, оскільки пожвавлення конкурентної боротьби за споживачів та ринки збуту є водночас і наслідком використання інтелектуального капіталу, і стимулом його застосування. В таких обставинах залучення до господарської діяльності об’єктів права інтелектуальної власності (ОПІВ) стає визначальним фактором забезпечення підприємствами своїх конкурентних переваг. Воло- діння виключними правами на унікальні розробки, ві- домий бренд чи репутацію сьогодні є більш впливовою та прибутковою передумовою успішної діяльності компанії, аніж наявність матеріальних активів. Тому, зважаючи на багатий світовий досвід використання ОПІВ та різноманітність їх видів, підприємницький сектор України потребує глибокого дослідження та пошуку найбільш ефективного, найбільш альтернати- вного методу впровадження і розвитку інтелектуаль- ної власності (ІВ) в господарській діяльності, що є важливим кроком якісного розвитку держави в цілому. Аналіз останніх досліджень і публікацій. Широке використання терміну «інтелектуальна власність» в су- часному законодавстві, науковій літературі та практиці багатьох країн розпочалося в 1967 р., коли у Сток- гольмі була підписана Конвенція про заснування Все- світньої організації інтелектуальної власності (ВОІВ), яка трактує інтелектуальну власність як збірне по- няття, що позначає усі права на результати творчої ді- яльності і деякі прирівняні до них об’єкти. Загалом поняття «інтелектуальна власність» має багато трактувань, що в першу чергу пояснюється ши- роким колом різноманітних об’єктів, які підпадають під його визначення. Більшість економістів трактують інтелектуальну власність як матеріально виражений результат розумової діяльності, який охороняється встановленими нормами і офіційними документами (патентами і т. д.) і надає автору виняткове право на нього, при цьому акцент в даному понятті роблять або на абстрактній природі, втіленні розумових та творчих ідей людини або, навпаки, віддають перевагу правовій природі інтелектуальної власності, тобто виділяють в першу чергу право володіння результатами розумової та творчої діяльності (табл. 1). Метою статті є дослідження світового досвіду за- лучення інтелектуальної власності до господарської ді- яльності підприємницького сектору та обґрунтування її ролі у формуванні конкурентних переваг україн- ських підприємств. Виклад основного матеріалу. Інтелектуальний ка- пітал вважається найбільш важливим активом багатьох найбільших і найбільш потужних світових компаній. Він служить основою для домінування на ринку та за- безпечення постійної прибутковості провідних корпо- рацій. Інтелектуальна власність як одна з основних складових інтелектуального капіталу також привертає все більшу увагу як науковців, так і ділових кіл.

Розв’язання задачі маршрутизації з використанням модифікованого мурашино-клітинно-автоматного алгоритму

Institution

Ähnliche Einträge