Routing under Choice of Conveyance

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

A tourist visits a city and wants to see a selection of touristic sights. However, he only has a certain time available and his monetary resources are also limited. Of course, traveling in the city will incur a cost and a travel time, both depending on the means of transportation that is used (and that might be different for every edge traversed) walking will be cheap, but time-consuming, whereas using a taxicab will be quick, but expensive, with bus or metro connections ranging somewhere in between these two alternatives. The question faced by the tourist is now this: Find a tour visiting all sights, including a choice of conveyance for every edge traversed, that respects the limits for time and budget available (we will refer to this problem as the Sightseeing Circuit Problem for its resemblance to the Hamiltonian Circuit Problem).

Of course, for cities with a lot of things to see and very limited time/budget, there might not be a feasible tour, which leads to straightforward generalizations (much like the TSP and its generalization the Orienteering Problem):

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).

In this setting, we may also consider costs for visiting a node (think of museums' entrance fees).

These problem statements clearly include both classical TSP and Orienteering Problem as special cases and represent a somewhat natural extension of these problems to multiple valued (one value per resource) multigraphs (one edge per possible choice of conveyance). In contrast to the classical versions there is no natural notion of a triangle inequality in these graphs and the usual metric techniques (like computing a metric completion of an incomplete graph by using shortest paths or enhancing a heuristic solution by taking shortcuts) will not work anymore: While a tour might be shorter than some other with regards to one resource (e.g. time), it could be longer with regards to a different resource (e.g. monetary costs). Of course, similar extensions are possible for a multitude of routing and graph problems. In addition to the TSP and the Orienteering Problem one might consider Shortest Path, Minimum Spanning Tree or Network Flow Problems with respect to choice of conveyance.

The following Applet gives an impression of what we plan to do.

Urban Health-Care

A cooperation with the Institute of Production and Logistics at the University of Natural Resources and Life Sciences, Vienna (BOKU)

For this project an optimal schedule of nurses to visit immobile patients at their homes under several additional constraints has to be computed. In a rural setting, where every nurse has to do the visits with her own car, the core of the problem is a typical vehicle routing problem with time windows, the nurses being the vehicles to be routed to visit all customers - the patients. In major cities cars may be obstructive and it is usually much cheaper and faster to use urban transport. But this means we are back in the situation as described above: the nurses are now just travelers, with a free choice of conveyance to use. And even assuming that they own a season ticket for public transport, because of time limits and time windows it may be reasonable to spend extra money for a chauffeur or a taxi.

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)

In forest industry, two different kinds of wood transport occur: from the forest (shown on the left) to the sawmill at the centre of the picture, and from the sawmills the customers on the right. Traditionally, different types of transportation trucks are being used for the two parts. The mathematical core in this setting is a relatively easy assignment problem (with time windows), the drawback however is, that the ratio of empty trips is close to 50 %.

The target in this project is to analyze the potential savings offered by the usage of foldable containers, such that four empty containers may be transported by a single truck. This allows for more efficient routing and for further time savings, as containers an vehicles can be handled (e.g. loaded and unloaded) separately. As an example, it now makes sense that a single truck delivers empty containers to some point demanding them, the containers are filled and shipped with another truck. In this setting the trucks are just a mode of conveyance to be chosen by the travelers - the containers.

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)

Research Unit M9

Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics