Projects

Motivation

Ever increasing cost and competitive pressures in the port industry require the identification and analysis of new alternative courses of action and data-driven decisions. As an important link within global supply chains, container terminals are particularly challenged to identify, evaluate and address new optimization potentials. Transparency plays an essential role in the continuous and sustainable improvement of efficiency, reliability and quality of processes in container terminals. The use of digital technologies in the context of Industrie 4.0 can significantly increase transparency and forms an important basis for data-driven decision support. Digital twins are regarded as a key technology of Logistics 4.0 and enable physical systems to be mapped in the digital world.

Project Aims

The TwinSim project aims to develop a digital twin for the virtual mapping of processes and equipment in container terminals together with project partners from research, development and end users. This virtual mapping will enable analyses and simulation-based optimizations that will lead to improving the efficiency, productivity, resilience and environmental impact of terminals. In doing so, technologies and approaches will be researched and developed that will lead to a new digital and innovative tool that can be used directly for planning transport, storage and maintenance operations. In particular, the digital transformation of the terminals as well as the topic of Logistics 4.0 will be driven forward. The application will initially be tested and be made available at the EUROGATE Container Terminal Hamburg (CTH).

Solution

First, functional and non-functional requirements are to be elicited by means of a requirements analysis and a use-case definition. Based on the evaluation of these requirements, the relevant devices and systems are connected to a data lake using IIoT technologies. In the further course of the project, the resulting data platform will form the basis for real-time 3D visualization as well as historical data visualization. Furthermore, the platform is used for the development of simulation models and AI methods for the optimization of transport, storage and maintenance processes.

Lead partner: TÜV Rheinland Consulting

Project volume : 3.648.293,- € (of which a percentage of 54% is sponsored by the BMVI)

Project start and end date: 10/2021 – 09/2024

Scientific project manager: Dr. Leonard Heilig, leonard.heilig@uni-hamburg.de

We are currently working on the dynamic berth allocation problem. Data from the following paper can be found here.

You can download the paper here or via the following link: https://doi.org/10.1016/j.ejor.2019.03.036

The “Landesforschungsförderung Hamburg” is funding the development of international research cooperation in the Baltic Sea region and promoting research in maritime logistics with the project “Maritime Load Dependent Lead Times: Lead Time and Eco-Efficient Lean Management in the Maritime Supply Chain (M-LDLT).”

Together with two German Partners, the Center for Engineering Operations Management of the University of Southern Denmark with Associate Professor Julia Pahl, and the University of Paderborn with Assistant Professor Kevin Tierney, the University of Hamburg with the team of Prof. Dr. Stefan Voss will investigate the phenomenon of maritime load dependent lead times (M-LDLT). These are triggered by delays and insufficient information management between maritime logistic chain partners. A thorough analysis of the causes and system wide improvements from an operations and information management perspective will be conducted. Another focus is on energy efficiency and the minimization of waste in terms of resources such as energy, time, and other critical resources.

The project is funded for two years starting from the 1st of January 2017 and includes the establishment of a solid international research group that will be able to form a strong consortium for competing for European funding such as Horizon 2020. The project includes the realization of workshops and conference visits aiming at creating visibility and linkages of M-LDLT with neighboring research topics and within the maritime research community.

We are eager and very positive that within the two year project horizon we will be able to attract highly recognized researchers and teams to build a strong international network for maritime logistics and information sciences for dealing with the global challenges in maritime logistics in the years to come.

In an erratum to their paper `A hybrid genetic algorithm for the multi-depot open vehicle routing problem', Liu et al. [3]¹ corrected some of the table entries from their paper [4]. However, they did not correct an issue regarding the data of one of the problem instances. In their paper, the authors correctly stated that they used the problem instances provided by Cordeau et al. [1]. However, when they mapped the problem instances from the Cordeau et al. format to their own format, they incorporated a mistake. In this short note, we point out the difference in the data within the problem instance from the original source [1] and Liu et al.
[4]. Moreover, we provide the optimal solution value using the optimization model provided by Lalla-Ruiz et al. [2] in both cases, namely, for the Liu et al. instance as well as for the corrected one replicating the same scenario provided by Cordeau et al. as stated in [4]. Note that this also constitutes a corrigendum of the optimal value reported in [2].

Table 1: Problem instance p15

Table 1 shows the Erratum in the data of instance p15 as well as the optimal solution value (Opt. value) and computational time (Time (s)) for the instance with (Corrected Value) and without the correction using the same mathematical model and environment as in [2]. As reported in the table, one of the coordinates of one of the depots, pos_mx , was not well mapped leading to a modified optimal solution value for the above-mentioned original instance. Finally, as an electronic attachment to this corrigendum, we provide the problem instance of Liu et al. with the mistake corrected and a downloadable version of this note for citation (below).

¹ Note that the erratum was based on the hints of one of the authors of this paper.

References:

1. J. F. Cordeau, M. Gendreau, and G. Laporte. A tabu search heuristic for periodic and
multi-depot vehicle routing problems. Networks, 30(2): 105-119, 1997.
2. E. Lalla-Ruiz, C. Exposito-Izquierdo, S. Taheripour, and S. Voß. An improved formulation
for the multi-depot open vehicle routing problem. OR Spectrum, 38(1): 175-187, 2016.
3. R. Liu, Z. Jiang, and N. Geng. Erratum to: A hybrid genetic algorithm for the multi-depot
open vehicle routing problem. OR Spectrum, 36(2): 423-424, 2014.
4. R. Liu, Z. Jiang, and N. Geng. A hybrid genetic algorithm for the multi-depot open vehicle
routing problem. OR Spectrum, 36(2):401-421, 2014.

Please click here for the note as a pdf-version for citation.

Please click here for the zip-file including the original version of the p15-instance by Cordeau et al., the original by Liu et al., and the corrected version.

In this paper we propose a new problem of finding the maximal bi-connected partitioning of a graph with a size constraint (MBCPG-SC).  With the goal of finding approximate solutions for the MBCPG-SC, a heuristic method is developed based on the open ear decomposition of graphs. Its essential part is an adaptation of the broad first search which makes it possible to grow bi-connected subgraphs. The proposed randomized algorithm consists of  growing several subgraphs in parallel. The quality of solutions generated in this way is further improved using a local search which exploits neighboring relations between the subgraphs. In order to evaluate the performance of the method, an algorithm for generating pseudo-random unit disc graphs with known optimal solutions is created. Computational experiments have also been conducted on graphs representing  electrical distribution systems for the real world problem of dividing them into a system of fault-tolerant interconnected microgrids. The  experiments show that the proposed  method  frequently manages to find optimal solutions and has an error average of only a few percent to known optimal solutions. Further, it manages to find high-quality approximate solutions for graphs having up to 10.000 nodes in a reasonable time.

Please find here our problem instances.

At container terminals, remarshalling of containers is performed to reduce the need for further relocation. For instance, once the stowage plan for an arriving vessel is known, remarshalling operations in the yard are carried out with the goal of minimizing
unproductive moves. Particular problems like the Blocks Relocation Problem (BRP) or the Premarshalling Problem (PMP) take into
account whether the remarshalling is carried out before arrival of the vessel or in parallel to the loading phase.

Instances

You can download the problem instances for the Blocks Relocation Problem (BRP)
from M. Caserta, S. Schwarze, S. Voß: A mathematical formulation and complexity considerations for the blocks relocation problem. European Journal of Operational Research, 219(1), pp. 96-104, 2012 here.

For an update of our OR Spectrum paper on the corridor method plus its code please click here.

Literature

M. Caserta, M. Sniedovich, S. Voß: Applying   the   corridor method   to   a   blocks   relocation problem. OR Spectrum  33, pp. 915 - 929,  2011

M. Caserta, S. Schwarze, S. Voß: A mathematical formulation and complexity considerations for the blocks relocation problem. European Journal of Operational Research, 219(1), pp. 96-104, 2012

M. Caserta, S. Schwarze, S. Voß: A New Binary Description of the Blocks Relocation Problem and Benefits in a Look Ahead Heuristic, In: Cotta, C. and Cowling P., editors, Evolutionary Computation in Combinatorial Optimization, volume 5482 of Lecture Notes in Computer Science, pp. 37-48. Springer, Berlin (2009)

M. Caserta, S. Schwarze, S. Voß: Container Rehandling at Maritime Container Terminals, In: J.W. Böse (ed): Handbook of Terminal Planning, Operations Research/Computer Science Interfaces Series, Vol. 49, pp. 247-269, Springer (2011)

M. Caserta, S. Voß: A  corridor  method-based  algorithm  for  the pre-marshalling  problem.
Lecture Notes in Computer Science 5484,  pp. 788-797, Springer (2009)

R. Jovanovic, M. Tuba, S.Voß: A multi-heuristic approach for solving the pre-marshalling problem. Central European Journal of Operations Research, online available. [DOI 10.1007/s10100-015-0410-y]

R. Jovanovic; S. Voß: A chain heuristic for the blocks relocation problem. Computers & Industrial Engineering 75 (2014), pp. 79 - 86. [DOI 10.1016/j.cie.2014.06.010]

D. Pacino, K. Tierney, S. Voß: Solving the Pre-Marshalling Problem to Optimality with A* and IDA* . Working Paper, University of Hamburg (2013).

S. Schwarze, M. Caserta, S. Voß: Die Kunst des Stapelns – Eine Einführung in das Blocksortierproblem, WiSt, Wirtschaftswissenschaftliches Studium, Vol. 39 (12), pp. 576 - 581, 2010.

S. Schwarze, S. Voß: Some remarks on alternative objectives for the blocks relocation problem. Working Paper, University of Hamburg (2015).

E. Zehendner, M. Caserta, D. Feillet, S. Schwarze, S. Voß: An Improved Mathematical Formulation for the Blocks Relocation Problem. European Journal of Operational Research  245, pp. 415-422, 2015.

Today, there is no "heuristics stockroom" with ready-to-use software components for heuristic search. So the application of advanced metaheuristics for some new type of problem usually requires starting the implementation from scratch. This led to the development of an application framework in C++ called HotFrame (Heuristic OpTimization FRAMEwork), which provides adaptable components that incorporate different metaheuristics as well as an architectural description of the collaboration among these components and application-specific complements. All typical application-specific concepts are treated as objects (classes): problems, solutions, neighbors, solution, and move attributes. Metaheuristics concepts and their building-blocks, such as tabu criteria and diversification strategies, are also treated as objects. HotFrame employs genericity as the primary mechanism to make respective classes adaptable. That is, common behavior of metaheuristics is factored out and grouped in generic classes, applying static type variation. Metaheuristics template classes are parameterized by aspects such as solution spaces and neighborhood structures.

HotFrame includes metaheuristics such as basic and iterated local search, simulated annealing and similar methods, different variants of tabu search, evolutionary methods, variable depth neighborhood search, candidate list approaches and some hybrid methods. All heuristics are implemented in a consistent way, which facilitates easy embedding of arbitrary methods into application systems or as parts of more advanced/hybrid methods. (That is, HotFrame is not intended to serve as a stand-alone application with a fancy GUI, but aims at providing functionality that can be reused within other applications or just called from the command line.) Both new metaheuristics and new applications can be added to the framework. HotFrame includes built-in support for solution spaces that can be represented as binary vectors, permutations, or assignments of objects to resources (in each case in connection with corresponding standard neighborhood structures, solutions, and move attributes). Otherwise, the user may derive special application classes from suitable built-in classes or implement respective classes from scratch according to a specified interface.

Please note that, according to the nature of an application framework, a new kind of application requires one to complete the framework by actually coding in C++ (with regard to respective application-specific hot-spots). That is, there is no way to apply the framework without having a good command of C++ (including templates). Thus far, HotFrame has been successfully applied for quite some applications from research and practice. Some of these applications are described in the papers referenced below. Unfortunately, the framework lacks comprehensive documentation. For more information you may consider the references below or contact Andreas Fink (fink@econ.uni-hamburg.de) or Stefan Voß (stefan.voss@uni-hamburg.de).

Source Code

• Once more, please note that HotFrame is not a fancy GUI-based tool, but a C++ framework that requires, perhaps for good reasons, coding in C++ in order to apply it for some new application.
• The core of the source code can be provided on demand. The authors retain the copyright, but the code can be freely used for academic and research purposes (of course without any warranties as HotFrame is just a research prototype). For commercial usage, please contact the authors.

Literature:

A. Fink, S. Voß: HotFrame: A Heuristic Optimization Framework. In: S. Voß, D.L. Woodruff (Eds.), Optimization Software Class Libraries, Kluwer, Boston (2002), 81-154.
A. Fink, S. Voß: Anwendung von Metaheuristiken zur Lösung betrieblicher Planungsprobleme - Potenziale und Grenzen einer softwaretechnischen Unterstützung (in German). Wirtschaftsinformatik 45 (2003) 4.
A. Fink, S. Voß: Solving the Continuous Flow-Shop Scheduling Problem by Metaheuristics. European Journal of Operational Research, to appear (2004).
S. Voß, A. Fink: Efficient Metaheuristics Approaches for the Ring Load Balancing Problem. Proceedings of the 9th International Conference on Telecommunication Systems, Southern Methodist University, Dallas (2001), 243-250.
A. Fink: Software-Wiederverwendung bei der Lösung von Planungsproblemen mittels Meta-Heuristiken . Ph.D. Dissertation. Technische Universität Braunschweig, Shaker, Aachen, 2000.
A. Fink, G. Schneidereit, S. Voß: Solving General Ring Network Design Problems by Meta-Heuristics. In: M. Laguna, J.L. González Velarde (Eds.), Computing Tools for Modeling, Optimization and Simulation (Interfaces in Computer Science and Operations Research), Kluwer, Boston (1999), 91–113.
A. Fink, S. Voß: Generic Metaheuristics Application to Industrial Engineering Problems. Computers & Industrial Engineering 37 (1999), 281-284.
A. Fink, S. Voß: Applications of Modern Heuristic Search Methods to Pattern Sequencing Problems. Computers & Operations Research 26 (1999), 17-34.
A. Fink, S. Voß, D. Woodruff: Building Reusable Software Components for Heuristic Search. In: P. Kall, H.-J. Lüthi (Eds.), Operations Research Proceedings 1998, Springer, Berlin (1999), 210-219.
A. Fink, S. Voß: HOTFRAME - Heuristische Lösung diskreter Planungsprobleme mittels wiederverwendbarer Software-Komponenten. OR News 4/98, 18-24.

Figure 1: Lead time syndrome

Figure 2: Non-linear relationship between lead time and resource utilization

At the beginning of the resource utilization, the waiting time is relatively constant, but above a certain level of resource utilization, which is about 80–85%, the waiting time increases exponentially.

Present "planning systems," which include linear programming algorithms, only allow one resource limit, amounting to 100%, that must not be exceeded. But this does not take into account that the lead time has been increasing predecedingly. This leads to deviations between planned and actual lead time. Consequences of these deviations may fuel the lead time syndrome again.

With our study we want to investigate load-dependent lead times and their factors more closely on a practical level.

Literature:

J. Pahl, S. Voß, and D.L. Woodruff. Production planning with load dependent lead times. 4OR: A Quarterly Journal of Operations Research, 3(4):257–302, 2005 (Link: Springerlink)
J. Pahl, S. Voß, D.L. Woodruff. Production Planning with Load Dependent Lead Times: An Update of Research, Annals of Operations Research, 153(1), p. 297-345, 2007 (Link: Springerlink)
J. Pahl, S. Voß, and D.L. Woodruff. Load dependent lead times - from empirical evidence to mathematical modeling. In H. Kotzab, S. Seuring, M. Müller, and G. Reiner, editors, Research Methodologies in Supply Chain Management, 539–554. Physica, Heidelberg, 2005 (Link: Research Methodologies in Supply Chain Management (Link: Springerlink)

Project description

The ever-growing demand for bandwidth creates a constant need for the planning of new telecommunication networks and for the expansion of existing systems. State-of-the-art long-haul and metro high-speed networks are mainly based on Synchronous Digital Hierarchy (SDH) or its American equivalent Synchronous Optical Network (SONET) and Dense Wavelength Division Multiplex (DWDM). On the other hand, the large amount of traffic growth during the last years has been caused largely by Internet Protocol (IP) traffic. Traditionally, the IP-router-based networks and the cross-connect based synchronous networks are often planned and operated separately. However, in line with new developments such as Generalized Multiprotocol Label Switching (GMPLS), network providers begin to realize that the convergence of these two worlds promises significant benefits.

We work on multi-layer network design problems for high-speed telecommunication networks based on SDH, DWDM, and IP technology. The network has to carry a certain set of demands with the objective of minimizing the investment in the equipment. Several variations of the problems, including path-protected demands and specific types of equipment, are considered. Mixed integer linear programming models and greedy heuristics (including a GRASP-like approach) have been successfully used on several real-world problems. For more information you may consider the references below or contact Stefan Voß (stefan.voss@uni-hamburg.de).

References

H. Höller, S. Voß: Software Tools for a Multilayer Network Design, presented at the IV International Conference on Decision Support for Telecommunications and Information Society, September 2004, Warsaw, Poland.

H. Höller, S. Voß: A Heuristic Approach for Combined Equipment-Planning and Routing in Multi-layer SDH/WDM Networks, European Journal of Operational Research, to appear (2004).

H. Höller, S. Voß, M. Fricke, S. Neidlinger: Vergleich des Einflusses der Bedarfsstrukturen und Netztopologien von SDH/WDM Netzen auf das eingesetzte Schutzverfahren, in: ITG-Fachbericht 182 "Photonische Netze", Vorträge der 5. ITG Fachtagung "Photonische Netze" in Leipzig, VDE Verlag, Berlin (2004), 115-120.

H. Höller, S. Voß: A Mixed Integer Linear Programming Model for Multilayer SDH/WDM Networks, working paper, Universität Hamburg (2003).

H. Höller, S. Voß, M. Fricke, S. Neidlinger: Schichtenübergreifende Netzplanung, in: ITG-Fachbericht 175 "Photonische Netze", Vorträge der 4. ITG Fachtagung "Photonische Netze" in Leipzig, VDE Verlag, Berlin (2003), 21-28.