Project Description

The project titled Implementation of the Probabilistic Traveling Salesman in HeuristicLab was the Master Thesis for my Computer Engineering Masters Degree in Johannes Kepler University. It wouldn't have been possible without the help and support of my advisor, Professor Michael Affenzeller.

Project Details

The Probabilistic Traveling Salesman Problem (PTSP) is one of the most popular problems in stochastic routing. The main reasons for this are the large number of interesting real-world situations where it can be applied and the inherent difficulty of solving stochastic combinatorial optimization problems. Therefore, a lot of effort has been put into designing efficient metaheuristics for tackling this problem. Recently, there has been a shift from exact methods based on analytical computation to approximate methods based on Monte Carlo sampling for the way in which the solutions are evaluated.

The main goal of our work is to develop an implementation of the PTSP for HeuristicLab, an existing framework for heuristic and evolutionary algorithms. This consists of modelling the problem itself and an efficient algorithm based on Local Search with estimated delta evaluation expressions for the different neighborhoods. It is shown that the solution proposed is comparable in terms of performance with similar documented studies, by means of an empirical study.

Moreover, to characterize the PTSP and get some insight into which optimization method would be more appropriate, a Fitness Landscape Analysis is performed. In order to do this, the features of the landscape are studied from different points of view and scales. The interpretation of the obtained results gives an idea of the shape of underlying fitness landscape and how it varies across the different types of PTSP instances. This work serves as a starting point for researching fitness landscapes of the Probabilistic Traveling Salesman Problem.

Links

• PDF