In my PhD Dissertation I consider the Capacitated Arc Routing Problem (CARP). The problem is defined on a graph with demand on the edges and a fleet of capacitated vehicles located in a special depot node. The goal is to minimize the total routing cost of tours servicing all demand edges and respecting the vehicle capacity. CARP arises frequently in both public and private business, for instance in the determination of routes for street sweeping, snow removal, or mail delivery. In contrast to the node routing counterpart, this problem has not been studied much in the literature up until the last 5-10 years.

In the Dissertation, I consider three variations of the problem, a) the classical problem as defined above, which is the one usually addressed in the literature, b) an extension of the problem with multiple depots and vehicles of different capacities (CARP-MD), and finally c) an extension with time windows for the servicing of edges (CARP-TW). Both extensions have been studied in the node routing counterpart, but not formally for arc routing as in this work. Algorithmic procedures for calculation of lower bounds and solution procedures are presented in each case.

The main results can be summarized as follows:

• Approximation: An approximation algorithm with fixed approximation factor is given. For the CARP which for all instances of the problem, it performs at least as well as the only other existing approximation algorithm for the problem.
• Lower Bounds: A new lower bound for the CARP is developed. The new bound outperforms the elsewhere available best bounds known for the problem. The bound is extended to the CARP-MD and the CARP-TW.
• Heuristics: A Simulated Annealing algorithm for the CARP is developed. A non standard neighborhood structure based upon dynamic programming for finding near optimal solutions is an integral part of the algorithm. The algorithm is extended to other routing and scheduling problems including the Minimum Makespan Problem.
• Modeling: It is well known that the construction of a linear programming model for the CARP-TW requires some kind of graph transformation, and no such formulation has to our knowledge been presented before. Two such formulations are suggested, one based upon a transformation of the problem into a node routing problem, and the other based upon the definition of an equivalent arc routing problem on a transformed graph.
• Optimal solution: An algorithm based on column generation for identifying a proven optimal solution for the CARP-TW is presented. To our knowledge the CARP-TW has not been solved to optimality before. This part of the thesis is joint work with Dr.\ Ellis Johnson Georgia Institute of Technology.