Решение задачи об оптимальных маршрутах — это классическая отраслевая задача, имеющая множество практических приложений в сфере оптимизации цепочки поставок. Можно рассматривать это как вариант задачи коммивояжёра, где у нас есть отправная точка, например наш продуктовый склад, и набор городов для доставки, каждый маршрут между двумя городами имеет стоимость, например стоимость топлива и пошлины и налоги. Мы также можем предположить, что каждая дорога имеет форму общей доступной пропускной способности, а каждый город имеет определенный спрос и излишек, который он может дать.
Итак, теперь наша проблема заключается в следующем: мы хотим максимизировать количество отправляемых товаров, минимизируя расстояние и стоимость и доставляя их в каждый отдельный город.
это сложная задача комбинаторной оптимизации, и в этой статье мы рассмотрим, как мы можем решить ее, используя вышеупомянутые методы.
Мы начнем с простого, а затем добавим больше сложности по ходу дела.
1- Генерация данных
Предположим, наша судоходная компания находится во Франции, наш склад находится в Париже, и мы должны доставить товар в несколько городов по всей стране. Мы будем использовать библиотеку networkx в python для создания графических данных, представляющих эту проблему.
import networkx as nx
import geopandas as gpd
from shapely.geometry import Point, LineString
import matplotlib.pyplot as plt
# Set the number of nodes (cities)
num_nodes = 10
# Define the city data
city_data = {
'city': ['Paris', 'Marseille', 'Lyon', 'Toulouse', 'Nice', 'Nantes', 'Montpellier', 'Strasbourg', 'Bordeaux', 'Lille'],
'lat': [48.8567, 43.2964, 45.7600, 43.6045, 43.7034, 47.2181, 43.6119, 48.5833, 44.8400, 50.6278],
'lng': [2.3522, 5.3700, 4.8400, 1.4440, 7.2663, -1.5528, 3.8772, 7.7458, -0.5800, 3.0583]
}
# Create a complete graph with num_nodes nodes
G = nx.complete_graph(num_nodes)
# Add nodes to the graph with city names as labels
for i in range(num_nodes):
G.nodes[i]['city'] = city_data['city'][i]
# Create a GeoDataFrame for the cities with Point geometries
gdf_cities = gpd.GeoDataFrame(city_data, geometry=gpd.points_from_xy(city_data['lng'], city_data['lat']))
# Create a GeoDataFrame for the routes (edges)
routes = []
for edge in G.edges():
city1 = G.nodes[edge[0]]['city']
city2 = G.nodes[edge[1]]['city']
route = LineString([(gdf_cities[gdf_cities['city'] == city1].geometry.x.iloc[0], gdf_cities[gdf_cities['city'] == city1].geometry.y.iloc[0]),
(gdf_cities[gdf_cities['city'] == city2].geometry.x.iloc[0], gdf_cities[gdf_cities['city'] == city2].geometry.y.iloc[0])])
routes.append(route)
gdf_routes = gpd.GeoDataFrame(geometry=routes)
# Create a plot for the map of France
fig, ax = plt.subplots(figsize=(10, 8))
world = gpd.read_file(gpd.datasets.get_path('naturalearth_lowres'))
france_shapefile = world[world.name == 'France']
france_shapefile.boundary.plot(ax=ax, color='lightgray', linewidth=0.8)
gdf_cities.plot(ax=ax, marker='o', color='red', markersize=100, alpha=0.7)
gdf_routes.plot(ax=ax, color='blue', linewidth=1, alpha=0.6)
# Add labels for the cities
for x, y, label in zip(gdf_cities.geometry.x, gdf_cities.geometry.y, gdf_cities['city']):
ax.annotate(label, xy=(x, y), xytext=(3, 3), textcoords="offset points", color='black', fontsize=10)
# Set the axis limits to focus on France
ax.set_xlim(-5, 10)
ax.set_ylim(40, 54)
# Show the plot
plt.title('Cities and Routes in France')
plt.show()
Теперь давайте начнем с простой задачи, где мы хотим только минимизировать стоимость расстояния, мы предположим, что стоимость составляет 0,25 евро за км, и вычислим веса для каждого ребра как такового.
# Compute the distance and add weight to each edge
from geopy.distance import geodesic
import numpy as np
for edge in G.edges():
city1 = G.nodes[edge[0]]['city']
city2 = G.nodes[edge[1]]['city']
coord1 = (city_data['lat'][city_data['city'].index(city1)], city_data['lng'][city_data['city'].index(city1)])
coord2 = (city_data['lat'][city_data['city'].index(city2)], city_data['lng'][city_data['city'].index(city2)])
distance_km = geodesic(coord1, coord2).kilometers
G.edges[edge]['weight'] = np.round(0.25 * distance_km)
# Create a plot for the graph data with assigned weights
fig, ax = plt.subplots(figsize=(10, 8))
# Create a GeoDataFrame for the cities with Point geometries
gdf_cities = gpd.GeoDataFrame(city_data, geometry=gpd.points_from_xy(city_data['lng'], city_data['lat']))
# Draw the cities as nodes
pos = {i: (city_data['lng'][i], city_data['lat'][i]) for i in range(num_nodes)}
nx.draw_networkx_nodes(G, pos, node_size=200, node_color='red', alpha=0.7, ax=ax)
# Draw the routes as edges with weights as labels
edges = nx.draw_networkx_edges(G, pos, edge_color='blue', alpha=0.6, width=1)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=8, ax=ax)
# Add labels for the cities
for x, y, label in zip(gdf_cities.geometry.x, gdf_cities.geometry.y, gdf_cities['city']):
ax.annotate(label, xy=(x, y), xytext=(3, 3), textcoords="offset points", color='black', fontsize=10)
# Set the axis limits to focus on the cities
ax.set_xlim(min(city_data['lng']) - 1, max(city_data['lng']) + 1)
ax.set_ylim(min(city_data['lat']) - 1, max(city_data['lat']) + 1)
# Show the plot
plt.title('Graph Data with Assigned Weights (Distances in Euros)')
plt.axis('equal')
plt.show()
2- Простая проблема: путь Shotest минимизирует только стоимость расстояния
Хорошо, теперь мы можем попытаться найти решение этой проблемы, мы установим нашу начальную точку как Париж и используем алгоритм Кристофидеса–Сердюкова для аппроксимации решения, это можно сделать с помощью библиотеки networkx , в частности, функция: nx.приближение.traveling_salesman_problem(G, cycle=True)),Затем мы нанесем на график найденное решение
# Convert the problem to finding a Hamiltonian cycle starting and ending at the specified start point
start_point = 'Paris'
# Add the start point to the city_data dictionary
start_lat = city_data['lat'][city_data['city'].index(start_point)]
start_lng = city_data['lng'][city_data['city'].index(start_point)]
city_data['city'].append(start_point)
city_data['lat'].append(start_lat)
city_data['lng'].append(start_lng)
# Create a new node representing the start point
new_node_id = num_nodes
G.add_node(new_node_id, city=start_point)
# Connect the new node to all other nodes
for i in range(num_nodes):
city = G.nodes[i]['city']
coord = (city_data['lat'][city_data['city'].index(city)], city_data['lng'][city_data['city'].index(city)])
distance_km = geodesic(coord, (start_lat, start_lng)).kilometers
G.add_edge(new_node_id, i, weight=0.25 * distance_km)
# Find the Hamiltonian cycle starting and ending at the specified start point
optimal_route = list(nx.approximation.traveling_salesman_problem(G, cycle=True))
# Remove the added node representing the start point
optimal_route.remove(new_node_id)
# Rearrange the route to start from the specified start point
start_index = optimal_route.index(city_data['city'].index(start_point))
optimal_route = optimal_route[start_index+1:] + optimal_route[:start_index+1]
# Remove the added node representing the start point
G.remove_node(new_node_id)
# Rearrange the route to start from the specified start point
start_index = optimal_route.index(new_node_id)
optimal_route = optimal_route[start_index+1:] + optimal_route[:start_index+1]
# Create a GeoDataFrame for the optimal route
route_points = [(city_data['lng'][i], city_data['lat'][i]) for i in optimal_route]
gdf_route = gpd.GeoDataFrame({'geometry': [LineString(route_points + [route_points[0]])]})
# Set the positions of nodes using spring_layout
node_positions = nx.spring_layout(G, seed=42, iterations=100, scale=30)
# Plot the optimal route in red color with arrows
optimal_route_edges = [(optimal_route[i], optimal_route[i + 1]) for i in range(len(optimal_route) - 1)] + [(optimal_route[-1], optimal_route[0])]
optimal_route_positions = {node: node_positions[node-1] if node != 0 else (0, 0) for node in optimal_route}
# Create a plot for the graph data with assigned weights
fig, ax = plt.subplots(figsize=(10, 8))
# Create a GeoDataFrame for the cities with Point geometries
gdf_cities = gpd.GeoDataFrame(city_data, geometry=gpd.points_from_xy(city_data['lng'], city_data['lat']))
# Draw the routes as edges with weights as labels
edges = nx.draw_networkx_edges(G, pos, edge_color='blue', alpha=0.6, width=1)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=8, ax=ax)
# Add labels for the cities
for x, y, label in zip(gdf_cities.geometry.x, gdf_cities.geometry.y, gdf_cities['city']):
ax.annotate(label, xy=(x, y), xytext=(3, 3), textcoords="offset points", color='black', fontsize=10)
# Plot the optimal route in red color with arrows
for i in range(len(optimal_route) - 1):
city1 = city_data['city'][optimal_route[i]]
city2 = city_data['city'][optimal_route[i + 1]]
x_coords = [city_data['lng'][optimal_route[i]], city_data['lng'][optimal_route[i + 1]]]
y_coords = [city_data['lat'][optimal_route[i]], city_data['lat'][optimal_route[i + 1]]]
ax.plot(x_coords, y_coords, color='red', linewidth=2, alpha=0.6, zorder=1)
# Add arrows to the line segments
dx = x_coords[1] - x_coords[0]
dy = y_coords[1] - y_coords[0]
ax.arrow(x_coords[0], y_coords[0], dx, dy, head_width=0.1, head_length=0.1, fc='red', ec='red')
# Connect the last city to the first city in the optimal route
city1 = city_data['city'][optimal_route[-1]]
city2 = city_data['city'][optimal_route[0]]
x_coords = [city_data['lng'][optimal_route[-1]], city_data['lng'][optimal_route[0]]]
y_coords = [city_data['lat'][optimal_route[-1]], city_data['lat'][optimal_route[0]]]
ax.plot(x_coords, y_coords, color='red', linewidth=2, alpha=0.6, zorder=1)
# Draw the cities as nodes on top of the edges
#nx.draw_networkx_nodes(G, pos, node_size=200, node_color='red', alpha=0.7, ax=ax)
# Set the axis limits to focus on the cities
ax.set_xlim(min(city_data['lng']) - 1, max(city_data['lng']) + 1)
ax.set_ylim(min(city_data['lat']) - 1, max(city_data['lat']) + 1)
# Show the plot
plt.title('Graph Data with Assigned Weights (Distances in Euros) and Optimal Route')
plt.axis('equal')
plt.show()
Итак, вот решение: начните с Париж -> Нант -> Бордо -> Тулуза -> Монпелье -> Ницца -> Марсель -> Лион -> Страсбург -> Лилль и, наконец, вернитесь в Париж. .
3- Добавление большей сложности: минимизация стоимости расстояния и стоимости транспортировки
Хорошо, теперь предположим, что у каждой дороги есть другая конкретная стоимость, такая как дорожные сборы и налоги, стоимость дороги больше не зависит от расстояния в км. Давайте попробуем смоделировать это, добавив некоторую случайную положительную стоимость к каждому ребру.
import random
# Add random positive cost to each edge
for edge in G.edges():
G[edge[0]][edge[1]]['cost'] = random.randint(25, 200)
# Define a custom weight function that considers both distance and cost
def custom_weight(u, v, data):
distance_weight = data['weight'] # Distance weight (previously calculated)
cost_weight = data['cost'] # Custom cost weight for the edge
return distance_weight + cost_weight
# Compute the shortest path with the custom weight function
optimal_route = nx.approximation.traveling_salesman_problem(G, cycle=True, weight=custom_weight)
Теперь посмотрим решение
Итак, теперь решение: Начните с Парижа – › Лилля – › Парижа – › Нанта – › Ниццы – › Монпелье – › Тулузы – › Парижа – › Страсбурга – › Лиона – › Бордо – › Марселя – › Парижа, Обратите внимание, что мы не добавили условие не возвращаться в город, а хотя бы посетить каждый город по одному разу.
4 – Решение с помощью агента RL.
Чтобы решить с помощью агента RL, нам нужно определить нашу среду, то есть состояния: в каких городах мы сейчас находимся (посещенные города и еще не посещенные города), набор возможных действий (какой город посетить следующим) и вознаграждение ( отрицательное вознаграждение, представляющее стоимость) за каждое действие.
Для этого мы будем использовать следующие библиотеки на питоне: stable_baselines3 и gym.
from stable_baselines3 import DQN
from stable_baselines3.common.env_util import DummyVecEnv
import gym
from gym import spaces
# Define the RL environment as a wrapper for the TSPEnvironment
class TSPGymEnv(gym.Env):
def __init__(self, G):
self.G = G
self.num_nodes = G.number_of_nodes()
self.reset()
# Action space
self.action_space = spaces.Discrete(self.num_nodes)
# Observation space (current city)
self.observation_space = spaces.Discrete(self.num_nodes)
# Initialize the set of visited cities
self.visited_cities = set()
# Initialize the starting city as the current city
self.current_city = 0
def reset(self):
self.visited_cities = set()
self.current_city = random.choice(list(self.G.nodes()))
self.visited_cities.add(self.current_city)
return self.current_city
def step(self, action):
if self.current_city not in self.visited_cities:
# Add the current city to the set of visited cities
self.visited_cities.add(self.current_city)
next_city = list(self.G[self.current_city])[action - 1 if action != 0 else 0]
reward = -self.G[self.current_city][next_city]['cost'] # Negative cost as the reward
done = len(self.visited_cities) == self.num_nodes
if not done:
self.current_city = next_city
return next_city, reward, done, {}
# Create the RL environment
env = DummyVecEnv([lambda: TSPGymEnv(G)])
# Create the DQN model
model = DQN("MlpPolicy", env, verbose=1)
# Train the model
model.learn(total_timesteps=30000)
# Create a list to store the optimal route
optimal_route = [0]
# Continue predicting the next cities until all cities have been visited
while len(optimal_route) < num_nodes:
# Convert the current_city to a numpy array
current_city_array = np.array([current_city])
# Predict the next action using the RL model
action, _ = model.predict(current_city_array)
# Get the next city based on the predicted action
next_city = list(G[current_city])[action[0] - 1 if action[0] != 0 else 0]
# If the next city has not been visited yet, add it to the optimal route
if next_city not in optimal_route:
optimal_route.append(next_city)
# Update the current_city for the next iteration
current_city = next_city
Вот решение, найденное Агентом: Начните с Парижа – › Лиона – › Тулузы – › Бордо – › Лилля – › Ниццы – › Страсбурга – › Нанта – › Марселя – › Монпелье
5 – Проблема потока с минимальной стоимостью
Наконец, давайте предположим, что у вас есть общий запас d товаров для отправки, у каждого города есть требуемый спрос f и возможные излишки, которые он может предоставить, и для каждого маршрута существует максимальное количество товаров, которые вы можете отправить по этому конкретному маршруту, и мы хотят найти оптимальный маршрут, чтобы мы могли минимизировать общие затраты, а также максимально удовлетворить спрос. теперь проблема действительно стала довольно сложной задачей.
Математически это вариант задачи потока с минимальной стоимостью или сети потоков, мы можем сформулировать это как задачу оптимизации следующим образом:
Пусть G = (V , E ) — ориентированный граф с исходной вершиной s ∈ V и стоковой вершиной t ∈ V. Каждое ребро (u, v) ∈ E имеет положительную пропускную способность c(u, v), значение потока f(u, v) и стоимость a(u, v). Стоимость отправки потока по ребру (u, v) определяется выражением f(u, v) * a(u, v). Цель состоит в том, чтобы найти поток заданного количества d с минимальной стоимостью из источника s в сток t с учетом ограничений пропускной способности на ребрах. Цель состоит в том, чтобы минимизировать общую стоимость потока по всем ребрам:
Чтобы решить эту проблему, мы будем использовать симплексный алгоритм в networkx.
Симплексный алгоритм — это популярный алгоритм для решения задач линейного программирования, то есть задач оптимизации, в которых целевая функция и ограничения являются линейными. Алгоритм работает, двигаясь от одной вершины допустимой области (множество точек, удовлетворяющих ограничениям) к другой, вдоль ребер многогранника (геометрической формы, образованной ограничениями), пока не достигнет оптимального решения или не найдет что задача неограничена12
Алгоритм включает в себя добавление резервных переменных для преобразования неравенств в равенства, а затем выполнение ряда операций, называемых поворотом, которые обменивают базовую переменную (та, которая появляется в левой части равенства) на небазовую переменную ( тот, который появляется в правой части или целевой функции), сохраняя при этом осуществимость и улучшая целевое значение34
1: Симплексный алгоритм — Википедия 2: Симплексный алгоритм — Открытый учебник по вычислительной оптимизации Корнельского университета — Optimization Wiki 3: 1 Симплексный метод — Факультет компьютерных наук 4: Симплексный метод решения LPP (с примерами ) | Оперативное исследование
Итак, сначала нам нужно переопределить наш график и создать новые данные.
Симплексный решатель в networkx принимает только направленные графы, поэтому мы создадим ориентированный граф, представляющий наши города и ограничения, мы предположим, что у нас есть общий начальный запас 1000, и для упрощения генерации данных мы назначим случайный спрос для каждого города. , то мы будем использовать метод networkx nx.network_simplex(G), чтобы найти решение.
Также обратите внимание, что при таком подходе мы больше не предполагаем, что у нас есть только одно депо в Париже и один грузовик доставки, курсирующий по всем городам, а вместо этого каждый город с избытком можно рассматривать как склад и может отправить небольшой грузовик (или несколько грузовиков). ) для доставки товаров и удовлетворения некоторых потребностей других городов. В будущей статье мы рассмотрим, как еще больше ужесточить эти ограничения, например, заставить один грузовик разъезжать и иметь своего рода последовательный маршрут, то есть, например, мы не можем иметь несколько исходящих маршрутов из одного узла в то же самое время. время грузовик должен покинуть узел i до узла j, прежде чем вернуться в узел i, например, для пополнения запасов, или мы можем добавить еще одно ограничение на грузоподъемность самого грузовика, но мы также можем предположить, что в этом сценарии пропускная способность дорог фактически представляют собой грузоподъемность работающих на них грузовиков доставки.
import random
import networkx as nx
import matplotlib.pyplot as plt
# Set the number of nodes (cities) and maximum possible routes between two nodes
num_nodes = 10
max_routes = 3
required_flow = 1000 # Total flow across the graph
# Define the city data
city_data = {
'city': ['Paris', 'Marseille', 'Lyon', 'Toulouse', 'Nice', 'Nantes', 'Montpellier', 'Strasbourg', 'Bordeaux', 'Lille'],
'lat': [48.8567, 43.2964, 45.7600, 43.6045, 43.7034, 47.2181, 43.6119, 48.5833, 44.8400, 50.6278],
'lng': [2.3522, 5.3700, 4.8400, 1.4440, 7.2663, -1.5528, 3.8772, 7.7458, -0.5800, 3.0583]
}
# Create a random graph with num_nodes nodes and random edges
G = nx.DiGraph() # Convert to directed graph
# Add nodes to the graph with demand attributes
total_demand = 0
# Set the source node (Paris) demand to a negative value
for city in city_data['city']:
if city_data['city'] != 'Paris':
demand = random.randint(-required_flow, required_flow)
G.add_node(city, demand=demand)
total_demand += demand
else:
demand = -required_flow
G.add_node(city, demand=demand)
total_demand += demand
# Balance the total demand to sum to 0
G.nodes[city_data['city'][-1]]['demand'] -= total_demand
# Generate random edges between nodes
for i in range(num_nodes):
for j in range(i + 1, num_nodes):
if random.random() < 0.5:
num_routes = random.randint(1, max_routes)
for _ in range(num_routes):
distance = random.randint(50, 500) # Random distance between 50 to 500 km
cost = random.randint(10, 100) # Random cost between 10 to 100 Euros
capacity = random.randint(100, 500) # Random capacity between 100 to 500 units
G.add_edge(city_data['city'][i], city_data['city'][j], distance=distance, cost=cost, capacity=capacity)
G.add_edge(city_data['city'][j], city_data['city'][i], distance=distance, cost=cost, capacity=capacity) # Reverse direction
# Solve the problem using Minimum Cost Flow algorithm with required flow constraint
flow_cost, flow_dict = nx.network_simplex(G)
Теперь давайте найденное решение:
Оптимальный маршрут: [('Париж', 'Нант'), ('Париж', 'Страсбург'), ('Париж', 'Лилль'), ('Марсель', 'Страсбург'), ('Марсель', ' Лилль'), ('Лион', 'Париж'), ('Лион', 'Марсель'), ('Лион', 'Лилль'), ('Тулуза', 'Марсель'), ('Тулуза', ' Бордо'), ('Ницца', 'Марсель'), ('Ницца', 'Бордо'), ('Нант', 'Тулуза'), ('Нант', 'Бордо'), ('Монпелье', ' Лион'), ('Монпелье', 'Лилль'), ('Бордо', 'Марсель'), ('Бордо', 'Лилль')]
Общее расстояние: 4895 км
Общая стоимость: 5763 евро
Общая мощность: 5697 единиц
Общий поток достигнут: 711 единиц
На данный момент это все. В следующий раз мы увидим, как мы можем создать агент RL, чтобы попытаться решить эту сложную проблему, поскольку среда теперь намного сложнее, например, набор действий больше не просто куда двигаться дальше, но также сколько вы можете взять с собой, соблюдая все ограничения, а также пытаясь минимизировать общую стоимость.
Надеюсь, эта статья окажется для вас полезной :)
