Adapted Ant Colony Optimization for Large-Scale Orienteering Problem
Pages 223 - 226
Abstract
The orienteering problem (OP) is a challenging route optimization problem with the objective of finding an optimal subset of nodes and the optimal path to visit these nodes so that the total profit under the constraint of the cost is maximized. Since ant colony optimization (ACO) algorithms have shown remarkable performance in solving path planning problems, they are likely promising for solving OP. To verify this, this paper takes the first try to adapt five classical ACO algorithms, namely Ant System (AS), Elite Ant System (EAS), Rank based Ant System (ASrank), Min-Max Ant System (MMAS), and Ant Colony System (ACS), to solve OP. To this end, we determine the candidate nodes in the path construction by considering the constraint. To verify the optimization effectiveness of the five ACO algorithms in solving OP, we also take the first attempt to conduct experiments on large-scale OP instances. Experimental results have shown that the five ACO algorithms are very promising for OP and ASrank obtains the best performance on the large-scale OP instances.
References
[1]
Gunawan, A., Lau, H.C., and Vansteenwegen, P., 2016. Orienteering Problem: A Survey of Recent Variants, Solution Approaches and Applications. European Journal of Operational Research 255, 2, 315--332.
[2]
Thayer, T.C. and Carpin, S., 2021. An Adaptive Method for the Stochastic Orienteering Problem. IEEE Robotics and Automation Letters 6, 2, 4185--4192.
[3]
ŞEVKLİ, A.Z. et al., 2010. StPSO: Strengthened Particle Swarm Optimization. Turkish Journal of Electrical Engineering and Computer Sciences 18, 6, 1095--1114.
[4]
Kobeaga, G. et al., 2018. An Efficient Evolutionary Algorithm for the Orienteering Problem. Computers & Operations Research 90, 42--59.
[5]
Santini, A., 2019. An Adaptive Large Neighbourhood Search Algorithm for the Orienteering Problem. Expert Systems with Applications 123, 154--167.
[6]
Urrutia - Zambrana, A., Tirado, G., and Mateos, A., 2021. Variable Neighborhood Search to Solve the Generalized Orienteering Problem. International Transactions in Operational Research 28, 1, 142--167.
[7]
Yang, Q. et al, 2023. Random Contrastive Interaction for Particle Swarm Optimization in High-Dimensional Environment. IEEE Transactions on Evolutionary Computation, 1--1.
[8]
Yang, Q. et al., 2024. Triple Competitive Differential Evolution for Global Numerical Optimization. Swarm and Evolutionary Computation 84, 101450.
[9]
Zhang, J. et al, 2023. Proximity Ranking-based Multimodal Differential Evolution. Swarm and Evolutionary Computation 78, 101277.
[10]
Yang, Q. et al., 2017. Multimodal Estimation of Distribution Algorithms. IEEE Transactions on Cybernetics 47, 3, 636--650.
[11]
Bao, C. et al, 2021. A Comparative Study on Population-Based Evolutionary Algorithms for Multiple Traveling Salesmen Problem with Visiting Constraints. In IEEE Symposium Series on Computational Intelligence, 01--08.
[12]
Sun, B. et al, 2021. Ant Colony Optimization for Balanced Multiple Traveling Salesmen Problem. In International Conference on Computational Science and Computational Intelligence, 476--481.
[13]
Zhu, R.-Y et al., 2022. Proximity-Based MAENS for Capacitated Multiple Traveling Salesmen Problem. In Artificial Intelligence Trends in Systems Springer International Publishing, 22--33.
[14]
Bao, C. et al, 2022. Ant Colony Optimization with Shortest Distance Biased Dispatch for Visiting Constrained Multiple Traveling Salesmen Problem. In Proceedings of the Proceedings of the Genetic and Evolutionary Computation Conference Companion, 77--80.
[15]
Xu, N. et al, 2023. Ant Colony Optimization for Multiple Travelling Salesmen Problem with Pivot Cities. In International Conference on Advanced Computational Intelligence, 1--8.
[16]
Nie, Z.H. et al., 2022. Ant Colony optimization for Electric Vehicle Routing Problem with Capacity and Charging Time Constraints. In IEEE International Conference on Systems, Man, and Cybernetics 480--485.
[17]
Cao, H. et al, 2023. Random Pairwise Competition Based Ant Selection for Pheromone Updating in Ant Colony Optimization. In IEEE International Conference on Systems, Man, and Cybernetics, 1455--1460.
[18]
Chen, W.N. et al., 2020. Ant Colony Optimization for the Control of Pollutant Spreading on Social Networks. IEEE Transactions on Cybernetics 50, 9, 4053--4065.
[19]
Stützle, T. and Hoos, H.H., 2000. MAX-MIN Ant System. Future Generation Computer Systems 16, 8, 889--914.
[20]
Shi, L. et al., 2022. Memory-Based Ant Colony System Approach for Multi-Source Data Associated Dynamic Electric Vehicle Dispatch Optimization. IEEE Transactions on Intelligent Transportation Systems 23, 10, 17491--17505.
Index Terms
- Adapted Ant Colony Optimization for Large-Scale Orienteering Problem
Recommendations
Ant colony optimization theory: a survey
Research on a new metaheuristic for optimization is often initially focused on proof-of-concept applications. It is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the ...
Optimization of the quadratic assignment problem using an ant colony algorithm
Ant algorithm is a multi-agent systems inspired by the behaviors of real ant colonies function to solve optimization problems. In this paper an ant colony optimization algorithm is developed to solve the quadratic assignment problem. The local search ...
Running time analysis of Ant Colony Optimization for shortest path problems
Ant Colony Optimization (ACO) is a modern and very popular optimization paradigm inspired by the ability of ant colonies to find shortest paths between their nest and a food source. Despite its popularity, the theory of ACO is still in its infancy and a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
2187 pages
Copyright © 2024 Copyright held by the owner/author(s).
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 August 2024
Check for updates
Author Tags
Qualifiers
- Poster
Funding Sources
- National Key Research and Development Program of China
- National Natural Science Foundation of China
Conference
GECCO '24 Companion
Sponsor:
GECCO '24 Companion: Genetic and Evolutionary Computation Conference Companion
July 14 - 18, 2024
VIC, Melbourne, Australia
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 34Total Downloads
- Downloads (Last 12 months)34
- Downloads (Last 6 weeks)9
Reflects downloads up to 13 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in