UNIVERSIDAD NACIONAL DEL LITORAL FACULTAD DE INGENIERÍA QUÍMICA DEPARTAMENTO DE INGENIERÍA...
-
Upload
pilar-maestre-martin -
Category
Documents
-
view
217 -
download
0
Transcript of UNIVERSIDAD NACIONAL DEL LITORAL FACULTAD DE INGENIERÍA QUÍMICA DEPARTAMENTO DE INGENIERÍA...
UNIVERSIDAD NACIONAL DEL LITORALFACULTAD DE INGENIERÍA QUÍMICA
DEPARTAMENTO DE INGENIERÍA INDUSTRIAL
UN AMBIENTE AMIGABLE PARA RUTEO Y PROGRAMACION DE VEHICULOS
Bernardo Páez de la Torre - Pedro A. González Rossia
Lineamientos de la Presentación
• Motivación
• Características del enfoque de solución adoptado
• Requerimientos del ambiente
• Arquitectura del ambiente
• Breve ilustración de la implementación realizada
• Conclusiones
• Tareas Futuras
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Motivación
• Actualmente, los costos logísticos constituyen, en promedio,
aproximadamente un 12 % del costo de los productos.
• Los problemas reales de ruteo y programación de vehículos
(R&P) son inherentemente complejosson inherentemente complejos.
• Deben abordar una amplia variedad de restricciones y amplia variedad de restricciones y
preferenciaspreferencias que pueden ser difíciles de expresar en un
modelo computacional y que están asociadas a un conjunto
de medidas de performance generalmente conflictivasmedidas de performance generalmente conflictivas.
• Los procedimientos puramente automáticos de R&P no son
suficientemente realistas dado que ignoran el rol crucial del el rol crucial del
experto humanoexperto humano.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
• Dado que la mayoría de los problemas R&P son NP-hardNP-hard, los métodos empleados para hallar soluciones óptimas sufren un crecimiento exponencial de la carga computacional con el
tamaño del problema. • Existe una amplia variedad de problemas reales de R&Pvariedad de problemas reales de R&P
que surgen al considerar diferentes características del diferentes características del problemaproblema (naturaleza de la demanda, tipo y tamaño de la flota disponible, costos, etc.) y restriccionesrestricciones (relacionadas a los vehículos, a los clientes, a ambos, etc.).
• Por lo tanto, hay una real necesidad por ambientes de real necesidad por ambientes de soportesoporte que sean capaces de encapsular diferentes metodologías para resolver varios tipos de problemas.
Motivación (cont.)
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia,P.
Diferentes Enfoques de Solución
• Modelos de Programación Matemática
• Heurísticas
• Algoritmos basados en grafos
• Algoritmos genéticos
• …
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
• Dado que la mayoría de los problemas R&P son altamente complejos, las heurísticas y técnicas para obtener las heurísticas y técnicas para obtener soluciones sub-óptimas se han popularizadosoluciones sub-óptimas se han popularizado.
• Diferentes tipos de heurísticasDiferentes tipos de heurísticas, apropiadas en distintas situaciones, han sido propuestas para diversas clases de problemas R&P.
• Como las diferentes heurísticas demandan distintas distintas representaciones del problemarepresentaciones del problema es necesario contar con un ambiente que sea capaz de encapsular a todas ellas.
• La representación del problema que se adopte debe ser además apropiada cuando otros enfoques de solución (por ej. Modelos de Programación Matemática) son elegidos.
Características del Enfoque de Solución Adoptado
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Requerimientos del Ambiente
• Representación no específica del conocimiento del
dominio
• Potencia
• Configurabilidad
• Adaptabilidad a diversos tipos de problemas
• Integración con otros sistemas
• Capacidad de visualización en mapas
• Amigabilidad e interacción con el usuario
• Reactividad
• Posibilidad de introducir cambios manuales
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Arquitectura del Ambiente
• Basado en tecnología orientada a objetos.
• Implementado en el ambiente de desarrollo KAPPA-PC 2.4.
• Puede ser descripto en término de tres paquetes:
» Paquete de Conocimiento del Dominio
» Paquete de Resolución de Problemas
» Paquete de Interfaz
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Paquete de Conocimiento del Dominio
Contiene la información relevante para describir:
• el dominio de aplicación (datos casi permanentes que describen
sitios a visitar, rutas, vehículos, etc.).
• los datos temporarios/específicos del problema (ventanas de
tiempo, cantidades colectadas/entregadas).
• la solución del problema o las soluciones alternativas evaluadas
(planes de ruteo, “tours”, agendas de vehículos).
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
RouteIDTypeDistance
EvaluateNorm1Distance()EvaluateNorm2Distance()CalculateAverageSpeed()
SiteIDNameXCoordinateYCoordinate
Neighbors?()
+1..*+2,2 connect
PickUpVisitDeliveryQuantity
DeliveryVisitPickUpQuantity
BackHaulVisitPickUpQuantityDeliveryQuantity
ServicePoint
VisitTimeWindowArrivalTimeDepartureTime
ServiceTime?()+0..1
predecessor+0..1
RoutingPlanIDTotalDistanceTotalCost
TourIDTotalDistanceTotalTimeCost
InitialTime?()FinalOperation()
VehicleIDMaximumOperationTimeCapacityForbiddenSitesAssignmentCost
RemainingCapacity?()
+1..1 +1..1
assigned
Depot location
Modelo de Clases de Dominio
IX ELAVIO – Vaquerías, Córdoba –
Páez de la Torre, B. & González Rossia, P.
Paquete de Resolución de Problemas
• Encapsula algoritmos heurísticos de construcción de tours y
operadores de mejora para resolver problemas de R&S.
• Además puede, automáticamente y en forma transparente al
usuario, crear el correspondiente modelo matemático,
resolverlo y presentar los resultados. Se ha integrado a este
ambiente el lenguaje GAMS.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Paquete de Resolución de Problemas (cont.)
Se ha seleccionado una metodología jerárquica orientada a tareas para
el modelado de :
- métodos heurísticos de R&S que generan soluciones iniciales.
- metodologías de mejora que apuntan a aumentar la calidad de
estas soluciones.
- facilidades interactivas dirigidas por el usuario que modifican
una solución existente a través de la interacción por medio de
una interfaz gráfica activa.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
comprises
Body
execute()
TaskVersion
Precondition Postcondition
Task
taskID : Integertypepurpose : String
selectVersion()
1..1
0..1
1..1
0..1 task-specification
1..1
1..*
1..1
1..*
1..1
1..*
1..1
1..*
variant1..*
1..*
1..*
1..*
precondition
1..*
1..*
1..*
1..*
postcondition
1..*
1..*
1..*
temporal-link
1..*
Metamodelo jerárquico orientado a tareas
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Modelo jerárquico orientado a tareas
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Se
com
pon
e d
e
CALCULAR-COORD-POLARES ORDENAR-VISITAS ASIGNAR-VEHICULOS
METODO-BARRIDO
Es
var
ian
te d
e
AGRUPAR VISITAS
METODO-AHORRO METODO-RADIO/BARRIDO
Antes de Antes de
Contiene facilidades para:
• Definir, acceder y modificar entidades del paquete de
conocimiento del dominio.
• Soportar la definición y modificación de problemas de
R&S, así como el monitoreo de las metodologías de
solución implementadas.
• Soportar la visualización, inspección y análisis de
resultados.
• Realizar actividades de modificación interactiva.
Paquete Interfaz
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Breve Ilustración de la Breve Ilustración de la Implementación RealizadaImplementación Realizada
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Posibilidad de trabajar en distintos tipos de
problemas
Opciones relacionadas Opciones relacionadas a los tours. a los tours.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Selección de Selección de actividades a actividades a través de menúes.través de menúes.
Alternativas para
“clustering”
Alternativas para generación
de tours
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Modelos matemáticos
Métodos heurísticos
Información desplegada al hacer clic sobre el icono
de una visita
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Generación de distintos reportes...
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Cruces
Arcos largos
Son síntomas de una mala solución...IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Cruces
Arcos largos
Se deben observar patrones deseables en la solución
Sin crucesSin superposición
Tours con forma de lágrimaIX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Posibilidad de mejorar soluciones iniciales obtenidas
con heurísticas
Objetivos alternativos a minimizar:
distancias o función de costos
Operadores intrarruta e interruta
Operadores alternativos
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Se distinguen patrones deseables...
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Podría intentarse relocalizar Knoxville...
Facilidades de mejora
interactiva
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
El sistema no permite tomar
decisiones infactibles
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Reporte del cronograma de visitas para cada vehículo...
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
El usuario puede generar y/o modificar tours manualmente
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
La capacidad remanente del vehículo no alcanza para atender
el requerimiento de Chicago
Conclusiones
Se han presentado avances en el desarrollo de un ambiente de R&S
que proveen un marco amigable donde el usuario puede:
• Definir una variedad de problemas empleando una interfaz
orientada a menúes.
• Recurrir a diferentes métodos de solución para generar y explorar
soluciones alternativas del problema en estudio.
• Evaluar la calidad de cada solución obtenida a través de distintas
medidas de performances y de una representación visual.
• Mejorar la calidad de una dada solución aplicando operadores de
mejora.
• Modificar soluciones manualmente por medio de acciones dirigidas
con el mouse. IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Tareas Futuras
• Desarrollo e incorporación de mejores algoritmos heurísticos de
solución y “clustering”
• Mejora de las facilidades de ayuda existentes
• Generación automática de información acerca de adyacencia de
sitios con el fin de mejorar la implementación actual de los
operadores de mejora intra e inter-ruta.
• Definición de interfaces con Sistemas de Información Geográfica
comerciales.
No se esperan dificultades puesto que la orientación a objetos
subyacente asegura una construcción modular del sistema y una
fácil modificabilidad.
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.
Fin de la presentación
Gracias por su atención
IX ELAVIO – Vaquerías, Córdoba – Páez de la Torre, B. & González Rossia, P.