Arc routing problems can be applied to garbage collection, school bus route planning, package and newspaper delivery, deicing and snow removal with winter service vehicles that sprinkle salt on the road,[2] mail delivery, network maintenance, street sweeping, police and security guard patrolling,[1] and snow ploughing.
For a real-world example of arc routing problem solving, Cristina R. Delgado Serna & Joaquín Pacheco Bonrostro applied approximation algorithms to find the best school bus routes in the Spanish province of Burgos secondary school system.
The efficient scheduling and routing of vehicles can save industry and government millions of dollars every year.
[2][6] Arc routing problems have applications in school bus planning, garbage and waste and refuse collection in cities, mail and package delivery by mailmen and postal services, winter gritting and laying down salt to keep roads safe in the winter, snow plowing and removal, meter reading including remote radio frequency identification meter reading technology, street maintenance and sweeping, police patrol car route planning, and more.
[1] Arc routing problems impact strategic, tactical, and operational planning decisions.
[2] Vehicle routing decisions for the location of a depot depend on the cost of transporting materials over a geographical region.
[10] The earliest documented reference to the area of arc routing problems is the classic bridges of Königsberg challenge, which Euler proved to be impossible.
[11] This work was extended by Meigu Guan, also known as Kwan Mei-Ko at Shangtun Normal College.
Guan worked to find out a minimum length walk that traversed every edge of the graph at least once.
Guan described his goal in 1962: "A mailman has to cover his assigned segment before returning to the post office.
This problem is named after the postman and his challenge to deliver mail in any order he may choose, but minimizing his costs such as time or travel distance.
The heuristics described in this article ignore any such problems that arise due to application constraints.
In 1981, another pair of computer scientists, Golden and Wong, managed to prove that even deriving a .5 approximation to the URPP was NP-hard.
The WPP is NP-complete in general and can be solved in polynomial time if G is Eulerian, if the cost of two opposite orientations of every cycle in G in same or if G is a series-parallel graph.
Benavent proposed an integer linear programming formulation and different heuristics and lower bounds for the WRPP.
[9] Benavent et al published an evaluation of several heuristic methods used for solving the WRPP in a few seconds with a deviation no greater than 1% from the lower bound on medium sized graphs.
Scatter Search found solutions that deviated by less than 2% when implemented on networks with hundreds of nodes and thousands of edges.
[9] In real world applications, there are multiple vehicles that can move, which leads to the generalization named the Min-Max K-vehicles Windy Rural Postman Problem (MM K-WRPP).
The objective is to minimize the length of the longest tour in order to find a set of balanced routes for the vehicles.
In real applications of math, a solution that minimizes the total costs of all vehicles route and the length of the longest tour is preferable.
[3] This is modeled by a variant studied by Dussault et al, the Downhill Plowing Problem (DPP).
[3] A branch and cut algorithm was published by Angel Corberan for the windy postman problem.
The algorithm is based on heuristic and exact methods for manipulating odd-cut inequality violations.
The objective is a route that avoids plowing uphill on steep streets that completes the job faster by maximizing the deadhead time to get the location.
This was modeled with a heuristic algorithm that approximates a lower bound by Dussault, Golden and Wasil.
The simulation for the DPP deadheaded unplowed street about 5% of the time, which is a topic for future graph theory and arc routing research.
Dussault, Golden, and Wasil found an algorithm that did not exceed the lower bound by 5.5% in over 80 test runs.
The rural postman problem (RPP) makes some routes mandatory and absolute but the person traversing the graph does not have to go in one particular direction.
Benevant studied a generalization of this named Directed Rural Postman Problem with Turn Penalties (DRPP-TP).
[20] Benevant's algorithm approximated the solution by transforming the DRPP-TP into an asymmetrical traveling salesman problem (ATSP).