АНАЛІЗ ЕФЕКТИВНОСТІ МЕТОДІВ ОПТИМІЗАЦІЇ ДЛЯ ВИРІШЕННЯ ПРОБЛЕМИ ПРОДАВЦЯ, ЩО ПОДОРОЖУЄ

Autor: Natalia Christine, Chandra Agung
Rok vydání: 2021
Předmět:
Zdroj: Сучасний стан наукових досліджень та технологій в промисловості, Iss 1 (15) (2021)
Innovative Technologies and Scientific Solutions for Industries; No. 1 (15) (2021): Innovative Technologies and Scientific Solutions for Industries; 69-75
Современное состояние научных исследований и технологий в промышленности; № 1 (15) (2021): Современное состояние научных исследований и технологий в промышленности; 69-75
Сучасний стан наукових досліджень та технологій в промисловості; № 1 (15) (2021): Сучасний стан наукових досліджень та технологій в промисловості; 69-75
ISSN: 2524-2296
2522-9818
DOI: 10.30837/itssi.2021.15.069
Popis: The subject of this research is distance and time of several city tour problems which known as traveling salesman problem (tsp). The goal is to find out the gaps of distance and time between two types of optimization methods in traveling salesman problem: exact and approximate. Exact method yields optimal solution but spends more time when the number of cities is increasing and approximate method yields near optimal solution even optimal but spends less time than exact methods. The task in this study is to identify and formulate each algorithm for each method, then to run each algorithm with the same input and to get the research output: total distance, and the last to compare both methods: advantage and limitation. Methods used are Brute Force (BF) and Branch and Bound (B&B) algorithms which are categorized as exact methods are compared with Artificial Bee Colony (ABC), Tabu Search (TS) and Simulated Annealing (SA) algorithms which are categorized as approximate methods or known as a heuristics method. These three approximate methods are chosen because they are effective algorithms, easy to implement and provide good solutions for combinatorial optimization problems. Exact and approximate algorithms are tested in several sizes of city tour problems: 6, 9, 10, 16, 17, 25, 42, and 58 cities. 17, 42 and 58 cities are derived from tsplib: a library of sample instances for tsp; and others are taken from big cities in Java (West, Central, East) island. All of the algorithms are run by MATLAB program. The results show that exact method is better in time performance for problem size less than 25 cities and both exact and approximate methods yield optimal solution. For problem sizes that have more than 25 cities, approximate method – Artificial Bee Colony (ABC) yields better time which is approximately 37% less than exact and deviates 0.0197% for distance from exact method. The conclusion is to apply exact method for problem size that is less than 25 cities and approximate method for problem size that is more than 25 cities. The gap of time will be increasing between two methods when sample size becomes larger.
Предметом настоящего исследования является расстояние и время нескольких проблем с экскурсиями по городу, которые известны как проблема продавца-путешественника (ппп). Цель состоит в том, чтобы выяснить разрывы между расстояниями и временем между двумя типами методов оптимизации в проблеме продавца, который путешествует: точным и приблизительным. Точный метод дает оптимальное решение, но требует больше времени, когда количество городов увеличивается, а примерный метод дает почти оптимальное решение, даже оптимальное, но требует меньше времени, чем точные методы. Задачей данного исследования является определить и сформулировать каждый алгоритм для каждого метода, затем запустить каждый алгоритм с одинаковым входом и получить результат исследования: общее расстояние, которое даст возможность сравнить оба метода: их преимущество и ограничения. Использованные методы – методы Brute Force (BF) и Branch and Bound (B & B), которые классифицируются как точные методы, сравниваются с алгоритмами Artificial Bee Colony (ABC), Tabu Search (TS) и Simulated Annealing (SA), которые классифицируются как приблизительные методы или известны как методы эвристики. Эти три приближенные методы выбраны, поскольку они являются эффективными алгоритмами, просты в реализации и обеспечивают хорошие решения для комбинаторных задач оптимизации. Точные и приблизительные алгоритмы проверяются в нескольких размерах задач экскурсии по городу: 6, 9, 10, 16, 17, 25, 42 и 58 городов. 17, 42 и 58 городов выбраны из пппlib: библиотеки образцов экземпляров для ппп; а другие взяты из крупных городов острова Ява (Западный, Центральный, Восточный). Все алгоритмы запущены программой MATLAB. Результаты показывают, что точный метод лучше во времени по объему задания на менее чем 25 городов, когда и точные, и приблизительные методы дают оптимальное решение. Для объемов задачи, которая учитывает более 25 городов, приблизительный метод - Artificial Bee Colony (ABC) дает лучшее время, которое примерно на 37% меньше, чем при точном методе, и отклоняется на 0,0197% для расстояния точного метода. Вывод заключается в применении точного метода для объема проблемы менее 25 городов и приблизительного метода для объема проблемы более 25 городов. Разрыв во времени будет увеличиваться между двумя методами, когда объем выборки становится больше.
Предметом цього дослідження є відстань та час декількох проблем з екскурсіями містом, які відомі як проблема продавця-мандрівника (ппм). Мета полягає в тому, щоб з’ясувати розриви між відстанями та часом між двома типами методів оптимізації у проблемі продавця, що подорожує: точним та приблизним. Точний метод дає оптимальне рішення, але вимагає більше часу, коли кількість міст збільшується, а приблизний метод дає майже оптимальне рішення, навіть оптимальне, але потребує менше часу, ніж точні методи. Завданням цього дослідження є визначити та сформулювати кожен алгоритм для кожного методу, потім запустити кожен алгоритм з однаковим входом і отримати результат дослідження: загальна відстань, яка надасть можливість порівняти обидва методи: їх перевагу та обмеження. Використані методи – алгоритми Brute Force (BF) та Branch and Bound (B&B), які класифікуються як точні методи, порівнюються з алгоритмами Artificial Bee Colony (ABC), Tabu Search (TS) та Simulated Annealing (SA), які класифікуються як приблизні методи, або відомі як методи евристики. Ці три наближені методи обрані, оскільки вони є ефективними алгоритмами, прості у реалізації та забезпечують хороші рішення для комбінаторних задач оптимізації. Точні та приблизні алгоритми перевіряються у кількох розмірах задач екскурсії містом: 6, 9, 10, 16, 17, 25, 42 та 58 міст. 17, 42 та 58 міст вибрані з ппмlib: бібліотеки зразків екземплярів для ппм; а інші взяті з великих міст острова Ява (Західний, Центральний, Східний). Всі алгоритми запущені програмою MATLAB. Результати показують, що точний метод кращий у часі за обсягом завдання на менше ніж 25 міст, коли і точні, і приблизні методи дають оптимальне рішення. Для обсягів завдання, яке враховує більше 25 міст, приблизний метод – Artificial Bee Colony (ABC) дає кращий час, який приблизно на 37% менше, ніж точний, і відхиляється на 0,0197% для відстані від точного методу. Висновок полягає у застосуванні точного методу для обсягу проблеми менше 25 міст та приблизного методу для обсягу проблеми більше 25 міст. Розрив у часі буде збільшуватися між двома методами, коли обсяг вибірки стає більшим.
Databáze: OpenAIRE
Externí odkaz: