Metaheuristics for the Orienteering Problem with Hotel Selection (Metaheuristieken voor het orienteering probleem met hotel selectie)

Wanneer een toerist op enkele dagen een groot toeristisch gebied wil bezoeken, zoals een deel van een land of van Europa, moet een selectie gemaakt worden uit de mogelijke bezienswaardigheden. Tegelijkertijd moet ook voor elke nacht een verblijfplaats vastgelegd worden. De locatie van de gekozen verblijfplaatsen heeft uiteraard invloed op welke bezienswaardigheden er overdag bezocht kunnen worden en omgekeerd.
In dit doctoraat wordt deze situatie wiskundig gemodelleerd als een combinatorisch optimalisatieprobleem. Vervolgens worden er technieken uit operationeel onderzoek gebruikt om dit probleem op te lossen. Dit doctoraat bestaat uit twee delen. In het eerste deel wordt de hierboven geschetste situatie gemodelleerd als een nieuwe variant van het orienteering probleem, namelijk het orienteering probleem met hotel selectie. Vervolgens worden twee metaheuristieken geïmplementeerd om dit probleem op te lossen: een variable neighborhood search en een memetic algorithm.
In het tweede deel wordt een variant van dit probleem bekeken, waarin de openingsuren voor de bezienswaardigheden worden meegenomen. De complexiteit van deze variant is significant groter. Ook voor deze variant wordt een wiskundig model opgesteld en zowel een memetic algorithm als een two-stage heuristic worden uitgewerkt om dit probleem op te lossen.
Aangezien dit het eerste onderzoek is naar deze specifieke varianten van het orienteering probleem, werden ook een groot aantal nieuwe testinstanties gegenereerd op een zodanige manier dat voor elke instantie de optimale oplossing gekend is.
De kwaliteit van de ontwikkelde algoritmes wordt geëvalueerd door de gegeneerde instanties op te lossen. De resultaten van deze experimenten laten zien dat de voorgestelde algoritmes oplossingen van een hoge kwaliteit genereren binnen een aanvaardbare rekentijd en dat deze algoritmes gebruikt kunnen worden voor toepassingen in de praktijk.