Doctoral candidate: Martijn van Ee
Research track: Logistics & Operations Research
Start date: January 2014
Supervisors: Prof. dr. L. Stougie & dr. ir. R.A. Sitters
Approximation and complexity of a priori routing problems
Within the field of theoretical computer science, combinatorial optimization is concerned with finding an optimal solution among a set of feasible solutions. A classical example is the traveling salesman problem (TSP). Given a list of cities and a distance for each pair of cities, the goal is to find a tour that visits every city such that the total distance traveled is minimized. For large instance sizes, complete enumeration of all tours is too time consuming, even on a very fast computer. So we need to find methods, called algorithms, that approach the problem in a sensible way such that it will find “good” solutions “fast”. In computational complexity theory, we say an algorithm is “fast” if it runs in polynomial time, i.e. the number of steps the algorithm executes is bounded by a polynomial function of the input size. What we ideally would like to have is a polynomial time algorithm that finds the optimal solution for every instance. Unfortunately, for a large class of “hard” problems, including TSP, it is very unlikely (i.e. impossible, unless P=NP) that such an algorithm exists. Because we still want to be done in reasonable time, we stick to polynomial time algorithms but we do not ask the algorithm to find the optimal solution. Instead we are satisfied with a solution that is almost optimal. More formally, we want to find an approximation algorithm, where an α-approximation algorithm finds a feasible solution with an objective value (e.g. total distance) that is within α times the optimal solution for all problem instances. Research in combinatorial optimization is focused on determining the complexity of a problem, i.e. polynomial solvable or “hard”, and finding approximation algorithms for “hard” problems.
In my research, there is a distinction in deterministic and stochastic combinatorial optimization. In deterministic problems, we assume that the data in the instance is known. In stochastic problems, there is some uncertainty in the instance data. An example of the latter is a priori routing. In this setting, one has to construct a tour in the first stage and there is a probability distribution over active sets, vertices that have to be visited in the second stage. For a fixed first-stage tour, the second-stage tour on an active set is obtained by restricting the tour on the active set. In the a priori TSP, the goal is to find a first-stage tour that minimizes the expected length of the second-stage tour. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies, i.e. arrival or waiting times. Again, the goal is to understand the complexity and the approximability of these problems. To understand the stochastic problems, it is fundamental to understand the underlying deterministic problems. That is why part of my research in focused on deterministic problems, like special cases and variations of TRP. Another field that is concerned with solving problems under restricted information is the field of online optimization. Here, the instances are deterministic but the information is given in parts over time and one has to make irrevocable decisions when some piece of information is presented. It would be interesting to look at these problems too.