Traveling Salesman Problem (TSP) is a well-known and highly investigated topic in combinatorial optimization. TSP can be modelled as an undirected weighted graph, such that cities are the graph's vertices, paths are the graph's edges, and a path's distance is the edge's weight. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. Often a cost function (e.g. distance) is defined on the edges, hence one can try not only to find an aforementioned path but also an aim can be to find the „cheapest” one. A similar problem can be defined if we try to cover the points of the graph with several disjoint cycles where all but one points are contained by exactly one cycle and that one exception is contained by all the cycles (depot). A natural question is here to find
the minimal number of cycles with the previous conditions. This problem is a very important problem for example in logistics nowadays. Modelling the distribution and delivery of goods and optimizing the traveling distance and/or the delivery time and related parameters is of high interest both from financial and environmental reasons. There are several subproblems defined here by the real life applications:
- Capacitated Vehicle Routing Problem,
- Vehicle Routing Problem with Time Windows,
- Pickup and Delivery Problem
Combining these variations with additional conditions resulting a wide variety of problems that are interesting both from theoretical and indsutrial points of view.
The variety of applied methods and approaches for finding a solution is as high as colorful problems can be defined in this area. We know about effective heuristical methods and of course there are approximation algorithms and many interesting methods too. Not so surprisingly (because of TSP is NP-hard) most of these problems are NP-hard. So our aim is usually not solving the problem but approximating the optmial solution in a reasonable computational time.
The applicants task will be to investigate the literature of this topic, select most relevant problems for our applications and the most known algorithms related to them and of course understanding the mathematical tools for this. Following this we will select a task from our research topics that is the most suitable for the candidate. They will help in modelling the problem and implementing, debugging and testing a proposed algorithm for solving the
problem. For this they will need to learn essential programming skills and learn dealing with large data sets.
Referenciák
- P. Toth, D. Vigo, The Vehicle Routing Problem, SIAM, 2002
- J.-F. Cordeau, A branch-and-cut algorithm for the dial-a-ride problem, Operations Research,
54(3):573-586, 2006