Einführung in die Welt der Tourenoptimierung – Visualisierung und Lösungsverfahren in einem Python Jupyter Notebook (2/3)

Keine Kommentare

In diesem Artikel möchte ich euch zeigen, wie ihr Probleme der Tourenoptimierung in einem Python Jupyter Notebook lösen und visualisieren könnt. Am Beispiel eines Fahrradkurierdienst zeige ich außerdem, wie das Grundproblem um gängige Nebenbedingungen erweitert werden kann. Dieser Artikel ist der zweite meiner Tourenoptimierungs-Blogreihe und baut auf dem ersten Blogbeitrag auf, in dem wir die theoretischen Grundlagen besprochen haben. Mit ein paar Grundkenntnissen solltet ihr aber folgen können, auch ohne diesen Artikel gelesen zu haben.

Anforderungsanalyse für die Tourenoptimierung

Relevant für die Praxis ist in den meisten Fällen nicht die Basisvariante des Traveling Salesman Problem, sondern Abwandlungen von dieser. So gibt es eine ganze Reihe von Beschränkungen und Nebenbedingungen die zusätzlich berücksichtigt werden müssen. Bei vielen Transportproblemen stehen mehrere Fahrer oder Fahrzeuge zur Auswahl und es ist nicht von vornherein festgelegt, wer welchen Zielpunkt anfahren soll. Zusätzlich gibt es häufig Kapazitätsbeschränkungen. Ein Transporteur kann nur eine bestimmte Anzahl von Transportgütern transportieren. Typisch ist außerdem die Priorisierung bestimmter Kunden und die Einhaltung von Lieferzeitfenstern. Weiterhin müssen Unternehmen sicherstellen, dass sie innerhalb kürzester Zeit auf wechselnde Bedingungen reagieren können, z. B. neue kurzfristige Aufträge oder dynamische Verkehrsbedingungen. Je nach Anwender kann auch die Berücksichtigung von wechselnden Wetterbedingungen oder unterschiedlichen Ausliefergeschwindigkeiten von verschiedenen Fahrzeugen oder Fahrern wichtig sein. Diese Liste kann noch beliebig erweitert werden. Die meisten der zuvor aufgezählten Punkte sind zugleich super praxisrelevant und gut erforscht. Daher gibt es viele Bibliotheken, in denen diese Fälle bereits implementiert wurden. Zur reinen mathematischen Optimierung bieten sich verschiedene Open-Source-Lösungen an. Eine dieser Bibliotheken sind die Google-OR-Tools. Im nächsten Abschnitt zeige ich euch, wie ihr mit Hilfe dieser Bibliothek einen einfachen Demo Case (Hier gehts zum Repository) implementieren könnt und wie dieser in einem Jupyter Notebook mit Hilfe der Folium-Bibliothek visualisieren könnt. 

Zu Beginn der Implementierung erläutere ich, wie der Demo Use Case aussieht. Dabei beginne ich mit einem Grundproblem, löse dieses und erweitere diese einfache Basisanwendung dann im nächsten Schritt um realistischere Anforderungen und Nebenbedingungen.

Grundproblem: Ein Fahrer

Für den Demo Case gehe ich von einem Fahrradkurier aus, der seine Kunden ausgehend von einem Zentrallager beliefern soll. Die Zuteilung der Zielpunkte auf die verschiedenen Fahrer ist bereits erfolgt und Kapazitätseinschränkungen und Lieferzeitfenster müssen zunächst nicht berücksichtigt werden. Der Fokus liegt ausschließlich darauf, 10 Zielpunkte in einer möglichst kurzen Route effizient miteinander zu verbinden und das Ergebnis zu visualisieren. Dafür habe ich 10 zufällige Adressen in Münster gewählt. Das grüne Icon symbolisiert dabei den Start- und Endpunkt. Die 10 blauen Icons symbolisieren die Zielpunkte.

Zur Umsetzung müssen ein paar Bibliotheken importiert und installiert werden. Neben den bekannten Bibliotheken Pandas und NumPy zum Data Handling, benötigen wir Folium zum Erstellen von Karten (ähnlich der oben abgebildeten), Geopy zum Bestimmen der Geokoordinaten unserer Zieladressen, Ortools zur Tourenoptimierung und Pyroutelib3 zur Routenoptimierung.

import pandas as pd
import numpy as np
import folium
 
from geopy import Nominatim
from geopy.distance import great_circle as GC
 
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
from pyroutelib3 import Router

Als nächstes erstelle ich eine Liste von zufällig ausgewählten Adressen in Münster.

# Define list of target points addresses:
addresses = [
    'Sternstraße 12 Münster',
    'Bohlweg 17 Münster',
    'Scharnhorststraße 85 Münster',
    'Geiststraße 46 Münster',
    'Kanalstraße 14 Münster',
 
    'Junkerstraße 2 Münster',
    'Alter Fischmarkt 11 Münster',
    'Scharnhorststraße 2 Münster',
    'Königsstraße 3 Münster',
    'Fürstenbergstraße 30 Münster',
]

Um die Geokoordinaten der Adressen abzurufen, nutze ich die geopy-Library. Nominatim ist ein Geocoding-Tool, das basierend auf OpenStreetMaps-Daten die Geokoordinaten von Adressen ermittelt. Dazu iteriere ich über jede Adresse in der Liste und erstellen eine neue Liste, die zu jedem Zielpunkt die Adresse und die Geokoordinaten beinhaltet.

# Get coordinates and create list of target points including address and coordinates retrieved from Open Street Map Server:
geolocator = Nominatim(user_agent="TSP_Muenster")
 
addresses_geo_data = []
for address in addresses:
 
    loc = geolocator.geocode(address)
 
    # Handle cases in which address couldn't be retrieved:
    if loc is None:
        print(f"Address couldn't be located: {address}")
        break
 
    addresses_geo_data.append({
        'address': address,
        'coords': (loc.latitude,loc.longitude)
    })

Außerdem erstelle ich noch ein Ausgangslager, das am Münsteraner Hafen liegen soll.

# Create Warehouse:
warehouse_address = 'Am Mittelhafen 14 Münster'
loc = geolocator.geocode(warehouse_address)
 
warehouse = {
    'address': warehouse_address,
    'coords': (loc.latitude,loc.longitude)
}

Im nächsten Schritt können wir die bereits zu Beginn gezeigte Karte visualisieren. Dazu verwende ich die Bibliothek Folium, die als Python Wrapper um die beliebte Leaflet Javascript Library zum Erstellen interaktiver Karten verwendet wird.
Im ersten Schritt erstelle ich zunächst eine Karte zentriert auf die Koordinaten des Zentrallagers. Das Zoom-Level stelle ich so hoch, dass es einen schönen Überblick über Münster liefert. Als nächstes erstelle ich ein Icon für das Zentrallager. Neben den Koordinaten, dem Inhalt beim Hovern (Tooltip) und dem Inhalt des Popup-Fensters, lässt sich auch die Farbe für das Icon anpassen. Neben einigen built-in Icons können auch Font-Awesome v4 Icons verwendet werden. Ein solches nutze ich für das Zentrallager. Abschließend iteriere ich über die Zielpunkte, erstelle auch hier jeweils ein Icon und gebe dann die resultierende Karte aus.

# Create map object:
map_osm = folium.Map(location=warehouse['coords'], zoom_start=14, tiles='Open Street Map')
 
# Create icon for warehouse:
folium.Marker(
    location=warehouse['coords'],
    icon=folium.Icon(color='green', icon='industry', prefix='fa'),
    popup=warehouse['address'],
    tooltip=warehouse["address"],
    draggable=False).add_to(map_osm)
 
# Create icons for each address:
for address in addresses_geo_data:
    folium.Marker(
        location=address['coords'],
        icon=folium.Icon(color='darkblue', icon='home'),
        popup=address['address'],
        tooltip=address["address"],
        draggable=False).add_to(map_osm)
 
map_osm

Im nächsten Schritt stelle ich die Distanzmatrix zwischen den Zielpunkten und dem Ausgangspunkt auf. Dazu werden zwei Hilfsfunktionen benötigt. Die erste dient dem Zweck, die Distanz zwischen zwei Punkten zu berechnen. Der Einfachheit halber verzichte ich für den Moment darauf, die genaue Fahrdistanz zu verwenden, sondern nutze die Luftlinie zwischen zwei Punkten als Proxy für die tatsächliche Entfernung. Zum Erstellen der Distanzmatrix verwende ich eine Funktion, die als flexibles Rückgabeformat entweder ein Pandas DataFrame oder ein NumPy Array zurückgibt. Während auf das NumPy Array mit Hilfe der Zielpunkt-Indizes einfach zugegriffen werden kann, kann mit dem Pandas DataFrame eine übersichtliche Tabelle erstellt werden, um vor allem beim Entwickeln schnell überprüfen zu können, ob alles wie erwartet funktioniert.

def get_distance(point1: tuple, point2: tuple) -> float:
 
    # Air distance in meters:
    dist = GC(point1, point2).km * 1000
 
    return round(dist,2)
 
 
def create_distance_matrix(coords: list, address_name:list, format='DataFrame', verbose=False):
    # Create empty np-array:
    dist_array = np.empty((len(coords),len(coords)))
 
    # Compute distances:
    for i in range(0,len(coords)):
        for j in range(i,len(coords)):
            if i < j:
                dist = get_distance(coords[i],coords[j])
 
                if verbose:
                    print(f"Distance between: {address_name[i]} and {address_name[j]}: {dist} km")
 
                # Assuming symmetric TSP:
                dist_array[i][j] = dist
                dist_array[j][i] = dist
 
            elif i == j:
                dist_array[i][i] = 0
 
            else:
                continue
 
    if format == 'NumpyArray':
        return dist_array
 
    else:
        # Create pandas distance matrix:
        return pd.DataFrame(data=dist_array, index=address_name, columns=address_name)


Nun verbinde ich die Liste aus Zieladressen und Ausgangspunkt und nutze die zuvor erstellten Funktionen, um die Distanzmatrix zu erstellen.

# Create list of addresses including warehouse and target points to be used when creating the distance matrix dataframe as column names and index names:
address_list = [warehouse['address']] + [obj['address'] for obj in addresses_geo_data]
coords_list = [warehouse['coords']] + [obj['coords'] for obj in addresses_geo_data]
 
# Call function twice for returning a numpyArray and a DataFrame:
dist_matrix_np = create_distance_matrix(address_name=address_list, coords=coords_list, verbose=False, format='NumpyArray')
dist_matrix_df = create_distance_matrix(address_name=address_list, coords=coords_list, verbose=False, format='DataFrame')


Optimierung mit Google OR-Tools

Jetzt kommt der interessante Teil: Das Finden einer effizienten Tour. Natürlich können ich dafür eine der Funktionen verwenden, die ich im ersten Blogartikel eingeführt hatte. Ich möchte diese Demo aber für einen kleinen Einblick in die Google OR-Tools Library für Tourenoptimierung nutzen. Mit dieser mächtigen Bibliothek können auch die gängigsten Beschränkungen und Nebenbedingungen ohne großen Implementierungsaufwand abgebildet werden.
Zunächst erstelle ich einen IndexManager und ein RoutingModel-Objekt. Der IndexManager dient dazu, die internen Indizes des Solvers in die Indizes der Distanzmatrix zu konvertieren. Dazu übergebe ich die Anzahl der Knoten, also alle 11 Punkte, die Anzahl der Fahrzeuge und den Index unseres Ausgangspunkts. Das RoutingModel-Objekt ist das zentrale Objekt, um das sich ab jetzt so ziemlich alles dreht. Sobald alles konfiguriert ist, kann mit Hilfe der Solve-Methode eine Lösung berechnet werden.

# The index manager handles the conversion of the solver's internal indices to the location indices of our distance matrix:
index_manager = pywrapcp.RoutingIndexManager(len(dist_matrix_np), 1, 0) ## 11 nodes, 1 vehicle, 0 warehouse_index
 
# The routing model is the central object that we can configure to solve our problem:
routing_model = pywrapcp.RoutingModel(index_manager)


Vorher muss ich aber noch weitere Konfigurationen treffen. Als nächstes wird eine Callback-Funktion benötigt, welche die Distanz zwischen zwei Punkten zurückgibt. Hier werden die Distanzmatrix und das RoutingModel miteinander verknüpft.
Weiterhin müssen noch die Kosten für das Wählen einer Verknüpfung zwischen zwei Punkten festlegen. Moment mal, habe ich das nicht gerade gemacht? Nicht ganz. In diesem Fall will ich als Kosten die Distanz zwischen zwei Punkten verwenden. Theoretisch könnte man aber hier auch noch weitere oder alternative Faktoren einfließen lassen. Beispielsweise könnten wir statt der Distanz die Fahrzeit und somit auch mögliche Geschwindigkeitsunterschiede bei verschiedenen Fahrern oder Fahrzeugen berücksichtigen.
Als nächstes muss ich eine Optimierungsmethode wählen. Ich wähle dafür die Default-Strategie. Um eine initiale Lösung zu erhalten (First Solution Strategy), setze ich auf den Greedy-Ansatz, ähnlich wie im ersten Teil der Artikelreihe beschrieben.
Abschließend ermittelt die Methode SolveWithParameters die Lösung.

# Function that returns the distance between two points. In this case the easiest solution is to use the distance matrix:
def distance_callback(from_index, to_index):
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = index_manager.IndexToNode(from_index)
    to_node = index_manager.IndexToNode(to_index)
    return dist_matrix_np[from_node][to_node]
 
# Create Callback that is needed to connect our routing model object with the distance matrix:
transit_callback_index = routing_model.RegisterTransitCallback(distance_callback)
 
# The Arc Cost Evaluator tells the model how to compute the costs of choosing one arc and thus driving from one point A to another point B:
routing_model.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
 
# Set the search strategy to the default strategy:
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
 
# Use the 'greedy approach' to create an initial solution that is then improved:
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)


Zur Ausgabe des berechneten Tourenplans benötige ich eine weitere Hilfsfunktion. Hier iteriere ich über die zuvor berechnete Lösung und erstelle eine Liste, die die geplante Reihenfolge enthält. Da ich die Funktion später auch für Touren mit mehreren Fahrzeugen nutze, berücksichtige ich das gleich mit und erstelle für jedes Fahrzeug eine weitere eigene Liste, die die geplante Tour enthält.

def get_tours(solution, routing, manager):
    # Get vehicle routes and store them in a two dimensional array whose
    # i,j entry is the jth location visited by vehicle i along its route.
    all_tours = []
    for vehicle in range(routing.vehicles()):
        index = routing.Start(vehicle)
        curr_tour = [manager.IndexToNode(index)]
        while not routing.IsEnd(index):
            index = solution.Value(routing.NextVar(index))
            curr_tour.append(manager.IndexToNode(index))
        all_tours.append(curr_tour)
    return all_tours
 
tour_plan = get_tours(solution, routing_model, index_manager)


Jetzt fehlt noch die Visualisierung. Dazu erweitere ich den bestehenden Code um eine Schleife, die die einzelnen Zielpunkte der Tour miteinander verbindet. Auch hier abstrahiere ich von den tatsächlichen Routen zwischen zwei Zielpunkten und zeichne stattdessen eine gerade Linie zwischen zwei Punkten.

## Create map object:
map_osm = folium.Map(location=warehouse['coords'], zoom_start=14, tiles='Open Street Map')
 
## Create icon for warehouse:
folium.Marker(
    location=warehouse['coords'],
    icon=folium.Icon(color='green', icon='industry', prefix='fa'),
    popup=warehouse['address'],
    tooltip=warehouse["address"],
    draggable=False).add_to(map_osm)
 
## Create icons for each address:
for address in addresses_geo_data:
    folium.Marker(
        location=address['coords'],
        icon=folium.Icon(color='darkblue', icon='home'),
        popup=address['address'],
        tooltip=address["address"],
        draggable=False).add_to(map_osm)
 
## Create connections between target points:
# Iterate over tour plan:
for tour in tour_plan:
    # Iterate from first to penultimate element:
    for i in range(0,len(tour) - 1):
        coords_point_a = coords_list[tour[i]]
        coords_point_b = coords_list[tour[i+1]]
 
        folium.PolyLine([coords_point_a, coords_point_b],
                        color="black",
                        weight=3).add_to(map_osm)
 
map_osm


Das sieht doch schon ganz schick aus, oder?

Im nächsten Artikel der Reihe erweitere ich den Demo Case um die exakte Routen zwischen zwei Zielpunkten, statt weiter die Luftlinien als Annäherung für die tatsächliche Entfernung zu nutzen. Außerdem zeige ich, wie wir das Grundproblem um realistische Anforderungen wie mehrere Fahrzeuge und Kapazitätsbeschränkungen erweitern können.

Als Data Scientist und Machine Learning Engineer analysiert Lukas große Datenmengen und entwickelt Modelle zur Mustererkennung, um die Vergangenheit besser zu verstehen oder Vorhersagen für die Zukunft zu generieren. Besonders interessieren ihn Optimierungsprobleme und die Interpretierbarkeit von Machine-Learning-Modellen.

Über 1.000 Abonnenten sind up to date!

Die neuesten Tipps, Tricks, Tools und Technologien.
Jede Woche direkt in deine Inbox.

Kostenfrei anmelden und immer auf dem neuesten Stand bleiben!
(Keine Sorge, du kannst dich jederzeit abmelden.)

Kommentieren

Deine E-Mail-Adresse wird nicht veröffentlicht.