1. MMC
  2. All Volumes and Issues
  3. Volume 11, Number 1, 2024
  4. A combined ant colony optimization with Levy flight mechanism for the probabilistic traveling salesman problem with deadlines

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

MMC.
2024;
Volume 11, Number 1
: pp. 290–299
https://doi.org/10.23939/mmc2024.01.290
Received: June 26, 2023
Accepted: March 09, 2024

El Asri F., Tajani C., Fakhouri H. A combined ant colony optimization with Levy flight mechanism for the probabilistic traveling salesman problem with deadlines.  Mathematical Modeling and Computing. Vol. 11, No. 1, pp. 290–299 (2024)

Authors:
  1. F. El Asri
  2. C. Tajani
  3. H. Fakhouri
1
SMAD Team, Polydisciplinary Faculty of Larache, Abdelmalek Essaadi University
2
Polydisciplinary Faculty of Larache, Abdelmalek Essaadi University
3
SMAD, FPL, Abdelmalek Essaadi University

In 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 $\sharp$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.

stochastic combinatorial optimization
probabilistic traveling salesman problem
deadlines
metaheuristics
ant colony optimization
Levy flight
  1. Campbell A. M., Thomas B. W.  Probabilistic traveling salesman problem with deadlines.  Transportation Science.  42 (1), 1–21 (2008).
  2. Weyland D.  On the computational complexity of the Probabilistic Traveling Salesman Problem with Deadlines.  Theoretical Computer Science.  540, 156–168 (2014).
  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).
  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).
  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).
  6. Liu Y., Cao B.  Improving ant colony optimization algorithm with Levy flight.  MISTA 2017 Conference (2017).
  7. Liu Y., Cao B.  A Novel Ant Colony Optimization Algorithm With Levy Flight.  IEEE Access.  8, 67205–67213 (2020).
  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).
  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).
  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).
  11. Dorigo M., Maniezzo V., Colorni A.  The ant system: An autocatalytic optimizing process.  Technical Report (1991).
  12. Dorigo M.  Optimization, Learning and Natural algorithms.  PhD thesis, Politecnico di Milano (1992).
  13. Gambardella L. M., Dorigo M.  Ant-Q: A reinforcement learning approach to the traveling salesman problem.  Machine Learning Proceedings 1995.  252–260 (1995).
  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).
  15. Stützle 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).
  16. Monmarché N.  On data clustering with artificial ants.  AAAI-99 & GECCO-99 Workshop on Data Mining with Evolutionary Algorithms: Research Directions.  23–26 (1999).
  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).
  18. Labroche N., Monmarché N., Venturini G.  A new clustering algorithm based on the chemical recognition system of ants.  ECAI.  77, 345–349 (2002).
  19. Azzag H., Venturini G.  A clustering model using artificial ants.  Universite Francois-Rabelais (2004), (in France).
  20. Stützle T., Hoos H. H.  MAX–MIN ant system.  Future Generation Computer Systems.  16 (8), 889–914 (2000).
  21. Dorigo M.  Ant colony optimization.  Scholarpedia.  2 (3), 1461 (2007).
  22. Feyel P.  Optimisation des correcteurs par les métaheuristiques. Application à la stabilisation inertielle de ligne de visée.  PhD thesis, CentraleSupélec (2015).
  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).
  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).
  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).