Dynamic Shortest Path and Fleet Management

Student

  • Zubayr Ahmed Bhutta

Advisor

  • Dennis Marten

  • Holger Meyer

Description

The search for the shortest path in a graph is of great importance for many applications in industry and research. Each of these applications may be associated with different constraints. In this thesis, a shortest path problem in a maritime context has to be studied. JAKOTA Cruise Systems GmbH is one of the world’s leading companies in the analysis and distribution of AIS (Automatic Identification System) data [1, 2]. The latter are used in combination with geospatial information (ports, sea lanes, ...) to predict the movements of international shipping traffic by using graph algorithms [2, 3, 4]. Here, the routes of hundreds of thousands of ships are calculated daily in a large static graph. In this work, possibilities shall be investigated to extend the graph in the present infrastructure in such a way that the edge weights can be dynamic. This allows for inclusion of temporary critical effects like severe weather or port congestion. In particular, consideration should be given to the large amount of daily processing costs. As a prerequisite for applying shortest path algorithms at large scale, an appropriate graph data management strategy has to be designed.

Road Map

  • Extensive investigation and presentation of the state of the art in dynamic shortest path algorithms

  • Requirement analysis based of the companies AIS scenarios with a strong focus on time-dependent data

  • Development of a concept taking into account existing infrastructure

  • Prototype implementation and quality based evaluation using AIS scenarios

References

  1. D. Marten, C. Bünger and C. Hilgenfeld, Maritime Traffic Prediction as a Basis for Air Pollution Estimation, Proceedings of the 19th EUROPEAN TRANSPORT CONGRESS, Maribor (Slovenia), 2021.

  2. Yang, Dong, et al. "How big data enriches maritime research–a critical review of automatic identification system (AIS) data applications." Transport Reviews 39.6 (2019): 755-773.

  3. Hall,E.,andTexAustin."Time-dependent,shortest-pathalgorithmforreal-time intelligent vehicle highway system applications." (1993).

  4. Casey,Bradley,etal."Criticalreviewoftime-dependentshortestpathalgorithms:A multimodal trip planner perspective." Transport Reviews 34.4 (2014): 522-539.

  5. A. Orda and R. Rom, Shortest-path and minimum-delay algorithms in networks with time- dependent edge-length, J ACM 37 (1990), 607–625.

  6. Idri,Abdelfattah,etal."Anewtime-dependentshortestpathalgorithmfor multimodal transportation network." Procedia Computer Science 109 (2017): 692- 697.