Ruteo

Sistema de optimización para el ruteo dinámico de vehículos con ventanas de tiempo
Mi Caso de ruteo dinámico de vehículos con ventanas de tiempo es el de un delivery que entrega productos a domicilio, en el que cada entrega debe realizarse en una determinada banda horaria, elegida por el cliente. Para realizar la entrega el delivery cuenta con una flota de vehículos.
En nuestro caso lospedidos se van realizando a medida que transcurre el tiempo, es decir: inicialmente no hay pedidos para entregar y a medida que los clientes van realizando pedidos, estos se ingresan al sistema.
Nuestro objetivo para resolver el problema es encontrar la mejor manera de armar los recorridos de los vehículos logrando emplear la menor cantidad de vehículos posibles, recorriendo la menor distancia yminimizando los tiempos de espera de un vehículo entre una entrega y la siguiente.
Esta empresa cuenta con una flota de motos y al momento de hacer su pedido los clientes indican en que horario quieren recibirlo.
En la actualidad, hay una persona que se dedica a revisar los pedidos pendientes y organizarlos en recorridos que luego son asignados a las motos.
Esto tiene una serie de desventajas, comopor ejemplo que la calidad de los recorridos armados depende fuertemente de la habilidad de la persona que realiza la tarea Y del conocimiento que tiene de las distintas calles y barrios. Y que los recorridos producidos difícilmente logren aprovechar al máximo la capacidad de la flota de motos.
En lugar de utilizar un mapa de calles, vamos a utilizar una cuadricula como las que se usan en lasguías de transportes para definir el área donde se realiza la distribución de los pedidos. De esta manera queremos independizarnos del recorrido detallado que realiza la moto y solo nos fijamos entre que casillas se mueve.
Por otro lado, tenemos los pedidos que además de tener una banda horaria tienen un tamaño que podría corresponderse a su volumen o peso, y cuyo destino está ubicado en una casilladel mapa. Como dije antes, estos pedidos no se conocen inicialmente sino que van ingresando a medida que transcurre el horario de atención del delivery.
Nuestro objetivo es lograr encontrar soluciones que cumplan los que dice el slide.
Minimizar la cantidad de viajes para realizar las entregas, esto permite tener un flota que no sea excesivamente grande y con vehículos sin utilizar.
Minimizar eltiempo de espera entre entregas consecutivas, permite realizar mas entregas en la misma cantidad de tiempo.
Minimizar la distancia recorrida, va a permitir realizar un ahorro en el uso de combustible.
Maximizar la capacidad utilizada en cada vehículo, va a permitir poder enviar mas pedidos en un recorrido.
Vamos a suponer que los vehículos tienen velocidad constante, lo cual nuevamente no escierto, pero dado que los vehículos tienen características similares, seguramente se puede encontrar un estimador que indique la velocidad promedio dentro de la ciudad.
Por ultimo, los pedidos que ingresan son factibles, esto significa que desde el momento en el que entran en el sistema alcanza el tiempo para realizar el viaje hasta el cliente y cumplir con la ventana horaria.
El algoritmo quepropongo parte de una solución inicial vacía, lo cual representa que el delivery acaba de abrir y está esperando que ingresen pedidos.
Cuando ingresa un nuevo pedido al sistema hay que incorporarlo a la solución del problema, para realizar esta tarea encontramos como deseables los siguientes atributos:
-Debe ser rápida, ya que podrían entrar muchos pedidos en forma consecutiva y con ventanas detiempo con pronto vencimiento
-La solución resultante debe ser factible, es decir: luego de insertar el pedido en la solución queremos que los recorridos que maneja el sistema puedan ser cumplidos.
-Debe minimizar el costo de la solución, sería deseable que al insertar un pedido nuevo en una solución, la solución resultante fuera la mejor que se podría obtener al insertar ese pedido.
Para...