**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**3583

# Search results for: traveling salesman problem.

##### 3583 Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA)

**Authors:**
Buthainah Fahran Al-Dulaimi,
Hamza A. Ali

**Abstract:**

The well known NP-complete problem of the Traveling Salesman Problem (TSP) is coded in genetic form. A software system is proposed to determine the optimum route for a Traveling Salesman Problem using Genetic Algorithm technique. The system starts from a matrix of the calculated Euclidean distances between the cities to be visited by the traveling salesman and a randomly chosen city order as the initial population. Then new generations are then created repeatedly until the proper path is reached upon reaching a stopping criterion. This search is guided by a solution evaluation function.

**Keywords:**
Genetic algorithms,
traveling salesman problem solving,
optimization.

##### 3582 A Comparison between Heuristic and Meta-Heuristic Methods for Solving the Multiple Traveling Salesman Problem

**Authors:**
San Nah Sze,
Wei King Tiong

**Abstract:**

**Keywords:**
Multiple Traveling Salesman Problem,
GeneticAlgorithm,
Nearest Neighbor Algorithm,
k-Means Clustering.

##### 3581 Genetic Algorithms with Oracle for the Traveling Salesman Problem

**Authors:**
Robin Gremlich,
Andreas Hamfelt,
Héctor de Pereda,
Vladislav Valkovsky

**Abstract:**

By introducing the concept of Oracle we propose an approach for improving the performance of genetic algorithms for large-scale asymmetric Traveling Salesman Problems. The results have shown that the proposed approach allows overcoming some traditional problems for creating efficient genetic algorithms.

**Keywords:**
Genetic algorithms,
Traveling Salesman Problem,
optimal decision distribution,
oracle.

##### 3580 Evaluation of the exIWO Algorithm Based On the Traveling Salesman Problem

**Authors:**
Daniel Kostrzewa,
Henryk Josiński

**Abstract:**

The expanded Invasive Weed Optimization algorithm (exIWO) is an optimization metaheuristic modelled on the original IWO version created by the researchers from the University of Tehran. The authors of the present paper have extended the exIWO algorithm introducing a set of both deterministic and non-deterministic strategies of individuals’ selection. The goal of the project was to evaluate the exIWO by testing its usefulness for solving some test instances of the traveling salesman problem (TSP) taken from the TSPLIB collection which allows comparing the experimental results with optimal values.

**Keywords:**
Expanded Invasive Weed Optimization algorithm (exIWO),
Traveling Salesman Problem (TSP),
heuristic approach,
inversion operator.

##### 3579 Block Based Imperial Competitive Algorithm with Greedy Search for Traveling Salesman Problem

**Authors:**
Meng-Hui Chen,
Chiao-Wei Yu,
Pei-Chann Chang

**Abstract:**

Imperial competitive algorithm (ICA) simulates a multi-agent algorithm. Each agent is like a kingdom has its country, and the strongest country in each agent is called imperialist, others are colony. Countries are competitive with imperialist which in the same kingdom by evolving. So this country will move in the search space to find better solutions with higher fitness to be a new imperialist. The main idea in this paper is using the peculiarity of ICA to explore the search space to solve the kinds of combinational problems. Otherwise, we also study to use the greed search to increase the local search ability. To verify the proposed algorithm in this paper, the experimental results of traveling salesman problem (TSP) is according to the traveling salesman problem library (TSPLIB). The results show that the proposed algorithm has higher performance than the other known methods.

**Keywords:**
Traveling Salesman Problem,
Artificial Chromosomes,
Greedy Search,
Imperial Competitive Algorithm.

##### 3578 Parallel Branch and Bound Model Using Logarithmic Sampling (PBLS) for Symmetric Traveling Salesman Problem

**Authors:**
Sheikh Muhammad Azam,
Masood-ur-Rehman,
Adnan Khalid Bhatti,
Nadeem Daudpota

**Abstract:**

Very Large and/or computationally complex optimization problems sometimes require parallel or highperformance computing for achieving a reasonable time for computation. One of the most popular and most complicate problems of this family is “Traveling Salesman Problem". In this paper we have introduced a Branch & Bound based algorithm for the solution of such complicated problems. The main focus of the algorithm is to solve the “symmetric traveling salesman problem". We reviewed some of already available algorithms and felt that there is need of new algorithm which should give optimal solution or near to the optimal solution. On the basis of the use of logarithmic sampling, it was found that the proposed algorithm produced a relatively optimal solution for the problem and results excellent performance as compared with the traditional algorithms of this series.

**Keywords:**
Parallel execution,
symmetric traveling salesman problem,
branch and bound algorithm,
logarithmic sampling.

##### 3577 The Frequency Graph for the Traveling Salesman Problem

**Authors:**
Y. Wang

**Abstract:**

**Keywords:**
Traveling salesman problem,
frequency graph,
local
optimal Hamiltonian path,
four vertices and three lines inequality.

##### 3576 An Improved Method to Compute Sparse Graphs for Traveling Salesman Problem

**Authors:**
Y. Wang

**Abstract:**

The Traveling salesman problem (TSP) is NP-hard in combinatorial optimization. The research shows the algorithms for TSP on the sparse graphs have the shorter computation time than those for TSP according to the complete graphs. We present an improved iterative algorithm to compute the sparse graphs for TSP by frequency graphs computed with frequency quadrilaterals. The iterative algorithm is enhanced by adjusting two parameters of the algorithm. The computation time of the algorithm is *O*(*CN*_{max}*n*^{2}) where *C* is the iterations, *N*_{max} is the maximum number of frequency quadrilaterals containing each edge and *n* is the scale of TSP. The experimental results showed the computed sparse graphs generally have less than 5*n* edges for most of these Euclidean instances. Moreover, the maximum degree and minimum degree of the vertices in the sparse graphs do not have much difference. Thus, the computation time of the methods to resolve the TSP on these sparse graphs will be greatly reduced.

**Keywords:**
Frequency quadrilateral,
iterative algorithm,
sparse graph,
traveling salesman problem.

##### 3575 A Genetic Algorithm with Priority Selection for the Traveling Salesman Problem

**Authors:**
Cha-Hwa Lin,
Je-Wei Hu

**Abstract:**

**Keywords:**
Traveling salesman problem,
hybrid geneticalgorithm,
priority selection,
2-OPT.

##### 3574 A New Heuristic Algorithm for the Classical Symmetric Traveling Salesman Problem

**Authors:**
S. B. Liu,
K. M. Ng,
H. L. Ong

**Abstract:**

**Keywords:**
Local search,
overlapped neighborhood,
travelingsalesman problem.

##### 3573 An Improved Genetic Algorithm to Solve the Traveling Salesman Problem

**Authors:**
Omar M. Sallabi,
Younis El-Haddad

**Abstract:**

The Genetic Algorithm (GA) is one of the most important methods used to solve many combinatorial optimization problems. Therefore, many researchers have tried to improve the GA by using different methods and operations in order to find the optimal solution within reasonable time. This paper proposes an improved GA (IGA), where the new crossover operation, population reformulates operation, multi mutation operation, partial local optimal mutation operation, and rearrangement operation are used to solve the Traveling Salesman Problem. The proposed IGA was then compared with three GAs, which use different crossover operations and mutations. The results of this comparison show that the IGA can achieve better results for the solutions in a faster time.

**Keywords:**
AI,
Genetic algorithms,
TSP.

##### 3572 Extended Low Power Bus Binding Combined with Data Sequence Reordering

**Authors:**
Jihyung Kim,
Taejin Kim,
Sungho Park,
Jun-Dong Cho

**Abstract:**

**Keywords:**
low power,
bus binding,
switching activity,
multiple
traveling salesman problem,
data sequence reordering

##### 3571 Implementation of Heuristics for Solving Travelling Salesman Problem Using Nearest Neighbour and Minimum Spanning Tree Algorithms

**Authors:**
Fatma A. Karkory,
Ali A. Abudalmola

**Abstract:**

The travelling salesman problem (TSP) is a combinatorial optimization problem in which the goal is to find the shortest path between different cities that the salesman takes. In other words, the problem deals with finding a route covering all cities so that total distance and execution time is minimized. This paper adopts the nearest neighbor and minimum spanning tree algorithm to solve the well-known travelling salesman problem. The algorithms were implemented using java programming language. The approach is tested on three graphs that making a TSP tour instance of 5-city, 10 –city, and 229–city. The computation results validate the performance of the proposed algorithm.

**Keywords:**
Heuristics,
minimum spanning tree algorithm,
Nearest Neighbor,
Travelling Salesman Problem (TSP).

##### 3570 Adapting the Chemical Reaction Optimization Algorithm to the Printed Circuit Board Drilling Problem

**Authors:**
Taisir Eldos,
Aws Kanan,
Waleed Nazih,
Ahmad Khatatbih

**Abstract:**

Chemical Reaction Optimization (CRO) is an optimization metaheuristic inspired by the nature of chemical reactions as a natural process of transforming the substances from unstable to stable states. Starting with some unstable molecules with excessive energy, a sequence of interactions takes the set to a state of minimum energy. Researchers reported successful application of the algorithm in solving some engineering problems, like the quadratic assignment problem, with superior performance when compared with other optimization algorithms. We adapted this optimization algorithm to the Printed Circuit Board Drilling Problem (PCBDP) towards reducing the drilling time and hence improving the PCB manufacturing throughput. Although the PCBDP can be viewed as instance of the popular Traveling Salesman Problem (TSP), it has some characteristics that would require special attention to the transactions that explore the solution landscape. Experimental test results using the standard CROToolBox are not promising for practically sized problems, while it could find optimal solutions for artificial problems and small benchmarks as a proof of concept.

**Keywords:**
Evolutionary Algorithms,
Chemical Reaction
Optimization,
Traveling Salesman,
Board Drilling.

##### 3569 Optimizing Logistics for Courier Organizations with Considerations of Congestions and Pickups: A Courier Delivery System in Amman as Case Study

**Authors:**
Nader A. Al Theeb,
Zaid Abu Manneh,
Ibrahim Al-Qadi

**Abstract:**

Traveling salesman problem (TSP) is a combinatorial integer optimization problem that asks "What is the optimal route for a vehicle to traverse in order to deliver requests to a given set of customers?”. It is widely used by the package carrier companies’ distribution centers. The main goal of applying the TSP in courier organizations is to minimize the time that it takes for the courier in each trip to deliver or pick up the shipments during a day. In this article, an optimization model is constructed to create a new TSP variant to optimize the routing in a courier organization with a consideration of congestion in Amman, the capital of Jordan. Real data were collected by different methods and analyzed. Then, concert technology - CPLEX was used to solve the proposed model for some random generated data instances and for the real collected data. At the end, results have shown a great improvement in time compared with the current trip times, and an economic study was conducted afterwards to figure out the impact of using such models.

**Keywords:**
Travel salesman problem,
congestions,
pick-up,
integer programming,
package carriers,
service engineering.

##### 3568 A New Heuristic for Improving the Performance of Genetic Algorithm

**Authors:**
Warattapop Chainate,
Peeraya Thapatsuwan,
Pupong Pongcharoen

**Abstract:**

**Keywords:**
Genetic Algorithm,
Hybridisation,
Metaheuristics,
Travelling Salesman Problem.

##### 3567 DACS3:Embedding Individual Ant Behavior in Ant Colony System

**Authors:**
Zulaiha Ali Othman,
Helmi Md Rais,
Abdul Razak Hamdan

**Abstract:**

**Keywords:**
Dynamic Ant Colony System (DACS),
Traveling Salesmen Problem (TSP),
Optimization,
Swarm Intelligent.

##### 3566 DNA Computing for an Absolute 1-Center Problem: An Evolutionary Approach

**Authors:**
Zuwairie Ibrahim,
Yusei Tsuboi,
Osamu Ono,
Marzuki Khalid

**Abstract:**

**Keywords:**
DNA computing,
operation research,
1-center
problem.

##### 3565 Ant System with Acoustic Communication

**Authors:**
S. Bougrine,
S. Ouchraa,
B. Ahiod,
A. A. El Imrani

**Abstract:**

Ant colony optimization is an ant algorithm framework that took inspiration from foraging behavior of ant colonies. Indeed, ACO algorithms use a chemical communication, represented by pheromone trails, to build good solutions. However, ants involve different communication channels to interact. Thus, this paper introduces the acoustic communication between ants while they are foraging. This process allows fine and local exploration of search space and permits optimal solution to be improved.

**Keywords:**
Acoustic Communication,
Ant Colony Optimization,
Local Search,
Traveling Salesman Problem.

##### 3564 Two Individual Genetic Algorithm

**Authors:**
Younis R. Elhaddad,
Aiman S.Gannous

**Abstract:**

The particular interests of this paper is to explore if the simple Genetic Algorithms (GA) starts with population of only two individuals and applying different crossover technique over these parents to produced 104 children, each one has different attributes inherited from their parents; is better than starting with population of 100 individuals; and using only one type crossover (order crossover OX). For this reason we implement GA with 52 different crossover techniques; each one produce two children; which means 104 different children will be produced and this may discover more search space, also we implement classic GA with order crossover and many experiments were done over 3 Travel Salesman Problem (TSP) to find out which method is better, and according to the results we can say that GA with Multi-crossovers is much better.

**Keywords:**
Artificial intelligence,
genetic algorithm,
order crossover,
travel salesman problem.

##### 3563 Optimization Technique in Scheduling Duck Tours

**Authors:**
Norhazwani M. Y.,
Khoo,
C. F.,
Hasrul Nisham R.

**Abstract:**

**Keywords:**
Optimization,
Reactive Tabu Search,
Tabu Search,
Travelling Salesman Problem

##### 3562 Combined Simulated Annealing and Genetic Algorithm to Solve Optimization Problems

**Authors:**
Younis R. Elhaddad

**Abstract:**

Combinatorial optimization problems arise in many scientific and practical applications. Therefore many researchers try to find or improve different methods to solve these problems with high quality results and in less time. Genetic Algorithm (GA) and Simulated Annealing (SA) have been used to solve optimization problems. Both GA and SA search a solution space throughout a sequence of iterative states. However, there are also significant differences between them. The GA mechanism is parallel on a set of solutions and exchanges information using the crossover operation. SA works on a single solution at a time. In this work SA and GA are combined using new technique in order to overcome the disadvantages' of both algorithms.

**Keywords:**
Genetic Algorithm,
Optimization problems,
Simulated Annealing,
Traveling Salesman Problem

##### 3561 DACS3: Embedding Individual Ant Behavior in Ant Colony System

**Authors:**
Zulaiha Ali Othman,
Helmi Md Rais,
Abdul Razak Hamdan

**Abstract:**

**Keywords:**
Dynamic Ant Colony System (DACS),
TravelingSalesmen Problem (TSP),
Optimization,
Swarm Intelligent.

##### 3560 An Integrated Framework for the Realtime Investigation of State Space Exploration

**Authors:**
Jörg Lassig,
Stefanie Thiem

**Abstract:**

**Keywords:**
Global Optimization Heuristics,
Particle Swarm Optimization,
Ensemble Based Threshold Accepting,
Ruin and Recreate

##### 3559 A Review of Genetic Algorithm Optimization: Operations and Applications to Water Pipeline Systems

**Authors:**
I. Abuiziah,
N. Shakarneh

**Abstract:**

Genetic Algorithm (GA) is a powerful technique for solving optimization problems. It follows the idea of survival of the fittest - Better and better solutions evolve from previous generations until a near optimal solution is obtained. GA uses the main three operations, the selection, crossover and mutation to produce new generations from the old ones. GA has been widely used to solve optimization problems in many applications such as traveling salesman problem, airport traffic control, information retrieval (IR), reactive power optimization, job shop scheduling, and hydraulics systems such as water pipeline systems. In water pipeline systems we need to achieve some goals optimally such as minimum cost of construction, minimum length of pipes and diameters, and the place of protection devices. GA shows high performance over the other optimization techniques, moreover, it is easy to implement and use. Also, it searches a limited number of solutions.

**Keywords:**
Genetic Algorithm,
optimization,
pipeline systems,
selection,
cross over.

##### 3558 The Rank-scaled Mutation Rate for Genetic Algorithms

**Authors:**
Mike Sewell,
Jagath Samarabandu,
Ranga Rodrigo,
Kenneth McIsaac

**Abstract:**

A novel method of individual level adaptive mutation rate control called the rank-scaled mutation rate for genetic algorithms is introduced. The rank-scaled mutation rate controlled genetic algorithm varies the mutation parameters based on the rank of each individual within the population. Thereby the distribution of the fitness of the papulation is taken into consideration in forming the new mutation rates. The best fit mutate at the lowest rate and the least fit mutate at the highest rate. The complexity of the algorithm is of the order of an individual adaptation scheme and is lower than that of a self-adaptation scheme. The proposed algorithm is tested on two common problems, namely, numerical optimization of a function and the traveling salesman problem. The results show that the proposed algorithm outperforms both the fixed and deterministic mutation rate schemes. It is best suited for problems with several local optimum solutions without a high demand for excessive mutation rates.

**Keywords:**
Genetic algorithms,
mutation rate control,
adaptive mutation.

##### 3557 Transferring Route Plan over Time

**Authors:**
Barıs Kocer,
Ahmet Arslan

**Abstract:**

**Keywords:**
genetic algorithms,
transfer learning,
travellingsalesman problem

##### 3556 A Comparative Analysis of Heuristics Applied to Collecting Used Lubricant Oils Generated in the City of Pereira, Colombia

**Authors:**
Diana Fajardo,
Sebastián Ortiz,
Oscar Herrera,
Angélica Santis

**Abstract:**

Currently, in Colombia is arising a problem related to collecting used lubricant oils which are generated by the increment of the vehicle fleet. This situation does not allow a proper disposal of this type of waste, which in turn results in a negative impact on the environment. Therefore, through the comparative analysis of various heuristics, the best solution to the VRP (Vehicle Routing Problem) was selected by comparing costs and times for the collection of used lubricant oils in the city of Pereira, Colombia; since there is no presence of management companies engaged in the direct administration of the collection of this pollutant. To achieve this aim, six proposals of through methods of solution of two phases were discussed. First, the assignment of the group of generator points of the residue was made (previously identified). Proposals one and four of through methods are based on the closeness of points. The proposals two and five are using the scanning method and the proposals three and six are considering the restriction of the capacity of collection vehicle. Subsequently, the routes were developed - in the first three proposals by the Clarke and Wright's savings algorithm and in the following proposals by the Traveling Salesman optimization mathematical model. After applying techniques, a comparative analysis of the results was performed and it was determined which of the proposals presented the most optimal values in terms of the distance, cost and travel time.

**Keywords:**
Heuristics,
optimization model,
savings algorithm used vehicular oil,
VRP.

##### 3555 Understanding Evolutionary Algorithms through Interactive Graphical Applications

**Authors:**
Javier Barrachina,
Piedad Garrido,
Manuel Fogue,
Julio A. Sanguesa,
Francisco J. Martinez

**Abstract:**

**Keywords:**
Education,
evolutionary algorithms,
evolution
strategies,
interactive learning applications.

##### 3554 A New Approach for Controlling Overhead Traveling Crane Using Rough Controller

**Authors:**
Mazin Z. Othman

**Abstract:**

This paper presents the idea of a rough controller with application to control the overhead traveling crane system. The structure of such a controller is based on a suggested concept of a fuzzy logic controller. A measure of fuzziness in rough sets is introduced. A comparison between fuzzy logic controller and rough controller has been demonstrated. The results of a simulation comparing the performance of both controllers are shown. From these results we infer that the performance of the proposed rough controller is satisfactory.

**Keywords:**
Accuracy measure,
Fuzzy Logic Controller (FLC),
Overhead Traveling Crane (OTC),
Rough Set Theory (RST),
Roughness measure