Page 11 - Revista 2018 ultima

Revista de la Facultad de Ingeniería, Año 5, Número 1de Ingeniería, Año 5, Número 1

R
Ruteo de vehículos: uteo de vehículos:

desafíos, software y beneficiosesafíos, software y beneficios
d

MSc. Ing.MSc. Ing. Omar Viera

MSc en Ingeniería en Física, KTH, Estocolmo, en Ingeniería en Física, KTH, Estocolmo, en Ingeniería en Física, KTH, Estocolmo,
Suecia.uecia.
S
Profesor Titular, Grado 5, Departamento de rofesor Titular, Grado 5, Departamento de rofesor Titular, Grado 5, Departamento de
P P
I I Investigación nvestigación nvestigación O O I I Instituto nstituto nstituto de e e
Operativa, perativa, perativa,
d d
Computación, omputación, omputación, Facultad acultad acultad de e e Ingeniería, ngeniería, ngeniería,
d d
F F
I I
C C
Universidad de la República.niversidad de la República.
U
Tutor e Investigador de la Facultad de utor e Investigador de la Facultad de utor e Investigador de la Facultad de
T T
I
Ingeniería, UDE.ngeniería, UDE.
Consultor especialista en Optimización y Ruteo. nsultor especialista en Optimización y Ruteo. nsultor especialista en Optimización y Ruteo.

M
MSc. Ing. Sc. Ing. Martín Varela
MSc en Informática, PEDECIBA, UdelaR. Ing. en Sc en Informática, PEDECIBA, UdelaR. Ing. en Sc en Informática, PEDECIBA, UdelaR. Ing. en
M M
C
Computación, Facultad de Ingeniería, UdelaR.omputación, Facultad de Ingeniería, UdelaR.
Profesor Asistente Grado 2, Departamento de rofesor Asistente Grado 2, Departamento de rofesor Asistente Grado 2, Departamento de
P P
d d
I I Investigación nvestigación nvestigación O O Instituto nstituto nstituto de e e
I I
Operativa, perativa, perativa,
C
Computacióomputación, Facultad de Ingeniería, UdelaR.
J J
Jefe de Producto fwLogistic, Gerente del Área de efe de Producto fwLogistic, Gerente del Área de efe de Producto fwLogistic, Gerente del Área de
Optimización y Ruteo, ICA.ptimización y Ruteo, ICA.
O
Introducción
L L
Los Problemas de Ruteo de Vehículos buscan determinar un conjunto de rutas de os Problemas de Ruteo de Vehículos buscan determinar un conjunto de rutas de os Problemas de Ruteo de Vehículos buscan determinar un conjunto de rutas de
costo mínimo teniendo en cuenta las limitaciones operativas de cada caso. Estas osto mínimo teniendo en cuenta las limitaciones operativas de cada caso. Estas osto mínimo teniendo en cuenta las limitaciones operativas de cada caso. Estas
c c
l l
limitaciones, también llamadas restricciones, son las capacidades de la flota de imitaciones, también llamadas restricciones, son las capacidades de la flota de imitaciones, también llamadas restricciones, son las capacidades de la flota de
vehículos, los horarios de atención de los clientes (ventanas horarias), las rarios de atención de los clientes (ventanas horarias), las rarios de atención de los clientes (ventanas horarias), las
compatibilidades entre productos/clientes y vehículos y cualquier otro tipo de ompatibilidades entre productos/clientes y vehículos y cualquier otro tipo de ompatibilidades entre productos/clientes y vehículos y cualquier otro tipo de
c c
c
consideración relevante para la operativa. onsideración relevante para la operativa.
S S
Se entiende por ruta una secuencia ordenada de visitas y/o clientes y el e entiende por ruta una secuencia ordenada de visitas y/o clientes y el e entiende por ruta una secuencia ordenada de visitas y/o clientes y el costo puede
d d
definirse como el kilometraje y/o el tiempo total recorrido por la flota de vehículos.efinirse como el kilometraje y/o el tiempo total recorrido por la flota de vehículos.efinirse como el kilometraje y/o el tiempo total recorrido por la flota de vehículos.
Dicho de otra forma, el VRP trata sobre como modelar y resolver problemas de icho de otra forma, el VRP trata sobre como modelar y resolver problemas de icho de otra forma, el VRP trata sobre como modelar y resolver problemas de
D D
d d
distribución y/o recolección de productos y/o servicios al menor costo posible.istribución y/o recolección de productos y/o servicios al menor costo posible.istribución y/o recolección de productos y/o servicios al menor costo posible.
E E
En este artículo intentaremos analizar más en detalle este problema con tres n este artículo intentaremos analizar más en detalle este problema con tres n este artículo intentaremos analizar más en detalle este problema con tres
o o
objetivos en mente. Por un lado, plantear los desafíos y dificultades propias que bjetivos en mente. Por un lado, plantear los desafíos y dificultades propias que bjetivos en mente. Por un lado, plantear los desafíos y dificultades propias que
p p
presentan este tipo de problemas. Por otro lado, establecer algunas características resentan este tipo de problemas. Por otro lado, establecer algunas características resentan este tipo de problemas. Por otro lado, establecer algunas características
que debe tener un software de ruteo. Finalmente, buscamos orientar al lector sobre r un software de ruteo. Finalmente, buscamos orientar al lector sobre r un software de ruteo. Finalmente, buscamos orientar al lector sobre
e e
el potencial beneficio de buscar soluciones informatizadas para solucionar el VRP. l potencial beneficio de buscar soluciones informatizadas para solucionar el VRP. l potencial beneficio de buscar soluciones informatizadas para solucionar el VRP.
Los problemas del Problema de Ruteo de Vehículosos problemas del Problema de Ruteo de Vehículos
L
P P
Para comenzar y teniendo en cuenta la definición anterior lo primero que surge es la ara comenzar y teniendo en cuenta la definición anterior lo primero que surge es la ara comenzar y teniendo en cuenta la definición anterior lo primero que surge es la
dificultad que implica encontrar el conjunto de rutas de menor costo. Existen ificultad que implica encontrar el conjunto de rutas de menor costo. Existen ificultad que implica encontrar el conjunto de rutas de menor costo. Existen
d d
muchas formas distintas (calles) para ir de un cliente a otro. Encontrar la mejor uchas formas distintas (calles) para ir de un cliente a otro. Encontrar la mejor uchas formas distintas (calles) para ir de un cliente a otro. Encontrar la mejor
m m
entre todas esas combinaciones es casi imposible si esa búsqueda se realiza en s esas combinaciones es casi imposible si esa búsqueda se realiza en s esas combinaciones es casi imposible si esa búsqueda se realiza en
f f forma manual, sin el apoyo de una computadora. Peor aún, habiendo encontrado el orma manual, sin el apoyo de una computadora. Peor aún, habiendo encontrado el orma manual, sin el apoyo de una computadora. Peor aún, habiendo encontrado el
mejor camino entre un cliente y otro, esas calles pueden no ser la mejor opción ejor camino entre un cliente y otro, esas calles pueden no ser la mejor opción ejor camino entre un cliente y otro, esas calles pueden no ser la mejor opción
m m
11