Toepassingen van
Operationeel Onderzoek
Studiesamenvatting – volledige leerstof
Vak: TOPO – TvOO
Docent: prof. Ben Hermans
Inhoud: Lessen 1–10, studysets 1–4, voorbeeldexamen
Hoe dit document te gebruiken:
Per hoofdstuk wordt eerst de intuïtie gegeven (waarom dit probleem, wanneer toepassen),
dan de formele modellering (beslissingsvariabelen, doelfunctie, beperkingen), dan de algorit-
mes (exact en heuristiek), en tenslotte de verwijzingen naar relevante studyset-oefeningen.
Sleutelconcepten staan in gekleurde boxen. Eind van het document: cheatsheet en tref-
woordenregister per studyset.
,TOPO – Studiesamenvatting Inhoudsopgave
Inhoudsopgave
1 Inleidende OR-concepten (basis voor alle lessen) 2
1.1 Soorten optimalisatieproblemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Exacte methoden versus heuristieken . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Primale grens, duale grens, optimaliteitsgap . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Relaxaties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5 Soorten relaxaties die terugkomen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.6 Prestatiegaranties voor heuristieken . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.7 Branch & Bound en LP-relaxaties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.8 Totaal unimodulaire (TU) beperkingenmatrices . . . . . . . . . . . . . . . . . . . . . 3
2 Les 1 – Knapzakprobleem en heuristieken 4
2.1 Het 0-1 knapzakprobleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 LP-relaxatie en de afrondingsheuristiek . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Greedy heuristiek (alternatieve heuristiek) . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Greedy 2.0 – prestatiegarantie factor 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Wanneer welk soort heuristiek? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.6 Hoe een heuristiek evalueren? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Les 2 – Uitbreidingen van het knapzakprobleem 6
3.1 Knapzak cover probleem (productievestigingen) . . . . . . . . . . . . . . . . . . . . . 6
3.2 Lagrange-relaxatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Multiple knapsack probleem (opdrachten aan werknemers) . . . . . . . . . . . . . . . 6
3.4 Surrogate-relaxatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.5 Greedy heuristiek met prestatiegarantie 2 voor multiple knapsack . . . . . . . . . . . 7
3.6 2D-knapsack en 1D-cutting stock (oefeningen in les 2) . . . . . . . . . . . . . . . . . 7
4 Les 3 – Bin Packing, Cutting Stock en Kolomgeneratie 9
4.1 Bin packing probleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Heuristieken voor bin packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 Twee formuleringen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.4 Kolomgeneratie – het hart van les 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.5 Het pricing problem is een knapsack! . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.6 Superkolommen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.7 Van LP naar IP: branch-and-price . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.8 Wanneer kolomgeneratie toepassen? . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Les 4 – Netwerkoptimalisatie 12
5.1 Grafen – terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2 Toewijzingsprobleem (Assignment) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.3 Kortste-pad probleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.4 Minimum Spanning Tree (MST) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.5 Kruskal’s algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.6 Minimum Steiner Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.7 Spanning tree heuristiek voor Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.8 Vertex cover probleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.9 Afrondingsheuristiek voor vertex cover (LP-rounding) . . . . . . . . . . . . . . . . . 14
5.10 Greedy heuristiek voor vertex cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6 Les 5 – Clustering, UFL en Machineplanning 16
6.1 K-means clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.2 Uncapacitated Facility Location (UFL) . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1
,TOPO – Studiesamenvatting Inhoudsopgave
6.3 Greedy heuristiek voor UFL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.4 Local search voor UFL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.5 Lagrange-relaxatie voor UFL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.6 Lagrange-relaxatie heuristiek voor UFL . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.7 Parallelle machineplanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.8 Local search voor machineplanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.9 Lokaal optimum heeft prestatiegarantie 2 . . . . . . . . . . . . . . . . . . . . . . . . 18
6.10 List scheduling (greedy) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7 Les 6 – Traveling Salesperson Problem (TSP) 19
7.1 Het TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.2 Formulering 1: Dantzig-Fulkerson-Johnson (DFJ, 1954) . . . . . . . . . . . . . . . . 19
7.3 Alternatieve formulering: connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.4 Formulering 2: Miller-Tucker-Zemlin (MTZ, 1960) – compact . . . . . . . . . . . . . 19
7.5 Constructieheuristieken voor TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.6 Local search voor TSP: 2-opt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.7 Wat doen bij een lokaal optimum? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.8 Symmetrische TSP – formulering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.9 Double spanning tree heuristiek (symmetrisch TSP) . . . . . . . . . . . . . . . . . . 21
7.10 Historische verbinding: Eulerian vs Hamiltonian cycles . . . . . . . . . . . . . . . . . 21
8 Les 7 – Vehicle Routing Problems 22
8.1 Multiple TSP (MTSP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.2 MTZ-stijl formulering voor MTSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.3 Route-gebaseerde formulering – kolomgeneratie! . . . . . . . . . . . . . . . . . . . . . 22
8.4 Vehicle Routing Problem (VRP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.5 Two-index formulering met capaciteitsbeperkingen . . . . . . . . . . . . . . . . . . . 23
8.6 Heterogene vloot en pickup/delivery . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
8.7 VRP with Time Windows (VRPTW) . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
8.8 Case study: Coca-Cola Enterprises (CCE) . . . . . . . . . . . . . . . . . . . . . . . . 23
8.9 Praktische take-aways uit case studies . . . . . . . . . . . . . . . . . . . . . . . . . . 24
9 Les 8 – Case study: Course scheduling at FEB 25
9.1 Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.2 Vereenvoudigende veronderstellingen . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.3 Beslissingen en doelfunctie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.4 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.5 Beslissingsvariabelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.6 Beperkingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.7 Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
10 Les 9 – Gastles: Routing problems with electric vehicles 27
10.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.2 VRP recap (vanuit praktisch oogpunt) . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.3 Beperkingen in de praktijk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.4 Electric Vehicle Routing Problem (E-VRP) . . . . . . . . . . . . . . . . . . . . . . . 27
10.5 Batterijbereik en SoC-voorspelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.6 Charging in de VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.7 Charging schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
10.8 Laad-strategieën . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
10.9 Charging model – complete formulering . . . . . . . . . . . . . . . . . . . . . . . . . 28
10.10Charging on the go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
10.11Model-uitbreidingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2
, TOPO – Studiesamenvatting Inhoudsopgave
11 Les 10 – Metaheuristieken 30
11.1 Overzicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
11.2 Multistart en Iterated Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
11.3 Variable Neighborhood Search (VNS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
11.4 Tabu search (Fred Glover, 1989) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
11.5 Tabu-lengte en aspiratie-criterium . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
11.6 Tabu Search voorbeeld: 0-1 knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
11.7 Simulated Annealing (SA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
11.8 Eigenschappen van de aanvaardingskans . . . . . . . . . . . . . . . . . . . . . . . . . 32
11.9 SA voorbeeld: 0-1 knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
11.10Afkoelschema’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
11.11Genetische Algoritmes (GA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
11.12Selectiemethoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
11.13Crossover en mutatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.14Vervanging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.15Opmerkingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.16Algemene trade-off in metaheuristieken . . . . . . . . . . . . . . . . . . . . . . . . . . 33
12 Cheatsheet: wanneer welk concept gebruiken? 35
12.1 Probleem → techniek lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
12.2 Heuristiek-types met prestatiegarantie 2 in dit vak . . . . . . . . . . . . . . . . . . . 35
12.3 Soorten relaxaties en wanneer] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
12.4 Wanneer kolomgeneratie? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
12.5 Wanneer cutting plane? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
12.6 Metaheuristieken: kies de juiste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
13 Examenstrategie en formulebox 37
13.1 Typische examenvragen-types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
13.2 Formulebox – snel terugvinden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
13.3 Korte definities – snel doorlezen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
14 Trefwoordenregister naar studysets 39
14.1 Knapzak & uitbreidingen (les 1–2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
14.2 Netwerken & vertex cover & UFL & machineplanning (les 4–5) . . . . . . . . . . . . 39
14.3 Bin packing & cutting stock & kolomgeneratie (les 3) . . . . . . . . . . . . . . . . . . 39
14.4 TSP & VRP (les 6–7) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
14.5 Metaheuristieken (les 10) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
14.6 Voorbeeldexamen – overzicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3
Operationeel Onderzoek
Studiesamenvatting – volledige leerstof
Vak: TOPO – TvOO
Docent: prof. Ben Hermans
Inhoud: Lessen 1–10, studysets 1–4, voorbeeldexamen
Hoe dit document te gebruiken:
Per hoofdstuk wordt eerst de intuïtie gegeven (waarom dit probleem, wanneer toepassen),
dan de formele modellering (beslissingsvariabelen, doelfunctie, beperkingen), dan de algorit-
mes (exact en heuristiek), en tenslotte de verwijzingen naar relevante studyset-oefeningen.
Sleutelconcepten staan in gekleurde boxen. Eind van het document: cheatsheet en tref-
woordenregister per studyset.
,TOPO – Studiesamenvatting Inhoudsopgave
Inhoudsopgave
1 Inleidende OR-concepten (basis voor alle lessen) 2
1.1 Soorten optimalisatieproblemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Exacte methoden versus heuristieken . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Primale grens, duale grens, optimaliteitsgap . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Relaxaties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5 Soorten relaxaties die terugkomen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.6 Prestatiegaranties voor heuristieken . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.7 Branch & Bound en LP-relaxaties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.8 Totaal unimodulaire (TU) beperkingenmatrices . . . . . . . . . . . . . . . . . . . . . 3
2 Les 1 – Knapzakprobleem en heuristieken 4
2.1 Het 0-1 knapzakprobleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 LP-relaxatie en de afrondingsheuristiek . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Greedy heuristiek (alternatieve heuristiek) . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Greedy 2.0 – prestatiegarantie factor 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Wanneer welk soort heuristiek? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.6 Hoe een heuristiek evalueren? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Les 2 – Uitbreidingen van het knapzakprobleem 6
3.1 Knapzak cover probleem (productievestigingen) . . . . . . . . . . . . . . . . . . . . . 6
3.2 Lagrange-relaxatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Multiple knapsack probleem (opdrachten aan werknemers) . . . . . . . . . . . . . . . 6
3.4 Surrogate-relaxatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.5 Greedy heuristiek met prestatiegarantie 2 voor multiple knapsack . . . . . . . . . . . 7
3.6 2D-knapsack en 1D-cutting stock (oefeningen in les 2) . . . . . . . . . . . . . . . . . 7
4 Les 3 – Bin Packing, Cutting Stock en Kolomgeneratie 9
4.1 Bin packing probleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Heuristieken voor bin packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 Twee formuleringen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.4 Kolomgeneratie – het hart van les 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.5 Het pricing problem is een knapsack! . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.6 Superkolommen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.7 Van LP naar IP: branch-and-price . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.8 Wanneer kolomgeneratie toepassen? . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Les 4 – Netwerkoptimalisatie 12
5.1 Grafen – terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2 Toewijzingsprobleem (Assignment) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.3 Kortste-pad probleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.4 Minimum Spanning Tree (MST) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.5 Kruskal’s algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.6 Minimum Steiner Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.7 Spanning tree heuristiek voor Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.8 Vertex cover probleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.9 Afrondingsheuristiek voor vertex cover (LP-rounding) . . . . . . . . . . . . . . . . . 14
5.10 Greedy heuristiek voor vertex cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6 Les 5 – Clustering, UFL en Machineplanning 16
6.1 K-means clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.2 Uncapacitated Facility Location (UFL) . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1
,TOPO – Studiesamenvatting Inhoudsopgave
6.3 Greedy heuristiek voor UFL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.4 Local search voor UFL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.5 Lagrange-relaxatie voor UFL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.6 Lagrange-relaxatie heuristiek voor UFL . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.7 Parallelle machineplanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.8 Local search voor machineplanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.9 Lokaal optimum heeft prestatiegarantie 2 . . . . . . . . . . . . . . . . . . . . . . . . 18
6.10 List scheduling (greedy) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7 Les 6 – Traveling Salesperson Problem (TSP) 19
7.1 Het TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.2 Formulering 1: Dantzig-Fulkerson-Johnson (DFJ, 1954) . . . . . . . . . . . . . . . . 19
7.3 Alternatieve formulering: connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.4 Formulering 2: Miller-Tucker-Zemlin (MTZ, 1960) – compact . . . . . . . . . . . . . 19
7.5 Constructieheuristieken voor TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.6 Local search voor TSP: 2-opt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.7 Wat doen bij een lokaal optimum? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.8 Symmetrische TSP – formulering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.9 Double spanning tree heuristiek (symmetrisch TSP) . . . . . . . . . . . . . . . . . . 21
7.10 Historische verbinding: Eulerian vs Hamiltonian cycles . . . . . . . . . . . . . . . . . 21
8 Les 7 – Vehicle Routing Problems 22
8.1 Multiple TSP (MTSP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.2 MTZ-stijl formulering voor MTSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.3 Route-gebaseerde formulering – kolomgeneratie! . . . . . . . . . . . . . . . . . . . . . 22
8.4 Vehicle Routing Problem (VRP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.5 Two-index formulering met capaciteitsbeperkingen . . . . . . . . . . . . . . . . . . . 23
8.6 Heterogene vloot en pickup/delivery . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
8.7 VRP with Time Windows (VRPTW) . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
8.8 Case study: Coca-Cola Enterprises (CCE) . . . . . . . . . . . . . . . . . . . . . . . . 23
8.9 Praktische take-aways uit case studies . . . . . . . . . . . . . . . . . . . . . . . . . . 24
9 Les 8 – Case study: Course scheduling at FEB 25
9.1 Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.2 Vereenvoudigende veronderstellingen . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.3 Beslissingen en doelfunctie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.4 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.5 Beslissingsvariabelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.6 Beperkingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9.7 Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
10 Les 9 – Gastles: Routing problems with electric vehicles 27
10.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.2 VRP recap (vanuit praktisch oogpunt) . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.3 Beperkingen in de praktijk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.4 Electric Vehicle Routing Problem (E-VRP) . . . . . . . . . . . . . . . . . . . . . . . 27
10.5 Batterijbereik en SoC-voorspelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.6 Charging in de VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
10.7 Charging schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
10.8 Laad-strategieën . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
10.9 Charging model – complete formulering . . . . . . . . . . . . . . . . . . . . . . . . . 28
10.10Charging on the go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
10.11Model-uitbreidingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2
, TOPO – Studiesamenvatting Inhoudsopgave
11 Les 10 – Metaheuristieken 30
11.1 Overzicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
11.2 Multistart en Iterated Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
11.3 Variable Neighborhood Search (VNS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
11.4 Tabu search (Fred Glover, 1989) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
11.5 Tabu-lengte en aspiratie-criterium . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
11.6 Tabu Search voorbeeld: 0-1 knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
11.7 Simulated Annealing (SA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
11.8 Eigenschappen van de aanvaardingskans . . . . . . . . . . . . . . . . . . . . . . . . . 32
11.9 SA voorbeeld: 0-1 knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
11.10Afkoelschema’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
11.11Genetische Algoritmes (GA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
11.12Selectiemethoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
11.13Crossover en mutatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.14Vervanging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.15Opmerkingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.16Algemene trade-off in metaheuristieken . . . . . . . . . . . . . . . . . . . . . . . . . . 33
12 Cheatsheet: wanneer welk concept gebruiken? 35
12.1 Probleem → techniek lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
12.2 Heuristiek-types met prestatiegarantie 2 in dit vak . . . . . . . . . . . . . . . . . . . 35
12.3 Soorten relaxaties en wanneer] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
12.4 Wanneer kolomgeneratie? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
12.5 Wanneer cutting plane? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
12.6 Metaheuristieken: kies de juiste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
13 Examenstrategie en formulebox 37
13.1 Typische examenvragen-types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
13.2 Formulebox – snel terugvinden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
13.3 Korte definities – snel doorlezen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
14 Trefwoordenregister naar studysets 39
14.1 Knapzak & uitbreidingen (les 1–2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
14.2 Netwerken & vertex cover & UFL & machineplanning (les 4–5) . . . . . . . . . . . . 39
14.3 Bin packing & cutting stock & kolomgeneratie (les 3) . . . . . . . . . . . . . . . . . . 39
14.4 TSP & VRP (les 6–7) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
14.5 Metaheuristieken (les 10) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
14.6 Voorbeeldexamen – overzicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3
