Un algoritmo exacto basado en generación de columnas para resolver el problema de enrutamiento de vehículos de carga completa
Autores: Emre, Toygar; Erol, Rizvan
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Un algoritmo exacto basado en generación de columnas para resolver el problema de enrutamiento de vehículos de carga completa
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Estudio
Problema de entrega de carga completa
Empresa de logística turca
Sector de transporte líquido
Algoritmo exacto
Costos de transporte
Ventanas de tiempo
Tipos de remolques
Tipos de clientes
Tipos de productos
Capacidad de la flota
Puntos de partida
Tiempos de espera
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 34
Citaciones: Sin citaciones
Este estudio aborda una variante especializada del problema de entrega de carga completa inspirada por una empresa logística turca que opera en el sector del transporte de líquidos. Se propone un algoritmo exacto para el problema relevante, al cual no se ha aplicado enfoque exacto antes. Se introducen simultáneamente múltiples tipos de clientes y remolques, así como operaciones de lavado, durante el proceso de solución exacta, aportando nuevos aspectos al enfoque del algoritmo exacto entre los sistemas de carga completa en la literatura. El objetivo es minimizar los costos de transporte al abordar restricciones relacionadas con múltiples ventanas de tiempo, tipos de remolques, tipos de clientes, tipos de productos, una flota heterogénea con capacidad limitada, múltiples puntos de partida y diversas acciones como carga, descarga y lavado. Además, se proporciona la eliminación o reducción de los tiempos de espera a lo largo de las rutas de transporte. Para lograr soluciones óptimas, se propone un algoritmo exacto basado en el método de generación de columnas. También se emplea un algoritmo de inserción basado en rutas para rutas/columnas iniciales. En cuanto a la obtención de soluciones integrales en el algoritmo exacto, se incorporan tanto conjuntos dinámicos como estáticos de desigualdades válidas. Se utiliza un algoritmo de etiquetado para generar columnas dentro del algoritmo exacto acelerado a través de búsqueda bidireccional, relajación de ruta-ng, selección de subproblema y generación de columna heurística. Debido a la estructura dependiente del problema del método de generación de columnas y las técnicas de aceleración, se incluye una versión adaptada de ellos en el proceso de solución. El análisis de rendimiento, que se realizó utilizando conjuntos de datos artificiales basados en las operaciones reales de la empresa logística, demuestra que se pueden lograr brechas de optimalidad inferiores al 1% en tiempos razonables incluso para instancias a gran escala relevantes para la industria, como 120 clientes, 8 tipos de productos y 8 tipos de remolques, 4 ventanas de tiempo diarias y 40 puntos de partida.
Descripción
Este estudio aborda una variante especializada del problema de entrega de carga completa inspirada por una empresa logística turca que opera en el sector del transporte de líquidos. Se propone un algoritmo exacto para el problema relevante, al cual no se ha aplicado enfoque exacto antes. Se introducen simultáneamente múltiples tipos de clientes y remolques, así como operaciones de lavado, durante el proceso de solución exacta, aportando nuevos aspectos al enfoque del algoritmo exacto entre los sistemas de carga completa en la literatura. El objetivo es minimizar los costos de transporte al abordar restricciones relacionadas con múltiples ventanas de tiempo, tipos de remolques, tipos de clientes, tipos de productos, una flota heterogénea con capacidad limitada, múltiples puntos de partida y diversas acciones como carga, descarga y lavado. Además, se proporciona la eliminación o reducción de los tiempos de espera a lo largo de las rutas de transporte. Para lograr soluciones óptimas, se propone un algoritmo exacto basado en el método de generación de columnas. También se emplea un algoritmo de inserción basado en rutas para rutas/columnas iniciales. En cuanto a la obtención de soluciones integrales en el algoritmo exacto, se incorporan tanto conjuntos dinámicos como estáticos de desigualdades válidas. Se utiliza un algoritmo de etiquetado para generar columnas dentro del algoritmo exacto acelerado a través de búsqueda bidireccional, relajación de ruta-ng, selección de subproblema y generación de columna heurística. Debido a la estructura dependiente del problema del método de generación de columnas y las técnicas de aceleración, se incluye una versión adaptada de ellos en el proceso de solución. El análisis de rendimiento, que se realizó utilizando conjuntos de datos artificiales basados en las operaciones reales de la empresa logística, demuestra que se pueden lograr brechas de optimalidad inferiores al 1% en tiempos razonables incluso para instancias a gran escala relevantes para la industria, como 120 clientes, 8 tipos de productos y 8 tipos de remolques, 4 ventanas de tiempo diarias y 40 puntos de partida.