[en] Some of the most common decisions to be taken within a logistic systems at an operational level are related to the design of the vehicle routes. Vehicle Routing Problems and Arc Routing Problems are well-known families of problems addressing such decisions. Their main difference is whether service demand is located at the vertices or the edges of the operating network. In this thesis we focus on the study of several arc routing problems. We concentrate on three families of problems. The first family consists of Multi Depot Rural Postman Problems, which are an extension of Rural Postman Problems where there are several depots instead of only one. The second family of problems that we study are Location-Arc Routing Problems, in which the depots are not fixed in advance, so their location becomes part of the decisions of the problem. We finally study Target-Visitation Arc Routing Problems, where the service is subject to an ordering preference among the connected components induced by demand arcs. Different models are studied for each considered family. In particular, two different Multi Depot Rural Postman Problem models are considered, which differ in the objective function: the minimization of the overall transportation cost or the minimization of the makespan. Concerning Location-Arc Routing Problems, we study six alternative models that differ from each other in their objective function, whether there is an upper bound on the number of facilities to be located, or whether there are capacity constraints on the demand that can be served from selected facilities. Finally, two Target-Visitation Arc Routing Problem models are studied, which differ from each other in whether or not it is required that all the required edges in the same component are visited consecutively. The aim in this thesis is to provide quantitative tools to the decision makers to identify the best choices for the design of the routes. To this end and for each considered problem, we first study and analyze its characteristics and properties. Based on them we develop different Integer Linear Programming formulations suitable for being solved trough branch-and-cut. Finally, all formulations are tested trough extensive computational experience. In this sense, for Multi Depot Rural Postman Problems and Location-Arc Routing Problems we propose natural modeling formulations with three-index variables, where variables are associated with edges and facilities. For some of the models we also present alternative formulations with only two-index variables, which are solely associated with edges. Finally, for the Target-Visitation Arc Routing Problems we propose three different formulations, two alternative formulations for the general case, and one for the clustered version, where all the edges in the same components are served sequentially, which exploits some optimality conditions of the problem.

[es] Algunas de las decisiones más habituales que se toman en un sistema logístico a nivel operativo están relacionadas con el diseño de rutas de vehículos. Los conocidos Vehicle Routing Problems y Arc Routing Problems son familias de problemas que se ocupan de este tipo de decisiones. La principal diferencia entre ambas reside en si la demanda de servicios está localizada en los vértices o en las aristas de la red. Esta tesis se centra en el estudio de diversos problemas de rutas por arcos. Nos centramos en tres familias de problemas. La primera familia consiste en los Multi Depot Rural Postman Problems, que son una extensión del Rural Postman Problem donde hay varios depósitos en lugar de solamente uno. La segunda familia de problemas que estudiamos son los Location-Arc Routing Problems, en los que los depósitos no están fijados con antelación y, por lo tanto, su ubicación se convierte en parte de las decisiones a tomar en el problema. Finalmente, estudiamos los Target-Visitation Arc Routing Problems, donde el servicio está sujeto a una preferencia de ordenación entre las componentes conexas inducidas por los arcos con demanda. Se estudian diferentes modelos para cada una de las familias consideradas. En particular, se consideren dos modelos diferentes para el Multi Depot Rural Postman Problem que se diferencian en la función objetivo: la minimización del coste general de transporte o la minimización de la ruta más larga. En cuanto a los Location-Arc Routing Problems, estudiamos seis modelos alternativos que difieren en su función objetivo, en si hay un limite máximo sobre la cantidad de depósitos a ubicar, o en si hay restricciones de capacidad sobre la demanda que se puede servir desde los depósitos seleccionados. Finalmente, se estudian dos modelos de Target-Visitation Arc Routing Problem, que se diferencian en si es necesario que todas las aristas requeridas en la misma componente se visiten de forma consecutiva. El objetivo de esta tesis es proporcionar herramientas cuantitativas a los responsables, que permitan identificar las mejores opciones de diseño de las rutas. Por ello, y para cada uno de los problemas considerados, primero estudiamos y analizamos sus características y propiedades. A partir de estas, desarrollamos diferentes formulaciones de Programación Lineal Entera, adecuadas para su solución mediante un branch-and-cut. Finalmente, todas las formulaciones son probadas mediante un amplio testeo computacional. En este sentido, para los Multi Depot Rural Postman Problems y los Location-Arc Routing Problems, proponemos formulaciones naturales con variables de tres índices, donde las variables están asociadas a las aristas y a los depósitos. Para algunos de los modelos también presentamos formulaciones alternativas con variables de sólo dos índices, que sólo están asociadas a las aristas. Finalmente, para los Target-Visitation Arc Routing Problems proponemos tres formulaciones diferentes, dos formulaciones alternativas para el caso general y una para la versión en clúster, donde todas las aristas de la misma componente se sirven secuencialmente, lo que explora algunas condiciones de optimización propias