Abstract

Travelling Salesman Problem (TSP) has been a favorite problem to solve. The idea is to search an optimal route between location. TSP always uses a distance as a cost, although there are other costed elements except for the distance. We found out that obstacle was another cost besides distance in TSP. It increases the elements to be evaluated. We need an approach to solve multi-elements TSP. Multi-Element Genetic Algorithm (ME-GA) was used to solve the NP-hard problem. It was proved that ME-GA provided a solution for a multi-element problem. In the crossover process, we use Partial Map Crossover (PMX), showing that PMX is overwhelmed Oder Crossover (OX) and Cycle Crossover (CX) methods. We formulate a multi-elements fitness function by three elements: distance, fixed obstacle, and non-fixed obstacles. The elements have a proportion of the fitness function; we give 70% for the distance, 20% for the fixed obstacle and 10% for the non-fixed obstacles. The results show that the distance of the location increased but we can minimize the number of obstacles. Compared to if only distance to evaluation, we find the shortest distance between the location, but we cannot decrease the number of obstacles.

Concepts :

Access to Document

Citations by Year