Ant Colony Optimization With Local Search for Dynamic Traveling Salesman Problems

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• Dynamic Traveling Salesman Problems (DTSP) involve changing travel times between cities.
• Ant Colony Optimization (ACO) algorithms are effective for optimization due to their adaptive nature.
• Integrating local search operators can significantly boost ACO performance.

Purpose of the Study:

• To propose a novel memetic Ant Colony Optimization (ACO) algorithm for solving Dynamic Traveling Salesman Problems (DTSP).
• To enhance ACO by incorporating a specialized local search operator ('unstring and string') for improved solution quality.

Main Methods:

• A memetic ACO algorithm integrating a local search operator is developed.
• The 'unstring and string' local search operator refines ACO solutions by strategically removing and inserting cities.
• The algorithm is designed to handle both symmetric and asymmetric DTSPs.

Main Results:

• The proposed memetic ACO algorithm demonstrates superior efficiency in addressing DTSPs.
• Experimental results show significant performance improvements compared to existing state-of-the-art algorithms.
• The integration of local search effectively enhances the adaptation capabilities of ACO for dynamic environments.

Conclusions:

• The memetic ACO algorithm is an efficient and effective approach for solving DTSPs.
• The 'unstring and string' local search operator significantly improves solution quality in dynamic routing scenarios.
• This memetic approach offers a robust method for tackling complex optimization problems with changing parameters.