АНАЛІЗ ЕФЕКТИВНОСТІ МЕТОДІВ ОПТИМІЗАЦІЇ ДЛЯ ВИРІШЕННЯ ПРОБЛЕМИ ПРОДАВЦЯ, ЩО ПОДОРОЖУЄ
DOI:
https://doi.org/10.30837/ITSSI.2021.15.069Ключові слова:
проблема продавця, що подорожує, метод оптимізації, точний метод, наближені методи, прогалиниАнотація
Предметом цього дослідження є відстань та час декількох проблем з екскурсіями містом, які відомі як проблема продавця-мандрівника (ппм). Мета полягає в тому, щоб з’ясувати розриви між відстанями та часом між двома типами методів оптимізації у проблемі продавця, що подорожує: точним та приблизним. Точний метод дає оптимальне рішення, але вимагає більше часу, коли кількість міст збільшується, а приблизний метод дає майже оптимальне рішення, навіть оптимальне, але потребує менше часу, ніж точні методи. Завданням цього дослідження є визначити та сформулювати кожен алгоритм для кожного методу, потім запустити кожен алгоритм з однаковим входом і отримати результат дослідження: загальна відстань, яка надасть можливість порівняти обидва методи: їх перевагу та обмеження. Використані методи – алгоритми 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 міст. Розрив у часі буде збільшуватися між двома методами, коли обсяг вибірки стає більшим.
Посилання
Dimitrijevic, V., Saric, Z. (1997), "An Efficient Transformation of The Generalized Traveling Salesman Problem into The Traveling Salesman Problem on Diagraphs", Information Sciences, Vol. 102, Issues 1-4, P. 105–110. DOI: https://doi.org/10.1016/S0020-0255(96)00084-9
Baniasadi, P., Foumani, M., Miles, K. S., Ejov, V. (2020), "A Transformation Technique for The Clustered Generalized Traveling Salesman Problem with Applications to Logistics", European Journal of Operational Research, Vol. 285, Issue 2, P. 444–457. DOI: https://doi.org/10.1016/j.ejor
BPS – Statistik Indonesia (2019), "Land Transportation Statistics, Statistik Transportasi Darat", available at : www.bps.go.id
Saud, S., Kodaz, H., Babaoglu, I. (2017), "Solving the Traveling Salesman Problem Using Optimization Algorithms", IAIT Conference Proceddings. The 9th International Conference on Advances in Information Technology, Vol. 2017. DOI: https://doi.org/10.18502/kss.v3i1.1394
Jadczak, R. (2014), "Traveling Salesman Problem: Approach to Optimality", De Gruyter Open, Vol. XV, Issue 2, P. 157–159. DOI: https://doi.org/10.2478/eam-2014-0024
Chandra, A., Setiawan, B. (2018), "Optimizing the Distribution Routes Using Vehicle Routing Problem (VRP) Method", Journal Manajemen Transportasi dan Logistik, Vol. 05, No. 2, available at : http://ejournal.stmt-trisakti.ac.id/index.php/jmtranslog
Query, J. A. (2015), "The Impact of Transportation Costs and Trade Barriers on International Trade Flows", Dissertation, Department of Economics, Graduate School of the University of Oregon, available at: https://scholarsbank.uoregon.edu
Victoria Transport Policy Institute (2020), "Transportation Cost and Benefit Analysis II – Literature Review", availalble at : www.vtpi.org/tca/tca02.pdf (last accessed: 19.02.2021).
Keya, K. T., Rahman, M. M., Rob, U., Bellows, B. (2014), "Distance, Transportation Cost and Mode of Transport in the Utilization of Facility – Based Maternity Service: Evidence for Rural Bangladesh", International Quarterly of Community Health Education. DOI: https://10.2190/IQ.35.1.d
Bernatz, G. (2009),"Apples, Bananas, Oranges: Using GIS to Determine Distance Travelled, Energy Use, and Emissions from Imported Fruit", Papers in Resource Analysis, Saint Mary’s University of Minnesota Central Service Press. Winona, MN, Vol. 11, P. 16, available: http://www.gis.smumn.edu (last accessed: 13.02.2021).
Chandra, A., Naro, A. (2020), "A Comparative Study of Capacitated Vehicle Routing Problem Heuristics Model", International Journal of Engineering and Emerging Technology, Vol. 5, No. 2, P. 94-100. DOI: https://doi.org/10.24843/IJEET.2020.v05.i02.p015
Talbi, E. G. (2009), Metaheuristics: From Design to Implementation, John Wiley and Sons, New Jersey.
Vatutin, E. (2017), "Comparisons of Decisions Quality of Heuristics Methods with Limited Depth First Search Techniques in the Graph Shortest Path Problem", De Gruyter Open, P. 428–434. DOI: https://doi.org/10.1515/eng-2017-0041
Black, A. P. (2019), "Lecture 6: Exhaustive Serach Algorithms. Department of Compuer Science", Portland State University, available at : https://web.cecs.pdx.edu
Droste, I. (2017), "Algorithms for the Traveling Salesman Problem", Thesis, Universiteit Utrecht. Facuteit Betawetenschappen. Netherland, available at: https://dspace.library.uu.nl
Balas, E., Toth, P. (1983), "Branch and Bound Methods fo the Traveling Salesman Problem", Management Science Research Report, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, No. MSRR 488, available at : https://apps.dtic.mil
Karaboga, D., Basturk, B. (2008), "On the Performance of Artificial Bee Colony Algorithm", Applied Soft Computing, No. 8, P. 687–697. DOI: https://doi.org/10.1016/j.asoc.2007.05.007
Teodorovic, D., Selmic, M., Davidovic, T. (2015), "Bee Colony Optimization Part II: The Application Survey", Yugoslav Journal of Operations Research, Vol. 25, No. 2, P. 185–219. DOI: https://doi.org/10.2298/YJOR131029020T
Gendreau, M. (2002), An Introduction to Tabu Search, Universite de Montreal, Montreal, Canada. Available at: http://www.ifi.uio.no/infheur/Bakgrunn/Intro_to_TS.Gendreau.htm
Eglese, R. W. (1990), "Simulated Annealing: A Tool for Operational Research", European Journal of Operational Research, No. 46, P. 271–281. DOI: https://doi.org/10/1016/0377-2217(90)90001-R
De Weck, O. (2010), "Lecture 10: Simulated Annealing: A Basic Introduction", MIT OpenCourseWare, available at : http://ocw.mit.edu
Zhu, Y. W. (-), "Brute Force", University of Seattle, available at: http://www.fac-staff.seattleu.edu
Morrison, D., Jacobson, S. H., Sauppe, J. J., Sewell, E. C. (2016), "Branch and Bound algorithms: A Survey of Recent Advances in Searching, Branching, and Pruning", Discrete Optimization, No. 19, P. 79–102. DOI: http://dx.doi.org/10.1016/j.disopt.2016.01.005
Onder, E., Ozdemir, M., Yildrim, B. F. (2013), "Combinatorial Optimization Using Artificial Bee Colony Algorithm and Particle Swarm Optimization Supported Genetic Algorithm", KAU IIBF Dergisi, No. 4 (6), P. 59–70, available at : https://ssrn.com
Kocer, H. E., Akca, M. R. (2014), "An Improved Artificial Bee Colony Algorithm with Local Search for Traveling Salesman Problem", Cybernetics and Systems: An International Journal, Vol. 45, No. 8, P. 635–649. DOI: https://doi.org/10.1080/01969722.2014.970396
Boussaid, I., Lepagnot, J., Siarry, P. (2013), "A Survey On Optimization Metaheuristics", Information Sciences, No. 237, P. 82–117. DOI: https://doi.org/10.1016/j.ins.2013.02.041
Misevicius, A. (2004), "Using Iterated Tabu Search for the Traveling Salesman Problem", Informacines Technologijos Ir Valdymas, No. 3 (32), P. 29–40, available at : https://itc.ktu.lt
Zhou, A. H., Zhu, L. P., Hu, B., Deng, S., Song, Y., Qiu, H., Pan, S. (2019), "Traveling-Salesman-Problem Based on Simulated Annealing and Gene-Expression Programming", Information, Vol. 10, No. 7. DOI: https://doi.org/10.3390/info10010007
Mataija, M., Segic, M. R., Jozic, F. (2016), "Solving the Traveling Salesman Problem Using the Branch and Bound Method", Zbomik Veleucilista u Rjeci, Vol. 4 No. 1, P. 259–270, available at : https://hrcak.srce.hr
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Наше видання використовує положення про авторські права Creative Commons для журналів відкритого доступу.
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0), котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
Автори мають право укладати самостійні додаткові угоди щодо не комерційного та не ексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису опублікованої роботи, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи.
