Solving the Generalized Traveling Salesman Problem Using Sequential Constructive Crossover Operator in Genetic Algorithm

The generalized travelling salesman problem(GTSP),a generalization of the well-known travelling salesman problem(TSP),is considered for our study.Since the GTSP is NP-hard and very complex,finding exact solutions is highly expensive,we will develop genetic algorithms(GAs)to obtain heuristic solutions to the problem.In GAs,as the crossover is a very important process,the crossovermethods proposed for the traditional TSP could be adapted for the GTSP.The sequential constructive crossover(SCX)and three other operators are adapted to use in GAs to solve the GTSP.The effectiveness of GA using SCX is verified on some GTSP Library(GTSPLIB)instances first and then compared against GAs using the other crossover methods.The computational results show the success of the GA using SCX for this problem.Our proposed GA using SCX,and swap mutation could find average solutions whose average percentage of excesses fromthe best-known solutions is between 0.00 and 14.07 for our investigated instances.

A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery

In this paper, a hybrid genetic algorithm （GA） is proposed for the traveling salesman problem （TSP） with pickup and delivery （TSPPD）. In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics.

On the “Onion Husk” Algorithm for Approximate Solution of the Traveling Salesman Problem

The paper describes some implementation aspects of an algorithm for approximate solution of the traveling salesman problem based on the construction of convex closed contours on the initial set of points (“cities”) and their subsequent combination into a closed path (the so-called contour algorithm or “onion husk” algorithm). A number of heuristics related to the different stages of the algorithm are considered, and various variants of the algorithm based on these heuristics are analyzed. Sets of randomly generated points of different sizes (from 4 to 90 and from 500 to 10,000) were used to test the algorithms. The numerical results obtained are compared with the results of two well-known combinatorial optimization algorithms, namely the algorithm based on the branch and bound method and the simulated annealing algorithm. .

Appropriate Combination of Crossover Operator and Mutation Operator in Genetic Algorithms for the Travelling Salesman Problem

Genetic algorithms(GAs)are very good metaheuristic algorithms that are suitable for solving NP-hard combinatorial optimization problems.AsimpleGAbeginswith a set of solutions represented by a population of chromosomes and then uses the idea of survival of the fittest in the selection process to select some fitter chromosomes.It uses a crossover operator to create better offspring chromosomes and thus,converges the population.Also,it uses a mutation operator to explore the unexplored areas by the crossover operator,and thus,diversifies the GA search space.A combination of crossover and mutation operators makes the GA search strong enough to reach the optimal solution.However,appropriate selection and combination of crossover operator and mutation operator can lead to a very good GA for solving an optimization problem.In this present paper,we aim to study the benchmark traveling salesman problem(TSP).We developed several genetic algorithms using seven crossover operators and six mutation operators for the TSP and then compared them to some benchmark TSPLIB instances.The experimental studies show the effectiveness of the combination of a comprehensive sequential constructive crossover operator and insertion mutation operator for the problem.The GA using the comprehensive sequential constructive crossover with insertion mutation could find average solutions whose average percentage of excesses from the best-known solutions are between 0.22 and 14.94 for our experimented problem instances.

Improved ant colony optimization algorithm for the traveling salesman problems

Ant colony optimization （ACO） is a new heuristic algo- rithm which has been proven a successful technique and applied to a number of combinatorial optimization problems. The traveling salesman problem （TSP） is among the most important combinato- rial problems. An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature con- vergence problem of the basic ACO algorithm on TSP. The main idea is to partition artificial ants into two groups： scout ants and common ants. The common ants work according to the search manner of basic ant colony algorithm, but scout ants have some differences from common ants, they calculate each route＇s muta- tion probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability. Simulation on TSP shows that the improved algorithm has high efficiency and robustness.

The Quantum Approximate Algorithm for Solving Traveling Salesman Problem

The Quantum Approximate Optimization Algorithm(QAOA)is an algorithmic framework for finding approximate solutions to combinatorial optimization problems.It consists of interleaved unitary transformations induced by two operators labelled the mixing and problem Hamiltonians.To fit this framework,one needs to transform the original problem into a suitable form and embed it into these two Hamiltonians.In this paper,for the well-known NP-hard Traveling Salesman Problem(TSP),we encode its constraints into the mixing Hamiltonian rather than the conventional approach of adding penalty terms to the problem Hamiltonian.Moreover,we map edges(routes)connecting each pair of cities to qubits,which decreases the search space significantly in comparison to other approaches.As a result,our method can achieve a higher probability for the shortest round-trip route with only half the number of qubits consumed compared to IBM Q’s approach.We argue the formalization approach presented in this paper would lead to a generalized framework for finding,in the context of QAOA,high-quality approximate solutions to NP optimization problems.

Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem

As a typical representative of the NP-complete problem, the traveling salesman problem(TSP) is widely utilized in computer networks, logistics distribution, and other fields. In this paper, a discrete lion swarm optimization(DLSO) algorithm is proposed to solve the TSP. Firstly, we introduce discrete coding and order crossover operators in DLSO. Secondly, we use the complete 2-opt(C2-opt) algorithm to enhance the local search ability.Then in order to enhance the efficiency of the algorithm, a parallel discrete lion swarm optimization(PDLSO) algorithm is proposed.The PDLSO has multiple populations, and each sub-population independently runs the DLSO algorithm in parallel. We use the ring topology to transfer information between sub-populations. Experiments on some benchmarks TSP problems show that the DLSO algorithm has a better accuracy than other algorithms, and the PDLSO algorithm can effectively shorten the running time.

Applying the Method for Solving Traveling Salesman Problem Based on Backtracking Algorithm to Order Picking

In the distribution center, the way of order picking personnel to pick goods has two kinds: single picking and batch picking. Based on the way of the single picking and assumed warehouse model, in order to reduce the walking path of order picking, the order picking problem is transformed into the traveling salesman problem in this paper. Based on backtracking algorithm, the order picking path gets optimized. Finally verifing the optimization method under the environment of VC++6.0, order picking path in the warehouse model get optimized, and compared with the traditional order picking walking paths. The results show that in small and medium-sized warehouse, the optimization method proposed in this paper can reduce order picking walking path and improve the work efficiency as well as reduce the time cost.

Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs

Let G = （V, E） be a complete undirected graph with vertex set V, edge set E, and edge weights I（e） satisfying the triangle inequality. The vertex set V is partitioned into clusters V1, V2 ,…, Vk. The clustered traveling salesman problem （CTSP） seeks to compute the shortest Hamiltonian tour that visits all the vertices, in which the vertices of each cluster are visited consecutively. A two-level genetic algorithm （TLGA） was developed for the problem, which favors neither intra-cluster paths nor inter-cluster paths, thus realized integrated evolutionary optimization for both levels of the CTSP. Results show that the algorithm is more effective than known algorithms. A large-scale traveling salesman problem （TSP） can be converted into a CTSP by clustering so that it can then be solved by the algorithm. Test results demonstrate that the clustering TLGA for large TSPs is more effective and efficient than the classical genetic algorithm.

Use the Power of a Genetic Algorithm to Maximize and Minimize Cases to Solve Capacity Supplying Optimization and Travelling Salesman in Nested Problems

Using Genetic Algorithms (GAs) is a powerful tool to get solution to large scale design optimization problems. This paper used GA to solve complicated design optimization problems in two different applications. The aims are to implement the genetic algorithm to solve these two different (nested) problems, and to get the best or optimization solutions.

Traveling Salesman Problem Using an Enhanced Hybrid Swarm Optimization Algorithm

The traveling salesman problem( TSP) is a well-known combinatorial optimization problem as well as an NP-complete problem. A dynamic multi-swarm particle swarm optimization and ant colony optimization( DMPSO-ACO) was presented for TSP.The DMPSO-ACO combined the exploration capabilities of the dynamic multi-swarm particle swarm optimizer( DMPSO) and the stochastic exploitation of the ant colony optimization( ACO) for solving the traveling salesman problem. In the proposed hybrid algorithm,firstly,the dynamic swarms,rapidity of the PSO was used to obtain a series of sub-optimal solutions through certain iterative times for adjusting the initial allocation of pheromone in ACO. Secondly,the positive feedback and high accuracy of the ACO were employed to solving whole problem. Finally,to verify the effectiveness and efficiency of the proposed hybrid algorithm,various scale benchmark problems were tested to demonstrate the potential of the proposed DMPSO-ACO algorithm. The results show that DMPSO-ACO is better in the search precision,convergence property and has strong ability to escape from the local sub-optima when compared with several other peer algorithms.

An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem

In this paper we applicate the Hungarian algorithm for assignment problem to solve traveling salesman problem. Tree examples of application of algorithm are included.

Collision-free Scheduling of Multi-bridge Machining Systems： A Colored Traveling Salesman Problem-based Approach

Multi-bridge machining systems(MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially overlapping workspaces.Their scheduling problems can be abstracted into a serial-colored travelling salesman problem in which each salesman has some exclusive cities and some cities shared with its neighbor(s). To solve it, we develop a greedy algorithm that selects a neighboring city satisfying proximity. The algorithm allows a salesman to select randomly its shared cities and runs accordingly many times. It can thus be used to solve job scheduling problems for MBMS. Subsequently, a collision-free scheduling method is proposed to address both job scheduling and collision resolution issues of MBMS. It is an extension of the greedy algorithm by introducing time window constraints and a collision resolution mechanism. Thus, the augmented greedy algorithm can try its best to select stepwise a job for an individual machine such that no time overlaps exist between it and the job sequence of the neighboring machine dealt in the corresponding overlapping workspace; and remove such a time overlap only when it is inevitable. Finally, we conduct a case study of a large triplebridge waterjet cutting system by applying the proposed method.

K-DSA for the multiple traveling salesman problem

Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering method to divide all cities into several categories based on the center of various samples;the large-scale MTSP is divided into multiple separate traveling salesman problems(TSPs),and the TSP is solved through the DSA.The proposed algorithm adopts a solution strategy of clustering first and then carrying out,which can not only greatly reduce the search space of the algorithm but also make the search space more fully explored so that the optimal solution of the problem can be more quickly obtained.The experimental results from solving several test cases in the TSPLIB database show that compared with other related intelligent algorithms,the K-DSA has good solving performance and computational efficiency in MTSPs of different scales,especially with large-scale MTSP and when the convergence speed is faster;thus,the advantages of this algorithm are more obvious compared to other algorithms.

A Multi-Agent Approach for Solving Traveling Salesman Problem

The traveling salesman problem （TSP） is a classical optimization problem and it is one of a class of NP- Problem. This paper presents a new method named multiagent approach based genetic algorithm and ant colony system to solve the TSP. Three kinds of agents with different function were designed in the multi-agent architecture proposed by this paper. The first kind of agent is ant colony optimization agent and its function is generating the new solution continuously. The second kind of agent is selection agent, crossover agent and mutation agent, their function is optimizing the current solutions group. The third kind of agent is fast local searching agent and its function is optimizing the best solution from the beginning of the trial. At the end of this paper, the experimental results have shown that the proposed hybrid ap proach has good performance with respect to the quality of solution and the speed of computation.

Ant-cycle based on Metropolis rules for the traveling salesman problem

In this paper, recent developments of some heuristic algorithms were discussed. The focus was laid on the improvements of ant-cycle (AC) algorithm based on the analysis of the performances of simulated annealing (SA) and AC for the traveling salesman problem (TSP). The Metropolis rules in SA were applied to AC and turned out an improved AC. The computational results obtained from the case study indicated that the improved AC algorithm has advantages over the sheer SA or unmixed AC.

A Parallel Search System for Dynamic Multi-Objective Traveling Salesman Problem

This paper introduces a parallel search system for dynamic multi-objective traveling salesman problem. We design a multi-objective TSP in a stochastic dynamic environment. This dynamic setting of the problem is very useful for routing in ad-hoc networks. The proposed search system first uses parallel processors to identify the extreme solutions of the search space for each ofk objectives individually at the same time. These solutions are merged into the so-called hit-frequency matrix E. The solutions in E are then searched by parallel processors and evaluated for dominance relationship. The search system is implemented in two different ways master-worker architecture and pipeline architecture.

Development of an Efficient Genetic Algorithm for the Time Dependent Vehicle Routing Problem with Time Windows

This research considers the time-dependent vehicle routing problem (TDVRP). The time-dependent VRP does not assume constant speeds of the vehicles. The speeds of the vehicles vary during the various times of the day, based on the traffic conditions. During the periods of peak traffic hours, the vehicles travel at low speeds and during non-peak hours, the vehicles travel at higher speeds. A survey by TCI and IIM-C (2014) found that stoppage delay as percentage of journey time varied between five percent and 25 percent, and was very much dependent on the characteristics of routes. Costs of delay were also estimated and found not to affect margins by significant amounts. This study aims to overcome such problems arising out of traffic congestions that lead to unnecessary delays and hence, loss in customers and thereby valuable revenues to a company. This study suggests alternative routes to minimize travel times and travel distance, assuming a congestion in traffic situation. In this study, an efficient GA-based algorithm has been developed for the TDVRP, to minimize the total distance travelled, minimize the total number of vehicles utilized and also suggest alternative routes for congestion avoidance. This study will help to overcome and minimize the negative effects due to heavy traffic congestions and delays in customer service. The proposed algorithm has been shown to be superior to another existing algorithm in terms of the total distance travelled and also the number of vehicles utilized. Also the performance of the proposed algorithm is as good as the mathematical model for small size problems.

基于蚁群算法的Traveling Salesman Problem研究

本文介绍了一种求解复杂组合优化问题的新的拟生态算法——蚁群算法.阐述了该算法的基本原理以及蚁群算法在TSP问题上的应用,并提出了改进算法,使得算法有更好的全局性.

A Rule Based Evolutionary Optimization Approach for the Traveling Salesman Problem

The traveling salesman problem has long been regarded as a challenging application for existing optimization methods as well as a benchmark application for the development of new optimization methods. As with many existing algorithms, a traditional genetic algorithm will have limited success with this problem class, particularly as the problem size increases. A rule based genetic algorithm is proposed and demonstrated on sets of traveling salesman problems of increasing size. The solution character as well as the solution efficiency is compared against a simulated annealing technique as well as a standard genetic algorithm. The rule based genetic algorithm is shown to provide superior performance for all problem sizes considered. Furthermore, a post optimal analysis provides insight into which rules were successfully applied during the solution process which allows for rule modification to further enhance performance.