Ant Colony Optimization for TSP with Post-Processing Path De-Crossing

This paper presents an implementation of Ant Colony Optimization (ACO) for solving the Traveling Salesman Problem (TSP), with detailed explanation of post-optimization path de-crossing procedures. The implementation utilizes the att48 dataset, which contains coordinate information for 48 cities in a standard TSP benchmark. The Traveling Salesman Problem represents a classic combinatorial optimization challenge that requires finding the shortest possible route visiting each city exactly once and returning to the origin city. The ACO algorithm mimics the foraging behavior of natural ants, where artificial ants deposit pheromones on paths and follow probability-based selection rules to construct solutions. Key implementation components include: - Pheromone initialization and evaporation mechanisms - Path construction using probabilistic transition rules - Fitness evaluation through distance calculation functions In our experimental setup, we comprehensively discuss parameter optimization strategies including: - Colony size configuration - Pheromone influence factors (alpha) - Heuristic information weights (beta) - Evaporation rate calibration The post-processing de-crossing technique involves checking for intersecting path segments and applying 2-opt or 3-opt local search operations to eliminate crossings, significantly improving solution quality. This process employs intersection detection algorithms and segment reversal operations to optimize the final route. The implementation demonstrates how proper parameter tuning combined with effective de-crossing procedures can substantially enhance algorithm performance and solution optimality for complex TSP instances.