Traveling salesman problem (TSP) is a well-known NP-hard problem which can not be solved within a polynomial bounded computation time. However, genetic algorithm (GA) is a familiar heuristic algorithm to obtain near-optimal solutions within reasonable time for TSPs. In TSPs, the geometric properties are problem specific knowledge can be used to enhance GAs. Some tour segments (edges) of TSPs are fine while some maybe too long to appear in a short tour. Therefore, this information can help GAs to pay more attention to fine tour segments and without considering long tour segments as often. Consequently, we propose a new algorithm, called intelligent-OPT hybrid genetic algorithm (IOHGA), to exploit local optimal tour segments and enhance the searching process in order to reduce the execution time and improve the quality of the offspring. The local optimal tour segments are assigned higher priorities for the selection of tour segments to be appeared in a short tour. By this way, tour segments of a TSP are divided into two separate sets. One is a candidate set which contains the candidate fine tour segments and the other is a non-candidate set which contains non-candidate fine tour segments. According to the priorities of tour segments, we devise two genetic operators, the skewed production (SP) and the fine subtour crossover (FSC). Besides, we combine the traditional GA with 2-OPT local search algorithm but with some modifications. The modified 2-OPT is named the intelligent OPT (IOPT). Simulation study was conducted to evaluate the performance of the IOHGA. The experimental results indicate that generally the IOHGA could obtain near-optimal solutions with less time and higher accuracy than the hybrid genetic algorithm with simulated annealing algorithm and the genetic algorithm using the gene expression algorithm. Thus, the IOHGA is an effective algorithm for solving TSPs. If the case is not focused on the optimal solution, the IOHGA can provide good near-optimal solutions rapidly. Therefore, the IOHGA could be incorporated with some clustering algorithm and applied to mobile agent planning problems (MAP) in a real-time environment.

Dans cette thèse, nous proposons des solutions parrallèles basées sur le systèmes actuel GPU (graphics processing unit) pour deux problèmes de minimisation de graphe Euclidien, à savoir le problème de forêt/arbre couvrant minimum Euclidien (EMSF / EMST) et le problème du voyageur commerce (TSP). Les solutions proposées résolvent également aussi le problème d'une paire bichromatique la plus proche (BCP), et suivent la technique de ``contrôle décentralisé, du parallélisme des données et des mémoires partagées par GPU".Nous proposons une technique de recherche dans le voisinage le plus proche de dimension K Euclidienne basée sur les approches classiques de NNS d’Elias qui divisent l’espace Euclidien en cellules congruentes et ne se chevauchant pas, où la taille des points de chaque cellule est délimitée. Nous proposons aussi une technique d'élagage pour obtenir le NNS à base de composants afin de trouver le point de sortie le plus proche de l'ensemble de points de requête de Q dans la complexité temporelle linéaire séquentielle lorsque les données sont uniformément réparties. Ces techniques sont utilisées conjointement avec deux GPU algorithmes proposés pour arbre traversement, à savoir la recherche en largeur bidirectionnelle GPU et la liste chaînée dynamique distribuée, afin d'adresser le BCP. Basé sur la solution BCP, un algorithme parallèle Divide and Conquer est implémenté pour construire EMSF et EMST totalement côté GPU. Le TSP est adressé avec différents algorithmes de recherche locaux parallèles 2-opt, dans lesquels nous proposons une méthodologie ``évaluation multiple K-opt, mouvements multiples K-opt" afin d’exécuter simultanément, sans interférence, des processus massifs 2-/3-opt mouvements qui se retrouvent globalement sur le même circuit TSP pour de nombreux bords. Cette méthodologie est expliquée en détail pour montrer comment nous obtenons un calcul haute performance à la fois du côté du GPU et CPU. Nous testons les solutions proposées et rapportons des résultats de comparaison expérimentale par rapport aux algorithmes de pointe. / In this thesis, we propose parallel solutions based on current graphics processing unit (GPU) system for two Euclidean graph minimization problems, namely the Euclidean minimum spanning forest/tree (EMSF/EMST) and the travelling salesman problem (TSP). The proposed solutions also solve the bichromatic closest pair (BCP) problem, and follow technique of ``decentralized control, data parallelism, GPU shared memories".We propose a Euclidean K-dimensional nearest neighbourhood search (NNS) technique based on classical Elias' NNS approaches that divide the Euclidean space into congruent and non-overlapping cells where size of points in each cell is bounded. We propose a pruning technique to obtain component-based NNS to find a query point set Q's closest outgoing point within sequential linear time complexity when the data is uniformly distributed. These techniques are used together with two proposed GPU tree traversal algorithms, namely the GPU two-direction Breadth-first search and distributed dynamic linked list, to address the BCP. Based on the BCP solution, a divide and conquer parallel algorithm is implemented for building EMSF and EMST totally on GPU side. The TSP is addressed with different parallel 2-opt local search algorithms, in which we propose a ``multiple K-opt evaluation, multiple K-opt moves" methodology in order to simultaneously execute, without interference, massive 2-/3-opt moves that are globally found on the same TSP tour for many edges. This methodology is explained in details to show how we obtain high performance computing both on GPU and CPU side. We test the proposed solutions and report experimental comparison results against the state-of-the-art algorithms.

Ammunition Transfer System (ATS) is the electro-mechanical system of the Ammunition Resupply Vehicle (ARV) which will be used to meet T-155 mm Firtina howitzers&rsquo / ammunition demand for tactical requirements of higher firing rate by off-road mobility and survivability. The transfer of ammunitions from ARV to Firtina is to be optimized for an effective improvement of firing rate. In this thesis the transferring order of carried ammunitions is being optimized to minimize the total ammunition transferring time. This transfer problem is modeled as a modification of Travelling Salesman Problem (TSP). The given locations of the ammunitions are treated as cities to be visited and the gripper of ATS is treated as the traveling salesman. By GAMS / the small-size problems are solved optimally but large-size ones get only local optimum. A heuristic algorithm that contains nearest neighbor heuristics as construction method and 2-opt exchange heuristic as improvement method is developed to obtain same or better solutions obtained by GAMS with less computational time.

Ant Colony Optimization (ACO) algorithms have been successful in solving a wide variety of NPhard optimization problems. The Traveling Salesman Problem (TSP) has served as a benchmarking problem for many novel ACO algorithms. The slightly harder Dynamic Traveling Salesman Problem (DTSP) is more realistic in the sense that real-time changes happen in the graph belonging to a TSP instance. This thesis studied the original ACO algorithm: the Ant System, and how the amount of pheromone deposited by the ants within the algorithm affected the performance when solving both TSP and DTSP problems. Additionally, 2-opt local search was added to the algorithm, to see how it impacted the performance. We found that when the ants deposited a greater amount of pheromone, the performance for TSP increased, while the performance for DTSP decreased. We concluded that the Ant System in its original form is unsuitable for solving the DTSP. 2-opt local search improved the performance in all instances. / Ant Colony Optimization-algoritmer (ACO) har visat sig vara bra på att lösa många olika NP-svåra optimeringsproblem. För att mäta prestandan för nya ACO-algoritmer har i många fall Handelsresandeproblemet (eng. TSP) använts. Den dynamiska varianten av TSP (eng. DTSP), är ett något svårare problem då förändringar i grafen kan ske i realtid. Denna uppsats utredde hur olika mängder feromon som avges av myrorna inuti algoritmen Ant System, påverkade prestandan för både TSPoch DTSP-instanser. Utöver detta studerades hur den lokala sökningsheuristiken 2-opt påverkade prestandan. Resultaten visade att om myrorna tilläts släppa mer feromoner, ökade prestantan för TSP, men minskade för DTSP. Därav drog vi slutsatsen att algoritmen Ant System i sin ursprungliga form ej är lämplig för att lösa DTSP. Den lokala söknigsheuristiken 2-opt förbättrade prestandan i alla tester.