DRL027 Heuristics for stochastic optimization (Autumn 2021)

About the course

Some form of uncertainty is almost always present when important decisions are made. This is also the case for logistics planners, whether planning is performed at a strategic, tactical, or operational level. Decision support in the form of optimization tools can help planners make better choices, but many optimization problems are hard to solve and require specialized search methods to identify good solutions.

This course focuses on heuristic algorithms, in particular metaheuristics, and their application to optimization problems where uncertainty is taken into consideration. Examples from several applications in routing and scheduling are used to illustrate state-of-the-art techniques.

Topics:

• Introduction to optimization under uncertainty

• Introduction to heuristics

• Introduction to metaheuristics for stochastic optimization

• Modelling paradigms, including: Markov decision processes, stochastic programming (multi-stage, dual-level), and robust optimization

• Heuristic algorithms, based on GRASP, adaptive large neighborhood search, tabu search, iterated local search, and progressive hedging

Routing and scheduling problems, including the stochastic inventory routing problem, a fleet size and mix problem in offshore wind, the robust vehicle routing problem with time windows, and a stochastic and dynamic maritime pick-up and delivery problem.

The course is connected to the following study programs

• Philosophiae Doctor in Logistics (PhD)

Recommended requirements

The course is suitable for PhD candidates with some knowledge about stochastic optimization, who may learn how this domain can be approached using heuristics; PhD candidates with some knowledge about heuristics, who may learn how they need to be adapted to efficiently deal with stochastic problems; and PhD candidates with knowledge about vehicle routing and scheduling problems, who may learn how stochastic versions of such problems can be handled by heuristics.

The student's learning outcomes after completing the course

By the end of the course, the participants should be able to

• discuss different paradigms for stochastic optimization

• present basic designs of common metaheuristic frameworks

• explain common ways of adapting metaheuristics to solve stochastic optimization problems

• provide details of implementations of GRASP for solving Markov decision processes; adaptive large neighborhood search for robust optimization problems; tabu search for dynamic and stochastic routing problems; GRASP, iterated local search and progressive hedging for stochastic programming problems

• identify sources of uncertainty in typical applications of vehicle routing and scheduling problems

• write a well-structured academic report/paper on a specialized topic within heuristics for stochastic optimization

Forms of teaching and learning

• Reading papers and book chapters

• Attending lectures (1 week intensive lectures)

• Writing academic report/paper

Examination

• Form of assessment: Writing an academic paper/report on a topic related to the curriculum

• Duration:TBA

• Grouping:Individual

• Grading scale: Pass/Fail

Syllabus

Part 1: Introduction to stochastic optimization

• [1] W.B. Powell. Clearing the jungle of stochastic optimization. In: INFORMS TutORials in Operations Research. Published online: 27 Oct 2014; 109-137

• [2] W.B. Powell. A unified framework for stochastic optimization. European Journal of Operational Research, 275:795-821, 2019.
  

Part 2: Introduction to heuristics

• [3] C. Blum and A. Roli. Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Computing Surveys, 35:268−308, 2003.

• [4] K. Sörensen, M. Sevaux, and F. Glover. A history of metaheuristics. In: R. Martí, P. Pardalos, and M. Resende (eds) Handbook of Heuristics, pages 1−18. Springer, 2018.
  

Part 3: Introduction to metaheuristics for stochastic optimization

• [5] L. Bianchi, M. Dorigo, L.M. Gambardella, and W.J. Gutjahr. A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing, 8:239−287, 2009.

• [6] L.M. Hvattum and E.F. Esbensen. Metaheuristics for stochastic problems. In J.J. Cochran, L. A. Cox Jr., P. Keskinocak, J.P. Kharoufeh, and J.C. Smith (eds) Wiley Encyclopedia of Operations Research and Management Science, volume 5, pages 3218−3229. Wiley, New York, 2011.

• [7] S. Andradóttir and A.A. Prudius. Balanced explorative and exploitative search with estimation for simulation optimization. INFORMS Journal on Computing, 21:193−208, 2009.
  

Part 4: MDP/SIRP/GRASP/PHA

• [8] L.M. Hvattum, A. Løkketangen, and G. Laporte. Scenario tree based heuristics for stochastic inventory routing problems. INFORMS Journal on Computing, 21:268−285, 2009.

• [9] L.M. Hvattum and A. Løkketangen. Using scenario trees and progressive hedging for stochastic inventory routing problems. Journal of Heuristics, 15:527−557, 2009.

• Part 5: Stochastic programming, offshore wind, fleet-size-and-mix, and GRASP

• [10] K.H. Bolstad and M. Joshi. Heuristics for a dual-level stochastic fleet size and mix problem for maintenance operations at offshore wind farms. Master's thesis at NTNU, Trondheim, Norway, 2016.

• Part 6: Maritime dynamic and stochastic pickup-and-delivery problem with time windows

• [11] G. Tirado, L.M. Hvattum, K. Fagerholt, and J.-F. Cordeau. Heuristics for dynamic and stochastic routing in industrial shipping. Computers and Operations Research, 40:253‒263, 2013.

• [12] G. Tirado and L.M. Hvattum. Improved solutions to dynamic and stochastic maritime pick-up and delivery problems using local search. Annals of Operations Research, 253:825−843, 2017.

• [13] G. Tirado and L.M. Hvattum. Determining departure times in dynamic and stochastic maritime routing and scheduling problems. Flexible Services and Manufacturing Journal, 29:553−571, 2017.

• Part 7: Robust vehicle routing with time windows and adaptive large neighborhood search

• [14] S. Braaten, O. Gjønnes, L.M. Hvattum, and G. Tirado. Heuristics for the robust vehicle routing problem with time windows. Expert Systems with Applications, 77:136−147, 2017.

• Part 8: Recent topics of heuristics for stochastic optimization

• [15] W.J. Gutjahr. Recent trends in metaheuristics for stochastic combinatorial optimization. Central European Journal of Computer Science, 1:58−66, 2011.

• [16] A.A. Juan, J. Faulin, S.E. Grasman, M. Rabe, and G. Figueira. A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems. Operations Research Perspectives, 2:62−72, 2015.

• [17] A. Agra, M. Christiansen, L.M. Hvattum, and F. Rodrigues. A MIP based local search heuristic for a stochastic maritime inventory routing problem. In A. Paias, M. Ruthmair, and S. Voss (eds) Computational Logistics, volume 9855 of Lecture Notes in Computer Science, pages 18−34. Springer, Berlin/Heidelberg, 2016.