Problemas de rutas de vehículos e algoritmos de aforro: o algoritmo de Clarke and Wright

Abstract

[GL] Os Problemas de Rutas de Vehículos (VRP) son un exemplo de problemas para os que moitas veces non é posible aplicar algoritmos que os resolvan en tempo polinomial, principalmente debido ao seu tamaño e á súa complexidade. Habitualmente para resolver exemplos deste tipo de problemas usaranse algoritmos heurísticos. Neste traballo presentamos o Problema do Viaxante de Comercio (TSP) para continuar cos Problemas de Rutas de Vehículos. A continuación enunciaremos o algoritmo heurístico proposto por Clarke and Wright para o VRP con restricións de capacidade. Finalmente contaremos cos datos dun problema de rutas da vida real que usaremos para comparar as solucións obtidas usando unha implementación en R do algoritmo de Clarke and Wright coa solución obtida a dito problema mediante a súa modelación con linguaxe AMPL.

[EN] The Vehicle Routing Problems (VRP) are an example of problems where it can not be possible to apply an exact method to solve them in a polynomial time in many times due to their complexity or size. Frequently to solve examples of this kind of problems heuristic algorithms will be used. In this project we will first present the Travelling Salesman Problem (TSP) to continue with the Vehicle Routing Problems. Next, we will show the heuristic algorithm proposed by Clarke and Wright for Capacited VRP. Finally, based on a realworld problem, we will compare the solutions obtained by an R implementation of Clarke and Wright algorithm versus the results returned by an AMPL model used together with an exact optimization method.