More Web Proxy on the site http://driver.im/

poster

Adapted Ant Colony Optimization for Large-Scale Orienteering Problem

Authors:

Chang Jun Zhou,

Zhong Long Zheng,

Jun ZhangAuthors Info & Claims

GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Pages 223 - 226

https://doi.org/10.1145/3638530.3654270

Published: 01 August 2024 Publication History

GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Adapted Ant Colony Optimization for Large-Scale Orienteering Problem

Pages 223 - 226

Abstract
References

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 (AS_rank), 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 AS_rank 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.

Digital Library

[5]

Santini, A., 2019. An Adaptive Large Neighbourhood Search Algorithm for the Orienteering Problem. Expert Systems with Applications 123, 154--167.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Cited By

Wang BDuan DYang QZhao XLi TLiu DZhang J(2024)Adaptive Ant Selection for Pheromone Update in Ant Colony Optimization2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC54092.2024.10831815(667-672)Online publication date: 6-Oct-2024
https://doi.org/10.1109/SMC54092.2024.10831815

Index Terms

Adapted Ant Colony Optimization for Large-Scale Orienteering Problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial optimization
  2. Mathematical analysis
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

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

cover image ACM Conferences

GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion

July 2024

2187 pages

ISBN:9798400704956

DOI:10.1145/3638530

Chair:
Xiaodong Li,
Program Chair:
Julia Handl

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

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

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:

SIGEVO

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

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
53
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)11

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang BDuan DYang QZhao XLi TLiu DZhang J(2024)Adaptive Ant Selection for Pheromone Update in Ant Colony Optimization2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC54092.2024.10831815(667-672)Online publication date: 6-Oct-2024
https://doi.org/10.1109/SMC54092.2024.10831815

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten