Novel Ant Colony Optimization for Solving Traveling Salesman Problem in Congested Transportation System

This paper proposes a novel ant colony optimization named MMAS-MDS algorithm (max-min ant system extended by multidimensional scaling) for solving the traveling salesman problem more effectively in the congested transportation systems. Global heuristic information related to time-distance is put into the probabilistic selection rule of the ant tour construction. It provides global guides for promising explorations and makes up for the insufficiency of local heuristic information when the travel time violates triangular inequality. Experimental results show that the MMAS-MDS algorithm can find much better solutions than the MMAS algorithm with traffic congestions.