Information Technology Reference
In-Depth Information
6
Discrete/Binary Approach
Fatih Tasgetiren 1 , Yun-Chia Liang 2 , Quan-Ke Pan 3 , and Ponnuthurai Suganthan 4
1
Department of Operations Management and Business Statistics, Sultan Qaboos University,
Muscat, Sultanate of Oman
mfatih@squ.edu.om
2
Department of Industrial Engineering and Management, Yuan Ze University, Taiwan
ycliang@saturn.yzu.edu.tw
3
College of Computer Science, Liaocheng University, Liaocheng, P.R. China
qkpan@lctu.edu.cn
4
School of Electrical and Electronic Engineering, Nanyang Technological University,
Singapore 639798
epnsugan@ntu.edu.sg
Abstract. In a traveling salesman problem, if the set of nodes is divided into clusters so that a
single node from each cluster can be visited, then the problem is known as the generalized trav-
eling salesman problem where the objective is to find a tour with minimum cost passing through
only a single node from each cluster. In this chapter, a discrete differential evolution algorithm
is presented to solve the problem on a set of benchmark instances. The discrete differential evo-
lution algorithm is hybridized with local search improvement heuristics to further improve the
solution quality. Some speed-up methods presented by the authors previously are employed to
accelerate the greedy node insertion into a tour. The performance of the hybrid discrete differ-
ential evolution algorithm is tested on a set of benchmark instances with symmetric distances
ranging from 51 (11) to 1084 (217) nodes (clusters) from the literature. Computational results
show its highly competitive performance in comparison to the best performing algorithms from
the literature.
6.1
Introduction
The generalized traveling salesman problem (GTSP), one of several variations of the
traveling salesman problem (TSP), has been originated from diverse real life or poten-
tial applications. The TSP finds a routing of a salesman who starts from an origin (i.e. a
home location), visits a prescribed set of cities, and returns to the origin in such a way
that the total distance is minimum and each city is travelled once. On the other hand,
in the GTSP, a salesman when making a tour does not necessarily visit all nodes. But
similar to the TSP, the salesman will try to find a minimum-cost tour and travel each
city exactly once. Since the TSP in its generality represents a typical NP-Hard com-
binatorial optimization problem, the GTSP is also NP-hard. While many other combi-
natorial optimization problems can be reduced to the GTSP problem [11], applications
of the GTSP spans over several areas of knowledge including computer science, engi-
neering, electronics, mathematics, and operations research, etc. For example, publica-
tions can be found in postal routing [11], computer file processing [9], order picking in
Search WWH ::




Custom Search