On Maritime Optimization and Steiner Tree Problem

This DIKU Talk is hosted by the APL Research Section.

Speakers: David Pisinger and Martin Zachariasen.

Maritime Optimization
by David Pisinger, professor at DTU/Affiliate professor at DIKU


It is estimated that 90% of the global trade is carried out via the sea, hence calling for decision tools that can support an efficient, fast and reliable operation.

The talk gives an overview of various optimization problems in liner shipping, going in depth with a decision support tool for bunker purchasing. The cost for bunker fuel represents a major part of the daily running costs of liner shipping vessels. The vessels, sailing on a fixed roundtrips of ports, can lift bunker at the visited ports having fluctuating prices. The stock of bunker on a vessel is subject to a number of operational constraints as capacity limits, reserve requirements, sulphur content and others. Bunker purchasing is often done using contracts, ensuring supply and often giving a discounted price. A contract can supply any vessel in a period and port and is thus a shared resource between vessels, which must be distributed optimally, to reduce overall costs. The problem has been formulated as a mixed integer program which has been Dantzig-Wolfe decomposed and for which a novel Column Generation algorithm is developed. The algorithm has been implemented and run on a series of real world instances involving more than 500 vessels and 500 contracts showing promising results.

In the second part of the talk we adress the problem of liner shipping network design. A good network should ensure that the capacity of vessels is utilized well while having fast transportation times and good connections. A benchmark suite has been developed to make it easier for new researchers to enter this field, and preliminary results are reported for an automated tool designing the route network.

Short break

Two centuries of Euclidean Steiner trees
by Martin Zachariasen, professor and head of department at DIKU

The history of the Euclidean Steiner tree problem, which is the problem of constructing a shortest possible network interconnecting a set of given points in the Euclidean plane, goes back to Gergonne in the early 19th century. In this talk I present some of the contributions of the earliest papers on the Euclidean Steiner tree problem. Furthermore, I link these initial contributions with results from the recent literature on the problem.

Joint work with Marcus Brazil, Ronald L. Graham and Doreen A. Thomas.