Решение задачи коммивояжера

Nov 29 2022

Оптимизируйте маршруты доставки посылок с помощью Python, чтобы сократить расходы на доставку (Образец исследования: доставка посылок в Бандунге, Индонезия с простыми данными) Задача коммивояжёра или TSP — это задача комбинаторной оптимизации, которая пытается ответить на вопрос «данный список городов и расстояния между каждой парой городов, каков кратчайший возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходный город?». Проще говоря, перед TSP ставится задача найти кратчайший маршрут между набором точек, которые необходимо посетить.

Оптимизируйте маршруты доставки посылок с помощью Python, чтобы сократить расходы на доставку (учебный пример: доставка посылок в Бандунге, Индонезия с использованием простых данных)

Фото Хосе Мартина Рамиреса Карраско на Unsplash

Задача коммивояжёра или TSP — это задача комбинаторной оптимизации, которая пытается ответить на вопрос: «Учитывая список городов и расстояния между каждой парой городов, каков кратчайший возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходный город? ». Проще говоря, перед TSP ставится задача найти кратчайший маршрут между набором точек, которые необходимо посетить. Это становится реальной проблемой в цепочке поставок и логистической отрасли, поскольку они резко возросли после роста электронной коммерции.

Итак, почему TSP важен? По сути, это помогает компании получить больше прибыли за счет экономии времени и ресурсов. В логистической отрасли одним из способов получения большей прибыли является эффективность затрат и времени на доставку. Есть разные способы добиться этого, один из них — решить задачу коммивояжёра (TSP), где вы пытаетесь найти наиболее эффективные маршруты для путешествия. Чем эффективнее она решается, тем меньше времени тратится на вождение, тем больше экономится топлива, тем меньше часов требуется и даже тем больше посылок доставляется . В результате баланс любой коммерческой деятельности, основанной на доставке, выиграет вдвойне.

Поэтому я пытаюсь создать демонстрацию этой задачи коммивояжёра для курьера компании по доставке посылок в Бандунге, чтобы сократить расходы на доставку .

Примечание : поскольку это простая демонстрация, используемые данные представляют собой только 8 фиктивных точек доставки, и данные генерируются случайным образом.

Сценарий

Вы менеджер центра доставки посылок в Бандунге. Вы должны доставить посылки некоторым клиентам из вашего склада на 1 транспортном средстве. Распределение точек доставки и депо можно увидеть ниже (рисунок 1).

Рисунок 1. Пространственное распределение точек доставки

** В любом случае, вы можете настроить количество транспортных средств и количество точек доставки по своему усмотрению, отредактировав исходный код ниже.

Цели

Найдите лучшие маршруты для доставки всех посылок клиентам.

Чтобы отслеживать, насколько хороша модель или решение, которое мы пытаемся внедрить, лучше определить бизнес-показатели. Поскольку данные о связанных случаях недоступны, я упомяну только потенциал, не измеряя, насколько хорошо решение. Эти потенциальные бизнес-показатели:

Цена доставки
Время потрачено
Скорость доставки в срок
Оценка удовлетворенности клиентов (оценка CSAT)

С помощью Google OR-Tools лучший маршрут с одним транспортным средством:

Депо -> Адрес 5 -> Адрес 6 -> Адрес 7 -> Адрес 4 -> Адрес 3 -> Адрес 2 -> Адрес 1 -> Депо

Расстояние маршрута: 7,44 км

Рисунок 2. Анимация кратчайшего маршрута

Технические шаги

Рисунок 3. Блок-схема обработки в Python

Полный код приведен здесь .

I. Импорт библиотеки и чтение данных

Прежде всего, нам нужно импортировать библиотеки в Google Colab. Мы собираемся использовать некоторые библиотеки.

numpy и pandas : для числовых операций и манипулирования данными
itertools : для создания итераторов для эффективного цикла
ast : для обработки деревьев грамматики абстрактного синтаксиса Python.
запросы : для выполнения HTTP-запросов
json : для работы с данными JSON
networkx : для создания, управления и изучения структуры, динамики и функций сложных сетей.
osmnx : для загрузки геопространственных данных из OpenStreetMap и моделирования, проектирования, визуализации и анализа реальных уличных сетей и любой другой геопространственной геометрии.
folium : визуализировать данные, которые были обработаны в Python, на интерактивной карте листовок.
ortools : для решения задач комбинаторной оптимизации

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

Рисунок 4. Набор данных точки доставки

II. Геокодирование

Геокодирование — это процесс преобразования описания местоположения, такого как пара координат, адрес или название места, в местоположение на поверхности земли. Короче говоря, мы пытаемся получить широту и долготу из адреса набора данных. Эти широта и долгота будут использоваться позже для расчета расстояния между точками и определения наилучшего маршрута доставки.

Я использую HERE API для геокодирования, учитывая, что он довольно точен и бесплатен (с ограниченным числом вызовов). Вы можете прочитать эту статью для деталей этого процесса.

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

Рисунок 5. DataFrame после геокодирования

Обратите внимание, что теперь у нас есть поле с именем lat_lng , которое содержит широту и долготу точек.

III. Вычислить расстояние между точками

Далее следует рассчитать расстояние перемещения между точками. Это важно в задаче о коммивояжере, поскольку кратчайший маршрут создается из общего расстояния, взятого из всех возможных маршрутов. Вместо использования евклидова расстояния (проведение линии между точками) мы будем использовать более подходящее расстояние, которое создает путь по дороге между точками. Этот путь будет представлять собой расстояние между точками.

Для этого мы будем использовать метод shortest_path из networkx. Но перед этим мы должны создать DataFrame origin-destination, чтобы было проще вычислять расстояние между точками. Этот DataFrame генерируется путем создания всех возможных комбинаций/перестановок точек отправления и назначения.

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

Рисунок 6. Исходный и целевой DataFrame

Теперь мы можем рассчитать расстояние между точками, используя 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)

Рисунок 7. Расстояние между точками DataFrame

IV. Определение наилучшего маршрута транспортного средства

Затем мы можем определить лучший маршрут для доставки посылок всем клиентам с помощью Google OR-Tools . Во-первых, мы должны определить функции, которые помогут нам найти кратчайший маршрут. Он ссылается на эту страницу с некоторыми изменениями.

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

Депо -> Адрес 5 -> Адрес 6 -> Адрес 7 -> Адрес 4 -> Адрес 3 -> Адрес 2 -> Адрес 1 -> Депо

Этот кратчайший маршрут займет около 7,44 км.

V. Создайте путь для наиболее эффективного маршрута

Визуализация данных — один из лучших способов облегчить понимание этого случая. Поэтому на этом последнем шаге мы сделаем визуализацию пространственных данных, чтобы изобразить лучший маршрут. Мы должны создать новый DataFrame, который включает только лучший маршрут, а затем создать путь.

# 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

Решение может помочь нам найти лучшие маршруты для доставки всех посылок клиентам. Кратчайшее расстояние для поездки составляет 7,44 км по следующему маршруту: