Lösung des Problems des Handlungsreisenden

Nov 29 2022

Optimieren Sie die Routen zur Paketzustellung mit Python, um Lieferkosten zu sparen (Studienfall: Paketzustellung in Bandung, Indonesien mit einfachen Daten) Traveling Salesman Problem oder TSP ist ein kombinatorisches Optimierungsproblem, das versucht, die Frage „Angesichts einer Liste von Städten und der Entfernungen zwischen jedem Städtepaar, was ist die kürzestmögliche Route, die jede Stadt genau einmal besucht und zur Ausgangsstadt zurückkehrt? Auf einfache Weise wird TSP beauftragt, die kürzeste Route zwischen einer Reihe von Punkten zu finden, die besucht werden müssen.

Optimieren Sie die Routen zur Paketzustellung mit Python, um Lieferkosten zu sparen (Studienfall: Paketzustellung in Bandung, Indonesien mit einfachen Daten)

Foto von José Martín Ramírez Carrasco auf Unsplash

Das Problem des Handlungsreisenden oder TSP ist ein kombinatorisches Optimierungsproblem, das versucht, die Frage zu beantworten: „Wenn eine Liste von Städten und die Entfernungen zwischen jedem Städtepaar gegeben sind, was ist die kürzestmögliche Route, die jede Stadt genau einmal besucht und zur Ursprungsstadt zurückkehrt? “. Auf einfache Weise wird TSP beauftragt, die kürzeste Route zwischen einer Reihe von Punkten zu finden, die besucht werden müssen. Es wird zu einem echten Problem in der Lieferketten- und Logistikbranche, da sie nach dem Aufstieg des E-Commerce in die Höhe schnellten.

Also, warum ist TSP wichtig? Im Wesentlichen hilft es dem Unternehmen, mehr Gewinn zu erzielen, indem es Zeit und Ressourcen spart. In der Logistikbranche ist eine der Möglichkeiten, mehr Gewinn zu erzielen, die Effizienz bei Lieferkosten und -zeit. Es gibt verschiedene Möglichkeiten, dies zu erreichen, eine davon ist die Lösung des Problems des Handlungsreisenden (Traveling Salesman Problem, TSP), bei dem Sie versuchen, die effizientesten Routen für unterwegs zu finden. Je effizienter es gelöst wird, desto weniger Zeit wird mit dem Fahren verbracht, desto mehr Kraftstoff wird gespart, desto weniger Stunden werden benötigt und desto mehr Pakete werden zugestellt . Dadurch profitiert die Bilanz jeder lieferbasierten Geschäftstätigkeit gleich doppelt.

Daher versuche ich, für einen Kurier eines Paketzustellers in Bandung eine Demo dieses Traveling Salesman Problems zu erstellen, um die Lieferkosten zu senken .

Hinweis : Da es sich um eine einfache Demo handelt, handelt es sich bei den verwendeten Daten nur um 8 Dummy-Punkte für die Lieferung, und die Daten sind zufällig generierte Daten.

Szenario

Sie sind Manager in einem Paketdienstzentrum in Bandung. Sie sollten Pakete von Ihrem Depot aus mit 1 Fahrzeug an einige Kunden liefern. Die Verteilung der Lieferstellen und des Depots ist unten ersichtlich (Abbildung 1).

Abbildung 1. Räumliche Verteilung der Lieferpunkte

**Jedenfalls können Sie die Anzahl der Fahrzeuge und die Anzahl der Lieferpunkte beliebig anpassen, indem Sie den unten stehenden Quellcode bearbeiten

Ziele

Finden Sie die besten Routen, um alle Pakete an die Kunden zu liefern.

Um zu verfolgen, wie gut das Modell oder die Lösung ist, die wir zu implementieren versuchen, ist es besser, die Geschäftsmetriken zu definieren. Da die Daten verwandter Fälle nicht verfügbar sind, werde ich nur das Potenzial erwähnen, ohne zu messen, wie gut die Lösung ist. Diese potenziellen Geschäftsmetriken sind:

Versandkosten
Zeitaufwand
Pünktliche Lieferrate
Kundenzufriedenheitswert (CSAT-Wert)

Unter Verwendung der Google OR-Tools ist die beste Route mit einem Fahrzeug:

Depot -> Adresse 5 -> Adresse 6 -> Adresse 7 -> Adresse 4 -> Adresse 3 -> Adresse 2 -> Adresse 1 -> Depot

Streckenlänge: 7,44 km

Abbildung 2. Die Animation der kürzesten Route

Technische Schritte

Abbildung 3. Flussdiagramm der Verarbeitung in Python

Den vollständigen Code finden Sie hier .

I. Bibliothek importieren und Daten lesen

Zuvor müssen wir die Bibliotheken in Google Colab importieren. Wir werden einige Bibliotheken verwenden.

numpy und pandas : für numerische Operationen und Datenmanipulation
itertools : zum Erstellen von Iteratoren für effiziente Schleifen
ast : um Bäume der abstrakten Python
Anfragen : um HTTP-Anfragen zu stellen
json : um mit JSON-Daten zu arbeiten
networkx : für die Erstellung, Manipulation und Untersuchung der Struktur, Dynamik und Funktionen komplexer Netzwerke
osmnx : Zum Herunterladen von Geodaten von OpenStreetMap und zum Modellieren, Projizieren, Visualisieren und Analysieren von realen Straßennetzen und anderen Geogeometrien
folium : zum Visualisieren von Daten, die in Python manipuliert wurden, auf einer interaktiven Broschürenkarte
ortools : um kombinatorische Optimierungsprobleme zu lösen

# Install and Import Library
pip install osmnx
pip install ortools

import numpy as np
import pandas as pd
import itertools
import ast
import requests
import json
import networkx as nx
import osmnx as ox
import folium
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

from google.colab import drive
drive.mount('/content/drive')

import warnings 
warnings.filterwarnings('ignore')

# Read data
df_points = pd.read_excel('/content/drive/MyDrive/dataset/delivery_destinations.xlsx')

Abbildung 4. Der Lieferpunkt-Datensatz

II. Geokodierung

Geocodierung ist der Prozess der Umwandlung einer Beschreibung eines Ortes – wie z. B. eines Koordinatenpaars, einer Adresse oder eines Ortsnamens – in einen Ort auf der Erdoberfläche. Kurz gesagt, wir versuchen, den Breiten- und Längengrad aus der Adresse des Datensatzes abzurufen. Diese Breiten- und Längengrade werden später verwendet, um die Reiseentfernung zwischen Punkten zu berechnen und die beste Lieferroute zu bestimmen.

Ich verwende die HERE-API für die Geokodierung, da sie ziemlich genau und kostenlos zu verwenden ist (mit begrenzten Aufrufen). Sie können diesen Artikel für die Details dieses Prozesses lesen .

# Define variables
apikey = '<YOUR-API-KEY-HERE>'
url = 'https://discover.search.hereapi.com/v1/discover'
headers = {'Content-Type': 'application/json'}
origin_point = '-6.8918336,107.6103212'
latlong_origin = []
latlong_points = []

# Get lat long using HERE Map API
for i, data in df_points.iterrows():
  # your place name is defined below
  place_name = data.address
  my_params = {'at' : origin_point,
               'limit' : 1,
               'apikey' : apikey,
               'q' : place_name}
  r = requests.get(url, params=my_params, headers=headers)
  output = json.loads(r.text)
  latlong_dict = output['items'][0]['position']
  latlong = ', '.join(map(str, latlong_dict.values()))
  latlong_points += [latlong]

# Create dataframe
df_points['lat_lng'] = latlong_points
df_points['lat_lng'] = df_points.lat_lng.apply(ast.literal_eval)

Abbildung 5. DataFrame nach der Geokodierung

Beachten Sie, dass wir jetzt ein Feld namens lat_lng haben , das den Breiten- und Längengrad der Punkte enthält.

III. Reisestrecke zwischen Punkten berechnen

Als nächstes wird die Reisedistanz zwischen Punkten berechnet. Es ist beim Problem des Handlungsreisenden wichtig, da die kürzeste Route aus der Gesamtentfernung jeder möglichen Route generiert wird. Anstelle der euklidischen Entfernung (Zeichnen einer Linie zwischen Punkten) verwenden wir eine relevantere Entfernung, die einen Pfad erstellt, der der Straße zwischen Punkten folgt. Dieser Pfad stellt den Abstand zwischen Punkten dar.

Dazu verwenden wir die Methode shortest_path von networkx. Aber vorher sollten wir den Ursprungs-Ziel-DataFrame erstellen, um die Entfernung zwischen Punkten einfacher berechnen zu können. Dieser DataFrame wird generiert, indem alle möglichen Kombinationen/Permutationen von Ursprungs- und Zielpunkten vorgenommen werden.

# Create dataframe of origin-destination #

# Create variables
list_points_name = df_points['point_name']
# list_points_latlong = df_points['lat_long']
list_points_latlong = df_points['lat_lng']

# All points combinations
list_pair_name = [i for i in itertools.product(list_points_name, repeat=2)]
list_pair_latlong = [i for i in itertools.product(list_points_latlong, repeat=2)]
df_nodes = pd.DataFrame({'pair_name': list_pair_name, 'pair_latlong': list_pair_latlong})

# Source/Target
df_nodes['origin'] = df_nodes['pair_name'].apply(lambda t: t[0])
df_nodes['destination'] = df_nodes['pair_name'].apply(lambda t: t[1])
df_nodes['latlong_origin'] = df_nodes['pair_latlong'].apply(lambda t: t[0])
df_nodes['latlong_destination'] = df_nodes['pair_latlong'].apply(lambda t: t[1])
df_nodes.drop(['pair_name', 'pair_latlong'], axis =1, inplace = True)

Abbildung 6. Ursprungs- und Ziel-DataFrame

Jetzt können wir die Entfernung zwischen Punkten mit networkx berechnen.

# Calculate distance from point to point using networkx #

# Location where you want to find your route
place     = 'Bandung, West Java, Indonesia'
# Find shortest route based on the mode of travel
mode      = 'drive'        # 'drive', 'bike', 'walk'
# Find shortest path based on distance or time
optimizer = 'length'        # 'length','time'
# Create graph from OSM within the boundaries of some geocodable place(s)
graph = ox.graph_from_place(place, network_type = mode)

# Create lists
list_route = []
list_route_length = []

# Determining distance and route
for i in range(len(df_nodes)):
  # find the nearest node to the start location
  orig_node = ox.get_nearest_node(graph, df_nodes.iloc[i]['latlong_origin'])
  # find the nearest node to the end location
  dest_node = ox.get_nearest_node(graph, df_nodes.iloc[i]['latlong_destination'])
  #  find the shortest path
  shortest_route = nx.shortest_path(graph,
                                    orig_node,
                                    dest_node,
                                    weight=optimizer)
  shortest_route_length = nx.shortest_path_length(graph, orig_node, dest_node, weight=optimizer)
  # append list
  list_route.append(shortest_route)
  list_route_length.append(shortest_route_length)

Abbildung 7. Abstand zwischen Punkten DataFrame

IV. Bestimmen Sie die beste Fahrzeugroute

Dann können wir mithilfe von Google OR-Tools die beste Route für die Zustellung von Paketen an alle Kunden ermitteln . Zuerst müssen wir die Funktionen definieren, die uns helfen, die kürzeste Route zu finden. Es verweist auf diese Seite mit einigen Modifikationen.

def create_data_model(distance_matrix, num_vehicles, depot_order):
    """Stores the data for the problem."""
    data = {}
    data['distance_matrix'] = distance_matrix
    data['num_vehicles'] = num_vehicles
    data['depot'] = depot_order
    return data

def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    max_route_distance = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += '{}\n'.format(manager.IndexToNode(index))
        plan_output += 'Distance of the route: {}m\n'.format(route_distance)
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print('Maximum of the route distances: {} m'.format(max_route_distance))

def get_routes(solution, routing, manager):
  """Get vehicle routes from a solution and store them in an array."""
  # 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.
  routes = []
  for route_nbr in range(routing.vehicles()):
    index = routing.Start(route_nbr)
    route = [manager.IndexToNode(index)]
    while not routing.IsEnd(index):
      index = solution.Value(routing.NextVar(index))
      route.append(manager.IndexToNode(index))
    routes.append(route)
  return routes

# Instantiate the data problem.
data = create_data_model(distance_matrix=distance_matrix, 
                         num_vehicles=1, 
                         depot_order=0)

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                        data['num_vehicles'], data['depot'])

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback.
transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimension(
    transit_callback_index,
    0,  # no slack
    50000,  # vehicle maximum travel distance
    True,  # start cumul to zero
    dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)

# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)

# Print solution on console.
if solution:
    print_solution(data, manager, routing, solution)
else:
    print('No solution found !')

Depot -> Adresse 5 -> Adresse 6 -> Adresse 7 -> Adresse 4 -> Adresse 3 -> Adresse 2 -> Adresse 1 -> Depot

Diese kürzeste Route dauert etwa 7,44 km.

V. Erstellen Sie einen Pfad für die effektivste Route

Datenvisualisierung ist eine der besten Möglichkeiten, um diesen Fall besser nachvollziehen zu können. Daher werden wir in diesem letzten Schritt eine räumliche Datenvisualisierung erstellen, um die beste Route darzustellen. Wir sollten einen neuen DataFrame erstellen, der nur die beste Route enthält, und dann den Pfad erstellen.

# Create path for the most effective route #

# Create DataFrame of route order
df_nodes_best = pd.DataFrame({'origin' : route_name[:-1], 
                              'destination': route_name[1:]})
df_nodes_best = df_nodes_best.merge(df_nodes, on=['origin', 'destination'], how='inner')
df_nodes_best["route_order"] = [f"Route {i}" for i in range(1, len(df_nodes_best)+1)]
df_nodes_best

# Create lists
list_route_best = []
list_route_length_best = []

# Determining distance and route
for i in range(len(df_nodes_best)):
  # find the nearest node to the start location
  orig_node_best = ox.get_nearest_node(graph, df_nodes_best.iloc[i]['latlong_origin'])
  # find the nearest node to the end location
  dest_node_best = ox.get_nearest_node(graph, df_nodes_best.iloc[i]['latlong_destination'])
  #  find the shortest path
  shortest_route_best = nx.shortest_path(graph,
                                    orig_node_best,
                                    dest_node_best,
                                    weight=optimizer)
  shortest_route_length_best = nx.shortest_path_length(graph, orig_node_best, dest_node_best, weight=optimizer)
  # append list
  list_route_best.append(shortest_route_best)
  list_route_length_best.append(shortest_route_length_best)

# Store best route distance in a list
distance_result_best = list_route_length_best.copy()

# Convert nodes code into lat long
all_list_nodes_latlong = []

for i in range(len(list_route_best)):
  list_nodes_latlong = []
  for j in range(len(list_route_best[i])):
    tuple_nodes_latlong = (graph.nodes[list_route_best[i][j]]['y'], graph.nodes[list_route_best[i][j]]['x'])
    list_nodes_latlong.append(tuple_nodes_latlong)
  all_list_nodes_latlong.append(list_nodes_latlong)

# Load map
my_map = folium.Map(location=[-6.897097, 107.621903],
                    zoom_start=15,
                    tiles='cartodbpositron')

# Plot route polyline
for i in range(len(all_list_nodes_latlong)):
  folium.PolyLine(all_list_nodes_latlong[i],
                  tooltip=f"{df_nodes_best['route_order'].iloc[i].upper()}:\
                  {df_nodes_best['origin'].iloc[i]} to {df_nodes_best['destination'].iloc[i]}\
                  - Distance: {round(distance_result_best[i]/1000, 2)} km",
                  # color=random_color(),
                  weight=5).add_to(my_map)

# Plot points
for i in range(len(df_points)):
  if i != 0:
    folium.Marker(location = df_points['lat_lng'][i], 
                  popup = df_points['point_name'][i]).add_to(my_map)
  else:
    folium.Marker(location = df_points['lat_lng'][i], 
                  popup = df_points['point_name'][i],
                  icon = folium.Icon(color='crimson')).add_to(my_map) # mark depot with red symbology

print(f'Total distance: {round(sum(distance_result_best)/1000, 2)} km')
my_map

      
                
                    
                    
       Figure 8. The shortest route

Die Lösung kann uns helfen, die besten Routen zu finden, um alle Pakete an die Kunden zu liefern. Die kürzeste Reisestrecke beträgt 7,44 km bei folgender Route: