A time buffered arc routing problem

Arc routing problems are prevalent in our world today. They are important to society and businesses on a daily basis. The purpose of this work is to consider a problem that has not been addressed in the literature. That problem is how to find the maximal weighted tour of an undirected set of arcs that visits all of the edges within some time constraint, and no edge twice within some time buffer. This problem, similar to most arc and vehicle routing problems, is known to be NP-hard, and thus can only be solved optimally for the most simplistic problems. Furthermore, being a mixed-integer nonlinear program, most solvers may not be able to guarantee a solution is optimal for even small problem instances. To be able to address realistic problem sets with a large number of vertices, a comparative, route-building heuristic was developed to find a near optimal tour. This heuristic, the mixed-integer nonlinear program solver, and a hand solution were all compared for a relatively simple four node network problem. The program for the mixed-integer nonlinear solver could not solve the problem optimally. A hand solution found for the network was used to show the formulation's accuracy through the solver program, and was checked for general optimality by the solver. A heuristic was built that was able to find this optimal solution. It is assumed that the heuristic is scalable and hence will also provide a near optimal solution for higher complexity problem instances with a larger number of nodes and arcs