Implementación de planos de corte para el problema de ruteo de vehículos con conflictos por vértices

Estudiamos en este trabajo el problema de ruteo de vehículos con conflictos por vértices (VRPVC), donde se combina el problema clásico de ruteo de vehículos (VRP) con el de coloreo de vértices de un grafo (VCP). El VRPVC consiste en determinar un conjunto de rutas para una flota de vehículos de mane...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Delle Donne, Diego, Koch, Ivo, Montiel, Santiago
Formato: Objeto de conferencia Resumen
Lenguaje:Español
Publicado: 2021
Materias:
Ciencias Informáticas
Ruteo de vehículos
Coloreo de grafos
Conflictos por vértices
Planos de corte
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/141574
http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-03.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-141574
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
Ruteo de vehículos
Coloreo de grafos
Conflictos por vértices
Planos de corte
spellingShingle Ciencias Informáticas
Ruteo de vehículos
Coloreo de grafos
Conflictos por vértices
Planos de corte
Delle Donne, Diego
Koch, Ivo
Montiel, Santiago
Implementación de planos de corte para el problema de ruteo de vehículos con conflictos por vértices
topic_facet Ciencias Informáticas
Ruteo de vehículos
Coloreo de grafos
Conflictos por vértices
Planos de corte
description Estudiamos en este trabajo el problema de ruteo de vehículos con conflictos por vértices (VRPVC), donde se combina el problema clásico de ruteo de vehículos (VRP) con el de coloreo de vértices de un grafo (VCP). El VRPVC consiste en determinar un conjunto de rutas para una flota de vehículos de manera tal de visitar a todos los clientes de un conjunto predeterminado (i.e., VRP) respetando la restricción adicional que impide que ciertos pares de clientes sean visitados por el mismo vehículo. Estos problemas surgen en diversos escenarios reales, como por ejemplo en la entrega de productos a clientes, donde la imposibilidad de ciertos productos para viajar en un mismo vehículo se debe a diversas restricciones como por ejemplo, no mezclar productos alimenticios con productos de limpieza, o productos que no toleran los mismos niveles de refrigeración. En este trabajo formulamos modelos de programación lineal entera para el VRPVC, combinando características de formulaciones existentes para VRP y VCP. Utilizamos como base para la construcción de nuestras formulaciones dos modelos clásicos de la literatura de VCP, así como dos modelos de VRP que se diferencian por la manera de eliminar subtours en las soluciones. De los modelos de VCP tomamos el modelo estandár y el de representantes asimétrico y de VRP, la formulación two-index de Laporte et al. que elimina subtours mediante una familia exponencial de desigualdades válidas y la formulación MTZ de Miller et al. Siguiendo esta misma línea, analizamos desigualdades válidas conocidas para los distintos modelos de VRP y VCP de la literatura, como las desigualdades Comb propuesta por Chvátal y Grótschel y Padberg y las Clique que plantearon Méndez-Díaz y Zabala. Analizamos la validez de estas desigualdades en los modelos de VRPVC y presentamos también nuevas familias de desigualdades válidas para algunos de los modelos propuestos. Implementamos algoritmos de separación para estas desigualdades (tanto las nuevas como las existentes) y evaluamos empíricamente el uso de las mismas mediante una experimentación computacional. Utilizamos para ello tanto instancias aleatorias como generadas a partir de instancias existentes en la literatura de VRP y VCP (i.e., adaptamos al VRPVC).
format Objeto de conferencia
Resumen
author Delle Donne, Diego
Koch, Ivo
Montiel, Santiago
author_facet Delle Donne, Diego
Koch, Ivo
Montiel, Santiago
author_sort Delle Donne, Diego
title Implementación de planos de corte para el problema de ruteo de vehículos con conflictos por vértices
title_short Implementación de planos de corte para el problema de ruteo de vehículos con conflictos por vértices
title_full Implementación de planos de corte para el problema de ruteo de vehículos con conflictos por vértices
title_fullStr Implementación de planos de corte para el problema de ruteo de vehículos con conflictos por vértices
title_full_unstemmed Implementación de planos de corte para el problema de ruteo de vehículos con conflictos por vértices
title_sort implementación de planos de corte para el problema de ruteo de vehículos con conflictos por vértices
publishDate 2021
url http://sedici.unlp.edu.ar/handle/10915/141574
http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-03.pdf
work_keys_str_mv AT delledonnediego implementaciondeplanosdecorteparaelproblemaderuteodevehiculosconconflictosporvertices
AT kochivo implementaciondeplanosdecorteparaelproblemaderuteodevehiculosconconflictosporvertices
AT montielsantiago implementaciondeplanosdecorteparaelproblemaderuteodevehiculosconconflictosporvertices
bdutipo_str Repositorios
_version_ 1764820459365335041

Ejemplares similares