logo móvil
Contáctanos

Análisis competitivo de algoritmos para un problema de distribución en línea

Autores: Barba, Alessandro; Bertazzi, Luca; Golden, Bruce L.

Idioma: Inglés

Editor: MDPI

Año: 2024

Descargar PDF

Acceso abierto

Artículo científico
2024

Análisis competitivo de algoritmos para un problema de distribución en línea


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Problema de distribución en línea
Cotizaciones de precio de transporte
Costo de penalización
Costo de inventario
Algoritmo en línea
Ratio competitivo

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 27

Citaciones: Sin citaciones


Descripción
Estudiamos un problema de distribución en línea en el que un productor debe enviar una carga desde un origen hasta un destino. En cada período de tiempo antes de la fecha límite, solicitan cotizaciones de precios de transporte y tienen que decidir si aceptar o no aceptar el precio mínimo ofrecido. Si este precio no es aceptado, tienen que pagar un costo de penalización, que puede ser el costo de solicitar nuevas cotizaciones, el costo de penalización por una entrega tardía o el costo de inventario para almacenar la carga durante cierto tiempo. El objetivo es minimizar la suma de los costos de transporte y de penalización. Este problema tiene aplicaciones interesantes en el mundo real, dado que las cotizaciones de transporte se pueden obtener de sitios web profesionales en la actualidad. Mostramos que el algoritmo en línea clásico utilizado para resolver el conocido problema de la Secretaria no es capaz de proporcionar, en promedio, soluciones efectivas a nuestro problema, dada la compensación entre los costos de transporte y de penalización. Por lo tanto, diseñamos dos clases de algoritmos en línea. La primera clase se basa en un tiempo dado de aceptación, mientras que la segunda se basa en un precio umbral dado. Demostramos formalmente la relación de competencia de cada algoritmo, es decir, el rendimiento en el peor de los casos del algoritmo en línea con respecto a la solución óptima del problema fuera de línea, en el que todos los precios de transporte se conocen al principio, en lugar de revelarse con el tiempo. Los resultados computacionales muestran el rendimiento de los algoritmos en promedio y en el escenario del peor de los casos cuando los precios de transporte se generan en función de distribuciones de probabilidad dadas.

Otros recursos que podrían interesarte

Temas Virtualpro