Improving optimization efficiency by modifying algorithms in TSP variants

What does TSP entail?

TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips.

TSP asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

For example, imagine a travelling salesman, who has a list of cities in which they wish to sell their wares. Of course, the salesman wishes to spend as little time on the road as possible. The distances in this case denote the travelling time between two cities.

In real-life applications, the concept city represents, for example, custom ers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments.

Modifications in different fields

The first improvement proposed by Alkema focuses on algorithms in the One-of-a-Set variant of TSP. In this variation, each point has a color. Only one point of each color needs to be visited.  The second version of TSP for which Alkema developed enhancements is the Rectilinear One-of-a-Cube TSP. Here, a set of cubes is given. Every cube needs to be visited but may only be reached by moving only orthogonally: imagine wanting to take photos of certain city blocks in a grid-like (part of a) city such as Manhattan. The third and final improvement is prepared for the TSP in Narrow Cylinders version. Here, the point set is either guaranteed to be sparse or randomly generated, and all the points lie close to a line. Imagine a drone dropping off packages along a street, or visiting all the cities on mainland Japan.

In addition to his research on improving algorithms, Alkema also considered a series of following related problems. The first of these was the Minimal Rectilinear Steiner Tree in Narrow Strips. For this problem, the goal is to find the shortest network connecting all points (consisting of only orthogonal lines). Once more, a point set consisting of points close to a line is given, which is either guaranteed to be sparse or randomly generated. Such Rectilinear Steiner trees are most commonly found in circuit boards, where certain pins need to be connected via wire.

The second related challenge is the so-called On-Line TSP on a Line, where new `points' keep spawning on a line, the travelling salesman has some fixed speed, and the goal is to find a strategy for the movement of the salesman which minimises the expected waiting time of the points -- if a stable solution can be found at all. Imagine a highway maintenance worker, who fixes problems such as potholes and performs maintenance where and when required.

Conclusions with great practical utility

Alkema's proposed algorithm improvements focus on improving efficiency in the broadest sense, which has many applications in practice. One field in which this can come into excellent focus is computer-science research. In this field, improved efficiency immediately causes computers to perform better. And that in turn has far-reaching positive consequences in just about every aspect in society today.

Title of PhD thesis: Geometric TSP and related problems in (almost) low-dimensional spaces

Supervisors: prof.dr. Mark de Berg, prof.dr. Remco van der Hofstad