**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**3588

# Search results for: symmetric traveling salesman problem

##### 3588 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.

##### 3587 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.

##### 3586 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.

##### 3585 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.

##### 3584 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.

##### 3583 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.

##### 3582 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.

##### 3581 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.

##### 3580 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.

##### 3579 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.

##### 3578 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.

##### 3577 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

##### 3576 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).

##### 3575 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.

##### 3574 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.

##### 3573 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.

##### 3572 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.

##### 3571 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.

##### 3570 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.

##### 3569 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.

##### 3568 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

##### 3567 The Inverse Eigenvalue Problem via Orthogonal Matrices

**Authors:**
A. M. Nazari,
B. Sepehrian,
M. Jabari

**Abstract:**

In this paper we study the inverse eigenvalue problem for symmetric special matrices and introduce sufficient conditions for obtaining nonnegative matrices. We get the HROU algorithm from [1] and introduce some extension of this algorithm. If we have some eigenvectors and associated eigenvalues of a matrix, then by this extension we can find the symmetric matrix that its eigenvalue and eigenvectors are given. At last we study the special cases and get some remarkable results.

**Keywords:**
Householder matrix,
nonnegative matrix,
Inverse eigenvalue problem.

##### 3566 Conjugate Gradient Algorithm for the Symmetric Arrowhead Solution of Matrix Equation AXB=C

**Authors:**
Minghui Wang,
Luping Xu,
Juntao Zhang

**Abstract:**

*AXB=C*and the associate optimal approximation problem are considered for the symmetric arrowhead matrix solutions in the premise of consistency. The convergence results of the method are presented. At last, a numerical example is given to illustrate the efficiency of this method.

**Keywords:**
Iterative method,
symmetric arrowhead matrix,
conjugate gradient algorithm.

##### 3565 The Partial Non-combinatorially Symmetric N10 -Matrix Completion Problem

**Authors:**
Gu-Fang Mou,
Ting-Zhu Huang

**Abstract:**

An n×n matrix is called an N1 0 -matrix if all principal minors are non-positive and each entry is non-positive. In this paper, we study the partial non-combinatorially symmetric N1 0 -matrix completion problems if the graph of its specified entries is a transitive tournament or a double cycle. In general, these digraphs do not have N1 0 -completion. Therefore, we have given sufficient conditions that guarantee the existence of the N1 0 -completion for these digraphs.

**Keywords:**
Matrix completion,
matrix completion,
N10 -matrix,
non-combinatorially symmetric,
cycle,
digraph.

##### 3564 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

##### 3563 An Iterative Updating Method for Damped Gyroscopic Systems

**Authors:**
Yongxin Yuan

**Abstract:**

The problem of updating damped gyroscopic systems using measured modal data can be mathematically formulated as following two problems. Problem I: Given Ma ∈ Rn×n, Λ = diag{λ1, ··· , λp} ∈ Cp×p, X = [x1, ··· , xp] ∈ Cn×p, where p<n and both Λ and X are closed under complex conjugation in the sense that λ2j = λ¯2j−1 ∈ C, x2j = ¯x2j−1 ∈ Cn for j = 1, ··· , l, and λk ∈ R, xk ∈ Rn for k = 2l + 1, ··· , p, find real-valued symmetric matrices D,K and a real-valued skew-symmetric matrix G (that is, GT = −G) such that MaXΛ2 + (D + G)XΛ + KX = 0. Problem II: Given real-valued symmetric matrices Da, Ka ∈ Rn×n and a real-valued skew-symmetric matrix Ga, find (D, ˆ G, ˆ Kˆ ) ∈ SE such that Dˆ −Da2+Gˆ−Ga2+Kˆ −Ka2 = min(D,G,K)∈SE (D− Da2 + G − Ga2 + K − Ka2), where SE is the solution set of Problem I and · is the Frobenius norm. This paper presents an iterative algorithm to solve Problem I and Problem II. By using the proposed iterative method, a solution of Problem I can be obtained within finite iteration steps in the absence of roundoff errors, and the minimum Frobenius norm solution of Problem I can be obtained by choosing a special kind of initial matrices. Moreover, the optimal approximation solution (D, ˆ G, ˆ Kˆ ) of Problem II can be obtained by finding the minimum Frobenius norm solution of a changed Problem I. A numerical example shows that the introduced iterative algorithm is quite efficient.

**Keywords:**
Model updating,
iterative algorithm,
gyroscopic system,
partially prescribed spectral data,
optimal approximation.

##### 3562 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.

##### 3561 An Iterative Method for the Least-squares Symmetric Solution of AXB+CYD=F and its Application

**Authors:**
Minghui Wang

**Abstract:**

Based on the classical algorithm LSQR for solving (unconstrained) LS problem, an iterative method is proposed for the least-squares like-minimum-norm symmetric solution of AXB+CYD=E. As the application of this algorithm, an iterative method for the least-squares like-minimum-norm biymmetric solution of AXB=E is also obtained. Numerical results are reported that show the efficiency of the proposed methods.

**Keywords:**
Matrix equation,
bisymmetric matrix,
least squares problem,
like-minimum norm,
iterative algorithm.

##### 3560 New DES based on Elliptic Curves

**Authors:**
Ghada Abdelmouez M.,
Fathy S. Helail,
Abdellatif A. Elkouny

**Abstract:**

**Keywords:**
DES,
Elliptic Curves,
hybrid system,
symmetricencryption.

##### 3559 An Iterative Method for the Symmetric Arrowhead Solution of Matrix Equation

**Authors:**
Minghui Wang,
Luping Xu,
Juntao Zhang

**Abstract:**

**Keywords:**
Symmetric arrowhead matrix,
iterative method,
like-minimum norm,
minimum norm,
Algorithm LSQR.