A comparison of 3 metaheuristics for the location-arc routing problem

In this thesis, I compare the performance of three metaheuristics for the location-arc routing problem. The location-arc routing problem combines two well-known problems in Operations Research: the assignment facility location problem and the capacitated arc routing problem. It determines both the routing and depot location(s) for serving a finite number of clients. These clients are located on the arcs of a graph. The meta- heuristics used and discussed in this thesis are based on tabu search and the greedy randomized adaptive search procedure (GRASP). To make a comparison between the performance of these three metaheuristics, I make use of 14 data instances provided by Lopes et al (2014). Since these data instances are all undirected, I first look at the symmetric location-arc routing problem. Ad- ditionally, I modify some of these data instances to compare the performance of the three metaheuristics for special cases of the location-arc routing problem. Are the three metaheuristics suitable for the location-arc routing problem if only a subset of the arcs in the data instance have to be visited? And are these metaheuristics also suitable for the asymmetric location-arc routing problem?