A combined ant colony optimization with Levy flight mechanism for the probabilistic traveling salesman problem with deadlines

Simple item page
dc.citation.epage299
dc.citation.issue11
dc.citation.journalTitleМатематичне моделювання та комп'ютинг
dc.citation.spage290
dc.citation.volume1
dc.contributor.affiliationУніверситет Абдельмалека Ессааді
dc.contributor.affiliationAbdelmalek Essaadi University
dc.contributor.authorЕль Асрі, Ф.
dc.contributor.authorТаяні, К.
dc.contributor.authorФахурі, Х.
dc.contributor.authorEl Asri, F.
dc.contributor.authorTajani, C.
dc.contributor.authorFakhouri, H.
dc.coverage.placenameЛьвів
dc.coverage.placenameLviv
dc.date.accessioned2025-10-20T07:44:20Z
dc.date.created2024-02-24
dc.date.issued2024-02-24
dc.description.abstractУ цій статті нас цікавить ймовірнісна задача комівояжера з дедлайнами (PTSPD), де з клієнтами необхідно зв'язатися, окрім їхньої випадкової доступності, до встановленого дедлайну. Головна мета полягає в тому, щоб знайти оптимальний маршрут, який охоплює випадкову підмножину відвідувачів у тому ж порядку, в якому вони з'являються в турі, намагаючись зробити шлях якомога коротшим. ♯P-складною. Оптимізація колонії мурах (ACO) часто застосовується для вирішення цієї складної задачі оптимізації. Однак у цьому дослідженні ми пропонуємо вдосконалений ACO з використанням алгоритму польоту Леві. Це дозволяє деяким мурахам здійснювати довші стрибки на основі розподілу Леві, допомагаючи їм виходити з локальних оптимумів. Наші обчислювальні експерименти з використанням стандартних наборів даних демонструють, що запропонований алгоритм є ефективнішим і точнішим, ніж традиційний ACO.
dc.description.abstractIn this paper, we are interested in the Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) where clients must be contacted, in addition to their random availability before a set deadline. The main objective is to find an optimal route that covers a random subset of visitors in the same order as they appear on the tour, attempting to keep the path as short as possible. This problem is regarded as being ♯P-hard. Ant Colony Optimization (ACO) has been frequently employed to resolve this challenging optimization problem. However, we suggest an enhanced ACO employing the Levy flight algorithm in this study. This allows some ants to take longer jumps based on the Levy distribution, helping them escape from local optima situations. Our computational experiments using standard benchmark datasets demonstrate that the proposed algorithm is more efficient and accurate than traditional ACO.
dc.format.extent290-299
dc.format.pages10
dc.identifier.citationEl Asri F. A combined ant colony optimization with Levy flight mechanism for the probabilistic traveling salesman problem with deadlines / F. El Asri, C. Tajani, H. Fakhouri // Mathematical Modeling and Computing. — Lviv : Lviv Politechnic Publishing House, 2024. — Vol 1. — No 11. — P. 290–299.
dc.identifier.citationenEl Asri F. A combined ant colony optimization with Levy flight mechanism for the probabilistic traveling salesman problem with deadlines / F. El Asri, C. Tajani, H. Fakhouri // Mathematical Modeling and Computing. — Lviv : Lviv Politechnic Publishing House, 2024. — Vol 1. — No 11. — P. 290–299.
dc.identifier.doi10.23939/mmc2024.01.290
dc.identifier.urihttps://ena.lpnu.ua/handle/ntb/113788
dc.language.isoen
dc.publisherВидавництво Львівської політехніки
dc.publisherLviv Politechnic Publishing House
dc.relation.ispartofМатематичне моделювання та комп'ютинг, 11 (1), 2024
dc.relation.ispartofMathematical Modeling and Computing, 11 (1), 2024
dc.relation.references[1] Campbell A. M., Thomas B. W. Probabilistic traveling salesman problem with deadlines. Transportation Science. 42 (1), 1–21 (2008).
dc.relation.references[2] Weyland D. On the computational complexity of the Probabilistic Traveling Salesman Problem with Deadlines. Theoretical Computer Science. 540, 156–168 (2014).
dc.relation.references[3] Weyland D., Montemanni R., Gambardella L. M. Hardness results for the probabilistic traveling salesman problem with deadlines. International Symposium on Combinatorial Optimization. 392–403 (2012).
dc.relation.references[4] Weyland D., Montemanni R., Gambardella L. M. Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling. Computers & Operations Research. 40 (7), 1661–1670 (2013).
dc.relation.references[5] Dorigo M., Di Caro G. Ant colony optimization: a new meta-heuristic. Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406). 2, 1470–1477 (1999).
dc.relation.references[6] Liu Y., Cao B. Improving ant colony optimization algorithm with Levy flight. MISTA 2017 Conference (2017).
dc.relation.references[7] Liu Y., Cao B. A Novel Ant Colony Optimization Algorithm With Levy Flight. IEEE Access. 8, 67205–67213 (2020).
dc.relation.references[8] Zhang Y., Zhao H., Cao Y., Liu Q., Shen Z., Wang J., Hu M. A hybrid ant colony and cuckoo search algorithm for route optimization of heating engineering. Energies. 11 (10), 2675 (2018).
dc.relation.references[9] Campbell A. M., Thomas B. W. Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines. Computers & Operations Research. 36 (4), 1231–1248 (2009).
dc.relation.references[10] Deneubourg J. L., Aron S., Goss S., Pasteels J. M. The self-organizing exploratory pattern of the Argentine ant. Journal of Insect Behavior. 3 (2), 159–168 (1990).
dc.relation.references[11] Dorigo M., Maniezzo V., Colorni A. The ant system: An autocatalytic optimizing process. Technical Report (1991).
dc.relation.references[12] Dorigo M. Optimization, Learning and Natural algorithms. PhD thesis, Politecnico di Milano (1992).
dc.relation.references[13] Gambardella L. M., Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. Machine Learning Proceedings 1995. 252–260 (1995).
dc.relation.references[14] Gambardella L. M., Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies. Proceedings of IEEE International Conference on Evolutionary Computation. 622–627 (1996).
dc.relation.references[15] St¨utzle T., Hoos H. H. Improving the Ant System: A detailed report on the MAX–MIN Ant System. FG Intellektik, FB Informatik, TU Darmstadt, Germany, Tech. Rep. (1996).
dc.relation.references[16] Monmarch´e N. On data clustering with artificial ants. AAAI-99 & GECCO-99 Workshop on Data Mining with Evolutionary Algorithms: Research Directions. 23–26 (1999).
dc.relation.references[17] Cordon O., de Viana I. F., Herrera F., Moreno L. A new ACO model integrating evolutionary computation concepts: The best-worst Ant System. Proc. ANTS. 22–29 (2000).
dc.relation.references[18] Labroche N., Monmarch´e N., Venturini G. A new clustering algorithm based on the chemical recognition system of ants. ECAI. 77, 345–349 (2002).
dc.relation.references[19] Azzag H., Venturini G. A clustering model using artificial ants. Universite Francois-Rabelais (2004), (in France).
dc.relation.references[20] St¨utzle T., Hoos H. H. MAX–MIN ant system. Future Generation Computer Systems. 16 (8), 889–914 (2000).
dc.relation.references[21] Dorigo M. Ant colony optimization. Scholarpedia. 2 (3), 1461 (2007).
dc.relation.references[22] Feyel P. Optimisation des correcteurs par les m´etaheuristiques. Application `a la stabilisation inertielle de ligne de vis´ee. PhD thesis, CentraleSup´elec (2015).
dc.relation.references[23] Zhou Y., Ouyang X., Xie J. A discrete cuckoo search algorithm for travelling salesman problem. International Journal of Collaborative Intelligence. 1 (1), 68–84 (2014).
dc.relation.references[24] Liu Y., Cao B., Li H. Improving ant colony optimization algorithm with epsilon greedy and Levy flight. Complex & Intelligent Systems. 7 (4), 1711–1722 (2021).
dc.relation.references[25] Weyland D., Montemanni R., Gambardella L. M. A metaheuristic framework for stochastic combinatorial optimization problems based on GPGPU with a case study on the probabilistic traveling salesman problem with deadlines. Journal of Parallel and Distributed Computing. 73 (1), 74–85 (2013).
dc.relation.referencesen[1] Campbell A. M., Thomas B. W. Probabilistic traveling salesman problem with deadlines. Transportation Science. 42 (1), 1–21 (2008).
dc.relation.referencesen[2] Weyland D. On the computational complexity of the Probabilistic Traveling Salesman Problem with Deadlines. Theoretical Computer Science. 540, 156–168 (2014).
dc.relation.referencesen[3] Weyland D., Montemanni R., Gambardella L. M. Hardness results for the probabilistic traveling salesman problem with deadlines. International Symposium on Combinatorial Optimization. 392–403 (2012).
dc.relation.referencesen[4] Weyland D., Montemanni R., Gambardella L. M. Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling. Computers & Operations Research. 40 (7), 1661–1670 (2013).
dc.relation.referencesen[5] Dorigo M., Di Caro G. Ant colony optimization: a new meta-heuristic. Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406). 2, 1470–1477 (1999).
dc.relation.referencesen[6] Liu Y., Cao B. Improving ant colony optimization algorithm with Levy flight. MISTA 2017 Conference (2017).
dc.relation.referencesen[7] Liu Y., Cao B. A Novel Ant Colony Optimization Algorithm With Levy Flight. IEEE Access. 8, 67205–67213 (2020).
dc.relation.referencesen[8] Zhang Y., Zhao H., Cao Y., Liu Q., Shen Z., Wang J., Hu M. A hybrid ant colony and cuckoo search algorithm for route optimization of heating engineering. Energies. 11 (10), 2675 (2018).
dc.relation.referencesen[9] Campbell A. M., Thomas B. W. Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines. Computers & Operations Research. 36 (4), 1231–1248 (2009).
dc.relation.referencesen[10] Deneubourg J. L., Aron S., Goss S., Pasteels J. M. The self-organizing exploratory pattern of the Argentine ant. Journal of Insect Behavior. 3 (2), 159–168 (1990).
dc.relation.referencesen[11] Dorigo M., Maniezzo V., Colorni A. The ant system: An autocatalytic optimizing process. Technical Report (1991).
dc.relation.referencesen[12] Dorigo M. Optimization, Learning and Natural algorithms. PhD thesis, Politecnico di Milano (1992).
dc.relation.referencesen[13] Gambardella L. M., Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. Machine Learning Proceedings 1995. 252–260 (1995).
dc.relation.referencesen[14] Gambardella L. M., Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies. Proceedings of IEEE International Conference on Evolutionary Computation. 622–627 (1996).
dc.relation.referencesen[15] St¨utzle T., Hoos H. H. Improving the Ant System: A detailed report on the MAX–MIN Ant System. FG Intellektik, FB Informatik, TU Darmstadt, Germany, Tech. Rep. (1996).
dc.relation.referencesen[16] Monmarch´e N. On data clustering with artificial ants. AAAI-99 & GECCO-99 Workshop on Data Mining with Evolutionary Algorithms: Research Directions. 23–26 (1999).
dc.relation.referencesen[17] Cordon O., de Viana I. F., Herrera F., Moreno L. A new ACO model integrating evolutionary computation concepts: The best-worst Ant System. Proc. ANTS. 22–29 (2000).
dc.relation.referencesen[18] Labroche N., Monmarch´e N., Venturini G. A new clustering algorithm based on the chemical recognition system of ants. ECAI. 77, 345–349 (2002).
dc.relation.referencesen[19] Azzag H., Venturini G. A clustering model using artificial ants. Universite Francois-Rabelais (2004), (in France).
dc.relation.referencesen[20] St¨utzle T., Hoos H. H. MAX–MIN ant system. Future Generation Computer Systems. 16 (8), 889–914 (2000).
dc.relation.referencesen[21] Dorigo M. Ant colony optimization. Scholarpedia. 2 (3), 1461 (2007).
dc.relation.referencesen[22] Feyel P. Optimisation des correcteurs par les m´etaheuristiques. Application `a la stabilisation inertielle de ligne de vis´ee. PhD thesis, CentraleSup´elec (2015).
dc.relation.referencesen[23] Zhou Y., Ouyang X., Xie J. A discrete cuckoo search algorithm for travelling salesman problem. International Journal of Collaborative Intelligence. 1 (1), 68–84 (2014).
dc.relation.referencesen[24] Liu Y., Cao B., Li H. Improving ant colony optimization algorithm with epsilon greedy and Levy flight. Complex & Intelligent Systems. 7 (4), 1711–1722 (2021).
dc.relation.referencesen[25] Weyland D., Montemanni R., Gambardella L. M. A metaheuristic framework for stochastic combinatorial optimization problems based on GPGPU with a case study on the probabilistic traveling salesman problem with deadlines. Journal of Parallel and Distributed Computing. 73 (1), 74–85 (2013).
dc.rights.holder© Національний університет “Львівська політехніка”, 2024
dc.subjectстохастична комбінаторна оптимізація
dc.subjectімовірнісна задача комівояжера
dc.subjectтерміни виконання
dc.subjectметаевристика
dc.subjectоптимізація мурашиних колоній
dc.subjectполіт Леві
dc.subjectstochastic combinatorial optimization
dc.subjectprobabilistic traveling salesman problem
dc.subjectdeadlines
dc.subjectmetaheuristics
dc.subjectant colony optimization
dc.subjectLevy flight
dc.titleA combined ant colony optimization with Levy flight mechanism for the probabilistic traveling salesman problem with deadlines
dc.title.alternativeКомбінована оптимізація мурашиної колонії з механізмом польоту Леві для імовірнісної задачі комівояжера з термінами виконання
dc.typeArticle

Files

Original bundle

Now showing 1 - 2 of 2
Thumbnail Image
Name:
2024v1n11_El_Asri_F-A_combined_ant_colony_optimization_290-299.pdf
Size:
6.69 MB
Format:
Adobe Portable Document Format
Download
Thumbnail Image
Name:
2024v1n11_El_Asri_F-A_combined_ant_colony_optimization_290-299__COVER.png
Size:
454.89 KB
Format:
Portable Network Graphics
Download

License bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.82 KB
Format:
Plain Text
Description:
Download

Collections

Mathematical Modeling And Computing. – 2024. – Vol. 11, No. 1