Muelles y contenedores vacíos: dos artículos de investigación en nuestro planificador

Un modelo clásico de enrutamiento de vehículos comprueba cada ruta por separado. Cada ruta tiene su propia capacidad, sus propias ventanas horarias y su propio conductor, y las rutas solo se encuentran en el coste total. Eso es lo que hace que el problema sea tratable. También es la razón por la que tantos planes optimizados se desmoronan en el patio.

En el transporte de mercancías hay dos cosas que rompen esa independencia. Un muelle puede atender a un camión a la vez, sea de la ruta que sea. Un contenedor vacío que se lleva una ruta ya no está ahí para la siguiente. Estudiamos cómo la investigación operativa trata ambas cosas e incorporamos esas ideas al planificador que mueve el optimizador de Transportial y /vrp/solve.

Muelles: Bombelli y Fazi (2022)

A. Bombelli y S. Fazi estudiaron camiones que recogen carga aérea de transitarios y la entregan a agentes de handling en un aeropuerto. Un agente de handling reserva para ellos solo uno o dos muelles. Su artículo lo modela como un problema de recogida y entrega con ventanas horarias en el que un muelle no puede atender a más camiones de los que admite.

Su heurística es una búsqueda adaptativa de gran vecindario. Cada ruta sigue siendo factible por sí sola, pero el plan en su conjunto puede sobrepasar la capacidad de un muelle a cambio de una penalización. Después de cada inserción, un resolutor recorre los conflictos de muelle en orden cronológico. En cada uno retrasa el camión que menos hay que desplazar, lo que no cuesta nada si ese camión tiene holgura.

Sus conclusiones merecen conocerse si planificas con muelles:

• Sin coordinación, los camiones hacían cola hasta unas tres horas, y algunos planes se volvían infactibles.
• Coordinar los muelles redujo el tiempo de recorrido entre un 2 y un 19%.
• Un segundo muelle importaba sobre todo para la factibilidad: los dos muelles estuvieron ocupados a la vez menos del 10% del tiempo.

Lo que construimos

Nuestro planificador mantiene una línea de tiempo con un límite por cada lugar: un muelle, una rampa, un atraque o un apartadero ferroviario, igual para todos los modos. La línea de tiempo contiene las estancias de todas las rutas del plan. También contiene lo que está ocupado desde fuera del plan: otros viajes que ya están en ese lugar y franjas horarias de muelle ya reservadas.

Cuando el planificador calcula los horarios de una ruta, consulta la línea de tiempo en cada parada con límite. El servicio empieza en cuanto hay un muelle libre durante todo el servicio, si las ventanas horarias aún lo permiten. La espera cuenta como espera real, en la jornada del conductor y en el tiempo y el coste de la ruta. Cada parada con límite cuesta una consulta, así que probar una candidata sigue siendo barato, y un plan sin límites de muelle funciona exactamente igual que antes.

Aquí nos apartamos del artículo a propósito. Nuestra búsqueda también hace malabares con los relojes de los conductores, los remolques, los compartimentos y el stock de equipo, y un muelle con exceso de reservas haría inciertos todos esos horarios. Por eso mantenemos factible en muelles cada plan que maneja la búsqueda:

• Hacer sitio. Cuando una ruta candidata no puede esperar sin salirse de sus ventanas horarias, las rutas que le estorban se programan después de ella si aún encajan. Es el "cede el paso el camión que puede desplazarse" del artículo. La candidata paga su tiempo adicional, y si ningún desplazamiento funciona, la inserción se rechaza.
• El resolutor. Después de cada movimiento aceptado, una ruta que espera obtiene el muelle primero cuando la ruta que lo ocupa podría esperar con menos coste. Normalmente se trata de un desplazamiento dentro de la holgura, y el intercambio solo se conserva cuando reduce el tiempo total de las dos rutas.
• Reservas fijas. Los viajes existentes y las franjas horarias reservadas nunca se mueven.

Si prefieres permitir el exceso de reservas, configura la regla dock_capacity en modo aviso. Entonces una ruta puede sobrepasar la capacidad con un coste por minuto, y se informa de ello, como en el artículo.

Contenedores vacíos: Fazi, Choudhary y Dong (2023)

S. Fazi, S.K. Choudhary y J.X. Dong estudiaron empresas de acarreo de contenedores que trabajan desde una terminal interior. Un camión hace varios recorridos al día, con un contenedor cada vez.

• De dónde salen los vacíos. Una exportación necesita un contenedor vacío: del stock limitado de la terminal, de una importación que se acaba de descargar (un street-turn, es decir, reutilizar directamente un contenedor que acaba de quedar vacío para una carga de exportación) o de un depósito lejano.
• La restricción dura. El stock de vacíos de la terminal nunca puede bajar de cero, en ningún momento. Eso enlaza entre sí los recorridos de camiones distintos.
• Su solución. Lo resuelven de forma exacta, con branch-and-price. La restricción de stock solo se comprueba en los "instantes críticos": los momentos en que un recorrido retira un vacío, porque el stock solo puede quedarse corto cuando se retira una unidad. Un desvío al depósito se incluye en el coste del arco en lugar de convertirse en una parada adicional.

En casos reales cerca de Tilburg y 's-Hertogenbosch, sus planes fueron entre un 25 y un 43% más baratos que los que habían hecho los planificadores, con menos recorridos. También probaron qué ocurre cuando las condiciones son más ajustadas. Menos oportunidades de street-turn aumentaron los costes entre un 2 y un 12% en los casos reales, y empezar el día sin vacíos en stock los aumentó hasta un 27%.

Lo que construimos

Un envío ahora puede indicar que necesita una unidad en su recogida, que libera una después de su entrega, o ambas cosas. Una unidad puede ser un contenedor vacío, una caja móvil o un remolque de pool.

Cuando el planificador construye una ruta, busca un origen para cada unidad necesaria en este orden:

1. Una unidad liberada antes en la misma ruta, si ambos envíos permiten un street-turn y el camión puede llevarla entretanto.
2. El stock o depósito que menos distancia añade, recogido de camino a la recogida.

Una unidad liberada que no se reutiliza vuelve a un stock por el camino después de la entrega. Como los arcos de depósito del artículo, estas visitas se incluyen en el tramo como tiempo, distancia y coste, en lugar de convertirse en paradas.

Entre rutas, un único registro contiene cada stock controlado: su nivel inicial, las entradas y salidas conocidas, y las retiradas y devoluciones de cada ruta. Siguiendo el artículo, solo comprueba un stock cuando se retira una unidad. Una retirada que dejaría un stock por debajo de cero pasa a su siguiente origen, y si no queda ninguno, decide la regla equipment_stock. Los viajes que ya existen cuentan con sus retiradas y devoluciones pendientes.

No usamos branch-and-price. Una búsqueda de gran vecindario desmonta planes y los reconstruye, y eliminar una ruta puede dejar a otra sin el contenedor vacío con el que contaba. Por eso la búsqueda penaliza cada unidad que falta como si fuera un envío que se queda fuera, y la pasada final busca otro origen o elimina lo que siga faltando. El plan que recibes nunca envía dos camiones a por el último vacío del patio.

Donde se encuentran los dos

Lo interesante está donde se tocan los dos mecanismos. Cuando el planificador reprograma una ruta por un muelle, el momento en que esa ruta retira o devuelve un contenedor se mueve con ella. Si una devolución se retrasa más allá de la retirada de otra ruta, un stock que parecía suficiente puede quedarse corto de repente. En nuestro planificador, una ruta reprogramada lleva consigo su plan de equipo, así que el registro de stock siempre refleja los horarios reales de la ruta.

Para eso sirve ponerlo todo en una sola búsqueda. Con herramientas separadas, nadie se daría cuenta. La pantalla de muelles retrasaría un camión, el departamento de vacíos tendría razón sobre el stock de la mañana, y el plan fallaría igualmente.

Lo que dejamos fuera

• Muelles separados de carga y de descarga, y muelles reservados para determinados tipos de vehículo. Todos los muelles operativos de un emplazamiento cuentan juntos.
• Pools de chasis. Se planifica el origen del contenedor; un pool de chasis compartido entre camiones, no.
• Tipos de contenedor equivalentes (grupos de tamaño y tipo ISO) y capacidad del patio. Los tipos deben coincidir exactamente, y las devoluciones nunca se rechazan por un patio lleno.
• Stock de equipo y servicios regulares de tren o barcaza en una misma solicitud. Por ahora, planifica los tramos por carretera como envíos.

Lee los artículos

• A. Bombelli and S. Fazi (2022). The ground handler dock capacitated pickup and delivery problem with time windows: a collaborative framework for air cargo operations. Transportation Research Part E 159, 102603.
• S. Fazi, S.K. Choudhary and J.X. Dong (2023). The multi-trip container drayage problem with synchronization for efficient empty containers re-usage. European Journal of Operational Research 310(1), 343–359.

Nos basamos en el trabajo publicado. Los autores no participaron, y cualquier deficiencia de nuestra adaptación es nuestra. Para ver qué más decide el planificador en la misma búsqueda, lee Una búsqueda, todo el plan de transporte. Para los campos que debes usar, consulta la guía de VRP multimodal.