Repartir tres rutas entre tres repartidores
El problema de asignación reparte personas entre tareas, una para cada una, de modo que el coste total sea el menor. Sirve para repartir rutas, turnos o aulas.
La panadería tiene tres repartidores y tres rutas. Cada repartidor tarda un tiempo distinto en cada ruta, y hay que decidir quién va a cuál.
Al final de esta lección
Nota
Puedo resolver un problema de asignación pequeño.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Problema de asignación | dar a cada persona una tarea distinta al menor coste total | |
| Matriz de costes | una tabla con lo que cuesta cada persona en cada tarea | |
| Permutación | una forma de ordenar los mismos elementos | [2, 0, 1] |
| Fuerza bruta | probar todas las opciones y quedarse con la mejor | |
| Problema de transporte | llevar mercancía de varios orígenes a varios destinos al menor coste |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La matriz de costes guarda todos los tiempos
Cada fila es un repartidor y cada columna es una ruta. La celda dice cuántos minutos tarda ese repartidor en esa ruta.
Una asignación da a cada repartidor una ruta distinta. Su coste es la suma de las tres celdas elegidas.
Ejemplo resuelto: minutos por repartidor y ruta
| Repartidor | Centro (0) | Puerto (1) | Norte (2) |
|---|---|---|---|
| Ana | 9 | 4 | 7 |
| Bruno | 6 | 8 | 5 |
| Carla | 9 | 3 | 8 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Con tres repartidores hay seis repartos posibles
El primer repartidor puede elegir entre 3 rutas, el segundo entre las 2 que quedan y el tercero se lleva la última. Son 3 2 1 = 6 repartos.
Cada reparto es una permutación de las rutas. El orden [2, 0, 1] significa: Ana va a la ruta 2, Bruno a la 0 y Carla a la 1.
Ejemplo resuelto: los seis repartos y su coste
| Orden | Ana, Bruno, Carla | Minutos |
|---|---|---|
| [0, 1, 2] | Centro, Puerto, Norte | 25 |
| [0, 2, 1] | Centro, Norte, Puerto | 17 |
| [1, 0, 2] | Puerto, Centro, Norte | 18 |
| [1, 2, 0] | Puerto, Norte, Centro | 18 |
| [2, 0, 1] | Norte, Centro, Puerto | 16 |
| [2, 1, 0] | Norte, Puerto, Centro | 24 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Calcula el coste de los seis repartos
docker exec jupyter python3 -c "import itertools; c = [[9, 4, 7], [6, 8, 5], [9, 3, 8]]; print(sorted((sum(c[i][p[i]] for i in range(3)), p) for p in itertools.permutations(range(3))))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Prueba todos los repartos con dos bucles
costs = [[9, 4, 7], [6, 8, 5], [9, 3, 8]]
orders = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
best_cost = 999
best_order = []
for order in orders:
total = 0
for courier in range(3):
total = total + costs[courier][order[courier]]
if total < best_cost:
best_cost = total
best_order = order
print("Reparto más barato:", best_order, "con", best_cost, "minutos")
# Cambia el 3 de Carla por un 10 y vuelve a ejecutar: ¿cambia el reparto?
Probar todos los repartos deja de ser posible
Con n repartidores hay n (n - 1) ... * 1 repartos, un número que se llama n factorial. Crece muy deprisa.
Con 5 repartidores son 120, con 10 son más de tres millones y con 15 son más de un billón. Un ordenador que pruebe un millón por segundo tardaría más de dos semanas.
Repartos posibles con 5, 10 y 15 personas
docker exec jupyter python3 -c "import math; print(math.factorial(5), math.factorial(10), math.factorial(15))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error muy común
Advertencia
Mucha gente cree que basta con dar a cada persona su ruta más barata. Pero dos personas pueden querer la misma. Ana toma el Puerto (4) y Bruno el Norte (5). A Carla le queda el Centro (9). Son 18 minutos, peor que los 16 del mejor reparto.
Hay métodos que no prueban todos los repartos
El método húngaro resuelve la asignación sin probar todas las opciones, y SciPy lo trae en linear_sum_assignment. Con 15 repartidores contesta al instante.
El problema de transporte es el hermano mayor: cada origen tiene varias unidades y cada destino pide varias. La asignación es un transporte con una unidad en cada sitio. Los dos se pueden escribir como programas lineales.
Resuelve la asignación con SciPy
docker exec jupyter python3 -c "from scipy.optimize import linear_sum_assignment; c = [[9, 4, 7], [6, 8, 5], [9, 3, 8]]; rows, cols = linear_sum_assignment(c); print(list(cols), c[0][cols[0]] + c[1][cols[1]] + c[2][cols[2]])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Para ir más lejos: cuatro repartidores
Añade un cuarto repartidor y una cuarta ruta a la matriz. ¿Cuántos repartos hay ahora? Prueba con linear_sum_assignment y comprueba que el mejor reparto sigue siendo el que esperabas.