A genetic simplified swarm algorithm for optimizing n- cities open loop travelling salesman problem
Open Loop Travelling Salesman Problem (OTSP) is one of the extension of Travelling Salesman Problem (TSP) that finding a shortest tour of a number of cities by visiting each city exactly once and do not returning to the starting city. In the past, TSP and OTSP has been applied in various vehicle rou...
Disimpan dalam:
| Pengarang Utama: | |
|---|---|
| Format: | Thesis |
| Diterbitkan: |
2016
|
| Subjek-subjek: | |
| Capaian Atas Talian: | http://eprints.uthm.edu.my/8870/ http://eprints.uthm.edu.my/8870/1/CHIENG_HOCK_HUNG2.pdf |
| Penanda-penanda: |
Tambah Penanda
Tiada Penanda, Jadilah orang pertama menanda rekod ini!
|
| Ringkasan: | Open Loop Travelling Salesman Problem (OTSP) is one of the extension of
Travelling Salesman Problem (TSP) that finding a shortest tour of a number of cities
by visiting each city exactly once and do not returning to the starting city. In the past,
TSP and OTSP has been applied in various vehicle routing systems to optimize the
route distance. However, in real-life scenario such as transportation problem does not
seem similar as pictured in OTSP whereby do not all cities are required to be visited
but simply restrain to several number of n cities. Therefore, a new problem called n-
Cities Open Loop Travelling Salesman Problem (nOTSP) is proposed. In the past,
Genetic Algorithm (GA) is a popular algorithm that used to solve TSPs. However,
GA often suffers from premature convergence due to the difficulty in preventing the
loss of genetic diversity in the population. Therefore, Genetic Simplified Swarm
Algorithm (GSSA) is proposed in this study to overcome the drawback of GA.
GSSA is an improved GA based algorithm with Simplified Swarm Optimization
(SSO) algorithm’s characteristic named Solution Update Mechanism (SUM). The
SUM is modified by embedding three GA mutation operators. Then, GSSA is used
to optimize nOTSP in terms of finding the shortest tour. Later, the performance of
GSSA is compared with GA without crossover operator (GA-XX) and GA with onepoint
crossover operator (GA-1X). Performance of the proposed algorithm is
measured based on the shortest distance and average shortest distance found by the
algorithm. Meanwhile, an investigation on influence of population size towards
algorithm was also studied. The experiment results show that GSSA can discover
shorter tour than GA-XX and GA-1X. Nevertheless, the study also found that most
of the good solutions are discovered in the larger population sizes from 3000 to 5000. |
|---|