Schnelle Wegsucheverfahren auf digitalen Straßenkarten – Entwicklung, Implementierung und Anwendungsbeispiel bei einem Logistikdienstleister

The solution to many real-world transportation planning problems is combinatorially comprehensive, complex, and some of the necessary information is not available in a sufficiently structured form. Hence, standard solving methods are often not applicable. This holds for courier and express providers' operational dispatching, where vehicles are assigned to customer orders. Typically, dialog-oriented decision support systems (DSS) are used to generate recommendations from which a human dispatcher selects the most profitable one by means of domain-specific knowledge. In this process, solutions that consolidate the freight of multiple customer orders onto a single vehicle are usually particularly favorable. This work examines optimization of the dispatching process with particular attention to the potential of freight consolidation. In order to uncover possible savings by consolidating, many alternative vehicle routes need to be determined and compared with each other. For this purpose, fast routing algorithms are essential. These algorithms form the first focus of this work. Based on a comparative literature overview of classical'' as well as current routing algorithms, the center of attention is put on contraction hierarchies (CH) as they provide a particularly favorable ratio of query speed-up to additional memory requirement. Both optimizations of hierarchy creation and new enhancements for queries in CH are studied. The considerable merits of these approaches are empirically shown through extensive benchmarks on digital road maps provided by the OpenStreetMap project. More realistic routes are obtained when routing algorithms take turn restrictions into account. First, common approaches from literature are presented for this purpose. Next, the adaptive search is introduced as a more efficient new approach, and adjusted for usage in CH. The above-mentioned query enhancements can easily be applied to this method. The advantages of the adaptive search in CH over the edge-based search that is employed for turn restriction aware routing in earlier literature is emphasized by further benchmarks. For the second focus of this work --~the vehicle routing problem with freight consolidation~-- first, a thorough mathematical model is developed. Next, model assumptions are extracted from past operational real-world data provided by IN tIME Express Logistik GmbH. Eventually, the recursive savings algorithm is introduced as a heuristic that can generate freight consolidation recommendations in the context of a DSS. Employed in multiple benchmarks based upon the past operational data, it reveals considerable cost savings compared to former dispatching decisions.