En otras entradas, hemos hablado un poco por encima del problema del viajante o (TSP – Travelling Salesman Problem). En este post vamos otro problema introducido por George Dantzig y John Ramser, el problema de enrutamiento de vehículos o VPR (vehicle routing problem), problemas muy relacionados.
Limitare el alcance de esta explicación/algoritmo a la versión inicial de Clarke y Wright.
Repositorio
Si os sirve de ayuda el código en el repositorio una estrellita no estaría de más
Enlace: Github repo (Python)
Las reglas
Vamos que problema se plantea, en este ejercicio. Por un lado, tenemos un vehículo que tiene que llevar objetos desde el almacén, hasta los destinos que toque.
Por otro lado, planteamos las restricciones de:
- Cantidad de vehículos (1)
- Peso máximo que puede llevar el vehículo (x)
En la imagen anterior, si tenemos un vehículo y nos caben la paquetería de los dos destinos, vemos claramente que no es muy eficiente volver al almacén cada vez.
Un enfoque mas «optimo» seria la ruta: almacén -> destino 1 -> destino 2 -> almacén.
Para establecer las reglas, tendremos en cyent\\, estableceremos las bases en las cuales construiremos nuestra restricciones:
- Sólo tenemos un almacén
- No tenemos limite de kilómetros en los vehículos
- Límite de peso por vehículo
Planteando el caso:
Vamos a plantear eso caso en base de distancias, las ordenaremos y luego usaremos ese espacio, para construir la ruta mas optimas, respetando las restricciones.
Cómo podéis ver tenemos un coste de la D sup 1 de ida y vuelta al destino y luego le sumamos un segundo viaje con la distancia D sup 2. Pero, que estoy diciendo con esto ?
Si veis la imagem vamos a poner números en estos «simbolos». Pongamos, que desde el almacén al destino 1 hay una distancia de 10 y desde el almacén hasta el destino 2, tenemos una distancia de 9.
D1 = almacén -> destino 1 = 10 km
D2 = almacén -> destino 2 = 9 km
Ahora esta un poco mas clara la explicación, veamos los cálculos ahora que tenemos numeros:
- ruta 1 = almacén -> destino 1 -> almacén = 2D1 = 10 + 10 = 2*10 = 20km
- ruta 2 = almacén -> destino 2 -> almacén = 2D2 = 9 + 9 = 2*9 = 18km
total = ruta 1 + ruta 2 = 38km
En los algoritmos voraces, buscamos una heurística de mejora, que nos devuelva una opción optima a nuestro problema. Eso esta muy bien pero qué necesitamos ?
Ver todas las opciones y buscar/ordenar en base a la mejora
Para calcular la mejora entre dos opciones, que serian:
- Opción 1: 2D1 + 2D2 (primera imagen)
- Opción 2: D1 + D3 + D2 (segunda imagen)
Para, calcular la mejora entre las dos opciones, es bastante sencillo:
Mejora/ahorro = 2D1 + 2D2 – (D1 + D2 + D3) = 2D1 + 2D2 – D1 – D2 – D3
Podemos resumir 2D1 + 2D2 – D1 – D2 – D3, como D1 + D2 – D3
Para que veáis la magia, aplicaremos los números de arriba y diremos que D3, son 4km
2D1 + 2D2 – D1 – D2 – D3 = 2*10 + 2*9 – (10 + 9 + 4) = 20 + 18 – 10 – 9 – 4 = 15 km
- ahorro = 2D1 + 2D2 – D1 – D2 – D3 = 2*10 + 2*9 – (10 + 9 + 4) = 20 + 18 – 10 – 9 – 4 = 15 km
- ahorro = D1 + D2 – D3 = 10 + 9 – 4 = 15km
Con estos simples cálculos, podemos ver que la opción 2 tiene un ahorro, siendo así la opción más optima.
El código tras el algoritmo
Si entrais al repo, podeis ver como funciona y testearlo desde el package tests, donde tenéis test_greedy.py.
Esta test, valida su funcionamiento y os permite crear mas testing para hacer otro tipo de pruebas.
from typing import Dict, Tuple, List
import math
from operator import itemgetter
def calculate_distance(
coord1: Tuple[float, float],
coord2: Tuple[float, float]
) -> float:
return math.sqrt((coord1[0]-coord2[0])**2+(coord1[1]-coord2[1])**2)
def saving_between_cities_and_warehouse(
coord_left: Tuple[float, float],
coord_right: Tuple[float, float],
warehouse: Tuple[float, float]
) -> float:
distance_city_left_to_city_right = \
calculate_distance(coord_left, coord_right)
distance_coord_left_to_warehouse = \
calculate_distance(coord_left, warehouse)
distance_coord_right_to_warehouse = \
calculate_distance(coord_right, warehouse)
return distance_coord_left_to_warehouse + \
distance_coord_right_to_warehouse - \
distance_city_left_to_city_right
def savings(
cities: Dict[str, Tuple[float, float]],
warehouse: (float, float)
) -> Dict[Tuple[float, float], Tuple[float, float]]:
savings = {}
for city_left in cities:
for city_right in cities:
if city_left != city_right:
if not (city_left, city_right) in savings:
savings[city_left, city_right] = \
saving_between_cities_and_warehouse(
cities[city_left],
cities[city_right],
warehouse
)
return sorted(savings.items(), key=itemgetter(1), reverse=True)
def delivery_route(delivery_routes: List, city: Tuple[str, str]) \
-> Tuple[str, str]:
for route in delivery_routes:
if city in route:
return route
return None
def delivery_weight(delivery_routes: List, orders: Dict[str, int]) -> int:
weight: int = 0
for city in delivery_routes:
weight += orders[city]
return weight
def join_delivery_route(delivery_routes: List, route_left: List,
route_right: List, cities: Tuple[str, str],
orders: Dict[str, int], max_weight: int
) -> None:
if route_left[0] == cities[0] \
and route_right[len(route_right)-1] == cities[1]:
if delivery_weight(
route_left + route_right,
orders
) <= max_weight:
delivery_routes[delivery_routes.index(route_right)]\
.extend(route_left)
delivery_routes.remove(route_left)
elif route_left[len(route_left)-1] == cities[0] \
and route_right[0] == cities[1]:
if delivery_weight(
route_left + route_right,
orders
) <= max_weight:
delivery_routes[delivery_routes.index(route_left)]\
.extend(route_right)
delivery_routes.remove(route_right)
def city_appear_only_in_route_left(delivery_routes: List, route_left: List,
cities: Tuple[str, str],
orders: Dict[str, int], max_weight: int
) -> None:
if route_left[0] == cities[0]:
if delivery_weight(route_left + [cities[1]], orders) <= max_weight:
delivery_routes[delivery_routes.index(route_left)]\
.insert(0, cities[1])
elif route_left[len(route_left)-1] == cities[0]:
if delivery_weight(route_left + [cities[1]], orders) <= max_weight:
delivery_routes[delivery_routes.index(route_left)]\
.append(cities[1])
def city_appear_only_in_route_right(delivery_routes: List, route_right: List,
cities: Tuple[str, str],
orders: Dict[str, int], max_weight: int
) -> None:
if route_right == cities[1]:
if delivery_weight(route_right + [cities[0]], orders) <= max_weight:
delivery_routes[delivery_routes.index(route_right)]\
.insert(0, cities[0])
elif route_right[len(route_right)-1] == cities[1]:
if delivery_weight(route_right + [cities[0]], orders) <= max_weight:
delivery_routes[delivery_routes.index(route_right)]\
.append(cities[0])
def greedy(
s: Dict[Tuple[float, float], float],
orders: Dict[str, int],
max_weight: int = 40
) -> List:
delivery_routes: List = []
for cities, distance in s:
print(delivery_routes)
route_left: Tuple[str, str] = \
delivery_route(delivery_routes, cities[0])
route_right: Tuple[str, str] = \
delivery_route(delivery_routes, cities[1])
if route_left and route_right and route_left == route_right:
continue
elif route_left and route_right and route_left != route_right:
join_delivery_route(delivery_routes, route_left, route_right,
cities, orders, max_weight)
elif not route_left and not route_right:
if delivery_weight(cities, orders) <= max_weight:
delivery_routes.append([cities[0], cities[1]])
elif route_left and not route_right:
city_appear_only_in_route_left(delivery_routes, route_left, cities,
orders, max_weight)
elif not route_left and route_right:
city_appear_only_in_route_right(delivery_routes, route_right,
cities, orders, max_weight)
return delivery_routes
El algoritmo es bastante sencillo:
- Generamos un espacio «savings», con los ahorros ordenados
- En base los savings, si las ambas ciudades están en ruta y son iguales, pasamos al siguiente
- Si solo una de los dos, buscamos si lo podemos delante o detrás dependiendo en que posición aparece
- Miramos, sin el par se considera para unir las dos listas (están en los extremos)
Aunque lo mejor, para entenderlo es bajarse el repo y trastear