Desarrollo de un método de resolución para el problema de rutas de vehículos con clientes backhaul

Abstract

El presente proyecto estudia una de las variantes del popular problema de rutas de vehículos, en concreto, la que admite clientes de tipo backhaul (clientes donde se recoge en lugar de entregar). Esta característica del problema se puede utilizar para plantear soluciones que contengan rutas en las que los retornos en vacío de los vehículos sean aprovechados para transportar la mercancía que tiene que ser devuelta al depósito. El objetivo de este proyecto es desarrollar un método de resolución del problema planteado. Además, dada la calidad de las soluciones obtenidas a partir del procedimiento desarrollado, se podrá integrar el algoritmo en la plataforma para el análisis y modelado de sistemas de transporte, Aimsun. En concreto en su componente orientada a la logística urbana, conocida como Aimsun Logistics. Con este fin, este proyecto se divide básicamente en tres partes: en la primera se realiza la elección del algoritmo más adecuado, en la segunda se desarrolla e implementa cada una de las partes de éste y en la tercera se integra en el software. El proceso de elección del algoritmo se realiza después de una exhaustiva revisión del estado del arte sobre el tema, a partir de la cual se seleccionan cuatro procedimientos candidatos, entre los que se elige la heurística de Toth y Vigo (1999) por parecer la más adecuada para el problema que se trata. El método elegido consta de diferentes etapas, las cuales se analizan y discuten críticamente en lo que constituye el bloque principal del presente proyecto. A continuación se implementan en C++ para la realización de experiencias computacionales. Por último, se detalla el proceso de integración en el software Aimsun que incluye la explicación de la metodología de validación seguida, mediante la cual se verifica la corrección de la integración a través de la ejecución del algoritmo, aplicándolo a diferentes instancias ejemplo.