New genetic operator for solving the travelling salesman problem / Fadzilawani Astifar Alias ... [et al.]
The Travelling Salesman Problem (TSP) is a well-known and important combinatorial optimization problem. The goal is to find the shortest distance tour that visits each city in a given list exactly once and then returns to the starting city. TSP is an NP-complete problem that has many interaction var...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universiti Teknologi MARA, Pulau Pinang
2015
|
| Subjects: | |
| Online Access: | http://ir.uitm.edu.my/id/eprint/11988/ http://ir.uitm.edu.my/id/eprint/11988/1/AJ_FADZILAWANI%20ASTIFAR%20ALIAS%20EAJ%2015.pdf |
| Summary: | The Travelling Salesman Problem (TSP) is a well-known and important combinatorial optimization problem. The goal is to find the shortest distance tour that visits each city in a given list exactly once and then returns to the starting city. TSP is an NP-complete problem that has many interaction variables with a high degree of freedom. The main objective of TSP is to determine the network route to minimize the total distance, cost or time. In this research, the heuristic method called Genetic Algorithm (GA) is used to solve the TSP. GA is a system developing methods that uses the natural principle of a genetic population and involves three main processes that are crossover, mutation and inversion. GA is implemented with some new operators called Nearest Fragment (NF) and Modified Order Crossover (MOC). GA implementation on TSP is done by using Microsoft C++ Programming. Solutions to the problem are presented and performance comparison is
described with the existing best solution. |
|---|