Modelos de Programación de Rutas y Algoritmos de Resolución

Modelos de Programación de Rutas

• Camino crítico para encontrar la distancia más corta desde un punto de origen a uno de destino.

• Problema del viajante (Travelling Salesman Problem): desde un punto de origen hay que visitar un conjunto de destinos una sola vez y volver al punto de partida, de modo que la distancia recorrida sea mínima.

• Problema del transporte (VRP, Vehicle Routing Problem): plantea la elección de las mejores rutas contando con varios vehículos o con una capacidad máxima por vehículo (CVRP). Dependiendo de los parámetros del problema se pueden estudiar diferentes variantes del problema: VRP con múltiples almacenes (MDVRP), VRP periódico (PVRP), VRP de entrega dividida (SDVRP), VRP estocástico (SVRP), VRP con recogidas y entregas (VRPPD), VRP con backhauls (VRPB), VRP con ventanas de tiempo (VRPTW). Los algoritmos para este tipo de problemas se basan en los siguientes criterios:

• Entre varias rutas no debería haber cruces.

• El primer destino de una ruta debe ser el cliente más lejano, mientras que las distancias entre los sucesivos clientes deben ser lo más cortas posible, sobre todo si un cliente no puede recibir la entrega al momento de llegar y hay que realizar otra entrega para no estar ese tiempo inactivo.

• Distribución de productos desde distintos orígenes a diferentes destinos, según cantidades disponibles en origen (ofertas), cantidades solicitadas en destino (demandas) y los costes del transporte desde cada origen a cada destino. Si las cantidades de oferta no coinciden con la de demanda, se deben equilibrar ambas cantidades creando centros de origen o de destino ficticios a coste cero. Para resolver este problema se suelen usar los siguientes algoritmos:

• Esquina noroeste: se asigna el máximo de carga desde el primer origen al primer destino de una tabla que comienza en la esquina superior izquierda y se continúa del miso modo de forma sucesiva.
• Coste mínimo: el máximo de carga se va asignando a las ofertas o demandas de menor coste.
• Vogel: el máximo de carga se va asignando a las opciones que presenten mayor penalización por diferencia entre los menores costes.