DocumentCode :
2558383
Title :
A novel ant colony system for solving the one-commodity traveling salesman problem with selective pickup and delivery
Author :
Mou Lian-Ming ; Dai Xi-Li
Author_Institution :
Key Lab. of Numerical Simulation of Sichuan Province, Neijiang Normal Univ., Neijiang, China
fYear :
2012
fDate :
29-31 May 2012
Firstpage :
1096
Lastpage :
1101
Abstract :
The one-commodity traveling salesman problem with selective pickup and delivery (1-TSP-SELPD) is a generalization of the one-commodity pickup-and-delivery traveling salesman problem (1-PDTSP) and has many interesting applications. The 1-TSP-SELPD is known to be an NP-hard. In this paper, to solve effectively the 1-TSP-SELPD, we extend the ant colony system method from TSP to 1-TSP-SELPD. Meanwhile, to improve the quality of solution, the constrained local searching and neighborhood searching technique are introduced into this method to accelerate the convergence according to the characteristic of the 1-TSP-SELPD, and a novel mutation technique is also introduced into this method to avoid falling into local minima. Experimental results gathered from extensive simulations confirm that our proposed method is significantly superior to the state-of-the-art methods.
Keywords :
ant colony optimisation; computational complexity; convergence; evolutionary computation; search problems; travelling salesman problems; NP-hard; ant colony system; constrained local searching; convergence; mutation technique; neighborhood searching; one-commodity pickup-and-delivery traveling salesman problem; one-commodity traveling salesman problem; quality improvement; selective delivery; selective pickup; Base stations; Convergence; Robot sensing systems; Traveling salesman problems; 1-TSP-SELPD; ACS; constrained local searching; constrained mutation technique; neighborhood searching;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Natural Computation (ICNC), 2012 Eighth International Conference on
Conference_Location :
Chongqing
ISSN :
2157-9555
Print_ISBN :
978-1-4577-2130-4
Type :
conf
DOI :
10.1109/ICNC.2012.6234622
Filename :
6234622
Link To Document :
بازگشت