Una metodología de solución para el problema de ruteo de vehículos con demandas estocásticas

Abstract

El problema de ruteo de vehículos con demandas estocásticas es un problema crucial en transporte y logística, en donde un conjunto de vehículos sale de un depósito con carga completa para servir a un conjunto de clientes cuya demanda sólo es revelada en la ubicación de los mismos. Se trata de un problema de optimización combinatoria en la categoría NP-hard, el cual es modelado en este trabajo como un problema de programación estocástica de dos etapas bajo la política de optimización de diseño de rutas a priori. Esta tesis presenta una metodología de solución heurística para el problema de ruteo de vehículos en presencia de demandas estocásticas (VRPSD). El método se divide en dos fases: En la primera se genera un conjunto de ruta factibles mediante el enfoque de construcción route first - cluster second implementado sobre un espacio de búsqueda de subtours y tours del tipo del agente viajero; y en la segunda fase se utiliza un problema de partición de conjuntos para obtener las rutas que minimizan el costo esperado. Los tres primeros capítulos presentan el marco teórico, el estado del arte y algunos problemas de interés para la metodología; mientras que los capítulos cuatro a seis introducen el algoritmo propuesto, los resultados computacionales y las conclusiones de la metodología implementada.

Abstract: The Vehicle Routing Problem with Stochastic Demands (VRPSD) is a very important problem in the field of logistics and transportation, in which a set of vehicles depart from the depot with full load to serve a set of clients whose demands are not known with anticipation, which means that each client demand is known only when the vehicle reaches its location. This is a