Forskningsprojekt The aim of the project is to develop an exact algorithm for solving the traveling salesperson problems (TSP). The project suggests combining heuristics (to get an initial feasible solution) and exact methods (for solving a particular subproblem) to develop a new exact algorithm that constructs all existing optimal solutions for the TSP in an effective way.
The importance of traveling salesperson problem (TSP) arises from the variety of its applications with some of them not directly associated with routing. Solving TSPs is essential in such applications as vehicle routing, material handling in a warehouse, computer wiring, holes punching, wallpaper cutting, job sequencing, aircraft mission planning. The main applications in statistical data analysis include clustering proteins and ordering genes.
The aim of the project is to develop an exact algorithm for solving the traveling salesperson problems (TSP). The project suggests combining heuristics (to get an initial feasible solution) and exact methods (for solving a particular subproblem) to develop a new exact algorithm that constructs all existing optimal solutions for the TSP in an effective way. This also includes time complexity analysis of the algorithm as well as its implementation to provide infrastructure for handling and solving TSPs.
The importance of traveling salesperson problem (TSP) arises from the
variety of its applications with some of them not directly associated with routing. Solving TSPs is essential in such applications as vehicle routing, material handling in a warehouse, computer wiring, holes punching, wallpaper cutting, job sequencing, aircraft mission planning. The main applications in statistical data analysis include clustering proteins and ordering genes. The problem of sequencing or scheduling a group of jobs on a single machine to minimize the total time to complete all jobs, or equivalently to minimize the cost of switching, can also be viewed as a TSP.
The TSP is a rather simple problem to describe, but yet there is no efficient algorithm that can solve it. In fact the TSP belongs to the class of combinatorial optimization problems known as NP-complete. Due to both the straightforward statement of the problem and importance of the problem in numerous practical applications, the TSP has received huge amount of attention and lots of research has been devoted to it. Despite all of the attention received to tackle the problem, up to date no one has found an efficient algorithm to solve the TSP.
The postdoctoral fellowship is funded by the Kempe Foundations.
