Résoudre le problème du voyageur de commerce

Nov 29 2022

Optimiser les itinéraires pour livrer des colis en utilisant python pour réduire les coûts de livraison (Étude de cas : livraison de colis à Bandung, Indonésie avec des données simples) Traveling Salesman Problem ou TSP est un problème d'optimisation combinatoire qui tente de répondre à la question « étant donné une liste de villes et le distances entre chaque paire de villes, quel est l'itinéraire le plus court possible qui visite chaque ville exactement une fois et revient à la ville d'origine ? » De manière simple, TSP est chargé de trouver l'itinéraire le plus court entre un ensemble de points qui doivent être visités.

Optimiser les itinéraires pour livrer des colis en utilisant python pour réduire les coûts de livraison (Étude de cas : livraison de colis à Bandung, Indonésie avec des données simples)

Photo de José Martín Ramírez Carrasco sur Unsplash

Le problème du voyageur de commerce ou TSP est un problème d'optimisation combinatoire qui tente de répondre à la question « Étant donné une liste de villes et les distances entre chaque paire de villes, quel est l'itinéraire le plus court possible qui visite chaque ville exactement une fois et revient à la ville d'origine ? ”. De manière simple, TSP est chargé de trouver l'itinéraire le plus court entre un ensemble de points qui doivent être visités. Cela devient un véritable problème dans le secteur de la chaîne d'approvisionnement et de la logistique, car ils ont explosé à la suite de l'essor du commerce électronique.

Alors, pourquoi le TSP est-il important ? Essentiellement, cela aide l'entreprise à gagner plus de profit en économisant du temps et des ressources. Dans le secteur de la logistique, l'un des moyens de générer plus de profit est l'efficacité des coûts et des délais de livraison. Il existe différentes façons d'y parvenir, l'une d'entre elles consiste à résoudre le problème du voyageur de commerce (TSP), où vous essayez de trouver les itinéraires les plus efficaces à emprunter sur la route. Plus il est résolu efficacement, moins on passe de temps à conduire, plus on économise de carburant, moins on a besoin d'heures, et même plus on livre de colis . En conséquence, le bilan de toute activité commerciale basée sur la livraison en bénéficiera deux fois.

Par conséquent, j'essaie de créer une démo de ce problème de voyageur de commerce pour un coursier d'une entreprise de livraison de colis à Bandung afin de réduire les coûts de livraison .

Note : comme il s'agit d'une simple démo, les données utilisées ne sont que 8 points fictifs de livraison et les données sont des données générées aléatoirement.

Scénario

Vous êtes responsable dans un centre de service de livraison de colis à Bandung. Vous devez livrer des colis à certains clients depuis votre dépôt avec 1 véhicule. La répartition des points de livraison et du dépôt peut être vue ci-dessous (Figure 1).

Figure 1. Répartition spatiale des points de livraison

**De toute façon, vous pouvez ajuster le nombre de véhicules et le nombre de points de livraison comme vous le souhaitez en éditant le code source ci-dessous

Objectifs

Trouvez les meilleurs itinéraires pour livrer tous les colis aux clients.

Pour suivre la qualité du modèle ou de la solution que nous essayons de mettre en œuvre, il est préférable de définir les métriques commerciales. Étant donné que les données des cas connexes ne sont pas disponibles, je ne mentionnerai que le potentiel sans mesurer la qualité de la solution. Ces mesures commerciales potentielles sont :

Coûts de livraison
Temps passé
Taux de livraison dans les délais
Score de satisfaction des clients (score CSAT)

En utilisant Google OR-Tools , le meilleur itinéraire avec un véhicule est :

Dépôt -> Adresse 5 -> Adresse 6 -> Adresse 7 -> Adresse 4 -> Adresse 3 -> Adresse 2 -> Adresse 1 -> Dépôt

Distance du parcours : 7,44 km

Figure 2. Animation de l'itinéraire le plus court

Étapes techniques

Figure 3. Organigramme du traitement en Python

Le code complet est fourni ici .

I. Importer la bibliothèque et lire les données

Avant tout, nous devons importer les bibliothèques dans Google Colab. Nous allons utiliser certaines bibliothèques.

numpy et pandas : pour les opérations numériques et la manipulation de données
itertools : pour créer des itérateurs pour un bouclage efficace
ast : pour traiter les arbres de la grammaire de syntaxe abstraite Python
requests : pour faire des requêtes HTTP
json : pour travailler avec des données JSON
networkx : pour la création, la manipulation et l'étude de la structure, de la dynamique et des fonctions des réseaux complexes
osmnx : pour télécharger des données géospatiales à partir d'OpenStreetMap et modéliser, projeter, visualiser et analyser des réseaux routiers réels et toute autre géométrie géospatiale
folium : pour visualiser les données qui ont été manipulées en Python sur une carte dépliante interactive
ortools : pour résoudre des problèmes d'optimisation combinatoire

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

Figure 4. Le jeu de données des points de livraison

II. Géocodage

Le géocodage est le processus de transformation d'une description d'un emplacement, comme une paire de coordonnées, une adresse ou le nom d'un lieu, en un emplacement sur la surface de la Terre. En bref, nous essayons de récupérer la latitude et la longitude à partir de l'adresse du jeu de données. Cette latitude et longitude seront utilisées plus tard pour calculer la distance de déplacement entre les points et déterminer le meilleur itinéraire de livraison.

J'utilise l'API HERE pour le géocodage étant donné qu'elle est assez précise et gratuite (avec des appels limités). Vous pouvez lire cet article pour les détails de ce processus.

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

Figure 5. DataFrame après géocodage

Notez que nous avons maintenant un champ appelé lat_lng qui contient la latitude et la longitude des points.

III. Calculer la distance de déplacement entre les points

Ensuite, il faut calculer la distance parcourue entre les points. Il est important dans le problème du voyageur de commerce puisque l'itinéraire le plus court est généré à partir de la distance totale parcourue à partir de chaque itinéraire possible. Au lieu d'utiliser la distance euclidienne (tracer une ligne entre les points), nous utiliserons une distance plus pertinente qui crée un chemin suivant la route entre les points. Ce chemin représentera la distance entre les points.

Pour ce faire, nous utiliserons la méthode shortest_path de networkx. Mais avant cela, nous devons créer le DataFrame origine-destination pour faciliter le calcul de la distance entre les points. Ce DataFrame est généré en faisant toutes les combinaisons/permutations possibles des points d'origine et de destination.

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

Figure 6. DataFrame d'origine et de destination

Maintenant, nous pouvons calculer la distance entre les points en utilisant networkx.

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

Figure 7. Distance entre les points DataFrame

IV. Déterminer le meilleur itinéraire de véhicule

Ensuite, nous pouvons déterminer le meilleur itinéraire pour livrer les colis à tous les clients à l'aide de Google OR-Tools . Tout d'abord, nous devons définir les fonctions pour nous aider à trouver le chemin le plus court. Il renvoie à cette page avec quelques modifications.

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

Dépôt -> Adresse 5 -> Adresse 6 -> Adresse 7 -> Adresse 4 -> Adresse 3 -> Adresse 2 -> Adresse 1 -> Dépôt

Cet itinéraire le plus court prendra une distance d'environ 7,44 km.

V. Créer un chemin pour l'itinéraire le plus efficace

La visualisation des données est l'un des meilleurs moyens de faciliter la compréhension de ce cas. Par conséquent, dans cette dernière étape, nous ferons une visualisation des données spatiales pour décrire le meilleur itinéraire. Nous devons créer un nouveau DataFrame qui inclut uniquement le meilleur itinéraire, puis créer le chemin.

# 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

La solution peut nous aider à trouver les meilleurs itinéraires pour livrer tous les colis aux clients. La distance la plus courte à parcourir est de 7,44 km avec l'itinéraire suivant :