China
Africa
Explore chapters and articles related to this topic
Adaptation in Genetic Algorithms
Published in Sankar K. Pal, Paul P. Wang, Genetic Algorithms for Pattern Recognition, 2017
Lalit M. Patnaik, Srinivas Mandavilli
TSP: The traveling salesman problem (TSP) involves finding the shortest Hamiltonian cycle in a complete graph of n nodes. The Euclidean distance between any two nodes is computed from their coordinates. An instance of the TSP is specified by n, the number of cities, and the coordinates of the n cities (nodes). In our implementations, we have employed the order crossover operator [7, 16], and a mutation operator that swaps the positions of two randomly chosen cities. pc and pm determine the probability with which the operators are employed. We have chosen the 30-city and 105-city problems (see Reference [22] for coordinates of cities) for comparing the performance of the SGA and the AGA.
Mean and Insensitive. Random Permutations.
Published in Miklós Bóna, Combinatorics of Permutations, 2022
Now let p and q be two randomly selected n-permutations, and consider the graph Gp,q on vertex set [n] whose edges are the edges of Gp and the edges of Gq. Let n go to infinity. What is the probability that Gp,q contains a directed Hamiltonian cycle? (A Hamiltonian cycle of a graph is a cycle that contains all vertices of the graph.)
Optimal Graph Traversals
Published in Jonathan L. Gross, Jay Yellen, Mark Anderson, Graph Theory and Its Applications, 2018
Jonathan L. Gross, Jay Yellen, Mark Anderson
The next two heuristic algorithms have low-order polynomial complexity, and both have performance guarantees for graphs satisfying the triangle inequality. Both algorithms find a minimum spanning tree, create an Eulerian tour of an associated graph, and then extract a Hamiltonian cycle from the Eulerian tour by taking shortcuts.
Teams of robots in additive manufacturing: a review
Published in Virtual and Physical Prototyping, 2023
Abdullah Alhijaily, Zekai Murat Kilic, A. N. Paulo Bartolo
The starting and ending points of each line in the toolpath are either custom determined or taken directly from a readily available slicer software. After finding these points, the toolpath generation problem must be formulated. There are several reported attempts that formulate the toolpath generation as an optimisation problem. Two of these formulations are the Traveling Salesman Problem (TSP) (Ganganath et al. 2016) and the Rural Postman Problem (RPP) (Iori and Novellani 2020) (Figure 18). The TSP is concerned with finding the shortest Hamiltonian cycle that connects all the nodes in a graph. The RPP, on the other hand, tries to identify the shortest Euler cycle connecting all the required edges in a graph. Both TSP and RPP are proven to be NP-Hard problems (Jünger, Reinelt, and Rinaldi 1995). In the TSP any node can be connected to any other node. This is not applicable for toolpath generation of AM, as printing lines that connect two points must not be changed. Therfore, some researchers use the RPP instead of the TSP for the toolpath generation problem (Fok et al. 2018). However, the TSP can be transformed to the RPP and vice versa (Baldacci and Maniezzo 2006). There are several variations of these problems that can be used for toolpath generation and additional information can be found in (Monnot and Toulouse 2014; Eiselt, Gendreau, and Laporte 1995). To solve these problems different heuristics and metaheuristics are used.
An Effective Way to Large-Scale Robot-Path-Planning Using a Hybrid Approach of Pre-Clustering and Greedy Heuristic
Published in Applied Artificial Intelligence, 2020
Robot-path-planning has been prevailing in the field of robotics (Jahanshahi and Sari 2018). It aims to search the shortest path for a mobile robot, from a starting point to an ending one given in a finite workspace. In this research, the ending point is the same as the starting one, and every target past by the robot can be exactly visited once, which is the well-known traveling salesman problem (TSP). In the field of combinatorial optimization, it is a NP-hard problem (Holmqvist, Migdalas, and Pardalos 1997; Johnson and McGeoch 2007) for finding the shortest Hamiltonian cycle in a graph, where no algorithm with reasonable time is known for the solutions currently. Due to the NP-hard nature, it will be difficult to solve the large-scale TSP (Allwright and Carpenter 1989; Applegate and Cook 1993) when the moving targets become more and more, which requires enormous computational effort.
The adaptation of the harmony search algorithm to the ATSP with the evaluation of the influence of the pitch adjustment place on the quality of results
Published in Journal of Information and Telecommunication, 2019
Urszula Boryczka, Krzysztof Szwarc
The Traveling Salesman Problem (TSP) is a classical combinatorial optimization problem that involves finding the shortest Hamiltonian cycle in a complete weighted graph. Its popularity stems from the fact that it belongs to the class of NP-hard problems and that it can model a variety of utilitarian issues – its asymmetric variant (characterized by the possibility of varying weights of edges connecting the same nodes), representing line infrastructure located in urban areas, has become the basis for many logistical problems (it models, for example, the process of planning the mobile collection of waste electrical and electronic equipment, which has been described by Mrówczyńska & Nowakowski, 2015; Nowakowski, Szwarc, & Boryczka, 2018, and the process of transport activities related to the acquisition of municipal waste, described by Płaczek & Szołtysek, 2008; Syberfeldt, Rogstrom, & Geertsen, 2015).