1 Google Maps para la Optimización de RutasGMOR Google Maps para la Optimización de Rutas
2 Índice Introducción Problema de Enrutamiento de Vehículos (VRP)Problemas Clásicos Nuestro Caso Práctico: Transporte Escolar Método de Resolución Demo Futuro Conclusiones
3 Introducción - SIG ¿Qué es un SIG? Un Sistema de Información Geográfica es una integración organizada de hardware, software, datos geográficos y personal, diseñado para capturar, almacenar, manipular, analizar y desplegar en todas sus formas la información geográficamente referenciada con el fin de resolver problemas complejos de planificación y gestión.
4 Introducción – Google Maps¿Qué es Google Maps? Google Maps es el nombre de un servicio gratuito de Google. Es un servidor de aplicaciones de mapas en Web. Ofrece imágenes de mapas desplazables, así como fotos de satélite del mundo entero e incluso la ruta entre diferentes ubicaciones.
5 Introducción – Google MapsHistoria Primer anuncio el 8 de Febrero de 2005 Está desarrollado en Javascript En Junio de 2005 fueron añadidos mapas de carreteras El mayor responsable de las imágenes de Google Maps es QuickBird En Julio de 2005 se lanza la vista dual
6 Introducción – Google MapsAPI Permite insertar un completo Google Map en páginas Web externas a Google Inicialmente no podía hallar direcciones Existen dos versiones Gratuita Empresas Mapas proporcionados principalmente por TeleAtlas
7 Problema de Enrutamiento de Vehículos (VRP)Características de los problemas Los clientes Los depósitos Los vehículos Flota homogénea Flota heterogénea
8 Problemas Clásicos El problema del viajante de comercio (TSP)El problema de los m viajantes de comercio (m-TSP) El problema con capacidades (CVRP)
9 Nuestro Caso Práctico: Transporte EscolarDisponemos de un conjunto de puntos Salida Paradas Llegada
10 Nuestro Caso Práctico: Transporte EscolarComplejidad del problema:
11 Método de Resolución Algoritmo de ahorros de Clarke & Wright (Savings Algorithm)
12 Mejoras mediante búsquedas locales2-Opt 3-Opt Factorial
13 2-Opt
14 3-Opt
15 Factorial
16 La aplicación: GMOR Demo
17 Futuro Ampliaciones del problema Otras heurísticas clásicasEl problema con flota heterogénea El problema con ventanas de tiempo Otras heurísticas clásicas Algoritmo de ahorros basado en matching Búsquedas locales multi-ruta Transferencias cíclicas
18 Conclusiones Mapas digitales Ventajas Desventajas Gran personalizaciónAlta interacción con el mapa Información que proporcionan Desventajas Limitaciones en las operaciones
19 Conclusiones Resolución de problemas de enrutamientoAlgoritmos clásicos Mejoras con búsquedas locales Posibilidad de depurar los algoritmos
20 Preguntas ¿Alguna pregunta?
21 Gracias por su atención.Fin Gracias por su atención.