Gastles 2: Orienteering problem (Pieter van Steenwegen)

Question 1

Leg het concept uit van het optimalisatieprobleem bij de orienteering problem.

Answer 1

1. Persoonlijke data
   - Interesses
   - Beperkingen van de trip
2. Point of interest database
   => De persoonlijke interesses worden gecombineerd met de Point of interest database om een schatting te maken van de attracties voor de persoon.
   => Deze attracties worden fan gecombineerd met de beperkingen van de trip om een persoonlijke trip te maken voor de persoon.

Question 2

Wat is het orienteering probleem?

Answer 2

Bij het orienteering probleem

• Krijg je een set van punten die elk een waarde hebben
• De reistijd tussen all punten is gekend
• De beschikbare tijd is gekend

Beslissing: welke punten bezoeken
Doelfunctie: maximaliseren van de totale score
Beperkingen:
- Binnen de beschikbare tijd
- Er is een begin- en eindpunt
- Elk punt kan maximaal 1 keer worden bezocht.

Question 3

Welke 2 gekende optimalisatieproblemen komen terug in het orienteeringsprobleem?

Answer 3

1. Knapzak probleem

2. Rittenplanningprobleem (VRP)

Question 4

Wat was de uitbreiding op het orienteeringprobleem?

Answer 4

Uitbreiding: multiple day orienteering problem

Question 5

Wat zijn de typische technieken die gebruikt kunnen worden om het orienteeringsprobleem op te lossen? en van wat hangt de keuze van de techniek af?

Answer 5

Typische technieken:

• Exacte technieken
• (Meta -) heuristieken
• Simulatie
• Machine learning

Keuze van de techniek hangt af van:

• Beschikbare tijd
• Accurraatheid v/d oplossing
• Robustheid v/d oplossing

Bij een online applicatie willen mensen zeer snel een oplossing en zullen we dus heuristieken en metaheuristieken gebruiken.

Question 6

Als we het orienteeringsprobleem oplossen met een heuristiek krijgen we een grafiek met een specifiek verloop. Leg dit verloop kort uit.

Answer 6

De heuristiek zal eerst zoeken om de score te verhogen. Als dit niet meer lukt zal de score gelijk blijven maar zullen er punten veranderen zodat er meer tijd is en de score terug kan worden verhoogd.

Question 7

Welke metaheuristieken kunnen er worden gebruikt voor het (team) - orienteeringspobleem?

Answer 7

1. Tabu search (TS)
2. Variable Neighbourhood Search (VNS)
3. Ant colony optimalisatie
4. Greedy randomised adaptive search procedure (GRASP)

Question 8

Bij het kiezen van een metaheuristiek moeten we een afweging maken tussen 2 elementen. De welke?

Answer 8

1. Intensificatie
   - oplossingen verbeteren stap per stap
   - verbeteringen snel en lokaal evalueren
2. Diversificatie
   - Ontsnap aan het lokaal optimum
   - Zoeken naar een nieuw en beter lokaal optimum

Question 9

Hoe kan intensificatie worden toegepast?

Answer 9

1. Insert move: 1 punt toevoegen
2. Replace: 1 punt wegnemen om te vervangen met een punt met een hogere score
3. Two - opt move: de kruisingen eruit halen zodat er veel tijd kan worden bespaard
4. SWAP: Als je met meerdere routes werkt; kan je punten van routes wisselen

Question 10

Hoe kan diversificatie worden toegepast?

Answer 10

1. Verwijderen: # punten verwijderen

2. Groeperen van verschillende routes kan veel tijd vrijmaken voor nieuwe punten

Question 11

Wat waren de resultaten bij het gebruik van metheuristieken op het Orienteeringproblem? beste? snelste?
En wat zijn de resultaten van de uitbreiding op dit orienteeringproblem?

Answer 11

• Beste: GRASP: 0,04% v/d optimale oplossing maar lange zoektijd
• Snelste: VNS: 1% afwijkingen v/ optimale oplossing maar 4 sec. nodig!

Resultaten uitbreiding:
- Snelste is the iterated local search: 2% afwijking v/d optimale oplossing op enkele seconden.