Developing an exact solution method for a complex routing problem
Responsable(s) :
Iliya Markov, Nikola Obrenovic, Michel Bierlaire
Description :
The aim of this project is the development of an exact approach based on column generation for a complex routing problem. The student will start from an existing non-linear formulation of the problem, apply linearization techniques and identify assumptions to arrive at a linear closed-form model of a specific form called a path-based formulation. Given the complexity of the problem at hand, the focus will be put on developing a on column generation procedure, which has proved to be the best exact method for routing problems. This approach will be used for solving small and medium-sized instances exactly and computing lower bounds for large instances. The student needs to have good programming skills and knowledge of linear and mixed integer linear programming. The topic is appropriate for a master's thesis or a semester project of 10 credits or more.
Collaboration with:
Type :
masters project, semester project
Pré-requis :
Java (good knowledge), Operations Research (linear programming, mixed integer linear programming, branch-and-bound)
Submitted on :
August 29, 2017