Gezgin Satıcı Problemini Çözme

Nov 29 2022

Teslimat maliyetlerinden tasarruf etmek için python kullanarak kolileri teslim etme rotalarını optimize edin (Çalışma örneği: basit verilerle Endonezya, Bandung'da koli teslimatı) Gezgin Satıcı Problemi veya TSP, “Verilen bir şehirler listesi ve Her bir şehir çifti arasındaki mesafeler, her bir şehri tam olarak bir kez ziyaret eden ve çıkış şehrine geri dönen mümkün olan en kısa yol hangisidir?”. Basit bir şekilde, TSP, ziyaret edilmesi gereken bir dizi nokta arasındaki en kısa rotayı bulmakla görevlendirilir.

Teslimat maliyetlerinden tasarruf etmek için python kullanarak kolileri teslim etme rotalarını optimize edin (Çalışma örneği: Basit verilerle Endonezya, Bandung'da koli teslimatı)

Unsplash'ta José Martín Ramírez Carrasco'nun fotoğrafı

Gezgin Satıcı Problemi veya TSP, "Şehirlerin bir listesi ve her bir şehir çifti arasındaki mesafeler verildiğinde, her şehri tam olarak bir kez ziyaret eden ve orijinal şehre dönen mümkün olan en kısa rota nedir?" Sorusuna cevap vermeye çalışan bir kombinatoryal optimizasyon problemidir. ”. Basit bir şekilde, TSP, ziyaret edilmesi gereken bir dizi nokta arasındaki en kısa rotayı bulmakla görevlendirilir. E-ticaret artışlarının ardından hızla yükselen tedarik zinciri ve lojistik endüstrisinde gerçek bir sorun haline geliyor.

Peki, TSP neden önemlidir? Özünde, zamandan ve kaynaklardan tasarruf ederek şirketin daha fazla kar elde etmesine yardımcı olur. Lojistik sektöründe daha fazla kar elde etmenin yollarından biri de teslimat maliyetlerinde ve zamanında verimliliktir. Bunu başarmanın çeşitli yolları vardır, bunlardan biri, yolda en verimli rotaları bulmaya çalıştığınız Gezgin Satıcı Problemini (TSP) çözmektir. Ne kadar verimli bir şekilde çözülürse, sürüş için o kadar az zaman harcanır, o kadar çok yakıt tasarrufu yapılır, o kadar az saate ihtiyaç duyulur ve hatta o kadar çok paket teslim edilir . Sonuç olarak, teslimata dayalı herhangi bir ticari faaliyetin bilançosu iki kat fayda sağlayacaktır.

Bu nedenle, teslimat maliyetlerini azaltmak için Bandung'daki bir paket teslimat şirketinin kuryesi için bu Gezgin Satıcı Probleminin bir demosunu oluşturmaya çalışıyorum .

Not : Bu basit bir demo olduğundan, kullanılan veriler yalnızca 8 dağıtım kukla noktasıdır ve veriler rastgele oluşturulmuş verilerdir.

Senaryo

Bandung'da bir paket teslimat hizmet merkezinde yöneticisiniz. Deponuzdan bazı müşterilere paketleri 1 araçla teslim etmelisiniz. Teslimat noktalarının ve deponun dağılımı aşağıda görülebilir (Şekil 1).

Şekil 1. Teslimat noktalarının mekansal dağılımı

**Yine de aşağıdaki kaynak kodunu düzenleyerek araç sayısını ve teslim noktası sayısını istediğiniz gibi ayarlayabilirsiniz.

hedefler

Tüm kolileri müşterilere teslim etmek için en iyi yolları bulun.

Uygulamaya çalıştığımız modelin veya çözümün ne kadar iyi olduğunu izlemek için iş metriklerini tanımlamak daha iyidir. İlgili vakaların verileri mevcut olmadığından, çözümün ne kadar iyi olduğunu ölçmeden sadece potansiyelden bahsedeceğim. Bu potansiyel iş ölçütleri şunlardır:

Teslim ücreti
Harcanan zaman
Zamanında teslimat oranı
Müşteri Memnuniyeti puanı (CSAT puanı)

Google OR-Tools'u kullanarak, tek araçla en iyi rota:

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

Rotanın mesafesi: 7.44 km

Şekil 2. En kısa yol animasyonu

Teknik Adımlar

Şekil 3. Python'da işleme akış şeması

Tam kod burada sağlanır .

I. Kitaplığı İçe Aktar ve Verileri Oku

Her şeyden önce, kitaplıkları Google Colab'a aktarmamız gerekiyor. Bazı kütüphaneleri kullanacağız.

numpy ve pandas : sayısal işlemler ve veri işleme için
itertools : verimli döngü için yineleyiciler oluşturmak için
ast : Python soyut sözdizimi gramerinin ağaçlarını işlemek için
request : HTTP istekleri yapmak için
json : JSON verileriyle çalışmak için
networkx : karmaşık ağların yapısının, dinamiklerinin ve işlevlerinin oluşturulması, manipülasyonu ve incelenmesi için
osmnx : OpenStreetMap'ten jeo-uzaysal verileri indirmek ve gerçek dünya sokak ağlarını ve diğer jeo-uzaysal geometrileri modellemek, projelendirmek, görselleştirmek ve analiz etmek için
folium : etkileşimli bir broşür haritasında Python'da manipüle edilen verileri görselleştirmek için
ortools : kombinatoryal optimizasyon problemlerini çözmek için

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

Şekil 4. Teslimat noktası veri seti

II. coğrafi kodlama

Coğrafi kodlama, bir konumun tanımını - örneğin bir çift koordinat, bir adres veya bir yerin adı gibi - dünya yüzeyindeki bir konuma dönüştürme işlemidir. Kısaca enlem ve boylamı veri kümesinin adresinden almaya çalışıyoruz. Bu enlem ve boylam, daha sonra noktalar arasındaki seyahat mesafesini hesaplamak ve en iyi teslimat rotasını belirlemek için kullanılacaktır.

Oldukça doğru ve kullanımının ücretsiz (sınırlı aramalarla) olduğunu düşünerek Geocoding için HERE API kullanıyorum. Bu sürecin detayları için bu makaleyi okuyabilirsiniz .

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

Şekil 5. Geocoding sonrası DataFrame

Şimdi , noktaların enlem ve boylamını içeren lat_lng adında bir alanımız olduğuna dikkat edin .

III. Noktalar Arası Seyahat Mesafesini Hesaplayın

Sonraki, noktalar arasındaki seyahat mesafesini hesaplamaktır. En kısa rota, mümkün olan her rotadan alınan toplam mesafeden üretildiğinden, Gezgin Satıcı Probleminde önemlidir. Öklid mesafesini kullanmak yerine (noktalar arasında bir çizgi çizmek), noktalar arasındaki yolu takip eden bir yol oluşturan daha uygun bir mesafe kullanacağız. Bu yol, noktalar arasındaki mesafeyi temsil edecektir.

Bunu yapmak için, networkx'ten en kısa_yol yöntemini kullanacağız. Ancak bundan önce, noktalar arasındaki mesafeyi hesaplamayı kolaylaştırmak için başlangıç-varış noktası DataFrame'i oluşturmalıyız. Bu DataFrame, başlangıç ve varış noktalarının tüm olası kombinasyonları/permütasyonları yapılarak oluşturulur.

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

Şekil 6. Kaynak ve hedef DataFrame

Şimdi networkx kullanarak noktalar arasındaki mesafeyi hesaplayabiliriz.

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

Şekil 7. DataFrame noktaları arasındaki mesafe

IV. En İyi Araç Rotasını Belirleyin

Ardından, Google OR-Tools'u kullanarak tüm müşterilere koli teslim etmek için en iyi rotayı belirleyebiliriz . İlk olarak, en kısa rotayı bulmamıza yardımcı olacak fonksiyonları tanımlamalıyız. Bazı değişikliklerle bu sayfaya atıfta bulunur .

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

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

Bu en kısa rota yaklaşık 7,44 km'lik bir mesafe alacaktır .

V. En Etkili Rota İçin Bir Yol Oluşturun

Veri görselleştirme, bu durumun anlaşılmasını kolaylaştırmanın en iyi yollarından biridir. Bu nedenle, bu son adımda, en iyi rotayı tasvir etmek için bir konumsal veri görselleştirmesi yapacağız. Yalnızca en iyi rotayı içeren yeni bir DataFrame oluşturmalı, ardından yolu oluşturmalıyız.

# 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

Çözüm, tüm kolileri müşterilere ulaştırmak için en iyi yolları bulmamıza yardımcı olabilir. Aşağıdaki rota ile gidilebilecek en kısa mesafe 7,44 km'dir :