Introduction to Heuristics

by Breno A. Beirigo (b.alvesbeirigo@utwente.nl)

Figure 1: Local optima and global optimum.

Learning goals

• Understand the main principles of approximate optimization methods:​
  • Local optima and global optimum​;
  • Initial solution, neighborhood structure, and stopping criteria;
  • Intensification and diversification.
• Explain the following approximate algorithms in relation to optimization problems:​
  • Constructive heuristics​
  • Local Search​
  • Single-solution based metaheuristics:​
    • Tabu Search (TS)
    • Simulated Annealing (SA)​
  • Population-based metaheuristics:​
    • Genetic Algorithm (GA)

Content

1. On the complexity of routing problems
2. Heuristics for combinatorial optimization problems (COPs)
3. Solving the Traveling Salesman Problem (TSP):
   • MIP model (by Gurobi Optimization)
   • Constructive heuristics: Nearest Neighbor (NN) & Farthest Addition (NN)
   • Local search with 2-opt
   • Simulated annealing

References

• Hillier, F. S. & Lieberman G. J. (2021). Introduction to Operations Research (11th Edition) (Chapter 14 - Metaheuristics). McGraw-Hill Education.
• Taha, H. A. (2017). Operations research: an introduction (10th Edition) (Chapter 10 - Heuristic Programming). Pearson/Prentice Hall.
• Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.
• de Armas, J., Lalla-Ruiz, E., Tilahun, S. L., & Voß, S. (2021). Similarity in metaheuristics: a gentle step towards a comparison methodology. Natural Computing, 1-23.
• Talbi, E. G. (2009). Metaheuristics: from design to implementation (Vol. 74). John Wiley & Sons.
• Karimi-Mamaghan, M., Mohammadi, M., Meyer, P., Karimi-Mamaghan, A. M., & Talbi, E. G. (2021). Machine Learning at the service of Meta-heuristics for solving Combinatorial Optimization Problems: A state-of-the-art. European Journal of Operational Research.
• Levin, Oscar. Discrete mathematics: An Open Intruduction (Chapter 1.5 Stars and Bars).
• Ho, Sin C., et al. “A survey of dial-a-ride problems: Literature review and recent developments.” Transportation Research Part B: Methodological 111 (2018): 395-421.
• Aranha, C., Camacho Villalón, C.L., Campelo, F. et al. Metaphor-based metaheuristics, a call for action: the elephant in the room. Swarm Intell (2021).​ - Gonzalez, T. F. (Ed.). (2018). Handbook of Approximation Algorithms and Metaheuristics: Contemporary and Emerging Applications, Volume 2. CRC Press.
• Bentley, J. (1992). Fast Algorithms for Geometric Traveling Salesman Problems. INFORMS J. Comput., 4, 387-411.
• Chiarandini, M. (2010). Construction Heuristics and Local Search Methods for VRP/VRPTW (lecture slides). Dept. of Mathematics & Computer Science, University of Southern Denmark.