Pedro Maristany de las Casas successfully defended his dissertation “ New Multiobjective Shortest Path Algorithms“ at the Institute of Mathematics at Freie Universität Berlin on Mai 15, 2024. He developed the currently fastest algorithms for multicriteria shortest path optimization with three and more objectives for the 1-to-all, 1-to-1, and the time-dependent case, as well as the best fully polynomial time approximation scheme. An application of his method provides the fastest three and more objective spanning tree algorithm and new k-simple shortest path algorithm that matches the complexity of Yen’s algorithm but is much faster in practice. Test problems and implementations of all his algorithms are available in open source. The work originates from a research project with Lufthansa Systems on flight trajectory optimization, where objectives such as fuel consumption, speed, and overflight costs have to be balanced. The research took place in the MobilityLab of the BMBF Research Campus MODAL.
The picture shows (from left to right) Max Willert (postdoc committee member), Dorothea Wagner (Karlsruhe Institute of Technology, external committee member), Pedro Maristany, Ralf Borndörfer (promoter and committee head), and Georg Loho (committee member).
Congratulations!
- Link to flight planning homepage: https://www.zib.de/research/projects/flight-trajectory-optimization-airway-networks
- Link to algorithm downloads: https://github.com/maristanyPedro
- Link to test problems: https://git.zib.de/bzfmaris/mosp_instances
