Determine problem characteristics relevant for choosing the appropriate solution technique for a real-life problem.


50000403v1767

Promoter: Dirk Cattrysse, Pieter Vansteenwegen

details
Description: Three types of solution strategies can be distinguished in the operations research field: exact methods, heuristics and metaheuristics. With exact methods an optimal solution is guaranteed. Heuristics are more straightforward and much faster methods capable of solving big and complex problems. However, the solution quality is significantly reduced. Metaheuristics are the most recent solution strategy. Metaheuristics apply a meta-strategy to considerably improve the quality of the results of one or more simple heuristics. The most important metaheuristics are (Glover & Kochenberger, 2003) tabu search, iterated local search, guided local search, genetic and evolutionary algorithms, ant colony optimisation and variable neighbourhood search. Metaheuristics are capable of reaching a high quality solution within reasonable calculation time.

When a new type of problem comes up, a researcher will often try to solve this problem with the solution strategy he is familiar with. At this moment, not enough scientific insight is developed about strong and weak points of algorithms to make a well-considered choice for a certain procedure. Sometimes the quality of (specific implementations of) algorithms is compared for a given problem, but this comparison is almost always based on the obtained results and not on the question why one method obtained better results than the other method.

The goal of this project is to determine problem characteristics relevant in the choice of a well performing solution strategy. When a new problem arises, in logistics or production, it will be possible to select the most promising technique for this new problem, based on its characteristics. More specifically, this means that when a new problem has characteristic A (or B), algorithm X (or Y) will be a proper framework to start with. It is not the idea to determine which algorithm is “somewhat better”, but to determine which algorithm is the most promising one for a class of problems with a specific characteristic.

Since the research field of metaheuristics and optimisation problems is quite large, we limit this project to the following optimisation problems and their variants:
- the orienteering problem,
- the travelling salesperson problem,
- the knapsack problem.
We limit this research to the following metaheuristics:
- tabu search,
- variable neighbourhood search,
- guided local search,
- ant colony optimisation.


Key words: metaheuristics - optimization techniques - operations research

Latest application date: 2010-05-17

Financing: to apply for

Type of Position: scholarship

Source of Funding: no funding available - the candidate should have a full scholarship

Duration of the Project : 4 years

Research group: Department of Mechanical Engineering

Remarks: The candidate should have a full scholarship (living - housing - tuition fee)

Apply to Click here to apply to this project