Smallest Position Value Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 120

5

Smallest Position Value Approach

Fatih Tasgetiren 1 , Angela Chen 2 , Gunes Gencyilmaz 3 , and Said Gattoufi 4

1

Department of Operations Management and Business Statistics, Sultan Qaboos University,
Muscat, Sultanate of Oman
[e-mail]

2

Department of Finance, Nanya Institute of Technology, Taiwan 320, R.O.C
[e-mail]

3

Department of Management, Istanbul Kultur University, Istanbul, Turkey
[e-mail]

4

Department of Operations Management and Business Statistics, Sultan Qaboos University,
Muscat, Sultanate of Oman
[e-mail]

Abstract. In a traveling salesman problem, if the set of nodes is divided into clusters for a sin-
gle node from each cluster to be visited, then the problem is known as the generalized traveling
salesman problem (GTSP). Such problem aims to find a tour with minimum cost passing through
only a single node from each cluster. In attempt to show how a continuous optimization algo-
rithm can be used to solve a discrete/combinatorial optimization problem, this chapter presents a
standard continuous differential evolution algorithm along with a smallest position value (SPV)
rule and a unique solution representation to solve the GTSP. The performance of the differential
evolution algorithm is tested on a set of benchmark instances with symmetric distances ranging
from 51 (11) to 442 (89) nodes (clusters) from the literature. Computational results are presented
and compared to a random key genetic algorithm (RKGA) from the literature.

5.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 sim-
ilar 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 combinato-
rial optimization problem, the GTSP is also NP-hard. While many other combinatorial
optimization problems can be reduced to the GTSP problem [11], applications of the
GTSP spans over several areas of knowledge including computer science, engineering,
electronics, mathematics, and operations research, etc. For example, publications can
be found in postal routing [11], computer file processing [9], order picking in ware-
houses [17], process planning for rotational parts [3], and the routing of clients through
welfare agencies [24].