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. 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, mail delivery, network maintenance, street sweeping, police and security guard patrolling, and snow ploughing. 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.
There are generalizations of arc routing problems that introduce multiple mailmen, for example the k Chinese Postman Problem (KCPP).
Background
The efficient scheduling and routing of vehicles can save industry and government millions of dollars every year. 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.
Basis
The basic routing problem is: given a set of nodes and/or arcs to be serviced by a fleet of vehicles, find routes for each vehicle starting and ending at a depot. A vehicle route is a sequence of points or nodes, which the vehicle must traverse in order, starting and ending at a depot.
Chinese postman problem
The Chinese Postman Problem (CPP) is aimed at finding the minimum length cycle for a single postman. The CPP requires all edges be traversed once, the rural postman problem (RPP) requires a subset of the edges to be traversed with the minimum length cycle.
Vehicle routing problems/VRP
Arc routing problems impact strategic, tactical, and operational planning decisions. The strategic role of where a depot is placed depends on the most efficient arc route available. The decision of the vehicle fleet size and vehicle types with varying specifications relate to the tactical aspect of arc routing problems in operations research. Routing and scheduling decisions are operational planning decisions in arc routing problems. The operational planning decisions also includes the time that the vehicles are used by workers with staff decisions. Vehicle routing decisions for the location of a depot depend on the cost of transporting materials over a geographical region. Bodin et. al applied vehicle routing to the dial a ride problem.
Rural postman problem
In some situations, the set of edges that are required is different from the edges in the graph. This is modeled by the Rural Postman Problem (RPP), where the required edges are a subset of the system of edges.
Algorithms
Finding an efficient solution with large amounts data to the Chinese Postman Problem (CPP), the Windy Postman Problem (WPP), the Rural Postman Problem (RPP), the k-Chinese postman problem (KCPP), the mixed Chinese postman problem (MCPP), the Directed Chinese Postman Problem (DCPP), the Downhill Plowing Problem (DPP), the Plowing with Precedence Problem (PPP), the Windy Rural Postman Problem (WRPP) and the Windy General Routing Problem (WGRP) requires using thoughtful mathematical concepts, including heuristic optimization methods, branch-and-bound methods, integer linear programming, and applications of traveling salesman problem algorithms such as the Held–Karp algorithm makes an improvement from to . In addition to these algorithms, these classes of problems can also be solved with the cutting plane algorithm, convex optimization, convex hulls, Lagrange multipliers and other dynamic programming methods. In cases where it is not feasible to run the Held–Karp algorithm because of its high computational complexity, algorithms like this can be used to approximate the solution in a reasonable amount of time.