Algorithms for large orienteering problems
Gorka Kobeaga Urriolabeitia · 2021
Tesi lan honetan, tamaina handiko Orientazio Problemak ebazteko algoritmoak garatu ditugu. Orientazio Problema optimizazio konbinatorioko problema bat da: herri multzo bat eta hauen arteko distantzia emanik, herri bakoitzak bere saria duelarik, eta ibilbidearen distantzia osoaren murrizketa bat ezarririk, problemaren helburua sarien batura maximizatzen duen ibilbidea aurkitzean datza. Orientazio Problema ebazteko, algoritmo ebolutibo bat eta Branch-and-Cut algoritmo bat garatu ditugu. Algoritmo ebolutiboaren ezaugarri nagusienetako bat, soluzio ez bideragarriekin lan egitea da. Eragile genetikoen ikuspuntutik algoritmo honen ekarpen nagusia Orientazio Problemarentzako proposatutako Ertzen Birkonbinazio Gurutzaketa da. Beste ekarpen bat problema handiak ebazteko aproposa den bilaketa lokala da. Branch-and-Cut algoritmoak berriz, ziklo problementzako banantze algoritmoetan, banantze begiztan, aldagaien baloratzean, eta problemaren goi eta behe-mugen kalkuluan ditu ekarpen nagusiak. Aldi berean, ziklo problementzako algoritmo zehatzaren parte diren euskarri grafoen sinplifikazio teknika eta azpizikloak identifikatzeko separazio algoritmoak aztertu ditugu. Tamaina handiko problemekin, 7393 herrirainokoak, egindako esperimentuek erakusten dute bi algoritmoek primerako emaitzak lortzen dituztela, bai soluzioen kalitatearen aldetik eta bai algoritmoen azkartasunaren aldetik ere.------En esta tesis, hemos desarrollado algoritmos para resolver instancias de gran tamano para el Problema de Orientacion. El Problema de Orientacion es un problema de optimizacion combinatoria en el cual, dado un grafo, con distancias asociadas en las aristas y premios en los vertices, y la restriccion de longitud maxima de la ruta, el objetivo es maximizar la suma de recompensas de las ciudades visitadas.Para resolver el Problema de Orientacion, hemos desarrollado un algoritmo evolutivo y un algoritmo Branch-and-Cut. La principal caracteristica del algoritmo evolutivo es el uso de soluciones infactibles durante de la busqueda. Desde el punto de vista de los operadores geneticos, la contribucion mas notable es el desarrollo del Cruce de Recombinacion de Aristas para el Problema de Orientacion. Otra contribucion ha sido el desarrollo de una busqueda local que permite abarcar problemas de gran tamano. El algoritmo Branch-and-Cut incluye contribuciones en los algoritmos de separacion para problemas de ciclos, en el bucle de separacion, en la estimacion de precios de las variables, y en el calculo de las cotas inferiores y superiores del problema. Al mismo tiempo, generalizamos para problemas de ciclos, la contraccion de grafos soporte y procedimientos para acelerar la separacion exacta de las restricciones de eliminacion de subciclos. Los experimentos llevados a cabo en problemas de gran tamano, problemas de hasta 7393 nodos, muestran que ambos algoritmos obtienen resultados excelentes, en terminos de la calidad de la solucion y en terminos del tiempo de ejecucion.--------In this thesis, we have developed algorithms to solve large-scale Orienteering Problems. The Orienteering Problem is a combinatorial optimization problem were given a weighted complete graph with vertex profits and a maximum distance constraint, the goal is to find the simple cycle which maximizes the sum of the profits of the visited vertices. To solve the Orienteering Problem, we have developed an evolutionary algorithm and a Branch-and-Cut algorithm. One of the key characteristics of the evolutionary algorithm is to work with unfeasible solutions. From the point of view of genetic operators, the main contribution has been the development of the Edge Recombination Crossover for the Orienteering Problem, which in a wider context it is also valid for any cycle problem. Another contribution has been the developed local search to handle large problems. The Branch-and-Cut algorithm includes new contributions in the separation algorithms of inequalities stemming from the cycle problem, in the separation loop, in the variables pricing, and in the calculation of the lower and upper bounds of the problem. At the same time, we have generalized for cycle problems the support graph shrinking techniques and procedures to speed up the exact separation algorithms for subcycle elimination constraints. The experiments carried out in large-sized instances, up to 7393 nodes, show that both algorithms achieve outstanding results, both in terms of the quality of solutions and in terms of the execution time.