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 rerurning to the starting city. In the past, TSP and OTSP has been applied in various vehicle rou...

Full description

Saved in:

Bibliographic Details
Main Author:	Chieng, Hock Hung
Format:	Thesis
Language:	English English English
Published:	2016
Subjects:	QA Mathematics QA299.6-433 Analysis
Online Access:	http://eprints.uthm.edu.my/9943/2/24p%20CHIENG%20HOCK%20HUNG.pdf http://eprints.uthm.edu.my/9943/1/CHIENG%20HOCK%20HUNG%20COPYRIGHT%20DECLARATION.pdf http://eprints.uthm.edu.my/9943/3/CHIENG%20HOCK%20HUNG%20WATERMARK.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-uthm-ep.9943
record_format	uketd_dc
spelling	my-uthm-ep.99432023-09-13T07:31:26Z A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem 2016-01 Chieng, Hock Hung QA Mathematics QA299.6-433 Analysis 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 rerurning 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 nCities 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 srudy 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-IX). 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-IX. Nevertheless, the study also found that most of the good solutions are discovered in the larger population sizes from 3000 to 5000. 2016-01 Thesis http://eprints.uthm.edu.my/9943/ http://eprints.uthm.edu.my/9943/2/24p%20CHIENG%20HOCK%20HUNG.pdf text en public http://eprints.uthm.edu.my/9943/1/CHIENG%20HOCK%20HUNG%20COPYRIGHT%20DECLARATION.pdf text en staffonly http://eprints.uthm.edu.my/9943/3/CHIENG%20HOCK%20HUNG%20WATERMARK.pdf text en validuser mphil masters Universiti Tun Hussein Onn Malaysia Fakulti Sains Komputer dan Teknologi Maklumat
institution	Universiti Tun Hussein Onn Malaysia
collection	UTHM Institutional Repository
language	English English English
topic	QA Mathematics QA299.6-433 Analysis
spellingShingle	QA Mathematics QA299.6-433 Analysis Chieng, Hock Hung A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem
description	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 rerurning 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 nCities 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 srudy 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-IX). 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-IX. Nevertheless, the study also found that most of the good solutions are discovered in the larger population sizes from 3000 to 5000.
format	Thesis
qualification_name	Master of Philosophy (M.Phil.)
qualification_level	Master's degree
author	Chieng, Hock Hung
author_facet	Chieng, Hock Hung
author_sort	Chieng, Hock Hung
title	A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem
title_short	A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem
title_full	A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem
title_fullStr	A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem
title_full_unstemmed	A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem
title_sort	genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem
granting_institution	Universiti Tun Hussein Onn Malaysia
granting_department	Fakulti Sains Komputer dan Teknologi Maklumat
publishDate	2016
url	http://eprints.uthm.edu.my/9943/2/24p%20CHIENG%20HOCK%20HUNG.pdf http://eprints.uthm.edu.my/9943/1/CHIENG%20HOCK%20HUNG%20COPYRIGHT%20DECLARATION.pdf http://eprints.uthm.edu.my/9943/3/CHIENG%20HOCK%20HUNG%20WATERMARK.pdf
_version_	1783728972036571136

A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem

Similar Items