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.
Eulerian circuits 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. The resident of Konigsberg, now part of Kaliningrad, wanted to find a way to cross all seven bridges over the river Pregel without backtracking or retracing their steps, that is crossing each bridge once and only once. In 1736, Euler reduced the problem to a question of nodes and edges and showed that the problem was impossible. In 1873, Hierholzer did more work on the question of closed circuits.
Work on Eulerian circuits was popularized in the July 1953 issue of Scientific American. This work was extended by Meigu Guan, also known as Kwan Mei-Ko at Shangtun Normal College. Meigu Guan was interested in a different question instead of determining a closed circuit. 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. The problem is to find the shortest walking distance for the mailman."
Problem types Arc routing problems (ARPs) differ in their goal and heuristics. However, all of them are known to be NP-hard.
Undirected rural postman problem 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. It is also sometimes called the undirected chinese postman problem. The undirected rural postman problem (URPP) aims to minimize the total cost of a route that maps the entire network, or in more specific cases, a route that maps every edge that requires a service. If the whole network must be mapped, the route that maps the entire network is called a covering tour. In the case where only certain edges need to be mapped, the problem aims to solve the route that optimizes the demands, crossing over into non-required routes a minimal number of times.
Undirected capacitated arc routing problem The undirected capacitated arc routing problem consists of demands placed on the edges, and each edge must meet the demand. An example is garbage collection, where each route might require both a garbage collection and a recyclable collection. Problems in real life applications might arise if there are timing issues, such as the case in which certain routes cannot be serviced due to timing or scheduling conflicts, or constraints, such as a limited period of time. The heuristics described in this article ignore any such problems that arise due to application constraints.
History The URPP was first introduced in 1974 and was proven to be an NP-hard problem by Lenstra and Kan. The UCARP can be derived from the URPP, and thus is NP-hard as well. 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. In 2000, Dror published a book describing different arc routing problems.
Windy postman problem and variants The windy postman problem proposed by Minieka is a variant of the route inspection problem in which the input is an undirected graph, but where each edge may have a different cost for traversing it in one direction than for traversing it in the other direction. In contrast to the solutions for directed and undirected graphs, it is NP-complete.. The cost of traveling in one direction is greater when the wind is blowing in your face than when the wind is at your back, and this is the origin of the name Windy Postman problem. The work that it takes to traverse the street in one direction is different than the work it takes to traverse the street in another direction on a windy day.
The windy postman problem is an arc routing problem (ARP) that contains the Mixed Chinese Postman Problem MCPP as a special case.
The problem can be defined in the following manner: "Given an undirected and connected graph G=(V,E) with two non-negative costs and associated with each edge corresponding to the cost of traversing it from i to j and from j to i, respectively, the WPP is to find a minimum cost tour on G traversing each edge at least once." This problem was introduced by Minieka. 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. The Windy Rural Postman Problem (WRPP) is a generalization of the WPP in which not all the edges in the graph have to be traversed but only those in a given subset of required edges. For example, some rural roads are not required for the postman to cross and some roads on steep hills take longer to go up than down.
The Windy Rural Postman Problem (WRPP) is a generalization of the WPP in which not all the edges in the graph have to be traversed but only those in a given subset of required edges. For example, some rural roads are not required for the postman to cross and some roads on steep hills take longer to go up than down. Consider an undirected graph with two costs and associated with the cost to traverse the edge starting from i and j, respectively. G is the windy graph and we are interested in the subset of edges, or in mathematical symbols, .
If the WRPP includes the additional constraint that a certain set of vertices must be visited—, the problem turns into the Windy General Routing Problem (WGRP). Benavent proposed an integer linear programming formulation and different heuristics and lower bounds for the WRPP.
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. They improved on this with a Scatter Search algorithm that reduced the difference to 0.5%. Scatter Search found solutions that deviated by less than 2% when implemented on networks with hundreds of nodes and thousands of edges.
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 min–max K-vehicles Windy Rural Postman Problem (MM K-WRPP) is defined as follows: Given a windy graph , a distinguished vertex, , representing the depot, a subset of required edges , and a fixed number K of vehicles, the MM K-WRPP consists of finding a set of K tours for the vehicles in such a way that each tour starts and ends at the depot and each required edge is serviced by exactly one vehicle. The objective is to minimize the length of the longest tour in order to find a set of balanced routes for the vehicles. Some real-life applications of routing problems with min–max objectives are school bus routing (Delgado and Pacheco 2001), the delivery of newspapers to customers (Applegate et al. 2002) and waste collection (Lacomme et al. 2004).
The best MM K_WRPP algorithm was very close to the minimum solution with 2 and 3 vehicles, less than 0.4% on average. The gap increases to about 1.00% and 1.60% at 4 and 5 vehicles.