Optimale Standort- und Routenplanung für die Zeitungs-Distributionslogistik mit graphentheoretischen Modellen

Die tägliche Überbrückung von Transportstrecken, sowie die Realisierung von Lagerstandorten stellen einen erheblichen Kostenfaktor für Organisationen dar, weshalb der Planung und Optimierung dieser langfristigen und komplexen Entscheidungen eine hohe Bedeutung zukommt. In der Graphentheorie finden sich hierfür zahlreiche Modelle und Algorithmen mit vielfältigen Zielsetzungen. Die vorliegende Arbeit zielt darauf ab, wesentliche Verfahren der Graphentheorie auf den praktischen Fall der Zeitungslogistik anzuwenden. Das Problem lässt sich als ein k-Chinese-Postman-Problem mit mehreren Depotstandorten darstellen. Charakteristisch für diese Problemstellung ist die Ermittlung von k kostenminimalen Touren ausgehend von jedem Depot, welche als Summe jede Kante des Graphen mindestens einmal enthält. Nach einer ausführlichen Beschreibung der logistischen Ausgangslage, sowie einer Aufarbeitung des aktuellen Wissensstandes, werden die zwei gegensätzlichen Vorgehensweisen des „Route-First-Cluster-Second“ Ansatzes, sowie des „Cluster-First-Route-Second“ Ansatzes vorgestellt und deren Ergebnisse interpretiert und verglichen. Das Modell wurde mit Hilfe von OSMnx und PuLP in der Programmiersprache Python umgesetzt. Für drei reale Testgebiete in Graz wurde als bestes Modell der „Route-First-Cluster-Second“ Ansatz ermittelt.The daily covering of high distances regarding routes of transportation as well as the identification of warehouse locations are significant cost factors for organizations. Therefore, planning and optimizing those long-term and complex decisions is of high importance. The domain of graph theory offers numerous models and algorithms including multiple objectives for dealing with these issues. This thesis aims at testing and analyzing the applicability of essential methods to the practical case of newspaper logistics. This problem can be represented as the k-Chinese-Postman Problem with multiple warehouses. The determination of k tours of minimal costs starting and ending from each warehouse respectively, covering in sum every edge at least once, is distinctive of this problem. After clarifying the initial position and elaborating on the problem statement, the thesis reviews the current state of research and introduces the opposing approaches of “Route-First-Cluster-Second” and “Cluster-FirstRoute-Second”. The model has been implemented with OSMnx and PuLP using Python. As a result, “Route-First-Cluster-Second” turned out to be the superior approach for the investigated use-case consisting of three test areas in Graz.Julia HoferZusammenfassungen in Deutsch und EnglischAbweichender Titel laut Übersetzung des Verfassers/der VerfasserinKarl-Franzens-Universität Graz, Masterarbeit, 2019(VLID)380657