Search

This paper presents a strategy based on binary labelling of nodes for the creation of anti-loop formulations from existing strategies. This strategy prevents by default the formation of odd cycles, therefore it can have important role in iterative procedures based on generating subtour elimination constraints. It can also be used to modify the classic strategies used in problems associated to graphs. In this paper we focus on this last application. The behavior of this strategy is analyzed with two problems associated with graphs, the Asymmetric Traveling Salesman Problem (ATSP) and the Steiner Problem, where two configurations that modify the Miller-Tucking-Zemlig proposal to avoid cycles are compared. The experimental analysis shows that this strategy keep a good convergence, highlighting its use for the Steiner problem. [ABSTRACT FROM AUTHOR]

This paper addresses the well-known NP-hard problem, the Symmetric Travelling Salesman Problem (STSP), which has numerous applications in logistics and graph theory. To solve this complex problem, a discrete version of the Marine Predators Algorithm (D-MPA) is introduced. Although MPA has been extensively studied for various optimization problems and real-world applications, its use in routing problems, particularly TSP, remains relatively unexplored. To adapt MPA for STSP, the positions of individuals are initially updated using the classical MPA algorithm. The continuous values generated by the classical MPA are then converted to discrete values, followed by the application of a permutation operator to maintain diversity in the population. In addition, a local search algorithm, 2-opt, is applied to further improve the results for STSP instances. The effectiveness of the proposed algorithm is demonstrated on STSP benchmark instances of sizes ranging from 14 to 439. The performance of D-MPA is compared against several existing algorithms, including the Genetic Algorithm (GA), Bat Algorithm (BA), Discrete Firefly Algorithm (DFA), Evolutionary Simulated Annealing (ESA), Island-Based Distributed Genetic Algorithm (IDGA), Discrete Imperialist Competitive Algorithm (DICA), and Discrete Grey Wolf Optimization (DGWO). To ensure an unbiased and rigorous comparison, descriptive statistics such as mean and standard deviation are used, and a Wilcoxon Signed-Rank test is conducted for statistical validation. The results demonstrate that D-MPA not only competes, but also consistently outperforms these algorithms, making it a valuable resource for the research community. [ABSTRACT FROM AUTHOR]

Unmanned aerial vehicles (UAVs) are one of the most popular and effective systems in various industrial applications such as surveillance, security, and infrastructure inspection. It is gradually becoming an essential part of navigation as a consequence of high progress in military and civilian missions. Path planning of UAVs in military and civilian missions or in unknown and restricted environments is one of the biggest problems facing the operation of UAVs. This problem is not only searching for a path from an initial point to the final but also linked to find an optimal among all possible paths and provides collision avoidance. By examining the best path for UAVs, there is a need for the consideration of various other issues such as security and privacy, turning angle, overtake speed of obstacle, etc. The fundamental problem of UAVs is finding an optimal and secure route in a challenging environment. To overcome these challenges, many researchers have used optimization techniques such as ant colony, particle swarm, artificial bee colony, etc. with planning and coordination. In this paper, a blockchain-based solution is used to secure and authenticate UAVs. Hence, we propose a blockchain-based method that uses a genetic algorithm, which solves both constrained and unconstrained optimization problems. The purpose of this technique is to locate the best possible flight path for the UAVs in a three-dimensional setting. In a genetic algorithm, each iteration is designed to surpass the previous one in terms of improvement. To achieve an ideal route, solving the travelling salesman problem is a crucial step in the proposed approach. Consequently, the blockchain technology offers a reliable wireless communication and a dependable network for UAVs path planning, guaranteeing efficient service. Simulation results demonstrate the impact of the proposed scheme. They show that a genetic algorithm is suitable for optimal path planning for UAVs.

In the path version of the Travelling Salesman Problem (Path-TSP), a salesman is looking for the shortest Hamiltonian path through a set of n cities. The salesman has to start his journey at a given city s , visit every city exactly once, and finally end his trip at another given city t. In this paper we show that a special case of the Path-TSP with a Demidenko distance matrix is solvable in polynomial time. Demidenko distance matrices fulfill a particular condition abstracted from the convex Euclidian special case by Demidenko (1979) as an extension of an earlier work of Kalmanson (1975). We identify a number of crucial combinatorial properties of the optimal solution and design a dynamic programming approach with time complexity O (n 6). [ABSTRACT FROM AUTHOR]

This study aimed to model group preference decision-making to implement Industry 4.0 on food and beverage small- and medium-sized enterprises (SMEs). An ant colony optimisation was adopted to model the decision-making process based on the travelling salesman problem. The model was demonstrated on three preferences of Industry 4.0, namely, ergonomic work methods, machineries and tools, and e-commerce and promotion. The Likert-scale Kansei words data were obtained from 120 SMEs' manager in Indonesia. The data were then plotted to Cartesian coordinates with the x and y-axes showing the mode and average values, respectively, and were simulated in a sequence using ACO. The results indicated that machinery and tools were the most preferred to implement Industry 4.0. Adaptiveness was the most preferred attribute in making the first decision. The benchmarking demonstrated ACO performed better than genetic algorithm in modelling group preference. The group preference was also compared to trust level and the finding showed a high correlation between both constructs. The high trust in the group preferences is expected to contribute for the sustainability of Industry 4.0. The method enriches various existing theoretical approaches for group preference decision-making and applicable to assist the SME's management for implementation of Industry 4.0. [ABSTRACT FROM AUTHOR]

The paper proposes an effective hybrid ACO-GA evolutionary algorithm combining the best features of the Ant Colony Optimization and Genetic algorithm. The algorithm was tested on benchmark instances of the traveling salesman problem from TSPLIB and compared to several algorithms described in the scientific literature solving the same instances. The comparison results allow us to perceive the proposed ACO-GA as an attractive compromise between the quality of solutions and the time to find a solution. [ABSTRACT FROM AUTHOR]

The travelling salesman problem is a well-known optimisation problem, with a large scope of application and high theoretical significance. The problem may be stated as this. A travelling salesman has to visit some cities. He starts from one city, visits every other city exactly once, going from one city to another, and comes back to the city from where he started. The cost of visiting a city from another city is given. The total cost of the visits is to be minimised. The repetitive nearest neighbour (RNN) heuristic method is a heuristic method to solve the problem. We describe a property of the RNN heuristic method of the travelling salesman problem. A general, simple and elementary example is constructed to show the property of the heuristic method. It is shown that the RNN heuristic method, too, can have efficiency that is arbitrarily bad, without any bound. This may happen even for small instances of the problem. [ABSTRACT FROM AUTHOR]

Gardening pruning robots are widely applied in green space construction. However, increase of green space environment complexity and obstacle number affect the coverage range and work efficiency of robots. To solve this problem, this research proposed a full-coverage path planning algorithm integrating hybrid genetic ant colony and A* algorithm. Specifically tailored to the lawn working environments of horticultural pruning robots, we initially employed visual simultaneous localization and mapping to create a 3D point cloud map, converting it into an occupancy grid map for future path planning. The obtained grid map was partitioned into multiple subareas on the basis of the locations of obstacles. The optimal traversal order of sub-regions was determined using hybrid genetic ant colony method and a new update strategy of heuristic and pheromone factors was developed for improving the ability of global search and probability of jumping out of local optimal solution. Boustrophedon method was applied to fully cover each sub-region, A* algorithm was adopted to connect various sub-regions, and connection strategy was optimized. Simulation results showed that compared with traditional ant colony algorithm and other full-coverage planning algorithms, the algorithm developed in this research presented superior performance in terms of traversal path length, starting distance, coverage rate and turning times on maps with various sizes and complexities. [ABSTRACT FROM AUTHOR]

Genetic algorithms (GAs) are very goodmetaheuristic algorithms that are suitable for solving NP-hard combinatorial optimization problems. A simpleGA begins with 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. [ABSTRACT FROM AUTHOR]

The study presents theHalfMax InsertionHeuristic (HMIH) as a novel approach to solving the Travelling Salesman Problem (TSP). The goal is to outperform existing techniques such as the Farthest Insertion Heuristic (FIH) and Nearest Neighbour Heuristic (NNH). The paper discusses the limitations of current construction tour heuristics, focusing particularly on the significant margin of error in FIH. It then proposes HMIH as an alternative that minimizes the increase in tour distance and includes more nodes. HMIH improves tour quality by starting with an initial tour consisting of a 'minimum' polygon and iteratively adding nodes using our novel Half Max routine. The paper thoroughly examines and compares HMIH with FIH and NNH via rigorous testing on standard TSP benchmarks. The results indicate that HMIH consistently delivers superior performance, particularly with respect to tour cost and computational efficiency. HMIH's tours were sometimes 16% shorter than those generated by FIH and NNH, showcasing its potential and value as a novel benchmark for TSP solutions. The study used statistical methods, including Friedman's Non-parametric Test, to validate the performance of HMIH over FIH and NNH. This guarantees that the identified advantages are statistically significant and consistent in various situations. This comprehensive analysis emphasizes the reliability and efficiency of the heuristic, making a compelling case for its use in solving TSP issues. The research shows that, in general, HMIH fared better than FIH in all cases studied, except for a few instances (pr439, eil51, and eil101) where FIH either performed equally or slightly better than HMIH. HMIH's efficiency is shown by its improvements in error percentage (d) and goodness values (g) compared to FIH and NNH. In the att48 instance, HMIH had an error rate of 6.3%, whereas FIH had 14.6% and NNH had 20.9%, indicating that HMIH was closer to the optimal solution. HMIH consistently showed superior performance across many benchmarks, with lower percentage error and higher goodness values, suggesting a closer match to the optimal tour costs. This study substantially contributes to combinatorial optimization by enhancing current insertion algorithms and presenting a more efficient solution for the Travelling Salesman Problem. It also creates new possibilities for progress in heuristic design and optimization methodologies. [ABSTRACT FROM AUTHOR]

Genetic Algorithm is an optimization technique inspired by nature. The technique has been used by scientists and engineers for real-life search and optimization problems. This work makes use of the genetic algorithm for the solution of the traveling salesman problem. This work focuses on real-time problems; the algorithm is used to find the optimum path for sales travelers inside the Khyber Pakhtunkhwa Province of Pakistan. The solution provides the shortest distance between the cities to be traveled and gives the optimal route. The coding is done in Python-3 and software is developed for the traveling salesmen, where the salesmen can select the cities, they want to travel, and the software will provide the optimal path and the distance. [ABSTRACT FROM AUTHOR]

Due to the many applications of the travelling salesman problem, solving this problem has been considered by many researchers. One of the subsets of the travelling salesman problem is the metric travelling salesman problem in which a triangular inequality is observed. This is a crucial problem in combinatorial optimization as it is used as a standard problem as a basis for proving complexity or providing solutions to other problems in this class. The solution is used usually in logistics, manufacturing and other areas for cost minimization. Since this is an NP-hard problem, heuristic and meta-heuristic algorithms seek near-optimal solutions in polynomial time as numerical solutions. For this purpose, in this paper, a heuristic algorithm based on the minimum spanning tree is presented to solve this problem. Then, by generating 20 instances, the efficiency of the proposed algorithm was compared with one of the most famous algorithms for solving the travelling salesman problem, namely the nearest neighbour algorithm and the ant colony optimization algorithm. The results show that the proposed algorithm has good convergence to the optimal solution. In general, the proposed algorithm has a balance between runtime and the solution found compared to the other two algorithms. So the nearest neighbour algorithm has a very good runtime to reach the solution but did not have the necessary convergence to the optimal solution, and vice versa, the ant colony algorithm converges very well to the optimal solution, but, its runtime solution is very longer than the proposed algorithm.

The travelling salesman problem (TSP) and its variants have been studied extensively due to its wide range of real-world applications, yet there are challenges in providing efficient algorithms to deal with some of its variants. The multiple travelling salesman problem (MTSP), is the generalization of TSP, which aims to determine m−routes for ‘m’ salesmen to cover a set of n−cities exactly once where each route starts and ends at a depot such that the total distance is least. In this, the number of cities in each route of the optimal solution may be distributed disproportionately. This paper presents, a bi-objective MTSP (BMTSP) with the load balancing constraint, where the first objective is to minimize the total travel distance and the second objective minimizes the total time. A metaheuristic based genetic algorithm with tournament selection (GATS) is designed by integrating with mixed strategies, such as flip, swap and scramble in mutation operation to obtain efficient Pareto solution for BMTSP. The computational experiments are carried out on different data sets, which are derived from the TSPLIB. The performance of GATS is compared with different genetic approaches and simulation results show that the proposed GATS obtained improved solutions on some of the benchmark instances.

The travelling salesman problem (TSP) and its variants have been studied extensively due to its wide range of real-world applications, yet there are challenges in providing efficient algorithms to deal with some of its variants. The multiple travelling salesman problem (MTSP), is the generalization of TSP, which aims to determine m − routes for ' m ' salesmen to cover a set of n − cities exactly once where each route starts and ends at a depot such that the total distance is least. In this, the number of cities in each route of the optimal solution may be distributed disproportionately. This paper presents, a bi-objective MTSP (BMTSP) with the load balancing constraint, where the first objective is to minimize the total travel distance and the second objective minimizes the total time. A metaheuristic based genetic algorithm with tournament selection (GATS) is designed by integrating with mixed strategies, such as flip, swap and scramble in mutation operation to obtain efficient Pareto solution for BMTSP. The computational experiments are carried out on different data sets, which are derived from the TSPLIB. The performance of GATS is compared with different genetic approaches and simulation results show that the proposed GATS obtained improved solutions on some of the benchmark instances. [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]

The present work is based on Stochastic Traveling Salesman Problem (STSP), which is a famous combinatorial optimization problem with NP-hard in nature. In this research, we have taken the path length of each pair of all points in the network as stochastic nature (i.e. random variable) with the application of Genetic Algorithm (GA) for obtaining the optimal route of the Stochastic Traveling Salesman Problem (STSP). GA is a good search algorithm to optimize this type of stochastic problems. The aim of this work is to find the best solution for the STSP by GA with roulette wheel method (RWM). We have also used the advancement ability of hereditary calculation to locate the possible answer for STSP. The scope of this work is further extend to optimize large problems in the field of Industry, Logistics, and other transportation problems. [ABSTRACT FROM AUTHOR]

The travelling salesman problem(TSP) is a classic optimization puzzle, widely studied and celebrated for its significance in operations research, mathematics and computer science. It can also be described as an evolution from a mathematical curiosity to a problem that challenges the computation boundaries, sparks algorithmic innovation, and finds practical applications in various industries. The neutrosophic TSP(NTSP) extends the problem by introducing neutrosophy, handling indeterminacy and inconsistency with distances represented by neutrosophic numbers (NNs). The single-valued triangular fuzzy neutrosophic TSP(SVTFNTSP) goes a step further by incorporating both single-valued triangular fuzzy numbers (SVTFNs) and neutrosophy, representing distances with SVTFNNs. The single-valued triangular fuzzy neutrosophic numbers (SVTFNNs) provide a way to model uncertainty via triangular membership functions, offering a more nuanced representation of uncertain and vague distances. This arises the need to use them and enhances realism in solving complex real-world optimization problems. These extensions adapt the TSP to varying uncertain and vague data, ideal for intricate real-world optimization scenarios. This research article delves into the SVTFNTSP, expressed as a single-valued triangular fuzzy neutrosophic distance matrix (SVTFNDM) with SVTFNNs as its core elements, accounting for both uncertainty and imprecision. The investigation encompasses the formulation and examination of this specialized problem by incorporating a score function to assess defuzzification and optimality, alongside the utilization of a proposed systematic stepwise approach to efficiently ascertain optimal solutions. This approach is practically demonstrated through its application to real-world scenarios, effectively showcasing its feasibility and real-world relevance. Subsequently, through a rigorous comparative analysis with the established methodologies, the superior effectiveness and value of the proposed approach are highlighted, specifically in terms of minimizing total travelling costs. This reaffirms its potential as a robust solution for tackling the SVTFNTSP by underlining its practical utility and enhanced performance.

The optimization of route planning is a critical consideration frequently happened in the logistics of product distribution. This study addresses distribution issues, such as long trip distances, which result in high distribution costs. The objective of this research is to increase distribution routes' effectiveness, which will enable it to reach the minimize distance and lower the cost of product distribution. The Travelling Salesman Problem (TSP) can be resolved by using the Genetic Algorithm (GA) technique to optimize the path. Variations in crossover, mutation, and population were made when experimenting with GA. The results of the study indicate that the overall distance travelled decreased from 55.5 km to 30.45 km and that the cost of distributing the product was reduced from Rp 94,350.00 to Rp 51,765.00. There is a about 45% improvement. There is about 45% improvement. This optimisation technique has a favourable effect on the overall financial performance and competitiveness of businesses involved in comparable distribution operations, as well as improving operational efficiency and offering the possibility of cost savings.

Introduction. The traveling salesman problem is a transport-type problem. It is natural to use a method based on the technology for solving transport problems to solve it. The cyclicity and degeneracy of the solution to the traveling salesman problem requires significant modification of the corresponding stages of solving the transport problem (drawing up an initial feasible solution; checking the plan for optimality; obtaining a new feasible solution). Purpose. Development of a natural approach to solving the traveling salesman problem. Description of the structure of a set of traveling salesman problems that have a predetermined optimal solution. Algorithmic formation of such problems for the purpose of conducting mass computing experiments. Results. The paper presents new results and computational experiments with a developed natural algorithm for solving the traveling salesman problem, based on the technology for solving transport problems, including a new effective method for generating an initial cyclic solution, an algorithm for transitioning from the initial cyclic to another, also cyclic, solution. An algorithm has been developed for constructing the traveling salesman problem with an optimal solution given in advance, which allows for a better understanding of the structure of traveling salesman problems. Conclusions. The results of computational experiments show that the use of potentials method technology for solving the traveling salesman problem, as a special transport problem, is a promising direction for searching for a high-quality solution. The developed algorithms and programs expand the possibilities of solving the traveling salesman problem. The time it takes to solve a problem depends significantly on the size of the problem. In this regard, it is essential to automatically generate the traveling salesman problem with a given optimal solution, which allows you to conduct mass experiments and draw conclusions.

This paper studies an interval data min–max regret (IDMR) version of the packing-delivery problem, in which a 0-1 knapsack problem is for parcel packing and a capacitated travelling salesman problem is for parcel delivery. The parcel profits for the courier and the tour costs are uncertain and they can take any value from a specific interval with lower and upper bound values. The problem is how to select and deliver a subset of parcels to minimise the maximum regret of net profit which is the difference between the total profits of the selected parcels and the total delivery costs, to deal with the trade-off of the solution robustness and performance. To tackle the problem effectively, we first prove the worst-case scenario of a solution to the problem, based on which, a mixed integer linear programming is formulated. A Benders-like decomposition algorithm is then developed to solve small-scale problems to optimality within the manageable computation time. For medium- and large-scale problems, a simulated-annealing-based heuristic method with a local search procedure is designed. Extensive computational experiments show the efficiency and effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

The travelling salesman problem(TSP) is a classic optimization puzzle, widely studied and celebrated for its significance in operations research, mathematics and computer science. It can also be described as an evolution from a mathematical curiosity to a problem that challenges the computation boundaries, sparks algorithmic innovation, and finds practical applications in various industries. The neutrosophic TSP(NTSP) extends the problem by introducing neutrosophy, handling indeterminacy and inconsistency with distances represented by neutrosophic numbers(NNs). The single-valued triangular fuzzy neutrosophic TSP(SVTFNTSP) goes a step further by incorporating both single-valued triangular fuzzy numbers(SVTFNs) and neutrosophy, representing distances with SVTFNNs. The single-valued triangular fuzzy neutrosophic numbers(SVTFNNs) provide a way to model uncertainty via triangular membership functions, offering a more nuanced representation of uncertain and vague distances. This arises the need to use them and enhances realism in solving complex real-world optimization problems. These extensions adapt the TSP to varying uncertain and vague data, ideal for intricate real-world optimization scenarios. This research article delves into the SVTFNTSP, expressed as a single-valued triangular fuzzy neutrosophic distance matrix(SVTFNDM) with SVTFNNs as its core elements, accounting for both uncertainty and imprecision. The investigation encompasses the formulation and examination of this specialized problem by incorporating a score function to assess defuzzification and optimality, alongside the utilization of a proposed systematic stepwise approach to efficiently ascertain optimal solutions. This approach is practically demonstrated through its application to real-world scenarios, effectively showcasing its feasibility and real-world relevance. Subsequently, through a rigorous comparative analysis with the established methodologies, the superior effectiveness and value of the proposed approach are highlighted, specifically in terms of minimizing total travelling costs. This reaffirms its potential as a robust solution for tackling the SVTFNTSP by underlining its practical utility and enhanced performance. [ABSTRACT FROM AUTHOR]

The Travelling Salesman Problem (TSP) is a well-known optimisation problem that has been widely studied over the last century. As a result, a variety of exact and approximate algorithms have been proposed in the literature. When it comes to solving large instances in real-time, greedy algorithms guided by priority rules represent the most common approach, being the nearest neighbour (NN) heuristic one of the most popular rules. NN is quite general but it is too simple and so it may not be the best choice in some cases. Alternatively, we may design more sophisticated heuristics considering the particular features of families of instances. To do that, we have to consider problem attributes other than the proximity of the next city to build priority rules. However, this process may not be easy for humans and so it is often addressed by some learning procedure. In this regard, hyper-heuristics as Genetic Programming (GP) stands as one of the most popular approaches. Furthermore, a single heuristic, even being good in average, may not be good for a number of instances of a given set. For this reason, the use of ensembles of heuristics is often a good alternative, which raises the problem of building ensembles from a given set of heuristic rules. In this paper, we study the application of two kinds of ensembles to the TSP. Given a set of TSP instances having similar characteristics, we firstly exploit a GP to build a set of heuristics involving a number of problem attributes, and then we build ensembles combining these heuristics by means of a Genetic Algorithm (GA). The experimental study provided valuable insights into the construction and utilisation of single rules and ensembles. It clearly demonstrated that the performance of ensembles justifies the time invested when compared to using individual heuristics. [ABSTRACT FROM AUTHOR]

Order-picking optimization in a business sustainable competitiveness context is challenging due to prior studies focusing on theoretical model development with unrealistic assumptions in their algorithms and methodological validation, often neglecting practical concerns. This paper improves order-picking operations by employing combinatorial optimization as a travelling salesman problem and class-based dedicated storage models for the ATP company. The paper's originality and novelty lie in bridging the gap between academia and management, presenting an effort to connect theoretical concepts with practical optimization in order-picking warehouse operations in an environment of competitiveness. Realistic data and LINGO software were employed, revealing substantial improvements in the ATP warehouse operations through optimized pick path decisions embedded in warehouse layouts. This paper provides managerial tools for distance traveled optimization in the warehouse that yield competitive edges, enhanced supply chain efficiency and effectiveness, as well as other positive impacts on social, and environmental concerns such as labor safety, customer satisfaction, energy consumption, and CO2 emission. The paper also outlines future research directions to advance warehouse management and address sustainable competitiveness challenges, adding a new dimension to the original research. [ABSTRACT FROM AUTHOR]

A travelling thief problem (TTP) is a proxy to real-life problems such as postal collection. TTP comprises an entanglement of a travelling salesman problem (TSP) and a knapsack problem (KP) since items of KP are scattered over cities of TSP, and a thief has to visit cities to collect items. In TTP, city selection and item selection decisions need close coordination since the thief's travelling speed depends on the knapsack's weight and the order of visiting cities affects the order of item collection. Existing TTP solvers deal with city selection and item selection separately, keeping decisions for one type unchanged while dealing with the other type. This separation essentially means very poor coordination between two types of decision. In this paper, we first show that a simple local search based coordination approach does not work in TTP. Then, to address the aforementioned problems, we propose a human designed coordination heuristic that makes changes to collection plans during exploration of cyclic tours. We further propose another human designed coordination heuristic that explicitly exploits the cyclic tours in item selections during collection plan exploration. Lastly, we propose a machine learning based coordination heuristic that captures characteristics of the two human designed coordination heuristics. Our proposed coordination based approaches help our TTP solver significantly outperform existing state-of-the-art TTP solvers on a set of benchmark problems. Our solver is named Cooperation Coordination (CoCo) and its source code is available from https://github.com/majid75/CoCo. [ABSTRACT FROM AUTHOR]

The Genetic Algorithm (GA) was developed as a search engine for difficult non-deterministic polynomial optimization problems. However, it suffers from internal weaknesses, such as premature convergence and low computation efficiency. One critical aspect of the GA is the selection process, which determines new paths and ultimately guides the algorithm towards a solution. This paper details a novel selection procedure that is a perfect blend of the two extremes, namely exploitation and exploration. The proposed technique eliminates the fitness scaling problem by changing the selection pressure continuously during the selection stage. Utilizing traveling salesman problem library (TSPLIB) instances, a performance comparison of the proposed method with a few traditional selection methods was conducted, and the proposed strategy yielded much better outcomes in the form of standard deviations and mean values. A two-sided t-test was also developed, and the results revealed that the proposed strategy enhanced the performance of a GA substantially. [ABSTRACT FROM AUTHOR]

This article explores how machine learning can be applied in efficiently solving a variation of the Travelling Salesman Problem (TSP) in the context of air travel tourism. Large number of cities create too many trip route combinations to be efficiently evaluated in real time. The method proposed uses a feedforward neural network to narrow down the number of trip route combinations, while a more traditional algorithm based on dynamic programming is then able to select the best trip offers. It was shown that the method could be applied in practice to achieve almost real-time generation of best possible trip offers while evaluating a large amount of real-world flight data. [ABSTRACT FROM AUTHOR]

Travelling salesman problem (TSP) is a well known combinatorial optimization problem which has drawn colossal attention due to its eclectic range of applications. In this article, we have proposed two modified versions of intelligent water drops (IWD) algorithm. The first one is the enhanced IWD (e-IWD) algorithm to solve single objective TSP. In the second modification, e-IWD algorithm has been extended to enhanced multi-objective IWD(e-MIWD) algorithm for solving multi-objective TSP. In order to achieve a better exploration capability in both of the proposed algorithms, the soil and velocity parameters of a randomly selected water drop are updated after every iteration of the algorithm when it traverses all the intermediate vertices for a tour. The proposed algorithms have been compared with some other existing similar algorithms on different benchmark instances of TSPs. Furthermore, we have addressed the TSP for both single and multiple objectives under uncertain environment.