Einführung in die Welt der Tourenoptimierung – Echte Routen und realistischere Nebenbedingungen (3/3)

In diesem Artikel möchte ich euch mit einem Python Jupyter Notebook  zeigen, wie ihr Anwendungsfälle der Tourenoptimierung inklusive Nebenbedingungen lösen und visualisieren könnt. Außerdem zeige ich euch, wie ihr mit OpenStreetMaps die Route zwischen zwei Punkten für verschiedene Transportmodi berechnen lassen könnt. Dieser Artikel gehört zu meiner dreiteiligen Tourenoptimierungs-Blogreihe und baut auf dem zweiten Blogbeitrag  auf, in dem ich gezeigt habe, wie wir ein einfaches Traveling Salesman Problem (TSP) praktisch lösen und visualisieren können. Schaut euch den Artikel am besten vorher an, da ich stark auf dem vorherigen aufbauen werde.

Von der Luftlinie zu echten Routen

Ihr wollt also gerne sehen wie man die Routen zwischen zwei Zielpunkten berechnet, damit die bisherige Planung nicht nur für fliegende Fahrräder funktioniert?

Auch hierfür setze ich, wie bereits im ersten Teil der Umsetzung, auf OpenStreetMaps. Die pyroutelib3 Library bietet eine ganze Reihe verschiedener Transportmodi: Auto, Fahrrad, Bahn und sogar Pferd. Ich nehme passend zum Anwendungsfall und, um dem Ruf der Stadt Münster gerecht zu werden, das Rad. Zum Speichern der Routen verwende ich eine verschachtelte Liste.

Auf der ersten Ebene liegt die einzelne Tour bzw. das einzelne Fahrzeug, da ich aktuell in dem Grundproblem nur jeweils ein Fahrzeug betrachte. Auf der zweiten Ebene liegt dann die Route von einem Zielpunkt zum nächsten (z. B. vom Ausgangslager zum ersten Kunden) und auf der dritten Ebene findet sich eine Liste aus Tupeln mit den einzelnen Geokloordinaten für jeden Pfad. Mit der findNode-Methode suchen wir für den aktuell betrachteten Punkt der nächsten Knoten. Anschließend ermitteln wir mit der doRoute-Methode die kürzeste Route zwischen Start- und Endknoten.

1# Initialize router:
2router = Router("bike")
3 
4# Stores the routes of all tours:
5tour_plan_all_routes = []
6 
7# Iterate over tours:
8for tour in tour_plan:
9 
10    # Stores the routes of the current tour:
11    curr_tour_route = []
12 
13    # Pairwise iterate to obtain paths between two given points:
14    for idx in range(0, len(tour) - 1):
15 
16        curr_start_point = coords_list[tour[idx]]
17        curr_end_point = coords_list[tour[idx+1]]
18 
19        # Find Start and End Nodes near desired location:
20        start = router.findNode(*curr_start_point)
21        end = router.findNode(*curr_end_point)
22 
23        # Get route:
24        status, route = router.doRoute(start, end)
25 
26        # Get coordinates of route:
27        if status == 'success':
28            routeLatLons = list(map(router.nodeLatLon, route))
29            curr_tour_route.append(routeLatLons)
30 
31    tour_plan_all_routes.append(curr_tour_route)

Um das besser zu verdeutlichen, visualisiere ich das Ergebnis im nächsten Schritt. Dazu iteriere ich über die verschachtelte Liste und zeichne für jede Verbindung von einem Knoten zum Folgeknoten eine gerade Linie. Das erreiche ich durch eine kleine Anpassung beim Erstellen der Karte.

1## Create connections between target points:
2# Iterate over tour plan:
3for tour in tour_plan:
4    # Iterate from first to penultimate element:
5    for i in range(0,len(tour) - 1):
6        coords_point_a = coords_list[tour[i]]
7        coords_point_b = coords_list[tour[i+1]]
8 
9        folium.PolyLine([coords_point_a, coords_point_b],
10                        color="black",
11                        weight=3).add_to(map_osm)
12 
13map_osm

Das Ergebnis sieht dann wie folgt aus:

Wer sich in Münster gut auskennt, erkennt schnell, dass ein Teil der Route auf der Münsteraner Promenade liegt, auf der lediglich Radfahrer zugelassen sind. Das Ergebnis kann sich also sehen lassen.

Erweiterung – Mehrere Fahrer und begrenzte Kapazitäten

Als nächstes möchte ich euch noch zeigen, wie durch ein paar kleine Anpassungen der Ansatz um gängige Nebenbedingungen wie mehrere Fahrzeuge oder Kapazitätsbeschränkungen erweitern werden kann. Kapazitätsbeschränkungen können dabei z. B. ein maximales Volumen oder Gewicht pro Fahrzeug darstellen. Im Folgenden erweitere ich den Demo Case um die Annahme, dass es drei Fahrer gibt, wobei eines der Fahrräder ein Lastenrad mit größerem Volumen ist. Außerdem ergänze ich das Volumen der Produkte, die unsere verschiedenen Kunden erwarten. Darüber hinaus muss ich beim IndexManager berücksichtigen, dass mehrere Transportmittel zur Verfügung stehen. Der darauf folgende Teil bleibt gleich und muss nicht geändert werden. Zusätzlich müssen wir jetzt aber noch ein Demand Callback hinzufügen, um die Kapazitätsbeschränkungen einzubauen. Dieses Callback gibt zu jedem Zielpunkt das zugehörige Nachfragevolumen zurück. Anschließend muss das Demand Callback lediglich noch mit unserem RoutingModel verknüpft werden. Auch dies funktioniert, ähnlich wie beim Demand Callback, mit der RegisterUnaryTransitCallback Methode. Auch hier gibt es eine ganze Reihe an Einstellungsmöglichkeiten. So können beispielsweise Warte-, bzw. Servicezeiten berücksichtigen, was bei anderen Dimensionen sinnvoll sein kann, wir hier aber nicht wollen.

1## New:
2# Extend to multiple vehicles:
3num_vehicles = 3
4 
5# Capacity constraints:
6demands=[0,20,40,50,30,40,40,60,40,20,20]
7vehicle_capacities=[200, 100, 100]
8 
9# The index manager handles the conversion of the solver's internal indices to the location indices of our distance matrix:
10index_manager = pywrapcp.RoutingIndexManager(len(dist_matrix_np), num_vehicles, 0) ## 11 nodes, 1 vehicle, 0 warehouse_index
11 
12 
13## Old:
14# The routing model is the central object that we can configure to solve our problem:
15routing_model = pywrapcp.RoutingModel(index_manager)
16 
17# Create Callback that is needed to connect our routing model object with the distance matrix:
18transit_callback_index = routing_model.RegisterTransitCallback(distance_callback)
19 
20# 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:
21routing_model.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
22 
23# Set the search strategy to the default strategy:
24search_parameters = pywrapcp.DefaultRoutingSearchParameters()
25 
26# Use the 'greedy approach' to create an initial solution that is then improved:
27search_parameters.first_solution_strategy = (
28    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
29 
30 
31## New:
32# Add Capacity constraint.
33def demand_callback(from_index):
34    """Returns the demand of a node."""
35    # Convert from routing variable Index to demands NodeIndex.
36    from_node = index_manager.IndexToNode(from_index)
37    return demands[from_node]
38 
39demand_callback_index = routing_model.RegisterUnaryTransitCallback(demand_callback)
40 
41routing_model.AddDimensionWithVehicleCapacity(
42    demand_callback_index,  # evaluator_index
43    0,  # slack_max
44    vehicle_capacities,  # vehicle maximum capacities
45    True,  # start cumulative to zero
46    'Capacity' # name
47)

Abschließend wird die Lösung berechnet. Für die anschließende Visualisierung möchte ich die verschiedenen Touren farblich unterscheidbar darstellen. Dafür lasse ich mir eine Liste der verfügbaren Farben ausgeben. Diese Liste nutze ich dann beim Erstellen der Marker für die unterschiedlichen Touren. Aus Gründen der Übersichtlichkeit nutze ich anstatt der tatsächlichen Routen erneut gerade Linien zur Darstellung.

1## Create map object:
2map_osm = folium.Map(location=warehouse['coords'], zoom_start=14, tiles='Open Street Map')
3 
4## Create icon for warehouse:
5folium.Marker(
6    location=warehouse['coords'],
7    icon=folium.Icon(color='green', icon='industry', prefix='fa'),
8    popup=warehouse['address'],
9    tooltip=warehouse["address"],
10    draggable=False).add_to(map_osm)
11 
12## Create icons for each address:
13# Get list of available colors:
14color_lst = list(folium.map.Icon.color_options)
15color_lst = ['darkblue', 'darkred', 'darkpurple']
16 
17# Iterate over tours:
18for tour_num, tour in enumerate(extended_tour_plan):
19    # Iterate over single tour:
20    for address_idx in tour:
21        # Skip warehouse address:
22        if address_idx == 0:
23            continue
24 
25        # Create marker:
26        folium.Marker(
27            location=coords_list[address_idx],
28            icon=folium.Icon(color=color_lst[tour_num], icon='home'),
29            popup=address_list[address_idx],
30            tooltip=address_list[address_idx],
31            draggable=False).add_to(map_osm)
32 
33## Create connections between target points:
34# Iterate over tour plan:
35for tour_num, tour in enumerate(extended_tour_plan):
36    # Iterate from first to penultimate element:
37    for i in range(0,len(tour) - 1):
38        coords_point_a = coords_list[tour[i]]
39        coords_point_b = coords_list[tour[i+1]]
40 
41        folium.PolyLine([coords_point_a, coords_point_b],
42                        color="black",
43                        weight=3).add_to(map_osm)
44 
45map_osm

Auf diese Art und Weise können mit vergleichsweise geringem Aufwand bereits etwas realistischere Tourenptimierungsprobleme gelöst werden.

Fazit

In der Praxis gibt es weit mehr Nebenbedingungen, die beachtet werden müssen, wie z.B. Lieferzeitfenster, Priorisierung von Zielpunkten, verschiedene Fahrzeugtypen, die unterschiedlich gut für bestimmte Produkte geeignet sind, und so weiter. Erfahrenen Anwendern fallen hier wahrscheinlich sofort eine ganze Liste an weiteren Anforderungen ein, die eine Tourenplanungslösung für ihren Anwendungsfall abdecken sollte. Zum Abschluss möchte ich noch einmal auf den zu Beginn der Blogreihe beschriebenen Praxisfall zurückkommen:

Ein Logistikanbieter, der auf das Fahrrad als Transportmittel setzt, hatte beim Einsatz von Tourenplanungs-SaaS-Produkten Probleme, da Standardlösungen häufig Schwierigkeitenmit der Transportvariante Rad haben. 

Insbesondere die Zeitplanung, also einzuschätzen zu welchem Zeitpunkt sich welcher Fahrer wo befindet, kann Probleme bereiten. Das ist unter anderem auf die unterschiedlichen Fahrgeschwindigkeiten bei den Fahrern zurückzuführen. Selbstverständlich gibt es diese je nach Verkehrsaufkommen auch im Autoverkehr. Aber gerade bei längeren Fahrwegen gibt es bei Fahrradkurieren, im Gegensatz zu motorisierten Lieferdiensten, eine deutlich größere Varianz bei der Ausliefergeschwindigkeit, welche u. a. auf den Fahrradtyp aber auch auf die Erfahrung und Sportlichkeit des Fahrers zurückzuführen ist. All diese beeinflussenden Faktoren sind in der Regel bekannt, können jedoch häufig in Standard-One-Size-fits-All-Lösungen nicht berücksichtigt werden. Dieses Problem ist daher ein gutes Beispiel, warum insgesamt der Trend wieder vermehrt zu Individuallösungen geht. Individuallösung muss dabei übrigens nicht heißen, dass eine Anwendung von Null auf neu gebaut wird. Ein Baukastenprinzip ermöglicht es, verschiedene Grundmodule, die sehr gängige Komponenten beinhalten, miteinander zu verbinden, um sich dann auf die spezielleren Anforderungen zu konzentrieren. Wenn ihr eigene Erfahrungen oder Fragen und Anmerkungen habt, dann freue ich mich auf eine Diskussion in den Kommentaren.