Capacitated arc routing problem: Formulations, algorithms and application

This dissertation analyzes the problem of designing efficient routes for salting and plowing trucks in snow emergencies. There are two objectives in this research for dealing with snow emergency operations. The first is to determine how many trucks are needed and the second is to design efficient routes for the trucks so as to minimize the total deadhead distance.; The nature of the problem is analyzed. Using network transformation, we formulate a Capacitated Minimum Spanning Tree (CMST) model to minimize the total number of trucks and formulate a Capacitated Arc Routing Problem (CARP) to find the routes for the trucks.; Both problems have been shown to be NP-hard. Therefore, heuristic procedures are needed to solve them. In this dissertation, we focus on the development of improvement methods for CARP with different extensions, since many algorithms have been suggested for a CMST.; Several test algorithms based on our improvement methods and meta-heuristics are proposed to solve the capacitated arc routing problem. Significant improvements in solutions are realized when the results are compared with the results from other algorithms in the literature.; Different methods for obtaining lower bounds for the value of objective function are analyzed in this dissertation. The reasons why the Lagrangian Relaxation Lower Bound method suggested by Pearn (1984) is not a good approach for this problem are discussed. Several branch and bound strategies that result in some good lower bounds are suggested.; A complete case study based on Calvert County's snow routes is presented in this dissertation. By applying our formulation and algorithm, we save 14.29% in total number trucks and 8.89% in total travel distance compared to the current operation. Sensitivity analyses show that the final solutions are sensitive to the truck capacity and depot (salt dome) locations. Further, these results show that the solutions are not very sensitive to the load balance parameters. This is very helpful for management decision-making.