RT Generic
T1 Problemas de rutas de vehículos e algoritmos de aforro: o algoritmo de Clarke and Wright
A1 Blanco González, Elena
AB [GL] Os Problemas de Rutas de Vehículos (VRP) son un exemplo de problemas para osque moitas veces non é posible aplicar algoritmos que os resolvan en tempo polinomial,principalmente debido ao seu tamaño e á súa complexidade. Habitualmente para resolverexemplos deste tipo de problemas usaranse algoritmos heurísticos. Neste traballo presentamoso Problema do Viaxante de Comercio (TSP) para continuar cos Problemas de Rutasde Vehículos. A continuación enunciaremos o algoritmo heurístico proposto por Clarke andWright para o VRP con restricións de capacidade. Finalmente contaremos cos datos dunproblema de rutas da vida real que usaremos para comparar as solucións obtidas usandounha implementación en R do algoritmo de Clarke and Wright coa solución obtida a ditoproblema mediante a súa modelación con linguaxe AMPL.
AB [EN] The Vehicle Routing Problems (VRP) are an example of problems where it can not bepossible to apply an exact method to solve them in a polynomial time in many times dueto their complexity or size. Frequently to solve examples of this kind of problems heuristicalgorithms 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 heuristicalgorithm proposed by Clarke and Wright for Capacited VRP. Finally, based on a realworldproblem, we will compare the solutions obtained by an R implementation of Clarkeand Wright algorithm versus the results returned by an AMPL model used together withan exact optimization method.
YR 2019
FD 2019-07
LK http://hdl.handle.net/10347/26303
UL http://hdl.handle.net/10347/26303
LA glg
NO Traballo Fin de Grao en Matemáticas. Curso 2018-2019
DS Minerva
RD 22 abr 2026