2025-2026
SAMENVATTING: TOEPASSINGEN VAN
OPERATIONEEL ONDERZOEK
HERMANS BEN
MERI DELBROEK
,Inhoudsopgave
Inhoudsopgave..........................................................................................................................................1
Les 1: Knapzak ..........................................................................................................................................7
Les 2: uitbereiding knapzak ...................................................................................................................... 13
0-1 knapzak cover probleem: Lagrangiaanse relaxatie ........................................................................... 13
Openen van productievestigingen ..................................................................................................... 13
Lagrangiaanse relaxatie .................................................................................................................... 13
Lagrange relaxatie ............................................................................................................................ 13
De kwaliteit van de grens .................................................................................................................. 14
0-1 multiple knapzak probleem: surrogate relaxatie ............................................................................... 15
Alloceren van opdrachten aan werknemers ....................................................................................... 15
0-1 multiple knapzak probleem ......................................................................................................... 15
Een surrogate relaxatie voor het 0-1 multiple knapzak probleem ......................................................... 15
Exercise: 2-dimensional knapsack problem .......................................................................................... 17
Exercise: 1-dimensional cutting stock problem ..................................................................................... 18
Les 3: bin packing en cutting stock ........................................................................................................... 19
Bin packing probleem .......................................................................................................................... 19
Heuristieken voor bin packing ........................................................................................................... 20
Een formulering voor het bin packing probleem ................................................................................. 20
LP relaxatie van het bin packing probleem ......................................................................................... 20
Een sterkere formulering voor het bin packing probleem .................................................................... 21
Een alternatieve formulering ............................................................................................................. 21
Kolomgeneratie voor het 1D cutting stock probleem .............................................................................. 22
1D cutting stock probleem ................................................................................................................ 22
Cutting stock: grotere dimensie ........................................................................................................ 23
Kolomgeneratie ................................................................................................................................ 23
Kolomgeneratie in het algemeen ........................................................................................................... 29
Kolomgeneratie algemeen ................................................................................................................ 29
Kolomgeneratie schematisch ............................................................................................................ 30
Optimaliteit ...................................................................................................................................... 30
Wat als de optimale LP oplossing fractioneel is? ................................................................................ 30
Geheeltallige oplossing .................................................................................................................... 30
Optimale IP oplossing....................................................................................................................... 31
Het pricing probleem ........................................................................................................................ 31
Knapzakprobleem ............................................................................................................................ 31
Pricing probleem .............................................................................................................................. 32
Superkolommen............................................................................................................................... 32
1
, Voorbeeld van een superkolom als startkolom voor het cutting stock probleem .................................. 32
Les 4: optimalisatie op netwerken ............................................................................................................ 32
Optimalisatie op netwerken.................................................................................................................. 32
Een graaf als formele voorstelling van een netwerk ............................................................................... 33
Toewijzingsprobleem............................................................................................................................ 33
Je geeft een feestje: wie doet wat?..................................................................................................... 33
Toewijzingsprobleem ........................................................................................................................ 33
Formulering voor het toewijzingsprobleem ........................................................................................ 34
Complexiteit van het toewijzingsprobleem ........................................................................................ 34
Kortste pad probleem........................................................................................................................... 34
Routeaanwijzing naar je feestje... ...................................................................................................... 34
Formulering voor het kortste pad probleem ....................................................................................... 34
Het kortste pad probleem: opmerkingen over het model .................................................................... 35
Minimum spanning tree probleem ........................................................................................................ 35
Installeren van een datanetwerk ....................................................................................................... 35
Minimum spanning tree probleem ..................................................................................................... 35
Karakterisering van spanning trees .................................................................................................... 36
Twee formuleringen voor het minimum spanning tree probleem ......................................................... 36
Oplossen van het minimum spanning tree probleem ......................................................................... 37
Greedy algoritme voor minimum spanning tree .................................................................................. 37
Greedy algoritmes ............................................................................................................................ 38
Minimum Steiner tree probleem ........................................................................................................... 38
Minimum Steiner tree probleem ........................................................................................................ 38
Formulering voor minimum Steiner tree............................................................................................. 38
Spanning tree heuristiek voor het minimum Steiner tree probleem ..................................................... 38
Vertex cover probleem ......................................................................................................................... 39
Vertex cover probleem ...................................................................................................................... 39
Een formulering voor het vertex cover probleem => NP hard probleem ................................................ 39
Een afrondingsheuristiek .................................................................................................................. 40
Correctheid van de afrondingsheuristiek ........................................................................................... 40
Hoe slecht kan de cover C zijn? ......................................................................................................... 40
Een greedy heuristiek voor het vertex cover probleem ........................................................................ 40
Les 5: Clustering, Facility location, Machineplanning ................................................................................ 41
K-means probleem .............................................................................................................................. 41
Data clustering: number recognition ................................................................................................. 41
Data clustering ................................................................................................................................. 41
Number recognition ......................................................................................................................... 42
Het K-means probleem ..................................................................................................................... 42
2
, Heuristiek voor het K-means probleem .............................................................................................. 42
K-means algoritme ........................................................................................................................... 43
K-means algoritme voor number recognition ..................................................................................... 46
Uncapacitated facility location problem ............................................................................................... 46
Uncapacitated facility location probleem (magazijnvestiging) ............................................................ 46
Formulering voor uncapacitated facility location problem .................................................................. 47
Greedy heuristiek ............................................................................................................................. 47
Local search .................................................................................................................................... 49
Lagrangiaanse relaxatie .................................................................................................................... 50
Parallelle machine planning ................................................................................................................. 54
Parallelle machine planning probleem .............................................................................................. 54
Formulering voor het parallelle machine planning probleem .............................................................. 54
Local search .................................................................................................................................... 54
Greedy algoritme .............................................................................................................................. 55
Les 6: Travelling Salesperson Problem ...................................................................................................... 56
Traveling salesman probleem (TSP) ....................................................................................................... 56
Een TSP instantie .............................................................................................................................. 56
Een TSP tour ..................................................................................................................................... 56
Worlds largest pub crawl .................................................................................................................. 56
Guide to the galaxy ........................................................................................................................... 57
TSP kunst ......................................................................................................................................... 57
Formuleringen voor TSP ....................................................................................................................... 57
Voorstellen TSP instantie als een graaf .............................................................................................. 57
Formulering voor TSP ........................................................................................................................ 58
Subtours .......................................................................................................................................... 58
Elimineren van subtours ................................................................................................................... 58
Subtour eliminatie: Dantzig-Fulkerson-Johnson formulering (1954) .................................................... 59
Subtour eliminatie door het opleggen van connectivity ...................................................................... 59
Een compacte formulering: Miller-Tucker-Zemlin (1960) ..................................................................... 60
Elimineren van subtours in de MTZ formulering .................................................................................. 60
Het oplossen van het TSP.................................................................................................................. 60
Constructieheuristieken voor TSP ......................................................................................................... 61
Constructie heuristieken voor het TSP ............................................................................................... 61
Nearest neighbor oplossing als we starten vanaf stad 1 ..................................................................... 61
Local search voor TSP .......................................................................................................................... 62
Local search voor het TSP: 2-opt ....................................................................................................... 62
Een 2-neighbor van de tour T’ =(1 , 2 , 3 , 4 , 6 , 5 , 1)............................................................................ 62
2-opt algoritme ................................................................................................................................ 63
3
, Veralgemening: 3-opt ....................................................................................................................... 63
Enkele typische moves in permutatieproblemen ................................................................................ 63
Eens we een lokaal optimum gevonden hebben... .............................................................................. 63
67 steden van België en Luxemburg ................................................................................................... 64
Symmetrische TSP ............................................................................................................................... 64
Het symmetrische TSP...................................................................................................................... 64
Formulering voor het symmetrische TSP ............................................................................................ 64
Subtour eliminatie door het opleggen van connectivity ...................................................................... 65
Double spanning tree heuristiek voor het symmetrische TSP .............................................................. 65
Historisch intermezzo: de oorsprong van grafentheorie ...................................................................... 65
Double spanning tree heuristiek voor het symmetrische TSP .............................................................. 66
Double spanning tree heuristiek voor het symmetrische TSP .............................................................. 67
Les 7: vehicle routing problems ................................................................................................................ 67
Multiple traveling salesperson problem ................................................................................................ 67
Multiple traveling salesperson problem (MTSP) .................................................................................. 67
Notation........................................................................................................................................... 68
A Miller-Tucker-Zemlin type formulation ............................................................................................ 68
An alternative formulation ................................................................................................................ 68
Remarks on the second formulation .................................................................................................. 69
Service requirement ......................................................................................................................... 69
Vehicle routing problem ....................................................................................................................... 69
Vehicle routing problem .................................................................................................................... 69
The two index formulation ................................................................................................................. 69
Heterogeneous Fleet VRP ................................................................................................................. 70
VRP with simultaneous deliveries and pickups .................................................................................. 70
Vehicle routing problem with time windows .......................................................................................... 70
Vehicle routing problem with time windows ....................................................................................... 70
A Miller-Tucker-Zemlin type formulation - part 1 ................................................................................. 71
A Miller-Tucker-Zemlin type formulation - part 2 ................................................................................. 71
Remarks on the second formulation .................................................................................................. 71
Les 8: Case study – course scheduling at FEB ........................................................................................... 72
Goal: schedule courses for second semester of first master Business engineering (BE) &
Handelsingenieur (HIR)..................................................................................................................... 72
Problem description............................................................................................................................. 72
Courses are organized into core, major, and elective courses ............................................................. 72
Data provided by the student administration: courses........................................................................ 72
Data provided by the student administration: rooms .......................................................................... 73
Simplifying assumptions................................................................................................................... 73
4
, What are the decisions to make? Which objective and constraints?.................................................... 73
A first model ........................................................................................................................................ 73
Parameters ...................................................................................................................................... 73
Decision variables ............................................................................................................................ 74
Constraints: assigning classes to periods and rooms ......................................................................... 74
Constraints: avoiding conflicts .......................................................................................................... 74
Constraints: room availability, incompatibility and binary constraints ................................................. 74
Objective function ............................................................................................................................ 75
Solving the model with IBM ILOG CPLEX ............................................................................................ 75
The first model is infeasible .............................................................................................................. 75
Towards a better model ........................................................................................................................ 75
Relaxing the ‘no overlap’ constraints ................................................................................................. 75
Can you propose a better model?...................................................................................................... 76
Enforcing no overlap for conflict-free coursepairs ................................................................................. 76
Conflict-free coursepairs .................................................................................................................. 76
Enforcing no overlap for conflict-free coursepairs .............................................................................. 76
Minimizing the number of overlaps in non-confluct-free coursepairs...................................................... 76
Modifications in the constraints ........................................................................................................ 77
Solving the new model with CPLEX .................................................................................................... 77
Taking into account the number of students .......................................................................................... 77
Number of students ......................................................................................................................... 77
Estimating the number of students in a coursepair ............................................................................ 77
Minimizing the number of students with overlapping courses ............................................................. 78
Minimizing the number of students with overlapping courses ............................................................. 78
Conclusion .......................................................................................................................................... 78
Les 9: Gastles.......................................................................................................................................... 78
Les 10: metaheuristieken ......................................................................................................................... 78
Een samenvatting ................................................................................................................................ 78
Vandaag: metaheuristieken .............................................................................................................. 79
Metaheuristieken ................................................................................................................................. 79
Ontsnappen uit lokale optima (Metaheuristics, El-Ghazali Talbi) ............................................................ 79
Itereer met verschillende oplossingen .................................................................................................. 80
Hoe verstoren en wanneer aanvaarden? ............................................................................................... 80
Ontsnappen uit lokale optima (Metaheuristics, El-Ghazali Talbi) ............................................................ 80
Variable neighborhood search .............................................................................................................. 80
Variable neighborhood search .............................................................................................................. 81
Ontsnappen uit lokale optima (Metaheuristics, El-Ghazali Talbi) ............................................................ 81
Naar een oplossing gaan die geen verbetering is .................................................................................... 81
5
,Tabu search (Fred Glover, 1989) ............................................................................................................ 82
0-1 knapzak ......................................................................................................................................... 82
Local search voor 0-1 knapzak .............................................................................................................. 82
Tabu search voor 0-1 knapzak ............................................................................................................... 83
Tabu search voor het TSP ...................................................................................................................... 83
Tabu search algoritme - trade-offs ........................................................................................................ 83
Simulated annealing ............................................................................................................................ 83
Simulated annealing ............................................................................................................................ 84
Simulated annealing: over de kans op aanvaarding................................................................................ 84
Simulated annealing voor 0-1 knapzak .................................................................................................. 84
Afkoelschema’s in simulated annealing ................................................................................................ 85
Ontsnappen uit lokale optima (Metaheuristics, El-Ghazali Talbi) ............................................................ 85
Genetische algoritmes ......................................................................................................................... 85
Selectiemethodes................................................................................................................................ 86
Selectiemethodes (Metaheuristics, El-Ghazali Talbi) ............................................................................. 86
Voorbeeld TSP met 10 steden: 10 tours en hun lengte ............................................................................ 86
Roulette wiel selectie ........................................................................................................................... 87
Alternatief: tornooi selectie .................................................................................................................. 87
Reproductie......................................................................................................................................... 87
Crossover: voorbeeld voor het TSP ........................................................................................................ 87
Vervanging ........................................................................................................................................... 88
Genetische algoritmes ......................................................................................................................... 88
Opmerkingen over genetische algoritmes ............................................................................................. 88
Samenvatting ...................................................................................................................................... 88
6
,Les 1: Knapzak
7
,8
, 9
SAMENVATTING: TOEPASSINGEN VAN
OPERATIONEEL ONDERZOEK
HERMANS BEN
MERI DELBROEK
,Inhoudsopgave
Inhoudsopgave..........................................................................................................................................1
Les 1: Knapzak ..........................................................................................................................................7
Les 2: uitbereiding knapzak ...................................................................................................................... 13
0-1 knapzak cover probleem: Lagrangiaanse relaxatie ........................................................................... 13
Openen van productievestigingen ..................................................................................................... 13
Lagrangiaanse relaxatie .................................................................................................................... 13
Lagrange relaxatie ............................................................................................................................ 13
De kwaliteit van de grens .................................................................................................................. 14
0-1 multiple knapzak probleem: surrogate relaxatie ............................................................................... 15
Alloceren van opdrachten aan werknemers ....................................................................................... 15
0-1 multiple knapzak probleem ......................................................................................................... 15
Een surrogate relaxatie voor het 0-1 multiple knapzak probleem ......................................................... 15
Exercise: 2-dimensional knapsack problem .......................................................................................... 17
Exercise: 1-dimensional cutting stock problem ..................................................................................... 18
Les 3: bin packing en cutting stock ........................................................................................................... 19
Bin packing probleem .......................................................................................................................... 19
Heuristieken voor bin packing ........................................................................................................... 20
Een formulering voor het bin packing probleem ................................................................................. 20
LP relaxatie van het bin packing probleem ......................................................................................... 20
Een sterkere formulering voor het bin packing probleem .................................................................... 21
Een alternatieve formulering ............................................................................................................. 21
Kolomgeneratie voor het 1D cutting stock probleem .............................................................................. 22
1D cutting stock probleem ................................................................................................................ 22
Cutting stock: grotere dimensie ........................................................................................................ 23
Kolomgeneratie ................................................................................................................................ 23
Kolomgeneratie in het algemeen ........................................................................................................... 29
Kolomgeneratie algemeen ................................................................................................................ 29
Kolomgeneratie schematisch ............................................................................................................ 30
Optimaliteit ...................................................................................................................................... 30
Wat als de optimale LP oplossing fractioneel is? ................................................................................ 30
Geheeltallige oplossing .................................................................................................................... 30
Optimale IP oplossing....................................................................................................................... 31
Het pricing probleem ........................................................................................................................ 31
Knapzakprobleem ............................................................................................................................ 31
Pricing probleem .............................................................................................................................. 32
Superkolommen............................................................................................................................... 32
1
, Voorbeeld van een superkolom als startkolom voor het cutting stock probleem .................................. 32
Les 4: optimalisatie op netwerken ............................................................................................................ 32
Optimalisatie op netwerken.................................................................................................................. 32
Een graaf als formele voorstelling van een netwerk ............................................................................... 33
Toewijzingsprobleem............................................................................................................................ 33
Je geeft een feestje: wie doet wat?..................................................................................................... 33
Toewijzingsprobleem ........................................................................................................................ 33
Formulering voor het toewijzingsprobleem ........................................................................................ 34
Complexiteit van het toewijzingsprobleem ........................................................................................ 34
Kortste pad probleem........................................................................................................................... 34
Routeaanwijzing naar je feestje... ...................................................................................................... 34
Formulering voor het kortste pad probleem ....................................................................................... 34
Het kortste pad probleem: opmerkingen over het model .................................................................... 35
Minimum spanning tree probleem ........................................................................................................ 35
Installeren van een datanetwerk ....................................................................................................... 35
Minimum spanning tree probleem ..................................................................................................... 35
Karakterisering van spanning trees .................................................................................................... 36
Twee formuleringen voor het minimum spanning tree probleem ......................................................... 36
Oplossen van het minimum spanning tree probleem ......................................................................... 37
Greedy algoritme voor minimum spanning tree .................................................................................. 37
Greedy algoritmes ............................................................................................................................ 38
Minimum Steiner tree probleem ........................................................................................................... 38
Minimum Steiner tree probleem ........................................................................................................ 38
Formulering voor minimum Steiner tree............................................................................................. 38
Spanning tree heuristiek voor het minimum Steiner tree probleem ..................................................... 38
Vertex cover probleem ......................................................................................................................... 39
Vertex cover probleem ...................................................................................................................... 39
Een formulering voor het vertex cover probleem => NP hard probleem ................................................ 39
Een afrondingsheuristiek .................................................................................................................. 40
Correctheid van de afrondingsheuristiek ........................................................................................... 40
Hoe slecht kan de cover C zijn? ......................................................................................................... 40
Een greedy heuristiek voor het vertex cover probleem ........................................................................ 40
Les 5: Clustering, Facility location, Machineplanning ................................................................................ 41
K-means probleem .............................................................................................................................. 41
Data clustering: number recognition ................................................................................................. 41
Data clustering ................................................................................................................................. 41
Number recognition ......................................................................................................................... 42
Het K-means probleem ..................................................................................................................... 42
2
, Heuristiek voor het K-means probleem .............................................................................................. 42
K-means algoritme ........................................................................................................................... 43
K-means algoritme voor number recognition ..................................................................................... 46
Uncapacitated facility location problem ............................................................................................... 46
Uncapacitated facility location probleem (magazijnvestiging) ............................................................ 46
Formulering voor uncapacitated facility location problem .................................................................. 47
Greedy heuristiek ............................................................................................................................. 47
Local search .................................................................................................................................... 49
Lagrangiaanse relaxatie .................................................................................................................... 50
Parallelle machine planning ................................................................................................................. 54
Parallelle machine planning probleem .............................................................................................. 54
Formulering voor het parallelle machine planning probleem .............................................................. 54
Local search .................................................................................................................................... 54
Greedy algoritme .............................................................................................................................. 55
Les 6: Travelling Salesperson Problem ...................................................................................................... 56
Traveling salesman probleem (TSP) ....................................................................................................... 56
Een TSP instantie .............................................................................................................................. 56
Een TSP tour ..................................................................................................................................... 56
Worlds largest pub crawl .................................................................................................................. 56
Guide to the galaxy ........................................................................................................................... 57
TSP kunst ......................................................................................................................................... 57
Formuleringen voor TSP ....................................................................................................................... 57
Voorstellen TSP instantie als een graaf .............................................................................................. 57
Formulering voor TSP ........................................................................................................................ 58
Subtours .......................................................................................................................................... 58
Elimineren van subtours ................................................................................................................... 58
Subtour eliminatie: Dantzig-Fulkerson-Johnson formulering (1954) .................................................... 59
Subtour eliminatie door het opleggen van connectivity ...................................................................... 59
Een compacte formulering: Miller-Tucker-Zemlin (1960) ..................................................................... 60
Elimineren van subtours in de MTZ formulering .................................................................................. 60
Het oplossen van het TSP.................................................................................................................. 60
Constructieheuristieken voor TSP ......................................................................................................... 61
Constructie heuristieken voor het TSP ............................................................................................... 61
Nearest neighbor oplossing als we starten vanaf stad 1 ..................................................................... 61
Local search voor TSP .......................................................................................................................... 62
Local search voor het TSP: 2-opt ....................................................................................................... 62
Een 2-neighbor van de tour T’ =(1 , 2 , 3 , 4 , 6 , 5 , 1)............................................................................ 62
2-opt algoritme ................................................................................................................................ 63
3
, Veralgemening: 3-opt ....................................................................................................................... 63
Enkele typische moves in permutatieproblemen ................................................................................ 63
Eens we een lokaal optimum gevonden hebben... .............................................................................. 63
67 steden van België en Luxemburg ................................................................................................... 64
Symmetrische TSP ............................................................................................................................... 64
Het symmetrische TSP...................................................................................................................... 64
Formulering voor het symmetrische TSP ............................................................................................ 64
Subtour eliminatie door het opleggen van connectivity ...................................................................... 65
Double spanning tree heuristiek voor het symmetrische TSP .............................................................. 65
Historisch intermezzo: de oorsprong van grafentheorie ...................................................................... 65
Double spanning tree heuristiek voor het symmetrische TSP .............................................................. 66
Double spanning tree heuristiek voor het symmetrische TSP .............................................................. 67
Les 7: vehicle routing problems ................................................................................................................ 67
Multiple traveling salesperson problem ................................................................................................ 67
Multiple traveling salesperson problem (MTSP) .................................................................................. 67
Notation........................................................................................................................................... 68
A Miller-Tucker-Zemlin type formulation ............................................................................................ 68
An alternative formulation ................................................................................................................ 68
Remarks on the second formulation .................................................................................................. 69
Service requirement ......................................................................................................................... 69
Vehicle routing problem ....................................................................................................................... 69
Vehicle routing problem .................................................................................................................... 69
The two index formulation ................................................................................................................. 69
Heterogeneous Fleet VRP ................................................................................................................. 70
VRP with simultaneous deliveries and pickups .................................................................................. 70
Vehicle routing problem with time windows .......................................................................................... 70
Vehicle routing problem with time windows ....................................................................................... 70
A Miller-Tucker-Zemlin type formulation - part 1 ................................................................................. 71
A Miller-Tucker-Zemlin type formulation - part 2 ................................................................................. 71
Remarks on the second formulation .................................................................................................. 71
Les 8: Case study – course scheduling at FEB ........................................................................................... 72
Goal: schedule courses for second semester of first master Business engineering (BE) &
Handelsingenieur (HIR)..................................................................................................................... 72
Problem description............................................................................................................................. 72
Courses are organized into core, major, and elective courses ............................................................. 72
Data provided by the student administration: courses........................................................................ 72
Data provided by the student administration: rooms .......................................................................... 73
Simplifying assumptions................................................................................................................... 73
4
, What are the decisions to make? Which objective and constraints?.................................................... 73
A first model ........................................................................................................................................ 73
Parameters ...................................................................................................................................... 73
Decision variables ............................................................................................................................ 74
Constraints: assigning classes to periods and rooms ......................................................................... 74
Constraints: avoiding conflicts .......................................................................................................... 74
Constraints: room availability, incompatibility and binary constraints ................................................. 74
Objective function ............................................................................................................................ 75
Solving the model with IBM ILOG CPLEX ............................................................................................ 75
The first model is infeasible .............................................................................................................. 75
Towards a better model ........................................................................................................................ 75
Relaxing the ‘no overlap’ constraints ................................................................................................. 75
Can you propose a better model?...................................................................................................... 76
Enforcing no overlap for conflict-free coursepairs ................................................................................. 76
Conflict-free coursepairs .................................................................................................................. 76
Enforcing no overlap for conflict-free coursepairs .............................................................................. 76
Minimizing the number of overlaps in non-confluct-free coursepairs...................................................... 76
Modifications in the constraints ........................................................................................................ 77
Solving the new model with CPLEX .................................................................................................... 77
Taking into account the number of students .......................................................................................... 77
Number of students ......................................................................................................................... 77
Estimating the number of students in a coursepair ............................................................................ 77
Minimizing the number of students with overlapping courses ............................................................. 78
Minimizing the number of students with overlapping courses ............................................................. 78
Conclusion .......................................................................................................................................... 78
Les 9: Gastles.......................................................................................................................................... 78
Les 10: metaheuristieken ......................................................................................................................... 78
Een samenvatting ................................................................................................................................ 78
Vandaag: metaheuristieken .............................................................................................................. 79
Metaheuristieken ................................................................................................................................. 79
Ontsnappen uit lokale optima (Metaheuristics, El-Ghazali Talbi) ............................................................ 79
Itereer met verschillende oplossingen .................................................................................................. 80
Hoe verstoren en wanneer aanvaarden? ............................................................................................... 80
Ontsnappen uit lokale optima (Metaheuristics, El-Ghazali Talbi) ............................................................ 80
Variable neighborhood search .............................................................................................................. 80
Variable neighborhood search .............................................................................................................. 81
Ontsnappen uit lokale optima (Metaheuristics, El-Ghazali Talbi) ............................................................ 81
Naar een oplossing gaan die geen verbetering is .................................................................................... 81
5
,Tabu search (Fred Glover, 1989) ............................................................................................................ 82
0-1 knapzak ......................................................................................................................................... 82
Local search voor 0-1 knapzak .............................................................................................................. 82
Tabu search voor 0-1 knapzak ............................................................................................................... 83
Tabu search voor het TSP ...................................................................................................................... 83
Tabu search algoritme - trade-offs ........................................................................................................ 83
Simulated annealing ............................................................................................................................ 83
Simulated annealing ............................................................................................................................ 84
Simulated annealing: over de kans op aanvaarding................................................................................ 84
Simulated annealing voor 0-1 knapzak .................................................................................................. 84
Afkoelschema’s in simulated annealing ................................................................................................ 85
Ontsnappen uit lokale optima (Metaheuristics, El-Ghazali Talbi) ............................................................ 85
Genetische algoritmes ......................................................................................................................... 85
Selectiemethodes................................................................................................................................ 86
Selectiemethodes (Metaheuristics, El-Ghazali Talbi) ............................................................................. 86
Voorbeeld TSP met 10 steden: 10 tours en hun lengte ............................................................................ 86
Roulette wiel selectie ........................................................................................................................... 87
Alternatief: tornooi selectie .................................................................................................................. 87
Reproductie......................................................................................................................................... 87
Crossover: voorbeeld voor het TSP ........................................................................................................ 87
Vervanging ........................................................................................................................................... 88
Genetische algoritmes ......................................................................................................................... 88
Opmerkingen over genetische algoritmes ............................................................................................. 88
Samenvatting ...................................................................................................................................... 88
6
,Les 1: Knapzak
7
,8
, 9
