Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively.[1] The objective of arc routing problems involves minimizing the total distance and time, which often involves minimizing deadheading time, the time it takes to reach a destination. 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.[3][4] Arc routings problems are NP hard, as opposed to route inspection problems that can be solved in polynomial-time.
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 researchers minimized the number of routes that took longer than 60 minutes to traverse first. They also minimized the duration of the longest route with a fixed maximum number of vehicles.[5]
There are generalizations of arc routing problems that introduce multiple mailmen, for example the k Chinese Postman Problem (KCPP).