Вплив параметрів мурашиного алгоритму на розв’язок задачі комівояжера
DOI:
https://doi.org/10.15587/1729-4061.2014.26290Ключові слова:
маршрутизація дрібногуртових перевезень, задача комівояжера, мурашиний алгоритм, керуючі параметри алгоритмуАнотація
Наведено коротку характеристику задачі комівояжера та методів її розв’язування. Докладно розкрито принципи роботи та основні залежності мурашиного алгоритму, який використовується для розв’язування цієї задачі. За результатами досліджень для мереж різних розмірів встановлено, що на ефективність роботи мурашиного алгоритму впливають керуючі параметри, та знайдено такі значення параметрів, за яких найшвидше досягається оптимальний розв’язок.Посилання
- Lashchenykh, O., Kuzkin, O. (2006). Metody i modeli optymizatcii transportnykh protcecsiv i system [Optimization methods and models for transport processes and systems]. Zaporizhzhia, ZNTU, 434.
- Hamdy, A. Taha (2005). Vvedenie v issledovanie operatsii [Operations research: an introduction]. Moscow, Williams, 912.
- Pozhydaiev, M. (2010). Algoritmy resheniia zadachi marshrutizatcii transporta [Algorithms for solving of vehicle route problem] Ph.D. dissertation, 05.13.18. Tomsk State University, 136.
- Shtovba, S. (2005). Muravinyie alhoritmy: teoriya i primenenie [The ant algorithm: theory and application]. Programmirovanie, 4, 1–16.
- Shtovba, S., Rudyy, O. (2004). Murashyni alhorytmy optymizatciyi [Ant colony for optimization]. Visnyk VPI, 4, 62–69.
- Shtovba, S. (2003). Muravinyie alhoritmy [Ant algorithms]. Exponenta Pro, 4, 70–75.
- Jones, M. T. (2004). Programmirovanie iskusstvennogo intelekta v prilozheniyah [AI application programming]. Moscow, DMK Press, 312.
- Subbotin, S., Oliynyk, A., Oliynyk, O. (2009). Neiteratyvni, evoliutciyni ta multiahentni metody syntezu nechitkolohichnykh i neyromerezhnykh modeley [Non-iterative, evolutionary and multi-agent methods of synthesis of fuzzy-logic and neural-network models]. Zaporizhzhia, ZNTU, 375.
- Dorigo, M., Stuzle, T. (2004). Ant Colony Optimization. Cambridge, A Bradford Book, 305.
- Kazharov, A., Kureichik, V. (2013). Ispolzovanie shablonnyh reshenii v muravinyh algoritmah [The usage of cut-and-dried solutions in the ant colony algorithms]. Izvestiya SFedU: Engineering Sciences, 7 (144), 17–22.
- Danchuk, V., Svatko, V. (2012). Optymizatciyi poshuku shlyakhiv po hrafu v dynamichniy zadachi komivoyazhera metodom modyfikovanoho murashynoho alhorytmu [Finding ways optimization on graf in dynamic problem by modified method of ant colony algorithm]. Systemni doslidzhennya ta informatciyni tekhnolohiyi, 2, 78–86.
- Cheng, C.-B., Mao, C.-P. (2007). A modified ant colony system for solving the travelling salesman problem with time windows. Mathematical and Computer Modelling, 46 (9-10), 1225–1235. doi:10.1016/j.mcm.2006.11.035
- Yang, J., Shi, X., Marchese, M., Liang, Y. (2008). An ant colony optimization method for generalized TSP problem. Progress in Natural Science, 18 (11), 1417–1422. doi:10.1016/j.pnsc.2008.03.028
- Dorigo, M., Gambardella, L. M. (1997). Ant Colony Systems: a Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1 (1), 53–66. doi:10.1109/4235.585892
- Ignatiev, A. (2009). Ispolzovanie algoritma muravinuh koloniy dlia resheniia zadachi marshrutizatcii transportnih sredstv [The usage of the ant colony algorithm for vehicle routing problem solving]. Proceedings of the IV international scientific and practical conference “Modern information technologies and IT-education”. Moscow, Lomonosov MSU. Available at: http://2009.it-edu.ru/docs/Sekziya_8/3_Ignat%27ev_Ignatyev.doc
- Jun-Mam, K., Yi, Z. (2012).Application of an Improved Ant Colony Optimization on Generalized Traveling Salesman Problem. Energy Procedia, 17, 319–325. doi: 10.1016/j.egypro.2012.02.101.
- Hlaing, Z. C., Khine, M. A. (2011). Solving Traveling Salesman Problem by Using Improved Ant Colony Optimization Algorithm. International Journal of Information and Education Technology, vol. 1, № 5, 404-409. doi: 10.7763/ijiet.2011.v1.67.
- Ivanova, I. (2012). Issledovanie raboti muravinogo algoritma na primere zadachi kommivoiazhera [Investigation of ant colony algorithm functioning based on travelling salesman problem example]. Research and Technology: Step into the Future, Vol. 7, № 3, 39–46.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2014 Ігор Андрійович Могила, Ірина Іванівна Лобач, Оксана Андріївна Якимець
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
