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

The method of solving the task of minimum graph way search on the basis of using the modified ant algorithm, in which the length of ribs of bidirectional oriented graph is variable, is offered. The method of local search is used in order to optimize the parameters of probabilistic-proportional searc...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2012
Автори:	Danchuk, V. D., Svatko, V. V.
Формат:	Стаття
Мова:	Українська
Опубліковано:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2012
Онлайн доступ:	https://journal.iasa.kpi.ua/article/view/71975
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	System research and information technologies
Завантажити файл:

Репозитарії

System research and information technologies

_version_	1867334270369923072
author	Danchuk, V. D. Svatko, V. V.
author_facet	Danchuk, V. D. Svatko, V. V.
author_institution_txt_mv	[ { "author": "V. D. Danchuk", "institution": "завідувач кафедри електроніки та обчислювальної техніки Національного транспортного університету, Україна, Київ" }, { "author": "V. V. Svatko", "institution": "аспірант кафедри електроніки та обчислювальної техніки Національного транспортного університету, Україна, Київ" } ]
author_sort	Danchuk, V. D.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2018-03-30T15:05:06Z
description	The method of solving the task of minimum graph way search on the basis of using the modified ant algorithm, in which the length of ribs of bidirectional oriented graph is variable, is offered. The method of local search is used in order to optimize the parameters of probabilistic-proportional search of minimum ribs distance for a graph.
first_indexed	2025-07-17T10:20:24Z
format	Article
fulltext	© В.Д. Данчук, В.В. Сватко, 2012 78 ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 УДК 656.013 ОПТИМІЗАЦІЇ ПОШУКУ ШЛЯХІВ ПО ГРАФУ В ДИНАМІЧНІЙ ЗАДАЧІ КОМІВОЯЖЕРА МЕТОДОМ МОДИФІКОВАНОГО МУРАШИНОГО АЛГОРИТМУ В.Д. ДАНЧУК, В.В. СВАТКО Запропоновано метод розв’язку задачі пошуку мінімального шляху по графу на основі застосування модифікованого мурашиного алгоритму, в якому дов- жина ребер двонаправленого орієнтованого графу — змінна величина. З метою оптимізації параметрів імовірнісно-пропорційного пошуку мінімальної дов- жини ребер по графу використовується метод локального пошуку. На сьогодні характерною особливістю переходу людства до інформаційного суспільства є надзвичайно швидкі трансформаційні зміни поколінь техноло- гій, споживчих стандартів, ринків виробництва та збуту товарів. Тому в су- часних умовах підприємства, які займають те або інше місце на економіч- ному ринку праці, являють собою динамічні, нестаціонарні системи. Нині ефективність функціонування більшості підприємств визначаєть- ся рівнем застосування логістики. Логістика посідає значне місце під час перебудови механізмів господарювання в сучасних ринкових умовах. Потрібно також зазначити, що задачі маршрутизації є ключовими в га- лузі транспортних перевезень та логістики. Відомо [1, 2], що в більшості сегментів ринку доставка товару додає до його вартості суму, яка прирівню- ється до вартості самого товару. Поряд із цим зауважимо, що використання комп’ютерних методів оптимізації такої доставки виражається економією часто не менше 5–20 % від загальної його вартості. Проте до теперішнього часу існуючі методи розв’язання задач дискрет- ної оптимізації процесів, що відбуваються в логістичних системах, не є дос- коналими і не дають однозначних рішень [3, 4]. Також останнім часом розробляються принципово нові наукові підходи розв’язку задач дискретної оптимізації, які базуються на використанні квазі- інтелектуальних методів. Так, наприклад, вважається перспективним застосування для розв’язку транспортних задач та задач складської логістики квазіінтелектуальних ме- тодів оптимізації, зокрема методу, який базується на механізмах самооргані- зації поведінки мурашиної колонії [5–7]. ПОСТАНОВКА ЗАДАЧІ Для перевірки коректності застосування відповідних методів, що розробля- ються, часто використовується задача комівояжера, як одна з найрепрезен- тативніших транспортних задач. За умовою цієї задачі необхідно обійти всі вузли з доставки товару та повернутися у вихідне положення. При цьому довжина шляху має бути найкоротшою. Тут довжина маршруту буде зале- Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом… Системні дослідження та інформаційні технології, 2012, № 2 79 жати від порядку обходу. Кількість варіантів обходу надзвичайно велика навіть за невеликої кількості вузлів. Відомо [6, 8], що за допомогою методів, які базуються на описі поведінки мурашиних колоній, вирішують складні комбінаторні задачі, не зважаючи на те, що окремо кожна мураха веде себе досить просто, рух якої можна описати аналітично. Саме тому моделювання поведінки мурашиної колонії вважається перспективним у вирішенні транс- портних проблем. Мета роботи — розробка ефективного методу оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом модифікованого мурашиного алгоритму. ОСНОВНА ЧАСТИНА Задача комівояжера — одна з основних задач комбінаторної оптимізації, що має широке прикладне застосування. Фактично не існує алгоритмів, що за- безпечують одержання якісних її розв’язків особливо при малих часових затратах [4]. Задачу комівояжера можна представити як задачу мінімізації витрат, в якій цільовою функцією будуть транспортні витрати, що знаходяться в прямій залежності від довжини пройденого шляху (маршруту). Саме тому цільовою функцією може бути сумарна довжина пройденого шляху. Автоматизація задачі комівояжера на сьогодні вирішена не повністю, у зв’язку з тим, що методи, які застосовуються для її розв’язку неефективні. Результатом постійного пошуку найефективніших методів розв’язку задачі комівояжера стало використання біонічних алгоритмів, у тому числі, еволюційних та генетичних [9, 10]. Відмінністю мурашиних алгоритмів є їх робота з набором альтернативних розв’язків та часткова незалежність від конкретного виду цільової функції. Результати деяких експериментальних досліджень довели високу продуктивність цих алгоритмів, а на деяких конт- рольних прикладах — їх беззаперечну перевагу над існуючими методами. Нехай локальні правила поведінки мурах при виборі маршруту опису- ються таким чином [11]: • Мурахи мають власну «пам’ять». Оскільки кожне місто може бути відвідане лише один раз, то в кожної мурахи є список вже відвіданих міст — список заборон. Нехай kiJ . — список міст, які необхідно відвідати мураши- ному агенту k, що знаходиться в місті і. • Мурахи мають «зір» — видимість є евристичним бажанням відвідати місто j, якщо мураха знаходиться в місті і. Вважатимемо, що видимість зво- ротно пропорційна відстані між містами ijij D1=η . • Мурахи здатні розпізнавати запахи. Вони можуть відчувати слід фе- ромону, що підтверджує бажання відвідати місто j з міста і на основі досвіду інших мурах. Кількість феромону на ребрі ),( ji у момент часу t позначимо через ).(tijτ • На основі цього можна сформулювати ймовірнісно-пропорційне правило, яке визначає ймовірність переходу k-ї мурахи з міста i у місто j : В.Д. Данчук, В.В. Сватко ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 80 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ∉= ∈= ∑ ∈ ,,0)( ,, ][)]([ ][)]([ )( ,, ,, . kikij ki Jl ilil ijij kij JjtP Jj t t tP ki βα βα ητ ητ (1) де βα , — параметри, що задають ваги сліду феромону; при 0=α алгоритм вироджується до жадібного алгоритму (буде обране найближче місто). Під час виконання алгоритму, який описується формулами (1–4), пра- вило (1) не змінюється, але у двох різних мурах значення ймовірності пере- ходу будуть відрізнятися, тому що вони мають різний список дозволених міст. • Пройшовши ребро ,),( ji мураха відкладає на ньому деяку кількість феромону, яка має бути пов’язана з оптимальністю зробленого вибору. Не- хай )(tТk — шлях, який пройшла мураха k до моменту часу t , )(tLk — довжина цього шляху, а Q — параметр, що має значення порядку довжини оптимального шляху. У цьому випадку кількість відкладеного феромону може бути задано у вигляді: ⎪⎩ ⎪ ⎨ ⎧ ∉ ∈ =∆ ).(),(,0 ),(),(, )()(, tTji tTji tL Q t k k kkijτ (2) Правила навколишнього середовища визначають, у першу чергу, випа- ровування феромону. Нехай ]1,0[∈p є коефіцієнтом випаровування, тоді правило випаровування матиме вигляд: ∑ = ∆=∆∆+−=+ m k kijijijijij ttttpt 1 , ),()();()()1()1( τττττ (3) де m — кількість мурах у колонії. На початку розв’язку кількість феромону на ребрах прийматиметься рівною невеликій кількості. Загальна кількість мурах залишається постійною та рівною кількості міст. Кожна мураха починає маршрут зі свого міста [11]. Додаткова модифікація алгоритму можлива у випадку введення так званих «елітних» мурах, котрі підсилюють ребра найкращого маршруту, знайденого на початку роботи алгоритму. Позначимо через ∗Т найкращий поточний шлях через ∗L — його довжину. Тоді, якщо в колонії є е елітних мурах, то ребра маршруту отримають додаткову кількість феромону .∗=∆ LQeeτ (4) Багаторазовість взаємодії реалізується ітераційним пошуком маршруту комівояжера одночасно декількома мурахами згідно з [12]. З метою підви- щення ефективності застосування методу мурашиного алгоритму для розв’язку задачі комівояжера запропоновано його модифікацію, пов’язану із застосуванням оптимізації управляючих параметрів ),,( ρβα шляхом вико- ристання методу локального пошуку. Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом… Системні дослідження та інформаційні технології, 2012, № 2 81 Інтерпретуючи задачу комівояжера до реальних обставин, можна сказа- ти, що цільовою функцію є найкоротший знайдений маршрут. Кількість місць призначення (а в реальній задачі йдеться про склади або супермаркети з доставки товарів) змінюється в залежності від потреби від 5 до 15. Таким чином кількість вершин графу визначає кількість складів, які необхідно від- відати транспортному засобу для того, щоб доставити товар. Окрім того, місце виїзду та повернення транспортного засобу може відбуватись з будь- якого складу. Тому кількість вершин графу збігається з кількістю складів, в які необхідно розвезти товар, а ребра між цими вершинами являють собою відстані між цими складами. Отже, отримуємо матрицю відстаней визначе- ної розмірності. У такому вигляді ми можемо говорити про класичну задачу комівояжера. Також відомо, що під час розрахунку витрат палива для транспортних засобів враховується велика кількість параметрів, що залежать від пройде- ного шляху. Під час розрахунку використання палива ключову роль відіграє кілометраж. Проте для деяких видів товару головним є час його доставки. У таких випадках цільовою функцією є мінімізація відповідних витрат часу. До того ж, зменшення часу роботи транспорту зменшує витрати палива. Та- кож важливе значення відіграє реальна ситуація на дорогах (аварії, затори тощо), яка може суттєво впливати на швидкість переміщення транспорту, а значить і на час доставки товару. Отже, ми можемо сформулювати дина- мічну задачу щодо оптимізації пошуку відстаней по графу, де роль довжин ребер графу відіграє час проходу від одного вузла до іншого. При цьому па- раметр часу є змінною величиною, який залежить від реальної швидкості руху транспорту. В якості тестової системи використовувалась робоча станція з процесо- ром Intel® Celeron® D CPU 3.06 ГГц та 512 МБ оперативної пам’яті. У ме- жах запропонованого алгоритму розроблено програмний комплекс на мові Delphi 7. Перед початком запуску роботи алгоритму приймаються такі умови: • кількість вершин графу дорівнює кількості мурах; • кожна мураха починає свій шлях з іншої вершини; • інтенсивність феромону, відкладеного на кожному ребрі до початку руху мурах однакова; • вибір першої вершини для кожної мурахи визначається за правилом «іди в найближчу»; • кожен наступний крок переміщення мурах визначається за ймовір- нісним рівнянням. Побудова маршруту транспортного засобу здійснюється покроково шляхом вибору наступного пункту до того часу, доки не будуть пройдені всі міста. З самого початку маршрут починається з міста, а його список пройде- них міст порожній. Мураха обирає наступне місто зі списку доступних, піс- ля чого оновлюється цільова функція, тобто пройдена відстань. Після чого знову здійснюється вибір наступного доступного міста. Мураха повертається у вихідне місто, у випадку проходження всіх міст. Сумарна довжина маршруту розраховується як значення цільової функції повного маршруту, пройденого мурахою. Алгоритм мурашиних колоній будує повний маршрут В.Д. Данчук, В.В. Сватко ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 82 для поточної мурахи, перед тим як наступна мураха почне свій рух. Це про- довжується до того часу, доки раніше визначена кількість мурах не побудує свої маршрути. Для проведення порівняльного аналізу визначеної задачі в роботі вико- ристовувались реальні дані про місця розташування складів, транспортні засоби, відстані між цими об’єктами, а також середні швидкості. Алгоритм мурашиної колонії було застосовано для пошуку найкоротшого шляху, а також для пошуку найшвидшого шляху під час доставки товарів до покупців. Матриця відстаней між складами та підприємством ЗАТ «Птахофабри- ка Київська» наведені в табл. 1. Т а б л и ц я 1 . Матриця відстаней між складами та ЗАТ «Птахофабрика Київська» (у км) Склади ЗА Т « П та хо ф аб - ри ка К иї вс ьк а» 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ЗАТ «Птахофабрика Київська» 0 17 16 28 17 23 19 25 15 32 16 34 15 25 30 1 17 0 15 20 5 6 2 23 8 15 15 16 10 9 15 2 16 15 0 16 10 21 17 14 13 22 1 24 15 17 20 3 28 20 16 0 25 21 18 2 28 6 16 8 30 13 8 4 17 5 10 25 0 11 7 28 3 20 10 21 5 14 20 5 23 6 21 21 11 0 3 24 14 16 21 17 16 10 16 6 19 2 17 18 7 3 0 21 10 13 17 14 12 7 13 7 25 23 14 2 28 24 21 0 31 7 14 9 32 15 9 8 15 8 13 28 3 14 10 31 0 23 13 24 8 10 15 9 32 15 22 6 20 16 13 7 23 0 22 2 25 9 4 10 16 15 1 16 10 21 17 14 13 22 0 24 10 16 21 11 34 16 24 8 21 17 14 9 24 2 24 0 25 7 3 12 15 10 15 30 5 16 12 32 8 25 10 25 0 18 24 13 25 9 17 13 14 10 7 15 10 9 16 7 18 0 6 14 30 15 20 8 20 16 13 9 15 4 21 3 24 6 0 Відстані між об’єктами є постійними та не змінюються з часом. Граф середніх швидкостей містить інформацію про середню швидкість між двома пунктами призначення (рис. 1). Сам рух із однієї точки в іншу складається з декількох частин різної довжини та різної швидкості. Таким чином, на основі цих даних можна визначити середню швидкість між пунктами призначення. Середні швидкості між двома пунктами доставки товару є змінною ве- личиною, яка враховує реальну ситуацію на автомобільних шляхах. Тому довжина ребер двонаправленого орієнтованого графу середніх швидкостей є також змінною величиною, а сам граф, враховуючи реальну обстановку на дорогах, змінюється з часом. Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом… Системні дослідження та інформаційні технології, 2012, № 2 83 Як приклад, на рис. 2 показано визначення середніх швидкостей між пунктами ЗАТ «Птахофабрика Київська» та склад 1. Тут шлях, що сполу- чає ці пункти, розбивається на п’ять ділянок різної довжини, на яких транспорт має різні середні швидкості. При цьому треба зауважити, що середні значення швидкостей руху транспорту вибирались реальними на основі даних, отриманих за допомогою програмного комплексу GLOBUS. Таким чином будувалась матриця середніх швидкостей між складами підприємства ЗАТ «Птахофабрика Київська», які наведено в табл. 2. У випадку мінімізації часових витрат на доставку товару цільовою функцією буде мінімізація витрат часу під час проходження визначеного маршруту. Тому, маючи дані про довжини шляхів, що сполучають склади підприємства, а також середні швидкості руху по цих ділянках, ми можемо побудувати відповідну матрицю часових витрат (табл. 3). Визначення часових витрат виконано за такою формулою: 60 υ lt = , (5) де t — час, затрачений на проходження маршруту, хв; l — довжина марш- руту, км; υ — середня швидкість руху транспортного засобу, км/год. Для більшої наочності час будемо визначати у хвилинах. 1 2 11,υl 22 ,υl 44 ,υl 55 ,υl 33 ,υl 1 2 5 км 1 км 3 км 7 км 1 км 60 км/год 15 км/год 55 км/год 60 км/год 25 км/год 1 2 17 км 54 км/год Рис. 2. Визначення середніх швидкостей між пунктами призначення: 1 — ЗАТ «Птахофабрика Київська», 2 — склад 1 1 2 3 5 4 12l 23l 34l 45l 13l 14l 15l 24l25l 35l 12υ 23υ 34υ 45υ 13υ 14υ 15υ 24υ25υ 35υ 12t 23t 34t 45t 13t 14t 15t 24t25t 35t а б в Рис. 1. Двонаправлено орієнтовані графи: а — відстані між об’єктами; б — середні швидкості між об’єктами; в — часові затрати між об’єктами В.Д. Данчук, В.В. Сватко ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 84 Т а б л и ц я 2 . Матриця середніх швидкостей між складами та ЗАТ «Пта- хофабрика Київська» (у км/год) Cклади ЗА Т « П та хо ф аб ри ка К иї вс ьк а» 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ЗАТ «Птахофабрика Київська» 0 54 49 44 47 44 45 25 15 32 45 44 36 25 30 1 54 0 38 55 51 52 53 48 46 55 58 58 51 44 40 2 49 38 0 49 56 38 45 58 38 36 39 42 45 56 45 3 44 55 49 0 52 49 53 55 43 57 46 51 55 58 48 4 47 51 56 52 0 55 58 50 41 43 43 51 47 59 58 5 44 52 38 49 55 0 42 49 47 57 45 52 56 45 51 6 45 53 45 53 58 42 0 55 59 54 54 55 55 43 51 7 25 48 58 55 50 49 55 0 44 49 45 50 40 41 45 8 15 46 38 43 41 47 59 44 0 53 54 43 51 56 57 9 32 55 36 57 43 57 54 49 53 0 45 45 47 52 53 10 45 58 39 46 43 45 54 45 54 45 0 56 54 43 45 11 44 58 42 51 51 52 55 50 43 45 56 0 56 59 60 12 36 51 45 55 47 56 55 40 51 47 54 56 0 33 45 13 25 44 56 58 59 45 43 41 56 52 43 59 33 0 57 14 30 40 45 48 58 51 51 45 57 53 45 60 45 57 0 У табл. 4 наведено результати проведених авторами тестових досліджень застосування модифікованого мурашиного алгоритму для розв’язку задачі комівояжера щодо пошуку мінімальних витрат на доставку товару за крите- рієм відстаней та часів руху транспорту між вузлами, залежно від загаль- ної кількості вузлів. При цьому зауважимо, що у випадку пошуку найкоротшого шляху (мі- німізація довжини обходу вершин) не приймається до уваги час обходу за- значених вершин. Проведені тестові обчислення вказують на те, що при мі- німізації відстані між об’єктами час обходу їх може бути досить великим. Тобто, час роботи транспорту суттєво збільшується, і як результат — збіль- шуються витрати на доставку цього товару. Тому вважаємо доцільним здійснювати також пошук шляху за критерієм мінімізації часових витрат на доставку товару. Слід відмітити, що під час мінімізації часових витрат, дов- жина отриманого маршруту дещо більша за довжину маршруту при мінімі- зації самої довжини маршруту (табл. 4). Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом… Системні дослідження та інформаційні технології, 2012, № 2 85 Т а б л и ц я 3 . Матриця часових затрат між складами та ЗАТ «Птахофаб- рика Київська» (у хв) Склади ЗА Т « П та хо ф аб - ри ка К иї вс ьк а» 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ЗАТ «Птахофабрика Київська» 0 19 20 38 22 31 25 60 60 60 21 46 25 60 60 1 19 0 24 22 6 7 2 29 10 16 16 17 12 12 23 2 20 24 0 20 11 33 23 14 21 37 2 34 20 18 27 3 38 22 20 0 29 26 20 2 39 6 21 9 33 13 10 4 22 6 11 29 0 12 7 34 4 28 14 25 6 14 21 5 31 7 33 26 12 0 4 29 18 17 28 20 17 13 19 6 25 2 23 20 7 4 0 23 10 14 19 15 13 10 15 7 60 29 14 2 34 29 23 0 42 9 19 11 48 22 12 8 60 10 21 39 4 18 10 42 0 26 14 33 9 11 16 9 60 16 37 6 28 17 14 9 26 0 29 3 32 10 5 10 21 16 2 21 14 28 19 19 14 29 0 26 11 22 28 11 46 17 34 9 25 20 15 11 33 3 26 0 27 7 3 12 25 12 20 33 6 17 13 48 9 32 11 27 0 33 32 13 60 12 18 13 14 13 10 22 11 10 22 7 33 0 6 14 60 23 27 10 21 19 15 12 16 5 28 3 32 6 0 Т а б л и ц я 4 . Порівняльний аналіз пошуку мінімальних затрат під час розв’язку задачі комівояжера Матриця часових затрат Матриця відстаней К іл ьк іс ть в ер ш ин За тр ач ен ий ч ас , х в Д ов ж ин а, к м Маршрут Д ов ж ин а, к м За тр ач ен ий ч ас , х в Маршрут 5 90 74 5→1→3→4→2→5 74 90 5→1→3→4→2→5 7 99 81 6→7→4→3→1→5→2→6 80 100 7→2→5→1→3→4→6→7 3→1→5→9→2→7→6→10→4→ 9→5→2→7→6→10→4→8→ 10 101 87 →8→3 82 135 →3→1→9 6→2→5→9→13→1→11→3→8→ 4→12→10→6→7→2→9→5→ 13 118 95 4→10→12→7→6 95 119 →13→1→11→3→8→4 1→2→7→6→13→5→9→14→15→ 10→12→14→2→6→7→9→5→ 15 133 127 10→12→8→4→11→3→1 108 140 13→1→11→3→4→8→15→10 В.Д. Данчук, В.В. Сватко ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 86 Таким чином, аналіз результатів розрахунків показав (табл. 4), що в низці випадків оптимізації пошуку довжини по графу за критерієм відста- ней витрати часу на доставку товару можуть бути більшими, ніж ті, які отримано під час оптимізації пошуку довжини по графу за критерієм часу. Також час доставки товару є досить важливим параметром, оскільки в більшості випадків саме час роботи транспорту визначає відповідні витрати. ВИСНОВКИ Отже, на прикладі конкретного підприємства проведено кількісний порівняльний аналіз результатів застосування зазначених методів дискретної оптимізації процесів розподіленої складської логістики, а саме, процесів доставки това- рів за допомогою транспортних засобів на склади підприємства. Результати аналізу вказують на ефективність використання запропонованого підходу. Крім того, врахування змінної довжини ребер графу дозволяє розв’язувати відповідні логістичні задачі в умовах реального стану руху транспорту по автомобільним дорогам. Отримані результати також вказують на перспективність застосування мурашиного алгоритму до розв’язку задач транспортної логістики, що мають велику розмірність вхідних даних. ЛІТЕРАТУРА 1. Ковалев В.П. Эффективность грузовых автомобильных перевозок: Состояние, проблемы, перспективы. — Мн.: Беларусь, 1984. — 112 c. 2. Гаджинский А.М. Логистика: учеб. для высш. и средних специальных учеб. за- ведений. — М.: ИВЦ «Маркетинг». — 2000. — 375 с. 3. Просветов Г.И. Математические методы в логистике. — М.: РДЛ, 2006. — 272 с. 4. Левитин А.В. Метод грубой силы: Задача коммивояжера // Алгоритмы: введе- ние в разработку и анализ (Introduction to The Design and Analysis of Algo- rithms). — М.: Вильямс, 2006. — [Гл. 3]. — С. 159–160. 5. Dorigo M. Optimization, Learning and Natural Algorithms. PhD Thesis, Diparti- mento di Elettronica, Politechnico Di Milano. — Italy. — 1992. — 140 p. 6. Чураков М., Якушев А. Муравьиные алгоритмы. — 2006. — http://rain.ifmo. ru/cat/data/theory/unsorted/ant-algo-2006/article.pdf. 7. Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a Colony of Cooperating Agents // IEEE Transaction on Systems. Man and Cybernetics. Part B. — 1996. — № 1. — 26. — P. 29–41. 8. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях. — 2003. — № 4. — С. 70–75. 9. Cantu-Paz E. Efficient and Accurate Parallel Genetic Algorithms. — Lawrence Limermore National Lab, 2000. — 167 р. 10. Gaber J., Bakhouya M. An Immune Inspired-based Optimization Algorithm: Appli- cation to the Traveling Salesman Problem // Advanced Modeling and Optimiza- tion. — 2007. — 9. — № 1. — Р. 105–116. 11. Стороженко А.С., Береза А.А. Применение муравьиного алгоритма для реше- ния задачи коммивояжера // Междунар. науч.-практ. интернет-конф., ап- рель–июнь. — 2006. — С. 56–59. 12. Goss S., Aron S., Deneubourg J.L. and Pasteels J.M. Self-organized shortcuts in the Argentine // Springer Online Journal Archives 1860-2000. — 1989. — 76. — Р. 579–581. Надійшла 10.06.2010
id	journaliasakpiua-article-71975
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:20:24Z
publishDate	2012
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/76/9a6a277c857550833538d02116356f76.pdf
spelling	journaliasakpiua-article-719752018-03-30T15:05:06Z Optimization of ways search by a graph in the dynamic task of traveling salesman by the method of the modified ant algorithm Оптимизации поиска путей по графу в динамической задаче коммивояжера методом модифицированного муравьиного алгоритма Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом модифікованого мурашиного алгоритму Danchuk, V. D. Svatko, V. V. The method of solving the task of minimum graph way search on the basis of using the modified ant algorithm, in which the length of ribs of bidirectional oriented graph is variable, is offered. The method of local search is used in order to optimize the parameters of probabilistic-proportional search of minimum ribs distance for a graph. Предложен метод решения задачи поиска минимального пути графа на основании применения модифицированного муравьиного алгоритма, в котором длина ребер двунаправленого ориентированного графа — переменная величина. С целью оптимизации параметров вероятностно-пропорционального поиска минимальной длины ребер по графу используется метод локального поиска. Запропоновано метод розв’язку задачі пошуку мінімального шляху по графу на основі застосування модифікованого мурашиного алгоритму, в якому довжина ребер двунаправленого орієнтованого графу — змінна величина. З метою оптимізації параметрів імовірнісно-пропорційного пошуку мінімальної довжини ребер по графу використовується метод локального пошуку. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2012-06-27 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/71975 System research and information technologies; No. 2 (2012); 78-86 Системные исследования и информационные технологии; № 2 (2012); 78-86 Системні дослідження та інформаційні технології; № 2 (2012); 78-86 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/71975/66948 Copyright (c) 2021 System research and information technologies
spellingShingle	Danchuk, V. D. Svatko, V. V. Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом модифікованого мурашиного алгоритму
title	Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом модифікованого мурашиного алгоритму
title_alt	Optimization of ways search by a graph in the dynamic task of traveling salesman by the method of the modified ant algorithm Оптимизации поиска путей по графу в динамической задаче коммивояжера методом модифицированного муравьиного алгоритма
title_full	Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом модифікованого мурашиного алгоритму
title_fullStr	Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом модифікованого мурашиного алгоритму
title_full_unstemmed	Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом модифікованого мурашиного алгоритму
title_short	Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом модифікованого мурашиного алгоритму
title_sort	оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом модифікованого мурашиного алгоритму
url	https://journal.iasa.kpi.ua/article/view/71975
work_keys_str_mv	AT danchukvd optimizationofwayssearchbyagraphinthedynamictaskoftravelingsalesmanbythemethodofthemodifiedantalgorithm AT svatkovv optimizationofwayssearchbyagraphinthedynamictaskoftravelingsalesmanbythemethodofthemodifiedantalgorithm AT danchukvd optimizaciipoiskaputejpografuvdinamičeskojzadačekommivoâžerametodommodificirovannogomuravʹinogoalgoritma AT svatkovv optimizaciipoiskaputejpografuvdinamičeskojzadačekommivoâžerametodommodificirovannogomuravʹinogoalgoritma AT danchukvd optimízacíípošukušlâhívpografuvdinamíčníjzadačíkomívoâžerametodommodifíkovanogomurašinogoalgoritmu AT svatkovv optimízacíípošukušlâhívpografuvdinamíčníjzadačíkomívoâžerametodommodifíkovanogomurašinogoalgoritmu

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

Репозитарії

Схожі ресурси