An Improved Ant Colony System for Solving1-PDTSP

An improved ant colony system optimization algorithm is proposed to solve One-Commodity Pickup-and-Delivery Traveling Salesman Problem. Firstly, the initializing method and updating rules of pheromone in ACS are improved according to the characteristic of 1-PDTSP; next, the stop phenomenon is solved by adopting the principle of “current optimal replacement”; straight after, to improve the solution quality and accelerate the convergence speed of algorithm, a variable neighborhood search algorithm with the capacity constraint is designed. And eventually, the experimental results indicate the improved ant colony system boasts its high precision and nice stability in solving 1-PDTSP