Rozwiązywanie problemu komiwojażera

Nov 29 2022

Zoptymalizuj trasy dostarczania paczek za pomocą Pythona, aby obniżyć koszty dostawy (Przypadek studyjny: dostawa paczek w Bandung w Indonezji z prostymi danymi) Problem komiwojażera lub TSP to kombinatoryczny problem optymalizacyjny, który próbuje odpowiedzieć na pytanie „Biorąc pod uwagę listę miast i odległości między każdą parą miast, jaka jest najkrótsza możliwa trasa, która odwiedza każde miasto dokładnie raz i wraca do miasta początkowego?”. TSP w prosty sposób ma za zadanie znaleźć najkrótszą trasę między zestawem punktów, które należy odwiedzić.

Zoptymalizuj trasy dostarczania paczek za pomocą Pythona, aby obniżyć koszty dostawy (Przypadek studyjny: dostawa paczek w Bandung w Indonezji z prostymi danymi)

Zdjęcie José Martín Ramírez Carrasco na Unsplash

Problem komiwojażera lub TSP to kombinatoryczny problem optymalizacji, który próbuje odpowiedzieć na pytanie: „Biorąc pod uwagę listę miast i odległości między każdą parą miast, jaka jest najkrótsza możliwa trasa, która odwiedza każde miasto dokładnie raz i wraca do miasta początkowego? ”. TSP w prosty sposób ma za zadanie znaleźć najkrótszą trasę między zestawem punktów, które należy odwiedzić. Staje się prawdziwym problemem w łańcuchu dostaw i branży logistycznej, ponieważ gwałtownie wzrosły one po wzroście handlu elektronicznego.

Dlaczego więc TSP jest ważne? Zasadniczo pomaga firmie uzyskać większy zysk dzięki oszczędności czasu i zasobów. W branży logistycznej jednym ze sposobów generowania większych zysków jest oszczędność kosztów i czasu dostaw. Można to osiągnąć na różne sposoby, jednym z nich jest rozwiązanie problemu komiwojażera (TSP), w którym próbujesz znaleźć najbardziej efektywne trasy do pokonania na drodze. Im skuteczniej jest to rozwiązywane, tym mniej czasu spędza się na prowadzeniu pojazdu, tym więcej oszczędza się paliwa, tym mniej godzin potrzeba, a nawet więcej paczek jest dostarczanych . W rezultacie bilans każdej działalności biznesowej opartej na dostawach odniesie podwójną korzyść.

Dlatego próbuję stworzyć demo tego problemu komiwojażera dla kuriera firmy dostarczającej paczki w Bandung, aby obniżyć koszty dostawy .

Uwaga : ponieważ jest to prosta wersja demonstracyjna, użyte dane to tylko 8 fałszywych punktów dostawy, a dane są generowane losowo.

Scenariusz

Jesteś kierownikiem w centrum obsługi paczek w Bandung. Powinieneś dostarczać paczki do niektórych klientów ze swojego magazynu 1 pojazdem. Rozmieszczenie punktów dostaw i magazynu można zobaczyć poniżej (Rysunek 1).

Rycina 1. Rozmieszczenie przestrzenne punktów dostawy

**W każdym razie możesz dostosować liczbę pojazdów i liczbę punktów dostawy według własnego uznania, edytując poniższy kod źródłowy

Cele

Znajdź najlepsze trasy, aby dostarczyć wszystkie paczki do klientów.

Aby śledzić, jak dobry jest model lub rozwiązanie, które próbujemy wdrożyć, lepiej zdefiniować metryki biznesowe. Ponieważ dane dotyczące powiązanych przypadków nie są dostępne, wspomnę tylko o potencjale bez mierzenia, jak dobre jest rozwiązanie. Te potencjalne wskaźniki biznesowe to:

Koszty dostawy
Czas spędzony
Szybkość dostawy na czas
Wynik satysfakcji klientów (wynik CSAT)

Korzystając z Google OR-Tools , najlepsza trasa z jednym pojazdem to:

Zajezdnia -> Adres 5 -> Adres 6 -> Adres 7 -> Adres 4 -> Adres 3 -> Adres 2 -> Adres 1 -> Zajezdnia

Dystans trasy: 7,44 km

Rysunek 2. Animacja najkrótszej trasy

Kroki techniczne

Rysunek 3. Schemat blokowy przetwarzania w Pythonie

Pełny kod znajduje się tutaj .

I. Importuj bibliotekę i czytaj dane

Przede wszystkim musimy zaimportować biblioteki do Google Colab. Będziemy korzystać z niektórych bibliotek.

numpy i pandy : do operacji numerycznych i manipulacji danymi
itertools : do tworzenia iteratorów dla wydajnego zapętlania
ast : do przetwarzania drzew gramatyki składni abstrakcyjnej Pythona
żądania : do wysyłania żądań HTTP
json : do pracy z danymi JSON
networkx : do tworzenia, manipulowania i badania struktury, dynamiki i funkcji złożonych sieci
osmnx : do pobierania danych geoprzestrzennych z OpenStreetMap oraz modelowania, projektowania, wizualizacji i analizowania rzeczywistych sieci ulic i wszelkich innych geometrii geoprzestrzennych
folium : do wizualizacji danych, którymi manipulowano w Pythonie, na interaktywnej mapie ulotek
ortools : do rozwiązywania kombinatorycznych problemów optymalizacyjnych

# 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')

Rysunek 4. Zestaw danych punktu dostawy

II. Geokodowanie

Geokodowanie to proces przekształcania opisu lokalizacji — takiego jak para współrzędnych, adres lub nazwa miejsca — w lokalizację na powierzchni ziemi. Krótko mówiąc, próbujemy pobrać szerokość i długość geograficzną z adresu zestawu danych. Ta szerokość i długość geograficzna zostaną później wykorzystane do obliczenia odległości podróży między punktami i określenia najlepszej trasy dostawy.

Używam HERE API do Geokodowania, biorąc pod uwagę, że jest dość dokładny i darmowy (z ograniczoną liczbą połączeń). Możesz przeczytać ten artykuł , aby poznać szczegóły tego procesu.

# 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)

Rysunek 5. DataFrame po geokodowaniu

Zauważ, że teraz mamy pole o nazwie lat_lng , które zawiera szerokość i długość geograficzną punktów.

III. Oblicz odległość podróży między punktami

Następnym krokiem jest obliczenie odległości podróży między punktami. Jest to ważne w problemie komiwojażera, ponieważ najkrótsza trasa jest generowana z całkowitej odległości pobranej z każdej możliwej trasy. Zamiast używać odległości euklidesowej (rysowanie linii między punktami), użyjemy bardziej odpowiedniej odległości, która tworzy ścieżkę wzdłuż drogi między punktami. Ta ścieżka będzie reprezentować odległość między punktami.

W tym celu wykorzystamy metodę shortest_path z networkx. Ale zanim to nastąpi, powinniśmy stworzyć DataFrame początek-cel, aby ułatwić obliczanie odległości między punktami. Ta ramka danych jest generowana przez wykonanie wszystkich możliwych kombinacji/permutacji punktów początkowych i docelowych.

# 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)

Rysunek 6. Początkowa i docelowa ramka danych

Teraz możemy obliczyć odległość między punktami za pomocą siecix.

# 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)

Rysunek 7. Odległość między punktami DataFrame

IV. Określ najlepszą trasę pojazdu

Następnie możemy określić najlepszą trasę doręczenia przesyłek do wszystkich klientów za pomocą Google OR-Tools . Najpierw musimy zdefiniować funkcje, które pomogą nam znaleźć najkrótszą trasę. Odnosi się do tej strony z pewnymi modyfikacjami.

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 !')

Zajezdnia -> Adres 5 -> Adres 6 -> Adres 7 -> Adres 4 -> Adres 3 -> Adres 2 -> Adres 1 -> Zajezdnia

Ta najkrótsza trasa będzie miała długość około 7,44 km.

V. Utwórz ścieżkę dla najbardziej efektywnej trasy

Wizualizacja danych jest jednym z najlepszych sposobów na ułatwienie zrozumienia tego przypadku. Dlatego w tym ostatnim kroku wykonamy wizualizację danych przestrzennych, aby przedstawić najlepszą trasę. Powinniśmy utworzyć nową ramkę DataFrame zawierającą tylko najlepszą trasę, a następnie utworzyć ścieżkę.

# 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

Rozwiązanie może pomóc nam znaleźć najlepsze trasy, aby dostarczyć wszystkie przesyłki do klientów. Najkrótsza odległość do pokonania to 7,44 km następującą trasą: