Optimización de rutas con Python: del Excel al solver

Casi todas las operaciones de reparto empiezan igual: una hoja de cálculo con las paradas del día, un planeador con quince años de calle y un ordenamiento hecho a mano. Funciona. Hasta que la operación crece, el planeador se va de vacaciones y nadie sabe reconstruir el criterio.

El salto al solver no requiere contratar un doctorado en investigación de operaciones. Requiere modelar bien el problema: nombrarlo con precisión, conseguir tres insumos que casi nunca están listos y medir antes de automatizar.

Primero: no es TSP, es VRP

El problema del agente viajero (TSP) tiene un vehículo que visita todas las paradas y regresa al origen. Rara vez es tu caso. Tienes flota, y en cuanto hay flota el problema es de ruteo de vehículos (VRP), formulado por Dantzig y Ramser en The Truck Dispatching Problem (Management Science, 1959).

La distinción importa porque el VRP casi nunca viene solo. Viene con restricciones, y cada restricción cambia el modelo:

Estos problemas son NP-difíciles (Lenstra y Rinnooy Kan, Complexity of Vehicle Routing and Scheduling Problems, Networks, 1981). No los vas a resolver por enumeración: un TSP simétrico de n paradas tiene (n−1)!/2 recorridos distintos. Por eso los solvers usan heurísticas de construcción más búsqueda local, no fuerza bruta.

Acción: antes de escribir una línea de código, escribe la definición formal en una página. Cuántos vehículos, capacidad homogénea o no, ventanas duras o suaves, uno o varios depósitos, y qué pasa si una parada no cabe en ninguna ruta.

Los tres insumos que nunca están listos

1. La matriz de distancias y tiempos real. No euclidiana. La distancia en línea recta ignora sentidos únicos, vueltas prohibidas, ríos y bardas. Además la matriz real es asimétrica: ir de A a B no cuesta lo mismo que de B a A. Puedes levantarla con un motor de ruteo sobre OpenStreetMap (OSRM o Valhalla, autoalojados) o con una API de matriz comercial. Ojo con el volumen: n paradas generan n² pares, así que cachea por par de nodos y por franja horaria.

2. Geocodificación confiable. En México la dirección postal es un campo de texto libre con colonia, código postal y a veces manzana y lote. Geocodifica una vez, valida el resultado contra una referencia conocida y guarda las coordenadas en tu maestro de clientes. Mide qué porcentaje de tus paradas tiene coordenada verificada en sitio contra coordenada interpolada sobre el eje vial: esa cifra es el techo de calidad de tu ruteo.

3. Demanda y restricciones por parada. Unidad consistente (cajas, kilogramos o metros cúbicos, elige una), tiempo de servicio estimado, ventana horaria y requisitos de vehículo. Si el tiempo de servicio no está en el modelo, el solver va a suponer que descargar un pallet toma cero minutos.

Acción: audita estos tres insumos esta semana y ponles un porcentaje de completitud. El solver no compensa datos faltantes; los amplifica.

Un CVRP que corre

Instala la biblioteca con pip install ortools. El siguiente ejemplo resuelve un CVRP de ocho paradas y un depósito con tres vehículos de capacidad limitada.

"""CVRP mínimo con Google OR-Tools: 1 depósito, 8 paradas, 3 vehículos."""

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def crear_datos():
    """El nodo 0 es el depósito. Distancias en metros, enteras."""
    return {
        # Matriz asimétrica de distancias reales de red vial.
        # Reemplázala por la salida de tu motor de ruteo.
        "distancias": [
            [0, 3460, 4490, 7480, 7430, 6570, 10150, 8930, 9740],
            [3340, 0, 8130, 9130, 7360, 6490, 14400, 5740, 11330],
            [4760, 8640, 0, 7270, 9340, 10080, 5480, 14490, 7770],
            [7040, 9180, 7030, 0, 15610, 5230, 9070, 15600, 14890],
            [7870, 7340, 8960, 14510, 0, 14190, 14450, 9000, 6390],
            [6510, 6400, 9870, 5570, 13460, 0, 13600, 11160, 16940],
            [10600, 13500, 6130, 8570, 14430, 13900, 0, 18850, 10860],
            [8900, 6130, 14340, 15480, 9620, 10880, 20130, 0, 15280],
            [9830, 11660, 8300, 15920, 6310, 16530, 10300, 15480, 0],
        ],
        # Demanda por nodo, en cajas. El depósito no demanda nada.
        "demandas": [0, 4, 3, 6, 2, 5, 3, 4, 2],
        # Capacidad de cada vehículo, en las mismas unidades.
        "capacidades": [12, 12, 12],
        "num_vehiculos": 3,
        "deposito": 0,
    }


def main():
    datos = crear_datos()

    # El manager traduce entre índices internos del solver y nodos del negocio.
    manager = pywrapcp.RoutingIndexManager(
        len(datos["distancias"]), datos["num_vehiculos"], datos["deposito"]
    )
    modelo = pywrapcp.RoutingModel(manager)

    # Costo de recorrer el arco entre dos nodos.
    def callback_distancia(indice_origen, indice_destino):
        origen = manager.IndexToNode(indice_origen)
        destino = manager.IndexToNode(indice_destino)
        return datos["distancias"][origen][destino]

    id_distancia = modelo.RegisterTransitCallback(callback_distancia)
    modelo.SetArcCostEvaluatorOfAllVehicles(id_distancia)

    # Dimensión de capacidad: acumula demanda a lo largo de cada ruta.
    def callback_demanda(indice_origen):
        origen = manager.IndexToNode(indice_origen)
        return datos["demandas"][origen]

    id_demanda = modelo.RegisterUnaryTransitCallback(callback_demanda)
    modelo.AddDimensionWithVehicleCapacity(
        id_demanda,
        0,                       # holgura: sin descarga parcial en ruta
        datos["capacidades"],    # cota superior por vehículo
        True,                    # cada ruta arranca con acumulado en cero
        "Capacidad",
    )

    parametros = pywrapcp.DefaultRoutingSearchParameters()
    # Heurística de construcción: arma una primera ruta factible rápido.
    parametros.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    # Búsqueda local guiada: mejora esa ruta escapando de óptimos locales.
    parametros.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    # Sin límite de tiempo la metaheurística no se detiene sola.
    parametros.time_limit.FromSeconds(10)

    asignacion = modelo.SolveWithParameters(parametros)
    if not asignacion:
        print("No se encontró ruteo factible. Revisa capacidades y demandas.")
        return

    distancia_total = 0
    for vehiculo in range(datos["num_vehiculos"]):
        indice = modelo.Start(vehiculo)
        ruta, carga, distancia = [], 0, 0
        while not modelo.IsEnd(indice):
            nodo = manager.IndexToNode(indice)
            carga += datos["demandas"][nodo]
            ruta.append(str(nodo))
            anterior = indice
            indice = asignacion.Value(modelo.NextVar(indice))
            distancia += modelo.GetArcCostForVehicle(anterior, indice, vehiculo)
        ruta.append(str(manager.IndexToNode(indice)))
        print(f"Vehículo {vehiculo}: {' → '.join(ruta)}")
        print(f"  distancia {distancia} m · carga {carga} cajas")
        distancia_total += distancia

    print(f"Distancia total: {distancia_total} m")


if __name__ == "__main__":
    main()

Dos detalles que cuestan horas si los detectas tarde. El solver trabaja con enteros: si necesitas decimales, escala (multiplica por 100 y divide al imprimir). Y PATH_CHEAPEST_ARC solo construye el punto de partida; la calidad la pone GUIDED_LOCAL_SEARCH con el tiempo que le des.

Acción: corre el script tal cual, verifica que la salida tenga sentido y recién entonces sustituye la matriz por la tuya.

El óptimo matemático no siempre es el operativo

El solver minimiza la función objetivo que le escribiste. El operador optimiza una función que tú no escribiste: dónde se puede estacionar, qué andén abre a las 7, en qué calle no cabe el rabón, con qué cliente conviene llegar temprano.

Tres causas frecuentes de que la ruta "óptima" se ignore:

1. Restricciones de acceso no modeladas: horarios de carga y descarga, altura o tonelaje restringido, plazas con acceso controlado.
2. Conocimiento de zona: un operador que repite territorio baja su tiempo de servicio porque ya sabe a quién buscar. Rotarlo por ahorrar kilómetros puede costar minutos.
3. Preferencias legítimas del equipo: continuidad de territorio, punto de comida, regreso a base.

Casi todo eso se modela. Costo fijo por vehículo para desincentivar abrir rutas, restricción de vehículos permitidos por nodo, penalización por dejar una parada fuera, ventanas horarias como dimensión de tiempo.

Acción: pide a los operadores que registren el motivo cada vez que se desvían de la ruta propuesta. Esa bitácora es tu backlog de restricciones faltantes, priorizado por frecuencia.

Cómo medir · la línea base va primero

Si no mediste antes, cualquier número posterior es una anécdota. Levanta al menos cuatro semanas de operación actual, con el mismo mix de clientes y la misma estacionalidad con la que vas a comparar.

Los kilómetros solos engañan: bajan si entregas menos. Por eso van normalizados y acompañados de una métrica de servicio.

Acción: define estas cinco métricas en una consulta versionada, no en una hoja manual, y déjala corriendo desde antes del piloto.

El patrón de despliegue: shadow mode primero

Un operador logístico no cambia su forma de despachar porque un script lo diga. El despliegue va por fases con criterio de salida explícito:

1. Shadow. El solver corre a diario en paralelo y nadie obedece su salida. Comparas ruta propuesta contra ruta ejecutada. Sales de esta fase cuando la propuesta es factible en la mayoría de los días y entiendes cada caso en que no lo fue.
2. Asistido. El planeador ve la propuesta y puede editarla. Registras cada edición y su motivo. Sales cuando las ediciones dejan de concentrarse en un mismo tipo de restricción faltante.
3. Automatizado con excepciones. El despacho toma la salida del solver y solo escala los casos marcados. Mantienes el registro de ediciones para siempre: es tu sistema de detección de deriva.

Acción: agenda la fase de shadow con fecha de fin y criterio de salida escrito. Sin eso, el piloto se vuelve permanente.

El trabajo real no está en el solver. Está en la matriz, en la geocodificación, en las restricciones que solo conoce quien maneja y en la disciplina de medir antes. OR-Tools es la parte que ya está resuelta.