Team
Project team leaders: | Dr. René Brandenberg, Dr. Michael Ritter |
---|
Co-operation partners | Institut für Produktionswirtschaft und Logistik, Universität für Bodenkultur Wien |
---|
Summary
In many classical routing problems we do not distinguish between the traveler / the good to be transported and the transporter / the conveyance. However, in many applications this may be necessary, e.g. due to multiple cost functions on the edges of the given graph (e.g. temporal and pecuniary travel costs), each choice of conveyance representing a different combination, and limited budgets. So, one may reduce the travel time by investing in more expensive transportation, and vice versa. The objective may be a route and a choice of conveyance on the edges of this route minimizing the pecuniary costs of the routing under the additional temporal budget constraint. In this setting already the Shortest Path Problem becomes NP-complete. Furthermore, caused by the two (or more) cost functions, there may be a huge number of alternative conveyance choices when going from A to B, which all have to be considered for the optimal routing. Just one consequence: the typical graph completion preprocessing is impractical under these terms. Our first goal in this research project will be the derivation of positive or negative results on approximability and the development of good frameworks for solving these problems in practical applications as the ones mentioned above.
Subprojects
Sight-seeing

- Find a cost-minimal tour visiting all sights, including a choice of conveyance for every edge traversed, that respects the given time limit (Sightseeing TSP).
- For each of the sights in the city we assume an additionally given numeric score value expressing the tourists preferences towards certain attractions. Now, choose a subset of the nodes and a tour through these nodes such that all bounds are respected and the overall valuation of the the chosen nodes is maximized (Sightseeing Problem).
Urban Health-Care
A cooperation with the Institute of Production and Logistics at the University of Natural Resources and Life Sciences, Vienna (BOKU)
Wood transport with foldable containers
A cooperation with the Institute of Production and Logistics at the University of Natural Resources and Life Sciences, Vienna (BOKU)
Related student theses and projects
Supervised Dissertations
- Wolfgang Ferdinand Riedl - Routing under choice of conveyance
Completed Theses and Projects
Completed Master's Theses / Diploma Theses
- Julia Baukmann - Meta-Heuristics for the Orienteering- and the Sightseeing-Problem (2015)
- Stephanie Nikola - Umsteigegraphen im ÖPNV (2013)
- Katharina Zahnweh - Multi-Weighted TSP - The Traveling Salesman Problem under Additional Knapsack Constraints (2013)
- Lisa Kehrer - The Path Sightseeing Problem: Heuristics and Cutting Planes for a Routing Problem (2011)
- Melanie Herzog - Sightseeing: Routenplanung unter Beachtung von Finanz- und Zeitbudgets (2010)
- Benjamin Broll - Untersuchungen verallgemeinerter Traveling Salesman Probleme zur Nutzung in elektronischen Besucherführern (2009)
- Christian Böhm - Routenplanung unter Budgetrestriktionen - Polytopale Untersuchungen zur Verwendung in Branch&Cut-Verfahren (2009)
Completed Bachelor's Theses (TopMath)
- Wolfgang Ferdinand Riedl - Optimale Einsatz- und Routenplanung in der ambulanten Krankenpflege (2011)
- Paul Stursberg - Tourenplanung in der Holzwirtschaft mit flexiblen Ladungsträgern (2011)
Completed Projects / Interdisciplinary Projects
- Daniela Steidl - Weiterentwicklung einer Webanwendung zur automatisierten Planung von Stadtbesichtigungen (2011)
- Christian Böhm, Benjamin Broll - Algorithmen zur Lösung verallgemeinerter TSP Probleme zur Nutzung in elektronischen Besucherführern (2008)
Completed Case Studies Projects
- Tillmann Gaida, Gabriel Guckenbiehl, Andreas Hussig, Katharina Juranek, Marco Ricci - The Sightseeing Problem (2012)
- Karolina Echter, Stefan Franz, Bendix Koopmann, Jakob Lindorff Larsen - Routing with Constraints (2012)
- Christian Donner, Elisabeth Finhold, Valentin Göbel, Ludwig Jäntschi, Andrei Morozyuk - Dynamic Heuristic Approach for Timber Transportation with Containers (2012)
- Nicole Bengesser, Gerhard Huber, Lukas Krauter, Johannes Nagler, Paul Stursberg - Optimizing Container Usage in the Logging Industry (2011)
- Jan Müller, Patricia Rachinger, Wolfgang Ferdinand Riedl, Tina Schmidt, Katharina Zahnweh - Scheduling and Routing in Home Health Care (2011)
- Martin Huber, Beate Müller, Katia Nedelec, Stephanie Nikola, Thomas Schmelz, Daniela Steidl - The Sightseeing Problem A smart way to plan your vacation! (2011)