The core area operations research focuses on classical combinatorial optimization problems. This topic includes many common problems appearing e.g. in industrial logistics like supply chain management or scheduling. The aim here, roughly spoken, is to find realizable solutions in a reasonable amount of time. On our chair, we investigate on one side various meta- and matheuristic algorithms like the simulated annealing, the tabu search, genetic algorithms or the large neighbourhood search and, on the other side, the exact boundary between $\mathcal{NP}$-hard problems and polynomial solvable special cases of them. Apart that we also focus on modelling of various practical logistic problems using linear and non-linear programming.

All these topics are essential parts of the bachelor's and master's programmes Industrial Logistics; thus we also cooperate with the Chair of Industrial Logistics.

The travelling salesperson problem (TSP) is one of the best known combinatorial optimization problems which has been exhaustively investigated for many decades. Given a complete graph $G = (V, E)$ with $|V|$ and $|E| = n(n-1)/2$ and non-negative distances $d_e$ for each $e \in E$, the TSP asks for a shortest tour with respect to the distances $d_e$ containing each vertex exactly once.

In our research we target very large instances with up to $10^9$ vertices. For such dimensions common approaches are useless, because even algorithms having a quadratic running time are too slow. Therefore we develop matheurstics dividing the original problem into many small subproblems, which are solved to optimality.

Similarly to the TSP in the quadratic travelling salesman problem (QTSP) we are looking for a tour; however, not only the costs of direct movements from one vertex to the next vertex are considered, but beyond that, costs arising for the successive use of two edges are taken into account. This means that we consider the transition in each vertex $v$ which depends both on the predecessor and on the successor of $v$ in the tour. As a consequence, transition costs, such as the effort of turning in path planning, changing the equipment in scheduling or the change of transportation means in logistic networks from one edge to another, can be modelled. If the transition costs correspond to turning angles, we speak of the angular-metric travelling salesperson problem (AngleTSP); the AngleTSP is therefore a special case of the QTSP.

In our research we look for efficient meta- and matheuristics for solving this problem. They are based 1) on geometric properties of “good” tours if considering the AngleTSP and 2) on rounding matheuristics using a linearization of the original quadratic program in the general case.

The maximum quadratic travelling salesperson problem (MaxQTSP) and the maximum angular-metric travelling salesperson problem (MaxAngleTSP) are the maximization versions of the QTSP and of the AngleTSP, respectively.

In our research we could show that the MaxAngleTSP is solvable in a polynomial time if the number of vertices $n$ is odd. The open question is, whether the MaxAngleTSP is solvable in a polynomial time if $n$ is even as well. If this is not the case, which complexity class does this problem belong to?

Further, we are also investigating this problem from the heuristic point of view: we could observe that using the optimum tours of the MaxAngleTSP “good” solutions for the Euclidean variant of the maximum weight matching problem can be constructed. Now we would like to reverse this process and use optimum matchings for the construction of “good” MaxAngleTSP tours.

The last research area is of theoretical nature: let $G = (V, E)$, where $|V(G)| = n$ be a so-called guest graph and let $d \geq 2$ be fixed. Furthermore, let the so-called host graph be a $d$-regular tree $T$ of height $h = \lceil\log_d{n}\rceil$ and let $B$ be the set of its leaves. The data arrangement problem on regular trees (DAPT) asks for an arrangement $\phi$ that minimizes the objective value $OV(G, d, \phi) := \sum_{(u, v) \in E}{d_T\big(\phi(u), \phi(v)\big)}$, where $\phi\colon V(G) \to B$ is an injective embedding and $d_T\big(\phi(u), \phi(v)\big)$ denotes the length of the unique $\phi(u)$-$\phi(v)$-path in the $d$-regular tree $T$.

In our research we would like to find the boundary between the $\mathcal{NP}$-hard variants and the polynomial solvable special cases of this problem. We could show that the problem remains $\mathcal{NP}$-hard even if the guest graph is a tree. The open question is whether the problem is solvable in a polynomial time if both the guest and the host graph are binary regular trees. This special case could seem to be easy to solve on the first view, but no polynomial-time algorithm is known. Moreover, it is very unlikely that the problem is $\mathcal{NP}$-hard, because $\mathcal{NP} = \mathcal{P}$ would follow otherwise. Is it possible that this problem is neither $\mathcal{NP}$-hard nor that it belongs to the complexity class $P$? If yes: which complexity class does it belong to?

Students who would like to write their bachelor's or master's thesis (theoretical as well as practical) on the field of operations research, are welcome to contact me via e-mail: rostislav.stanek(at)unileoben.ac.at. Collaborations with companies are welcome, too!