Improvement of a greedy-based TSP heuristic and its application to ACO
DOI:
https://doi.org/10.52731/liir.v004.175Keywords:
ant colony optimization, greedy-based heuristic, traveling salesman problemAbstract
Recent years have observed increased demand for deliveries and a shortage of human resources, necessitating more efficient transportation paths for products and other items in transportation, logistics, and associated sectors. This study introduces a heuristic by improving the greedy-based algorithm to solve the traveling salesman problem. This proposed method can rapidly find numerous promising paths. Furthermore, we explored the application of the proposed method for pheromone deposition in ant colony optimization (ACO). Specifically, pheromones are deposited on the paths charted by ants and those investigated using the proposed method. Computational experiments provided robust evidence of the effectiveness of the proposed method and its integration with ACO.
References
D. J. Rosenkrantz, R. E. Stearns, P. M. Lewis, “Approximate algorithms for the traveling salesperson problem,” In Proc. the 15th Annual Symp. Switching and Automata Theory (SWAT ‘74), New Orleans, USA, 1974, pp. 33.
R. Skinderowicz, “Improving Ant Colony Optimization Efficiency for Solving Large TSP Instances,” Applied Soft Computing, vol.120, 2022, pp. 108653.
P. Stodola, K. Michenka, J. Nohel, and M. Rybanský, “Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem,” Entropy, vol. 22, no. 8, 2020, pp. 884.
H. Ismkhan, “Effective Heuristics for Ant Colony Optimization to Handle Large-scale Problems,” Swarm and Evolutionary Computation, vol. 32, 2017, pp. 140.
M. Mavrovouniotis, S. Yang, M. Van, C. Li, and M. Polycarpou, “Ant Colony Optimization Algorithms for Dynamic Optimization: A Case Study of the Dynamic Travelling Salesperson Problem,” IEEE Computational Intelligence Magazine, vol. 15, no.1, 2020, pp. 52.
T. Stützle and H.H. Hoos, “MAX-MIN Ant System,” Future Generation Computer Sys- tems, vol. 16, no. 8, 2000, pp. 889.
P. Junjie and W. Dingwei, “An Ant Colony Optimization Algorithm for Multiple Traveling Salesman Problem,” In Proc. the First Int’l Conf. on Innovative Computing, Information and Control–Volume I (ICICIC’06), Beijing, China, 2006, vol. 1, pp. 210.
L. Strąk, R. Skinderowicz, U. Boryczka, and A. Nowakowski, “A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP,” Entropy, vol. 21, no. 8, 2019, pp. 738.
P.M. de las Casas, R. Borndörfer, L. Kraus, and A. Sedeño-Noda, “An FPTAS for Dy- namic Multiobjective Shortest Path Problems,” Algorithms, vol. 14, no. 2, 2021, pp. 43.
S. Sharma and J. Chou, “Distributed and Incremental Travelling Salesman Algorithm on Time-Evolving Graphs,” The Journal of Supercomputing, vol. 77, 2021, pp. 10896.
TSPLIB, http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (accessed on 22 July 2023).
