Show simple item record

dc.contributor.authorKobeaga, G. en_US
dc.description.abstractIn 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 an 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.en_US
dc.description.sponsorshipBERC.2014-2017 SEV-2013-0323 PID2019-104933GB-I00 MTM2015-65317-Pen_US
dc.rightsReconocimiento-NoComercial-CompartirIgual 3.0 Españaen_US
dc.subjectOrienteering Problemen_US
dc.subjectEvolutionary Algorithmen_US
dc.subjectLarge Problemsen_US
dc.subjectCycle Problemen_US
dc.titleAlgorithms for Large Orienteering Problemsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Reconocimiento-NoComercial-CompartirIgual 3.0 España
Except where otherwise noted, this item's license is described as Reconocimiento-NoComercial-CompartirIgual 3.0 España