Search

The traveling salesman problem (TSP) is a frequently studied problem by researchers today and belongs to the class of combinatorial optimization problems. It can be used to solve many current world problems such as scheduling, circuit design, layout design of plants in factories, route planning and printed circuit design. Therefore, researchers working in the field of optimization methods use it as a realistic test environment and evaluate the performance of new algorithms on it. In this study, a discrete version of the orca predation algorithm (OPA) was developed, called DOPA. DOPA is a novel discrete and permutation-coded optimization algorithm. As in OPA, it consists of two phases: chasing and attacking. However, these phases in DOPA were arranged to be able to solve a combinatorial optimization problem such as TSP. In the chasing phase, the distances between the orcas were calculated with the Hamming distance, and the speed values were obtained by using these distances. The positions of the orcas were updated using the speed values and 2-opt algorithm. In the attacking phase, the positions of the orcas were calculated by order crossover (OX1) operator. In the position adjustment procedure, swap local search operator was used. Thus, the convergence of the algorithm was accelerated. DOPA has much less parameters than OPA. Therefore, it is a simple and effective algorithm with few parameters. The parameters of DOPA were optimized by the Taguchi statistical method. It was tested on 67 well-known TSP instances. The results of different performance measures and tests showed that DOPA is a highly competitive and alternative method compared to other methods. [ABSTRACT FROM AUTHOR]

Copyright of Dokuz Eylul University Muhendislik Faculty of Engineering Journal of Science & Engineering / Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi is the property of Dokuz Eylul Universitesi Muhendislik Fakultesi Fen ve Muhendislik Dergisi and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The Traveling Salesman Problem (TSP) seeks the shortest closed tour that visits each city once and returns to the starting city. This problem is NP-hard, so it is not easy to solve using conventional methods. The grey wolf optimization (GWO) algorithm has shown outstanding performance in many practical applications. However, it is inclined towards premature convergence. This paper proposes an improved GWO (I-GWO) algorithm, which hybridizes GWO with genetic algorithms (GA) for the TSP. The main feature of the I-GWO algorithm is that it can make full use of the advantages of the GWO algorithm and the GA algorithm to make up for their respective shortcomings. Moreover, to make the GWO suitable for solving the TSP, both the 2-opt operator strategy and hamming distance h ave been designed to implement the discrete GWO directly. Additionally, to increase the diversity of solutions by expanding the search space, we present a new population update strategy with crossover and mutation operations in the next iteration. Meanwhile, the integration of the Simulated Annealing (SA) algorithm into the Improved Grey Wolf Optimizer (I-GWO) enhances its local search capabilities. Experimental results show that the I-GWO algorithm competes with established optimal methods for solving the TSP, suggesting its potential for different TSP variants and logistic transport domains. [ABSTRACT FROM AUTHOR]

This paper shows a novel method relied on growth optimization (GO) algorithm for searching the shortest tour length of the travelling salesman problem (TSP). GO is a recent algorithm relied on the idea of learning and reflecting of people in the society. To enhance performance of GO, the 2-opt local search technique is applied for adjusting the candidate solutions created by GO. The effectiveness of GO is validated on five TSP instances consisting of the 14-city, 30-city, 48-city, 52-city and 76-city. The error between the optimal tour length value obtained by GO and the best-known value for these instances is 0.0000%, 0.0000%, 0.0021%, 0.0314% and 0.0004%, respectively. Furthermore, the comparisons to the methods in the literature in term of the optimal and mean tour length values have shown that GO reaches the better values compared to other prvious methods. Thus, the proposed GO approach is a potential method for the TSP problem. [ABSTRACT FROM AUTHOR]

Particle Swarm Optimization (PSO) is a commonly used optimization to solve many problems. The PSO, which is developed for continuous optimization, is updated to solve discrete problems and Discrete PSO (DPSO) is obtained in this study. With DPSO, the Traveling Salesman Problem (TSP), which is well-known in the literature as a discrete problem, is solved. In order to improve the results, the swap method, the shift method, and the symmetry method are added to DPSO. The symmetry method is a new and successful method. The variations of the DPSO occurred according to the selected method type (DPSO1 (swap method), DPSO2 (shift method), DPSO3 (swap and shift methods), DPSO4 (symmetry method), DPSO5 (swap, shift, and symmetry methods), DPSO6 (swap, shift, symmetry, and 2-opt methods)). The effect of each method on the performance of the DPSO has been studied in detail. To demonstrate the success of the variations of the DPSO, the results are additionally compared with many well-known and new discrete algorithms in the literature. The results showed that the performance of DPSO has improved with the symmetry method and it has achieved better results than the discrete heuristic algorithms recently proposed in the literature. [ABSTRACT FROM AUTHOR]

We develop a novel method to improve biogeography-based optimization (BBO) for solving the traveling salesman problem (TSP). The improved method is comprised of a greedy randomized adaptive search procedure, the 2-opt algorithm, and G2BBO. The G2BBO formulation is derived and the process flowchart is shown in this article. For solving TSP, G2BBO effectively avoids the local minimum problem and accelerates convergence by optimizing the initial values. To demonstrate, we adopt three public datasets (eil51, eil76, and kroa100) from TSPLIB and compare them with various well-known algorithms. The results of G2BBO as well as the other algorithms perform close enough to the optimal solutions in eil51 and eil76 where simple TSP coordinates are considered. In the case of kroa100, with more complicated coordinates, G2BBO shows greater performance over other methods. [ABSTRACT FROM AUTHOR]

This paper deals with multi-objective school bus routing problem, which includes route balance, total number of school buses and total travel distance optimization objectives. An improved non-dominated sorting genetic algorithm (NSGAII) is proposed to solve this problem. First, the definition of measurement indicator that denotes the degree of route balance is given based on the analysis of the solved problem. And then, the multi-objective optimization function is provided. In the proposed algorithm, the individuals are obtained by using the tournament selection, sequential crossover and inverse mutation. The 2-opt neighborhood operator is adopted to improve the best individuals obtained in each iteration. At the same time, the route selection rule based on the degree of route balance is applied to select the final optimal solution set. The solution with better balance degree will be taken as the best solution. Finally, some benchmark instances are used to test the effectiveness of proposed algorithm. The results reveal that the proposed algorithm outperforms the standard NSGAII and Multi-objective Evolutionary Algorithm(MOEA). The experimental results also show that our algorithm has good stability. [ABSTRACT FROM AUTHOR]

The Continuous Hopfield Network (CHN) became one of the major breakthroughs in the come back of Neural Networks in the mid 80s, as it could be used to solve combinatorial optimization problems such as the Traveling Salesman Problem. Once researchers provided a mechanism, not based in trial-and-error, to guarantee the feasibility of the CHN, the quality of the solution was inferior to the ones provided by other heuristics. The next natural step is to study the behavior of the CHN as an optimizer, in order to improve its performance. With this regard, this paper analyzes the attractor basins of the CHN and establishes the mathematical foundations that guarantee the behavior of the network as a 2-opt; with the aim to open a new research line in which the CHN may be used, given the appropriate parameter setting, to solve a k-opt, which would make the network highly competitive. The analysis of the attraction basins of the CHN and its interpretation as a 2-opt is the subject of this article. [ABSTRACT FROM AUTHOR]

In view of the application scenarios that multiple UAVs cooperate with each other to complete the field sensor data collection task, it is particularly important to establish a path planning problem model for multiple UAVs with accurate energy consumption model. This paper presented the MUPP-AEC problem. The MUPP-AEC toke into account the differences in energy consumption under U AV acceleration, deceleration, cruising in constant speed and turning. For solving the MUPP-AEC, this paper proposed the DBSO-OS. In DBSO-OS, this paper proposed individual space integer encoding and the phased greedy decoding strategy with 2-opt,and defined the perturbation operator and individual update operator discretely. The individual update operators adopted the new individual generation strategy utilizing the random inversion transformation and the partial matching transformation. The experimental results show that the proposed algorithm can effectively solve the MUPP-AEC. The proposed discrete brainstorm operator is superior to the traditional brainstorm operators in terms of global convergence ability, convergence precision, and stability. In the small and medium-sized test cases and the large test cases, the proposed algorithm is better than the compared algorithms. [ABSTRACT FROM AUTHOR]

Local search is a fundamental tool in the development of heuristic algorithms. A neighborhood operator takes a current solution and returns a set of similar solutions, denoted as neighbors. In best improvement local search, the best of the neighboring solutions replaces the current solution in each iteration. On the other hand, in first improvement local search, the neighborhood is only explored until any improving solution is found, which then replaces the current solution. In this work we propose a new strategy for local search that attempts to avoid low-quality local optima by selecting in each iteration the improving neighbor that has the fewest possible attributes in common with local optima. To this end, it uses inequalities previously used as optimality cuts in the context of integer linear programming. The novel method, referred to as delayed improvement local search, is implemented and evaluated using the travelling salesman problem with the 2-opt neighborhood and the max-cut problem with the 1-flip neighborhood as test cases. Computational results show that the new strategy, while slower, obtains better local optima compared to the traditional local search strategies. The comparison is favourable to the new strategy in experiments with fixed computation time or with a fixed target. [ABSTRACT FROM AUTHOR]

The vehicle problem (VRP) is a typical optimization problem in logistics and transportation. The objective function is to find the shortest route distances visited by all vehicles originating from a central deport to travel customers, and the sum of deliveries of each vehicle should meet the capacity constraint. This problem belongs to NP hard problems, so it is not easy to resolve it with common methods. Ant colony optimization (ACO) has shown prominent performance for many practical applications. However, it is inclined to premature convergence. The paper offers a hybrid ACO&DE algorithm, which hybridizes ant colony optimization (ACO) with differential evolution (DE) for the VRP. The main feature of the ACO&DE can make full use of advantages of the ACO and DE algorithm to make up for its own weakness, i.e., the ACO has fast construction mechanism, and the DE can extend the search scope of the ACO. Moreover, to make the DE suitable for solving the VRP, both strategies of mutation operator and crossover operator have been redesigned to implement the discrete DE directly. In addition, to increase the solution diversity by expanding the search space, we present a new selection strategy with probabilistic mechanism to determine new target vectors in the next iteration. Meanwhile, 2-opt heuristic and 2-exchange neighborhood is embedded in the ACO&DE to improve the local search performance. The results have shown that the proposed ACO&DE algorithm is competitive with existing optimal methods in solving the VRP, and thus can be further extended in variants of the VRP and other logistics transportation fields. [ABSTRACT FROM AUTHOR]

This paper presents a new method based on Equilibrium Optimizer (EO) algorithm that is inspired from the mass balance of a control volume for traveling salesman problem (TSP). For enhancing the efficiency of EO, the 2- opt movement algorithm is used to update the solution generated by EO. The efficiency of the proposed EO for the TSP problem has been compared with Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) on different instances consisting of the 14-city, 30-city, 48-city and 52-city. The calculated results show that for the large scale instances such as 48-city and 52-city, EO has found the better tour than PSO. In comparison with GA, EO has ability finding the best tour with the smaller mean and standard deviation. The comparisons with previous methods in literature have also demonstrated that EO has ability to search the better tour than other methods. Thus, the proposed EO can be a potential method for the TSP problem. [ABSTRACT FROM AUTHOR]

The multiple Travelling Salesmen Problem (mTSP) is one of the most popular and important operational research problems. It is a problem where n salesmen have to visit m cities such that each salesman has to visit at least one city and all the cities should be visited exactly once, starting and ending at one specific city. In this paper a new hybrid approach called AC2OptGA is proposed to solve the mTSP. AC2OptGA is a combination of three algorithms: Modified Ant Colony, 2-Opt, and Genetic Algorithm. Ant Colony-based algorithm is used to generate solutions on which the 2-Opt edge exchange algorithm is applied to enhance the obtained solutions. A Genetic Algorithm is then used to again improve the quality of the solutions. The reason behind combining the above-mentioned algorithms is to exploit their strengths in both global and local searches. The proposed approach is evaluated using various data instances from standard benchmarks. Using the TSPLIB benchmarks for large-sized instances, AC2OptGA shows better results than M-GELS, the current best known approach. For medium and small-sized data instances, AC2OptGA shows better results than other approaches and comparable results to M-GELS. Using the MTSP benchmarks (MTSP-51, MTSP-100 and MTSP-150), AC2OptGA outperforms other methods for number of salesmen less than 10 and is competitive with NMACO (BKS) for 10 salesmen.

For the capacitated vehicle routing problem(CVRP),this paper proposed an imperialist competitive algorithm which integrated a split mechanism to solve the problem.Firstly,combined with the characteristics of CVRP,this algorithm used the encoding and decoding strategies based on greedy criteria to switch from the algorithm space to the solution space.Secondly,this algorithm presented an imperialist splitting mechanism to improve the global search ability of the algorithm,and simultaneously combined with the 2-Opt algorithm to enhance the local search ability.Finally,the results of simulation experiments with 25 benchmark examples indicate that:the proposed algorithm can effectively solve CVRP,and the optimization errors of all examples are less than 1.0%.Furthermore,the proposed algorithm is more efficiently than the existing imperialist competitive algorithms,particle swarm optimization algorithm,genetic algorithm and cuckoo search algorithm. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Computer Engineering & Applications is the property of Beijing Journal of Computer Engineering & Applications Journal Co Ltd. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Fig. 1. Graphic abstract of paper. • We propose a new faster and effective solution algorithm based on simple heuristic algorithms called the mixed steepest descent method and compared with other traditional algorithms. • The large scale case study and numerical results show that our method has strong applicability. • We apply this algorithm in emergency air logistics. In this paper, a new mixed steepest descent algorithm which has short computation time and stable solution is provided. Comparisons and case studies based on different traffic network and distance are made with other intelligent and exact algorithms. The large-scale experiment shows that the possibility of securing the optimal solution is greater than 99.5% and the average computation time is lower than 0.06 s when the node scales are less than 50. The proposed algorithm can not only be applied in emergency logistics problems but is also useful for solving other real-world problems. [ABSTRACT FROM AUTHOR]

This paper presents a Memetic Chicken swarm optimization (MeCSO) to solve job shop scheduling problem (JSSP). The aim is to find a better solution which minimizes the maximum of the completion time also called Makespan. In this paper, we adapt the chicken swarm algorithm which take into consideration the hierarchical order of chicken swarm while seeking for food. Moreover, we integrate 2-opt method to improve the movement of the rooster. The new algorithm is applied on some instances of OR-Library. The empirical results show the forcefulness of MeCSO comparing to other metaheuristics from literature in term of run time and quality of solution. [ABSTRACT FROM AUTHOR]

Harmony search algorithm that matches the (µ+1) evolution strategy, is a heuristic method simulated by the process of music improvisation. In this paper, a harmony search algorithm is directly used for the travelling salesman problem. Instead of conventional selection operators such as roulette wheel, the transformation of real number values of harmony search algorithm to order index of vertex representation and improvement of solutions are obtained by using the 2-Opt local search algorithm. Then, the obtained algorithm is tested on two different parameter groups of TSPLIB. The proposed method is compared with classical 2-Opt which randomly started at each step and best known solutions of test instances from TSPLIB. It is seen that the proposed algorithm offers valuable solutions.

In this work, we extended the original Traveling Salesman Problem (TSP) to cover not only the case of multiple vehicles but also to constrain the minimum and maximum numbers of cities each vehicle can visit. Our algorithm is a modified Ant Colony Optimization (ACO) algorithm which has the ability to avoid local optima; our algorithm can be applied to transportation problem that covers either a single vehicle or multiple vehicles. To the original ACO, we added a new reproduction method, a new pheromone updating strategy, and four improved local search strategies. We tested our algorithm on several standard datasets in the TSP library. Its single-vehicle performance was compared to that of ant system (AS) and elitist ant system (EAS) algorithms. Its multiple-vehicle performance was evaluated against that of ant colony system variants reported in the literature. The experiments show that our proposed ACO’s single-vehicle performance was superior to that of AS and EAS on every tested dataset and its multiple-vehicle performance was excellent.

We consider a generalization of the classical quadratic assignment problem, where material flows between facilities are uncertain, and belong to a budgeted uncertainty set. The objective is to find a robust solution under all possible scenarios in the given uncertainty set. We present an exact quadratic formulation as a robust counterpart and develop an equivalent mixed integer programming model for it. To solve the proposed model for large-scale instances, we also develop two different heuristics based on 2-Opt local search and tabu search algorithms. We discuss performance of these methods and the quality of robust solutions through extensive computational experiments.

Graphical Processing Units have been applied to solve NP-hard problems with no known polynomial time solutions. An example of such a problem is the Traveling Salesman Problem (TSP). The TSP is one of the most commonly studied combinatorial optimization problems and has multiple applications in the areas of engineering, transportation, and logistics. This article presents an improved algorithm for approximating the TSP on fully connected, symmetric graphs by utilizing the GPU. Our approach improves an existing 2-opt hill-climbing algorithm with random restarts by considering multiple updates to the current path found in parallel, and it allows k number of updates per iteration, called k-swap. With our k-swap modification, we show a speed-up over the existing algorithm of 4.5× to 22.9× on data sets ranging from 1,400 to 33,810 nodes, respectively. [ABSTRACT FROM AUTHOR]

2-Opt is a simple local search heuristic for the traveling salesperson problem that performs very well in experiments with respect to both running time and solution quality. In contrast to this, there are instances on which 2-Opt may need an exponential number of steps to reach a local optimum. To understand why 2-Opt usually finds local optima quickly in experiments, we study its expected running time in the model of smoothed analysis, which can be considered as a less-pessimistic variant of worst-case analysis in which the adversarial input is subject to a small amount of random noise. In our probabilistic input model, an adversary chooses an arbitrary graph G and a probability density function for each edge according to which its length is chosen. We prove that in this model the expected number of local improvements is O (mnΦ·16√lnm) = m1+o(1)nΦ, where n and mdenote the number of vertices and edges of G, respectively, and Φ denotes an upper bound on the density functions. [ABSTRACT FROM AUTHOR]

Harmony search algorithm that matches the (μ+1) evolution strategy, is a heuristic method simulated by the process of music improvisation. In this paper, a harmony search algorithm is directly used for the travelling salesman problem. Instead of conventional selection operators such as roulette wheel, the transformation of real number values of harmony search algorithm to order index of vertex representation and improvement of solutions are obtained by using the 2-Opt local search algorithm. Then, the obtained algorithm is tested on two different parameter groups of TSPLIB. The proposed method is compared with classical 2-Opt which randomly started at each step and best known solutions of test instances from TSPLIB. It is seen that the proposed algorithm offers valuable solutions. [ABSTRACT FROM AUTHOR]