HEURÍSTICAS PARA RESOLVER EL PERIODIC VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

Abstract

Este TFG se centra en modelar y resolver un problema de rutas de vehículos de una empresa real. En concreto, el problema tratado es el Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), que consiste en planificar las rutas de una flota de vehículos, satisfaciendo las demandas de los clientes dentro de sus ventanas de tiempo, sin exceder la capacidad de los camiones. Además se impone una restricción de tiempo de conducción de máximo por camión.

Debido a la complejidad algorítmica del problema, se ha optado por un enfoque aproximado para su resolución. Los algoritmos desarrollados han sido el Push Forward Insertion (PFI) y el Constructive Greedy-Random (CGR) como constructivos, en combinación con diferentes búsquedas locales y el Variable Neighborhood Descent (VND) para mejorar las soluciones iniciales.

El objetivo de este trabajo es mejorar la operativa actual de la empresa, permitiendo reducir el número de camiones necesarios para los repartos y el tiempo de conducción de los conductores.