Problemas de rutas de vehículos por arcos

Abstract

At the beginning of this work, we are going to give a historical introduction of arc routing. We will take a look at the complexity of this type of problems, and then, we will focus on the Chinese Postman Problem. It is arguably the most central problem in this area. Given a graph, it basically tries to find a minimun cost tour traversing at least once each edge. We will study the undirected, directed, mixed and windy version in detail, and their respective ways to deal with them. Finally, we will see some applications about real instances for each version.