Master
| Working title | Brief description & literature |
|---|---|
Methodological advances on metaheuristics (Bachelor/Master) | Metaheuristics is a a currently most widely used optimization approach in industry, engineering, disaster relief etc.etc. The aim of the thesis is to provide a tutorial-like summary on how metaheuristics can be analyzed formally, which conclusions can be drived from these pieces of analysis etc. You will have to explain in depth one or several selected results (e.g., most relevant, most interesting…) Jansen, T. (2013). Analyzing Evolutionary Algorithms The Computer Science Perspective. Springer. DeJong, K. (2006). Evolutionary Computation: A Unified Approach. MIT Press. |
Literature review on the novel ng-route relaxation approach for routing problems (Bachelor/Master) | Baldacci, Mingozzi and Roberti (2011) proposed the ng-routes as compromise between elementary and non-elementary routes. Given a TSP route, an elementary route is a route where each customer in the tour is visited exactly once. A non-elementary route relaxes this criterion by visiting some customers more than once or omits some customers in the final tour. The ng-routes pose dynamically computed restrictions on which customers can be visited next. This relaxation belongs to the state-of-the-art path relaxations for routing problems and is key in the development of state-of-the-art routing algorithms. Baldacci, Roberto; Mingozzi, Aristide; Roberti, Roberto (2011): New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem. In: Operations Research 59 (5), S. 1269–1283. Roberti, Roberto; Mingozzi, Aristide (2014): Dynamic ng-Path Relaxation for the Delivery Man Problem. In: Transportation Science 48 (3), S. 413–424. |
Fast solution of certain scheduling problems: Transformation to Gilmore-Gomory TSP (Bachelor/Master) | Gilmore and Gomory (1964) developed a brilliant algorithm which is able to solve a special case of the travelling salesman problem (TSP) in polynomial time. Since then, the algorithm and the problem have been used in different areas such as scheduling. The aim of this thesis is to find, review and categorize the studies which have used Gilmore-Gomory algorithm in scheduling problems and extract theoretical and practical insights on their applications. * Gilmore, P. C. , & Gomory, R. E. (1964). Sequencing a one state-variable machine: A solvable case of the traveling salesman problem. Operations Research, 12, 655–679. |
The Benders decomposition algorithm: Novel use cases, trends and acceleration strategies (Master) | The Benders decomposition algorithm is a well-established exact solution method originally proposed by Benders (1962), which was successfully applied to solve complicated problems in many divers fields, including planning and scheduling, health care, transportation and telecommunications, energy and resource management, and chemical process design. In recent years, it is in trend again for solving complicated combinatorial optimization problems which can be formulated as a mixed-integer linear program. Novel extensions, acceleration methods and hybrid applications (e.g. in combination with metaheuristics) have been recently introduced. The first step of this thesis is to get an overview about the functionality of the classical Benders decomposition algorithm and its extensions from the survey by Rhamaniani et al. 2017, as well as extensing this survey by further relevant works published since 2017. In the next step, the candidate should either identify a new use case suitable for Benders decomposition and apply the algorithm on that problem, or select a classical use case for Benders decomposition and extend the existing implementation by novel acceleration strategies or features. Rahmaniani, R., Crainic, T.G., Gendreau, & M. Rei, W. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259, 801-817. |
Share this page
