Arc routing

<h2 id="background">Background</h2>
The efficient scheduling and routing of vehicles can save industry and government millions of dollars every year.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> 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.

<h2 id="basis">Basis</h2>
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.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h2 id="chinese-postman-problem">Chinese postman problem</h2>
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.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h2 id="vehicle-routing-problemsvrp">Vehicle routing problems/VRP</h2>
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.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> 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.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="rural-postman-problem">Rural postman problem</h2>
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),<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> where the required edges are a subset of the system of edges.

<h2 id="algorithms">Algorithms</h2>
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 <a href="/facts/Mixed_Chinese_postman_problem/v56cXjqt">mixed Chinese postman problem</a> (MCPP), the Directed Chinese Postman Problem (DCPP),<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> 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 <a href="/facts/Heuristic_(computer_science)/PM2qkoa2">heuristic optimization methods</a>, <a href="/facts/Branch_and_bound/mhALtav7">branch-and-bound methods</a>, <a href="/facts/Integer_programming/MDaaadoA">integer linear programming</a>, and applications of <a href="/facts/Travelling_salesman_problem/2WEKVLnV">traveling salesman problem</a> algorithms such as the <a href="/facts/Held%25E2%2580%2593Karp_algorithm/tE6rrWA9">Held–Karp algorithm</a> makes an improvement from 
 
 
 
 O
 (
 n
 !
 )
 
 
 {\displaystyle O(n!)}
 
 to 
 
 
 
 O
 (
 
 2
 
 n
 
 
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(2^{n}n^{2})}
 
.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> In addition to these algorithms, these classes of problems can also be solved with the <a href="/facts/Cutting-plane_method/8V7TTfhx">cutting plane algorithm</a>, <a href="/facts/Convex_optimization/7D6U4MTN">convex optimization</a>, <a href="/facts/Convex_hull/D4Id3JDS">convex hulls</a>, <a href="/facts/Lagrange_multiplier/U5mSI5YP">Lagrange multipliers</a> and other <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming methods</a>. 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.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

<h2 id="eulerian-circuits">Eulerian circuits</h2>
The earliest documented reference to the area of arc routing problems is the classic <a href="/facts/Seven_Bridges_of_K%25C3%25B6nigsberg/r95CwL9f">bridges of Königsberg</a> challenge, which <a href="/facts/Leonhard_Euler/z2fsbjgj">Euler</a> proved to be impossible.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> The resident of <a href="/facts/K%25C3%25B6nigsberg/veeajbNW">Konigsberg</a>, now part of <a href="/facts/Kaliningrad/6BhPwXqR">Kaliningrad</a>, wanted to find a way to cross all seven bridges over the river <a href="/facts/Pregolya/mUjgaAwH">Pregel</a> 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.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>
The work on the Eulerian circuits was popularized with Scientific American on July 1, 1953.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> 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."<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>

<h2 id="problem-types">Problem types</h2>
Arc routing problems (ARPs) differ in their goal and heuristics. However, all of them are known to be <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>.

<h3>Undirected rural postman problem</h3>
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.
<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>

<h3>Undirected capacitated arc routing problem</h3>
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.
<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>

<h2 id="history">History</h2>
The URPP was first introduced in 1974 and was proven to be an NP-hard problem by <a href="/facts/Jan_Karel_Lenstra/IHhz668g">Lenstra</a> and <a href="/facts/Alexander_Rinnooy_Kan/bSeVecSA">Kan</a>. 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.

<h2 id="windy-postman-problem-and-variants">Windy postman problem and variants</h2>
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.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> In contrast to the solutions for directed and undirected graphs, it is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a><a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> 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.<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a>
The windy postman problem is an arc routing problem (ARP) that contains the Mixed Chinese Postman Problem MCPP as a special case.<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a>
The problem can be defined in the following manner: "Given an undirected and connected graph G=(V,E) with two non-negative costs 
 
 
 
 
 c
 
 i
 ,
 j
 
 
 
 
 {\displaystyle c_{i,j}}
 
 and 
 
 
 
 
 c
 
 j
 ,
 i
 
 
 
 
 {\displaystyle c_{j,i}}
 
 associated with each edge 
 
 
 
 {
 i
 ,
 j
 }
 ∈
 E
 
 
 {\displaystyle \{i,j\}\in E}
 
 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."<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a> 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.<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a>
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.<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a> Consider an undirected graph 
 
 
 
 G
 =
 {
 E
 ,
 V
 }
 
 
 {\displaystyle G=\{E,V\}}
 
 with two costs 
 
 
 
 
 c
 
 i
 j
 
 
 
 
 {\displaystyle c_{ij}}
 
 and 
 
 
 
 
 c
 
 j
 i
 
 
 
 
 {\displaystyle c_{ji}}
 
 associated with the cost to traverse the edge 
 
 
 
 (
 i
 ,
 j
 )
 
 
 {\displaystyle (i,j)}
 
 starting from i and j, respectively. G is the windy graph and we are interested in the subset of edges, or in mathematical symbols, 
 
 
 
 
 E
 
 R
 
 
 ⊆
 E
 
 
 {\displaystyle E_{R}\subseteq E}
 
.
If the WRPP includes the additional constraint that a certain set of vertices must be visited—
 
 
 
 
 V
 
 R
 
 
 ⊆
 V
 
 
 {\displaystyle V_{R}\subseteq V}
 
, 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. <a class="footnote-ref" id="fnref:31" href="#fn:31">31</a>
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.<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a>
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 
 
 
 
 G
 =
 {
 V
 ,
 E
 }
 
 
 {\displaystyle G=\{V,E\}}
 
, a distinguished vertex, 
 
 
 
 1
 ∈
 V
 
 
 {\displaystyle 1\in V}
 
, representing the depot, a subset of required edges 
 
 
 
 
 E
 
 R
 
 
 ⊆
 E
 
 
 {\displaystyle E_{R}\subseteq E}
 
, 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).<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a>
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.
According to Dussault et al and Benavent et al, a metaheuristics multi-objective simulating annealing algorithm (MOSA) can solve the different contraints imposed on the WRPP. The WRPP is an important Arc Routing Problem which generalizes many of the single-vehicles Arc Routing problems. 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. It's hard to be in a location where your package is always hours late.<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a> We should start with the assumption that several vehicles with a specific measurable capacity to serve customers is more realistic than one vehicle with unmeasurable infinite capacity. Rabbani et. al measured the performance of MOSA algorithms and models using a multi-objective development of Cuckoo search—developed by Yang et al,<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a> also referred to as Multi-objective Cuckoo Search and abbreviated by MOCS.<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a> They concluded that MOSA methods were more efficient than MOCS methods. In the future comparisons with other meta-heuristic methods could be researched, including Non-dominated Sorting Genetic Algorithm (NSGA- ), multi-objective particle swarm optimization algorithm (MOPSO) and multi-objective Imperialist Competitive Algorithm.
In the Windy Postman Problem (WPP) model, the cost of going in one direction is different than the cost it takes to go in the other direction. For example, if the wind is blowing down the street it takes more time and energy to go against the wind than with the wind. Another example of the WPP is the cost of plowing uphill is greater than the cost of plowing downhill.<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a> This is modeled by a variant studied by Dussault et al, the Downhill Plowing Problem (DPP).<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a> 
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.<a class="footnote-ref" id="fnref:39" href="#fn:39">39</a>

<h2 id="applications">Applications</h2>
Various combinatorial problems have been reduced to the Chinese Postman Problem, including finding a maximum cut in a planar graph and a minimum-mean length circuit in an undirected graph.<a class="footnote-ref" id="fnref:40" href="#fn:40">40</a>

<h3>Snow plows</h3>
In winter a common question is what set of routes has the smallest (minimum) maximum route length? Typically, this is assessed as an arc routing problem with a graph. The time it takes to travel a street, known as deadhead time, is faster than the time it takes to plow the snow from the streets (or deliver mail or drop off packages). Another aspect that must be considered when applying arc routing to snow plowing is the fact that on steep streets it is either difficult or impossible to plow uphill. 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.<a class="footnote-ref" id="fnref:41" href="#fn:41">41</a> This is the Downhill Plow Problem (DPP). Snow teams prefer to plow downhill and deadhill uphill. This problem assumes that the conditions are severe enough that the streets are closed and there is no traffic.
The Downhill Plowing Problem ignores the Plowing with Precedence Problem (PPP), which is built on the reasonable assumption that if the snow is too deep the snow plow cannot deadhead an unplowed street. The DPP makes the assumption that the snow level is low enough that the streets that are not plowed can be deadheaded, but that the snow is deep enough that there is no traffic. If there is traffic on the roads, the assumption that it is impossible to plow uphill can no longer be held. 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.
Considering an undirected graph 
 
 
 
 G
 =
 {
 V
 ,
 A
 }
 
 
 {\displaystyle G=\{V,A\}}
 
 where 
 
 
 
 V
 
 
 {\displaystyle V}
 
 is the set of vertices and nodes and 
 
 
 
 A
 
 
 {\displaystyle A}
 
 is the set of arcs. Each arc represented by 
 
 
 
 (
 
 v
 
 i
 
 
 ,
 
 v
 
 j
 
 
 )
 
 
 {\displaystyle (v_{i},v_{j})}
 
 has four costs: 
 
 
 
 
 c
 
 i
 j
 
 
 +
 
 
 
 
 {\displaystyle c_{ij}^{+}}
 
, defined as the cost of plowing from 
 
 
 
 
 v
 
 i
 
 
 
 
 {\displaystyle v_{i}}
 
 to 
 
 
 
 
 v
 
 j
 
 
 
 
 {\displaystyle v_{j}}
 
, 
 
 
 
 
 c
 
 j
 i
 
 
 +
 
 
 
 
 {\displaystyle c_{ji}^{+}}
 
, the cost of plowing from 
 
 
 
 
 v
 
 j
 
 
 
 
 {\displaystyle v_{j}}
 
 to 
 
 
 
 
 v
 
 i
 
 
 
 
 {\displaystyle v_{i}}
 
, 
 
 
 
 
 c
 
 i
 j
 
 
 −
 
 
 
 
 {\displaystyle c_{ij}^{-}}
 
, the cost of deadheading from 
 
 
 
 
 v
 
 i
 
 
 
 
 {\displaystyle v_{i}}
 
 to 
 
 
 
 
 v
 
 j
 
 
 
 
 {\displaystyle v_{j}}
 
, and 
 
 
 
 
 c
 
 j
 i
 
 
 −
 
 
 
 
 {\displaystyle c_{ji}^{-}}
 
, the cost of deadheading from 
 
 
 
 
 v
 
 j
 
 
 
 
 {\displaystyle v_{j}}
 
 to 
 
 
 
 
 v
 
 i
 
 
 
 
 {\displaystyle v_{i}}
 
. The setup assumes that 
 
 
 
 
 v
 
 j
 
 
 
 
 {\displaystyle v_{j}}
 
 has a higher elevation 
 
 
 
 
 v
 
 i
 
 
 
 
 {\displaystyle v_{i}}
 
, which leads to the statement: 
 
 
 
 
 c
 
 i
 j
 
 
 +
 
 
 ≫
 
 c
 
 j
 i
 
 
 +
 
 
 ≫
 
 c
 
 i
 j
 
 
 −
 
 
 ≥
 
 c
 
 j
 i
 
 
 −
 
 
 
 
 {\displaystyle c_{ij}^{+}\gg c_{ji}^{+}\gg c_{ij}^{-}\geq c_{ji}^{-}}
 
. In practice, downhill plowing time is two times as efficient as uphill plowing and deadheading is twice as efficient as plowing. The algorithm finds 
 
 
 
 k
 
 
 {\displaystyle k}
 
 routes will each begin and end at the depot 
 
 
 
 
 v
 
 0
 
 
 
 
 {\displaystyle v_{0}}
 
, plow the arc two times because the left side and right side of the street take two passes to plow.
The best solution will minimize the maximum route length. Dussault, Golden, and Wasil found an algorithm that did not exceed the lower bound by 5.5% in over 80 test runs. The deviation increased as the complexity of the model increased because there are more unoptimized approximations than optimized approximation as the model grows. An improvement on Dussault et. al's DPP algorithm might have penalties for making U-turns and left hand turns, or going straight across an intersection, which take additional time and pushes snow into the middle of the intersection, respectively. (see The Directed Rural Postman Problem with Turn Penalties problem, often referred to as the DRPP-TP below).

<h2 id="k-chinese-postman-problem-k-cpp">k-Chinese postman problem (k-CPP)</h2>
The k-Chinese Postman can be stated as follows: "given a connected edge-weighted graph G and integers p and k, decide whether there are at least k closed walks such that every edge of G is contained in at least one of them and the total weight of the edges in the walks is at most p?" The process of obtaining the solution to the k-CPP is NP complete. Gutin, Muciaccia, and Yeo proved in 2013 that the k-CPP is fixed-parameter tractable.<a class="footnote-ref" id="fnref:42" href="#fn:42">42</a> The authors prove the k-CPP admits a kernel with 
 
 
 
 O
 (
 
 k
 
 2
 
 
 log
 ⁡
 (
 k
 )
 )
 
 
 {\displaystyle O(k^{2}\log(k))}
 
 vertices and the directed version of the k-CPP is NP complete.

<h2 id="rural-postman-problem-rpp-and-generalizations">Rural postman problem (RPP) and generalizations</h2>
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. The RPP is NP hard and complete, in the same way that the kCPP, the DPP, the PPP, are NP hard. Benevant studied a generalization of this named Directed Rural Postman Problem with Turn Penalties (DRPP-TP).<a class="footnote-ref" id="fnref:43" href="#fn:43">43</a> Benevant's algorithm approximated the solution by transforming the DRPP-TP into an asymmetrical traveling salesman problem (ATSP). 

<h2 id="heuristics-and-algorithms">Heuristics and algorithms</h2>
Most algorithms require a pre-processing of the graph, which simplifies the initial graph by removing all edges that are not in the shortest path between two required edges. Another simplification that the pre-processing adds is that it transforms the shortest path between 2 required edges into a single, non-required edge, regardless of the number of edges in the path, provided that there were no required edges in the path.
Once the pre-processing is done, the problem can be generalized into a <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> problem, with the edges being the points of the hull. The convex hull problem can be solved through linear programming or through convex hull algorithms, but the process of finding the convex hull is an exponential problem.
Methods of solving the URPP after the pre-processing is done consist of the <a href="/facts/Integer_programming/MDaaadoA">cutting plane algorithm</a> and the <a href="/facts/Branch_and_cut/YJ07W6eP">branch & cut methodology</a>.
<a class="footnote-ref" id="fnref:44" href="#fn:44">44</a>

<h2 id="complexity">Complexity</h2>
This is a list of computational complexities for different arc routing problems.

<table><tbody><tr><th>CP variant</th><th>Classical complexity</th><th>Approximation</th><th>Parametrized complexity</th></tr><tr><td>Undirected</td><td> O ( | V | 3 ) {\displaystyle O(|V|^{3})} -time algorithm<a class="footnote-ref" id="fnref:45" href="#fn:45">45</a></td><td></td><td></td></tr><tr><td>Directed</td><td> O ( | V | 3 ) {\displaystyle O(|V|^{3})} -time algorithm<a class="footnote-ref" id="fnref:46" href="#fn:46">46</a> O ( ( | E | − | V | ) | V | 2 ) {\displaystyle O((|E|-|V|)|V|^{2})} -time algorithm<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a></td><td></td><td></td></tr><tr><td>Mixed</td><td>NP-complete<a class="footnote-ref" id="fnref:48" href="#fn:48">48</a> O ( | V | 3 ) {\displaystyle O(|V|^{3})} -time solvable if each vertex has even degree<a class="footnote-ref" id="fnref:49" href="#fn:49">49</a></td><td> O ( max { | V | 3 , | A | ( max { | A | , | E | } ) 2 } ) {\displaystyle O(\max\{|V|^{3},|A|(\max\{|A|,|E|\})^{2}\})} -time factor 3/2<a class="footnote-ref" id="fnref:50" href="#fn:50">50</a></td><td> O ( 2 | E | ⋅ | V | 3 ) {\displaystyle O(2^{|E|}\cdot |V|^{3})} -time algorithm<a class="footnote-ref" id="fnref:51" href="#fn:51">51</a>In FPT with respect to |A|<a class="footnote-ref" id="fnref:52" href="#fn:52">52</a>In XP with respect to treewidth<a class="footnote-ref" id="fnref:53" href="#fn:53">53</a></td></tr><tr><td>Windy</td><td>NP-complete<a class="footnote-ref" id="fnref:54" href="#fn:54">54</a>P in some special cases<a class="footnote-ref" id="fnref:55" href="#fn:55">55</a><a class="footnote-ref" id="fnref:56" href="#fn:56">56</a></td><td>Factor 3/2<a class="footnote-ref" id="fnref:57" href="#fn:57">57</a></td><td></td></tr><tr><td>k-Hierarchical</td><td>NP-complete<a class="footnote-ref" id="fnref:58" href="#fn:58">58</a> O ( k | V | 4 ) {\displaystyle O(k|V|^{4})} -time solvable if precedence relation linear</td><td></td><td></td></tr><tr><td>Min-sum k postmen</td><td> O ( | V | 3 ) {\displaystyle O(|V|^{3})} -time algorithm with post office vertex,<a class="footnote-ref" id="fnref:59" href="#fn:59">59</a> otherwise NP-complete<a class="footnote-ref" id="fnref:60" href="#fn:60">60</a></td><td></td><td>In FPT with respect to k without post office vertex<a class="footnote-ref" id="fnref:61" href="#fn:61">61</a></td></tr><tr><td>Min-max k postmen</td><td>NP-complete<a class="footnote-ref" id="fnref:62" href="#fn:62">62</a></td><td> O ( | V | 3 ) {\displaystyle O(|V|^{3})} -time factor(2-1/k)<a class="footnote-ref" id="fnref:63" href="#fn:63">63</a></td><td></td></tr></tbody></table>
<h2 id="list-of-arc-routing-variants">List of arc routing variants</h2>
<table><tbody><tr><th>Problem</th><th>Abbreviation</th><th>Description</th><th>Output Notes</th><th>Examples</th></tr><tr><td>Arc Routing Problem</td><td>ARP</td><td>Determine a least-cost traversal of a specified arc subset of a graph, with or without constraints.<a class="footnote-ref" id="fnref:64" href="#fn:64">64</a></td><td></td><td><a href="/facts/Seven_Bridges_of_K%25C3%25B6nigsberg/r95CwL9f">Seven Bridges of Konigsberg</a></td></tr><tr><td>Chinese Postman Problem</td><td>CPP</td><td>undirected graph G with Vertices V and weighted edges E</td><td>Traverse every edge at least once with minimal cost</td><td>"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."<a class="footnote-ref" id="fnref:65" href="#fn:65">65</a></td></tr><tr><td>Rural Postman Problem</td><td>RPP</td><td>undirected graph G with Vertices V and weighted edges E</td><td>Traverse a subset of the edges E at least once with minimum cost</td><td></td></tr><tr><td>Directed Rural Postman Problem</td><td>DRPP</td><td></td><td></td><td></td></tr><tr><td>Rural Postman Problem with Turn Penalties</td><td>RPP-TP, RPPTP</td><td></td><td></td><td></td></tr><tr><td>Windy Postman Problem</td><td>WPP<a class="footnote-ref" id="fnref:66" href="#fn:66">66</a></td><td></td><td></td><td></td></tr><tr><td>Windy Rural Postman Problem</td><td>WRPP</td><td></td><td></td><td></td></tr><tr><td>Street Sweeper Problem</td><td>SPP</td><td></td><td></td><td></td></tr><tr><td>m-Plowing Problem</td><td>m-PP</td><td></td><td></td><td></td></tr><tr><td>Capacitated Plow Problem</td><td>C-PP</td><td></td><td></td><td></td></tr><tr><td>Downhill Plow Problem</td><td>DPP<a class="footnote-ref" id="fnref:67" href="#fn:67">67</a></td><td></td><td></td><td></td></tr><tr><td>Downhill Plow Problem with Turn Penalties</td><td>DPP-TP<a class="footnote-ref" id="fnref:68" href="#fn:68">68</a><a class="footnote-ref" id="fnref:69" href="#fn:69">69</a></td><td></td><td></td><td></td></tr><tr><td>Rural Downhill Plow Problem with Turn Penalties</td><td>RDPP-TP</td><td></td><td></td><td></td></tr><tr><td>Capacitated Arc Routing Problem</td><td>CARP</td><td></td><td></td><td></td></tr><tr><td>k-Plow Windy Rural Postman Problem</td><td>k-WRPP</td><td></td><td></td><td></td></tr><tr><td>Min-Max Downhill Plow Problem with Multiple Plows</td><td>MM k-DPP</td><td></td><td></td><td></td></tr><tr><td>Min-Max Windy Rural Postman Problem</td><td>MM k-WRPP</td><td></td><td></td><td></td></tr><tr><td>Plowing with Precedence Problem</td><td>PPP</td><td></td><td></td><td></td></tr><tr><td>Min-Max Extended Downhill Plow Problem</td><td>MM k-DPPE</td><td></td><td></td><td></td></tr><tr><td>Capacitated Chinese Postman Problem</td><td>CCPP</td><td></td><td></td><td></td></tr><tr><td>Directed Chinese Postman Problem</td><td>DCPP</td><td></td><td></td><td></td></tr><tr><td>Directed Rural Postman Problem</td><td>DRPP</td><td></td><td></td><td></td></tr><tr><td>Extended Capacitated Arc Routing Problem</td><td>ECARP</td><td></td><td></td><td></td></tr><tr><td>Hierarchical Chinese Postman Problem</td><td>HCPP</td><td></td><td></td><td></td></tr><tr><td>Mixed Capacitated Arc Routing Problem</td><td>MCARP</td><td></td><td></td><td></td></tr><tr><td>Mixed Chinese Postman Problem</td><td>MCPP</td><td></td><td></td><td></td></tr><tr><td>Stacker Crane Problem</td><td>SCP</td><td>Certain arcs must be traversed at least once in one direction but can be traversed as many times in the other direction</td><td></td><td></td></tr><tr><td>Traveling Salesman Problem</td><td>TSP</td><td></td><td></td><td></td></tr><tr><td>Undirected Capacitated Arc Routing Problem</td><td>UCARP</td><td></td><td></td><td></td></tr><tr><td>Undirected Rural Postman Problem</td><td>URPP</td><td></td><td></td><td></td></tr><tr><td>Vehicle Routing Problem</td><td>VRP</td><td></td><td></td><td></td></tr><tr><td>Min-Max Multiple-Depot Rural Postman Problem</td><td>MMMDRPP<a class="footnote-ref" id="fnref:70" href="#fn:70">70</a></td><td></td><td></td><td></td></tr><tr><td>Generalized Vehicle Routing Problem</td><td>GVRP<a class="footnote-ref" id="fnref:71" href="#fn:71">71</a></td><td></td><td></td><td></td></tr></tbody></table>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.lancaster.ac.uk/lums/search/?q=arc+routing+problems">Arc Routing Problems Search page at Lancaster University</a></li>
<li><a href="http://www.gerad.ca/~alainh/Trends.pdf">Trends in Arc Routing</a></li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Route_inspection_problem/zh0EhCsU">Chinese postman problem</a> – Finding shortest walks through all graph edgesPages displaying short descriptions of redirect targets</li>
<li><a href="/facts/Vehicle_routing_problem/TS5pWNdR">Vehicle routing problem</a> – Optimization problem</li>
<li><a href="/facts/Travelling_salesman_problem/2WEKVLnV">Travelling salesman problem</a> – NP-hard problem in combinatorial optimization</li>
<li><a href="/facts/Eulerian_path/4l2G67c7">Eulerian path</a> – Trail in a graph that visits each edge once</li>
<li><a href="/facts/Capacitated_arc_routing_problem/p0Kkzkw7">Capacitated arc routing problem</a> – arc routing problem with capacity constraintsPages displaying wikidata descriptions as a fallback</li>
<li><a href="/facts/List_of_graph_theory_problems/VVPCd4TX">List of graph theory problems</a> – Area of discrete mathematicsPages displaying short descriptions of redirect targets</li>
<li><a href="/facts/Snow_plow_routing_problem/T46n5guU">Snow plow routing problem</a> – Application of Arc- and Vehicle Routing Problems to snow removal</li>
<li><a href="/facts/Chinese_Postman_Problem_Complexity_List/pM9Aj6g3">Chinese Postman Problem Complexity List</a> – Category of routing problem minimizing total distance and timePages displaying short descriptions of redirect targets</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02). "A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case". International Journal of Geographical Information Science. 32 (1): 169–190. Bibcode:2018IJGIS..32..169C. doi:10.1080/13658816.2017.1380201. ISSN 1365-8816. S2CID 29526595. <a href="https://doi.org/10.1080%2F13658816.2017.1380201" target="_blank">https://doi.org/10.1080%2F13658816.2017.1380201</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Omer, Masoud (2007). "Efficient routing of snow removal vehicles". <a href="https://researchrepository.wvu.edu/cgi/viewcontent.cgi?article=5362&context=etd" target="_blank">https://researchrepository.wvu.edu/cgi/viewcontent.cgi?article=5362&context=etd</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02). "A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case". International Journal of Geographical Information Science. 32 (1): 169–190. Bibcode:2018IJGIS..32..169C. doi:10.1080/13658816.2017.1380201. ISSN 1365-8816. S2CID 29526595. <a href="https://doi.org/10.1080%2F13658816.2017.1380201" target="_blank">https://doi.org/10.1080%2F13658816.2017.1380201</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Dussault, Benjamin; Golden, Bruce; Wasil, Edward (October 2014). "The downhill plow problem with multiple plows". Journal of the Operational Research Society. 65 (10): 1465–1474. doi:10.1057/jors.2013.83. ISSN 0160-5682. S2CID 36977043. <a href="https://www.tandfonline.com/doi/full/10.1057/jors.2013.83" target="_blank">https://www.tandfonline.com/doi/full/10.1057/jors.2013.83</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Eiselt, H. A.; Gendreau, Michel; Laporte, Gilbert (April 1995). "Arc Routing Problems, Part I: The Chinese Postman Problem". Operations Research. 43 (2): 231–242. doi:10.1287/opre.43.2.231. hdl:11059/14013. ISSN 0030-364X. <a href="https://doi.org/10.1287%2Fopre.43.2.231" target="_blank">https://doi.org/10.1287%2Fopre.43.2.231</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Delgado Serna, Cristina R.; Pacheco Bonrostro, Joaquín (2001), Voß, Stefan; Daduna, Joachim R. (eds.), "Minmax Vehicle Routing Problems: Application to School Transport in the Province of Burgos", Computer-Aided Scheduling of Public Transport, Berlin, Heidelberg: Springer, pp. 297–317, doi:10.1007/978-3-642-56423-9_17, ISBN 978-3-642-56423-9, retrieved 2022-05-01 <a href="978-3-642-56423-9" target="_blank">978-3-642-56423-9</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Omer, Masoud (2007). "Efficient routing of snow removal vehicles". <a href="https://researchrepository.wvu.edu/cgi/viewcontent.cgi?article=5362&context=etd" target="_blank">https://researchrepository.wvu.edu/cgi/viewcontent.cgi?article=5362&context=etd</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Bodin, Lawrence; Golden, Bruce (1981). "Classification in vehicle routing and scheduling". Networks. 11 (2): 97–108. doi:10.1002/net.3230110204. <a href="https://onlinelibrary.wiley.com/doi/10.1002/net.3230110204" target="_blank">https://onlinelibrary.wiley.com/doi/10.1002/net.3230110204</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Omer, Masoud (2007). "Efficient routing of snow removal vehicles". <a href="https://researchrepository.wvu.edu/cgi/viewcontent.cgi?article=5362&context=etd" target="_blank">https://researchrepository.wvu.edu/cgi/viewcontent.cgi?article=5362&context=etd</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02). "A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case". International Journal of Geographical Information Science. 32 (1): 169–190. Bibcode:2018IJGIS..32..169C. doi:10.1080/13658816.2017.1380201. ISSN 1365-8816. S2CID 29526595. <a href="https://doi.org/10.1080%2F13658816.2017.1380201" target="_blank">https://doi.org/10.1080%2F13658816.2017.1380201</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Omer, Masoud (2007). "Efficient routing of snow removal vehicles". <a href="https://researchrepository.wvu.edu/cgi/viewcontent.cgi?article=5362&context=etd" target="_blank">https://researchrepository.wvu.edu/cgi/viewcontent.cgi?article=5362&context=etd</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Bodin, Lawrence D.; Sexton, Thomas R. (February 1983). The Multi-Vehicle Subscriber Dial-A-Ride Problem (Technical report). Naval Postgraduate School. hdl:10945/63226. NPS55-83-002. <a href="https://calhoun.nps.edu/handle/10945/63226" target="_blank">https://calhoun.nps.edu/handle/10945/63226</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02). "A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case". International Journal of Geographical Information Science. 32 (1): 169–190. Bibcode:2018IJGIS..32..169C. doi:10.1080/13658816.2017.1380201. ISSN 1365-8816. S2CID 29526595. <a href="https://doi.org/10.1080%2F13658816.2017.1380201" target="_blank">https://doi.org/10.1080%2F13658816.2017.1380201</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Rabbani, Masoud; Alamdar, Safoura Famil; Farrokhi-Asl, Hamed (2016-02-01). "Capacitated Windy Rural Postman Problem with Several Vehicles: A Hybrid Multi-Objective Simulated Annealing Algorithm" (PDF). International Journal of Supply and Operations Management. 2 (4): 1003–20. doi:10.22034/2015.4.03. ISSN 2383-1359. <a href="http://www.ijsom.com/article_2619_d6c03fedd1ed8886e28cc52cc1c28caf.pdf" target="_blank">http://www.ijsom.com/article_2619_d6c03fedd1ed8886e28cc52cc1c28caf.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Benavent, E.; Corberán, A.; Piñana, E.; Plana, I.; Sanchis, J. M. (December 2005), "New heuristic algorithms for the windy rural postman problem", Computers and Operations Research, 32 (12): 3111–28, doi:10.1016/j.cor.2004.04.007, hdl:10251/94488 <a href="https://dl.acm.org/doi/abs/10.5555/1099064.1668279" target="_blank">https://dl.acm.org/doi/abs/10.5555/1099064.1668279</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Benavent, Enrique; Corberán, Ángel; Sanchis, José M. (July 2010). "A metaheuristic for the min–max windy rural postman problem with K vehicles". Computational Management Science. 7 (3): 269–287. doi:10.1007/s10287-009-0119-2. hdl:10251/100790. ISSN 1619-697X. S2CID 41426793. <a href="http://link.springer.com/10.1007/s10287-009-0119-2" target="_blank">http://link.springer.com/10.1007/s10287-009-0119-2</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Eiselt, H. A.; Gendreau, Michel; Laporte, Gilbert (April 1995). "Arc Routing Problems, Part I: The Chinese Postman Problem". Operations Research. 43 (2): 231–242. doi:10.1287/opre.43.2.231. hdl:11059/14013. ISSN 0030-364X. <a href="https://doi.org/10.1287%2Fopre.43.2.231" target="_blank">https://doi.org/10.1287%2Fopre.43.2.231</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Eiselt, H. A.; Gendreau, Michel; Laporte, Gilbert (April 1995). "Arc Routing Problems, Part I: The Chinese Postman Problem". Operations Research. 43 (2): 231–242. doi:10.1287/opre.43.2.231. hdl:11059/14013. ISSN 0030-364X. <a href="https://doi.org/10.1287%2Fopre.43.2.231" target="_blank">https://doi.org/10.1287%2Fopre.43.2.231</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">"Leonhard Euler and the Koenigsberg Bridges". Scientific American. July 1953. Retrieved 2022-04-30. <a href="https://www.scientificamerican.com/article/leonhard-euler-and-the-koenigsberg/" target="_blank">https://www.scientificamerican.com/article/leonhard-euler-and-the-koenigsberg/</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Eiselt, H. A.; Gendreau, Michel; Laporte, Gilbert (April 1995). "Arc Routing Problems, Part I: The Chinese Postman Problem". Operations Research. 43 (2): 231–242. doi:10.1287/opre.43.2.231. hdl:11059/14013. ISSN 0030-364X. <a href="https://doi.org/10.1287%2Fopre.43.2.231" target="_blank">https://doi.org/10.1287%2Fopre.43.2.231</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">H. A., Eiselt; Michel, Gendreau (1995). "Arc Routing Problems, Part II: The Rural Postman Problem". Operations Research. 43 (3): 399–414. doi:10.1287/opre.43.3.399. <a href="https://doi.org/10.1287%2Fopre.43.3.399" target="_blank">https://doi.org/10.1287%2Fopre.43.3.399</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">H. A., Eiselt; Michel, Gendreau (1995). "Arc Routing Problems, Part II: The Rural Postman Problem". Operations Research. 43 (3): 399–414. doi:10.1287/opre.43.3.399. <a href="https://doi.org/10.1287%2Fopre.43.3.399" target="_blank">https://doi.org/10.1287%2Fopre.43.3.399</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Minieka, Edward (July 1979). "The Chinese Postman Problem for Mixed Networks". Management Science. 25 (7): 643–648. doi:10.1287/mnsc.25.7.643. <a href="https://go.exlibris.link/Zrxk8KVH" target="_blank">https://go.exlibris.link/Zrxk8KVH</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Guan, Meigu (1984), "On the windy postman problem", Discrete Applied Mathematics, 9 (1): 41–46, doi:10.1016/0166-218X(84)90089-1, MR 0754427. <a href="/wiki/Meigu_Guan" target="_blank">/wiki/Meigu_Guan</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Lenstra, J.K.; Rinnooy Kan, A.H.G. (1981), "Complexity of vehicle routing and scheduling problems" (PDF), Networks, 11 (2): 221–7, doi:10.1002/net.3230110211 <a href="http://ageconsearch.umn.edu/record/272191/files/erasmus119.pdf" target="_blank">http://ageconsearch.umn.edu/record/272191/files/erasmus119.pdf</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Rabbani, Masoud; Alamdar, Safoura Famil; Farrokhi-Asl, Hamed (2016-02-01). "Capacitated Windy Rural Postman Problem with Several Vehicles: A Hybrid Multi-Objective Simulated Annealing Algorithm" (PDF). International Journal of Supply and Operations Management. 2 (4): 1003–20. doi:10.22034/2015.4.03. ISSN 2383-1359. <a href="http://www.ijsom.com/article_2619_d6c03fedd1ed8886e28cc52cc1c28caf.pdf" target="_blank">http://www.ijsom.com/article_2619_d6c03fedd1ed8886e28cc52cc1c28caf.pdf</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Corberán, Angel; Oswald, Marcus; Plana, Isaac; Reinelt, Gerhard; Sanchis, José M. (April 2012). "New results on the Windy Postman Problem". Mathematical Programming. 132 (1–2): 309–332. doi:10.1007/s10107-010-0399-x. ISSN 0025-5610. S2CID 12808962. <a href="http://link.springer.com/10.1007/s10107-010-0399-x" target="_blank">http://link.springer.com/10.1007/s10107-010-0399-x</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Corberán, Angel; Oswald, Marcus; Plana, Isaac; Reinelt, Gerhard; Sanchis, José M. (April 2012). "New results on the Windy Postman Problem". Mathematical Programming. 132 (1–2): 309–332. doi:10.1007/s10107-010-0399-x. ISSN 0025-5610. S2CID 12808962. <a href="http://link.springer.com/10.1007/s10107-010-0399-x" target="_blank">http://link.springer.com/10.1007/s10107-010-0399-x</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Benavent, Enrique; Corberán, Ángel; Sanchis, José M. (July 2010). "A metaheuristic for the min–max windy rural postman problem with K vehicles". Computational Management Science. 7 (3): 269–287. doi:10.1007/s10287-009-0119-2. hdl:10251/100790. ISSN 1619-697X. S2CID 41426793. <a href="http://link.springer.com/10.1007/s10287-009-0119-2" target="_blank">http://link.springer.com/10.1007/s10287-009-0119-2</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Benavent, Enrique; Corberán, Ángel; Sanchis, José M. (July 2010). "A metaheuristic for the min–max windy rural postman problem with K vehicles". Computational Management Science. 7 (3): 269–287. doi:10.1007/s10287-009-0119-2. hdl:10251/100790. ISSN 1619-697X. S2CID 41426793. <a href="http://link.springer.com/10.1007/s10287-009-0119-2" target="_blank">http://link.springer.com/10.1007/s10287-009-0119-2</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Benavent, E.; Corberán, A.; Piñana, E.; Plana, I.; Sanchis, J. M. (December 2005), "New heuristic algorithms for the windy rural postman problem", Computers and Operations Research, 32 (12): 3111–28, doi:10.1016/j.cor.2004.04.007, hdl:10251/94488 <a href="https://dl.acm.org/doi/abs/10.5555/1099064.1668279" target="_blank">https://dl.acm.org/doi/abs/10.5555/1099064.1668279</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Benavent, E.; Corberán, A.; Piñana, E.; Plana, I.; Sanchis, J. M. (December 2005), "New heuristic algorithms for the windy rural postman problem", Computers and Operations Research, 32 (12): 3111–28, doi:10.1016/j.cor.2004.04.007, hdl:10251/94488 <a href="https://dl.acm.org/doi/abs/10.5555/1099064.1668279" target="_blank">https://dl.acm.org/doi/abs/10.5555/1099064.1668279</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Benavent, Enrique; Corberán, Ángel; Sanchis, José M. (July 2010). "A metaheuristic for the min–max windy rural postman problem with K vehicles". Computational Management Science. 7 (3): 269–287. doi:10.1007/s10287-009-0119-2. hdl:10251/100790. ISSN 1619-697X. S2CID 41426793. <a href="http://link.springer.com/10.1007/s10287-009-0119-2" target="_blank">http://link.springer.com/10.1007/s10287-009-0119-2</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Rabbani, Masoud; Alamdar, Safoura Famil; Farrokhi-Asl, Hamed (2016-02-01). "Capacitated Windy Rural Postman Problem with Several Vehicles: A Hybrid Multi-Objective Simulated Annealing Algorithm" (PDF). International Journal of Supply and Operations Management. 2 (4): 1003–20. doi:10.22034/2015.4.03. ISSN 2383-1359. <a href="http://www.ijsom.com/article_2619_d6c03fedd1ed8886e28cc52cc1c28caf.pdf" target="_blank">http://www.ijsom.com/article_2619_d6c03fedd1ed8886e28cc52cc1c28caf.pdf</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Yang, Xin-She (2010). "Engineering Optimisation by Cuckoo Search". International Journal of Mathematical Modelling and Numerical Optimisation. 1 (4): 330–343. arXiv:1005.2908. doi:10.1504/IJMMNO.2010.035430. S2CID 34889796. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Rabbani, Masoud; Alamdar, Safoura Famil; Farrokhi-Asl, Hamed (2016-02-01). "Capacitated Windy Rural Postman Problem with Several Vehicles: A Hybrid Multi-Objective Simulated Annealing Algorithm" (PDF). International Journal of Supply and Operations Management. 2 (4): 1003–20. doi:10.22034/2015.4.03. ISSN 2383-1359. <a href="http://www.ijsom.com/article_2619_d6c03fedd1ed8886e28cc52cc1c28caf.pdf" target="_blank">http://www.ijsom.com/article_2619_d6c03fedd1ed8886e28cc52cc1c28caf.pdf</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Dussault, Benjamin; Golden, Bruce; Wasil, Edward (October 2014). "The downhill plow problem with multiple plows". Journal of the Operational Research Society. 65 (10): 1465–1474. doi:10.1057/jors.2013.83. ISSN 0160-5682. S2CID 36977043. <a href="https://www.tandfonline.com/doi/full/10.1057/jors.2013.83" target="_blank">https://www.tandfonline.com/doi/full/10.1057/jors.2013.83</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Dussault, Benjamin; Golden, Bruce; Wasil, Edward (October 2014). "The downhill plow problem with multiple plows". Journal of the Operational Research Society. 65 (10): 1465–1474. doi:10.1057/jors.2013.83. ISSN 0160-5682. S2CID 36977043. <a href="https://www.tandfonline.com/doi/full/10.1057/jors.2013.83" target="_blank">https://www.tandfonline.com/doi/full/10.1057/jors.2013.83</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Corberán, Angel; Oswald, Marcus; Plana, Isaac; Reinelt, Gerhard; Sanchis, José M. (April 2012). "New results on the Windy Postman Problem". Mathematical Programming. 132 (1–2): 309–332. doi:10.1007/s10107-010-0399-x. ISSN 0025-5610. S2CID 12808962. <a href="http://link.springer.com/10.1007/s10107-010-0399-x" target="_blank">http://link.springer.com/10.1007/s10107-010-0399-x</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002). <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">Dussault, Benjamin; Golden, Bruce; Wasil, Edward (October 2014). "The downhill plow problem with multiple plows". Journal of the Operational Research Society. 65 (10): 1465–1474. doi:10.1057/jors.2013.83. ISSN 0160-5682. S2CID 36977043. <a href="https://www.tandfonline.com/doi/full/10.1057/jors.2013.83" target="_blank">https://www.tandfonline.com/doi/full/10.1057/jors.2013.83</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Gutin, Gregory; Muciaccia, Gabriele; Yeo, Anders (2013-11-18). "Parameterized complexity of k-Chinese Postman Problem". Theoretical Computer Science. 513: 124–128. arXiv:1308.0482. doi:10.1016/j.tcs.2013.10.012. ISSN 0304-3975. S2CID 2867281. <a href="https://doi.org/10.1016%2Fj.tcs.2013.10.012" target="_blank">https://doi.org/10.1016%2Fj.tcs.2013.10.012</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">Benavent, Enrique; Soler, David (November 1999). "The Directed Rural Postman Problem with Turn Penalties". Transportation Science. 33 (4): 408–418. doi:10.1287/trsc.33.4.408. ISSN 0041-1655. <a href="https://dx.doi.org/10.1287/trsc.33.4.408" target="_blank">https://dx.doi.org/10.1287/trsc.33.4.408</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Hertz, Alain. "Recent trends in arc routing" (PDF). Ecole Polytechnique — GERAD. <a href="http://www.gerad.ca/~alainh/Trends.pdf" target="_blank">http://www.gerad.ca/~alainh/Trends.pdf</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Edmonds, Jack; Johnson, Ellis L. (1973). "Matching, Euler tours and the Chinese postman". Mathematical Programming. 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610. S2CID 15249924. <a href="https://dx.doi.org/10.1007/bf01580113" target="_blank">https://dx.doi.org/10.1007/bf01580113</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">Edmonds, Jack; Johnson, Ellis L. (1973). "Matching, Euler tours and the Chinese postman". Mathematical Programming. 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610. S2CID 15249924. <a href="https://dx.doi.org/10.1007/bf01580113" target="_blank">https://dx.doi.org/10.1007/bf01580113</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">Yaxiong, Lin; Yongchang, Zhao (January 1988). "A new algorithm for the directed chinese postman problem". Computers & Operations Research. 15 (6): 577–584. doi:10.1016/0305-0548(88)90053-6. ISSN 0305-0548. <a href="https://dx.doi.org/10.1016/0305-0548(88)90053-6" target="_blank">https://dx.doi.org/10.1016/0305-0548(88)90053-6</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
<li id="fn:48">Papadimitriou, Christos H. (July 1976). "On the complexity of edge traversing". Journal of the ACM. 23 (3): 544–554. doi:10.1145/321958.321974. ISSN 0004-5411. S2CID 8625996. <a href="https://doi.org/10.1145%2F321958.321974" target="_blank">https://doi.org/10.1145%2F321958.321974</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></li>
<li id="fn:49">Edmonds, Jack; Johnson, Ellis L. (1973). "Matching, Euler tours and the Chinese postman". Mathematical Programming. 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610. S2CID 15249924. <a href="https://dx.doi.org/10.1007/bf01580113" target="_blank">https://dx.doi.org/10.1007/bf01580113</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></li>
<li id="fn:50">Raghavachari, Balaji; Veerasamy, Jeyakesavan (January 1999). "A 3/2-Approximation Algorithm for the Mixed Postman Problem". SIAM Journal on Discrete Mathematics. 12 (4): 425–433. doi:10.1137/s0895480197331454. ISSN 0895-4801. <a href="https://dx.doi.org/10.1137/s0895480197331454" target="_blank">https://dx.doi.org/10.1137/s0895480197331454</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></li>
<li id="fn:51">Gutin, Gregory; Jones, Mark; Sheng, Bin (2014), "Parameterized Complexity of the k-Arc Chinese Postman Problem", Algorithms - ESA 2014, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 530–541, arXiv:1403.1512, doi:10.1007/978-3-662-44777-2_44, ISBN 978-3-662-44776-5, S2CID 3472348, retrieved 2022-05-09 <a href="978-3-662-44776-5" target="_blank">978-3-662-44776-5</a> <a href="#fnref:51" class="footnote-back-ref">↩</a></li>
<li id="fn:52">Gutin, Gregory; Jones, Mark; Sheng, Bin (2014), "Parameterized Complexity of the k-Arc Chinese Postman Problem", Algorithms - ESA 2014, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 530–541, arXiv:1403.1512, doi:10.1007/978-3-662-44777-2_44, ISBN 978-3-662-44776-5, S2CID 3472348, retrieved 2022-05-09 <a href="978-3-662-44776-5" target="_blank">978-3-662-44776-5</a> <a href="#fnref:52" class="footnote-back-ref">↩</a></li>
<li id="fn:53">Fernandes, Cristina G.; Lee, Orlando; Wakabayashi, Yoshiko (January 2009). "Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width". Discrete Applied Mathematics. 157 (2): 272–279. doi:10.1016/j.dam.2007.10.032. ISSN 0166-218X. <a href="/wiki/Yoshiko_Wakabayashi" target="_blank">/wiki/Yoshiko_Wakabayashi</a> <a href="#fnref:53" class="footnote-back-ref">↩</a></li>
<li id="fn:54">Guan, Meigu (September 1984). "On the windy postman problem". Discrete Applied Mathematics. 9 (1): 41–46. doi:10.1016/0166-218x(84)90089-1. ISSN 0166-218X. <a href="https://doi.org/10.1016%2F0166-218x%2884%2990089-1" target="_blank">https://doi.org/10.1016%2F0166-218x%2884%2990089-1</a> <a href="#fnref:54" class="footnote-back-ref">↩</a></li>
<li id="fn:55">Guan, Meigu (September 1984). "On the windy postman problem". Discrete Applied Mathematics. 9 (1): 41–46. doi:10.1016/0166-218x(84)90089-1. ISSN 0166-218X. <a href="https://doi.org/10.1016%2F0166-218x%2884%2990089-1" target="_blank">https://doi.org/10.1016%2F0166-218x%2884%2990089-1</a> <a href="#fnref:55" class="footnote-back-ref">↩</a></li>
<li id="fn:56">Win, Zaw (May 1989). "On the Windy Postman Problem on eulerian graphs". Mathematical Programming. 44 (1–3): 97–112. doi:10.1007/bf01587080. ISSN 0025-5610. S2CID 206800125. <a href="https://dx.doi.org/10.1007/bf01587080" target="_blank">https://dx.doi.org/10.1007/bf01587080</a> <a href="#fnref:56" class="footnote-back-ref">↩</a></li>
<li id="fn:57">Veerasamy, Jeyakesavan (1999). Approximation algorithms for Postman problems (PhD thesis). University of Texas at Dallas. <a href="#fnref:57" class="footnote-back-ref">↩</a></li>
<li id="fn:58">Dror, Moshe; Stern, Helman; Trudeau, Pierre (1987). "Postman tour on a graph with precedence relation on arcs". Networks. 17 (3): 283–294. doi:10.1002/net.3230170304. ISSN 0028-3045. <a href="https://dx.doi.org/10.1002/net.3230170304" target="_blank">https://dx.doi.org/10.1002/net.3230170304</a> <a href="#fnref:58" class="footnote-back-ref">↩</a></li>
<li id="fn:59">"12th world computer congress— IFIP congress'92". Computers in Industry. 20 (1): 124–126. January 1992. doi:10.1016/0166-3615(92)90137-c. ISSN 0166-3615. <a href="https://doi.org/10.1016%2F0166-3615%2892%2990137-c" target="_blank">https://doi.org/10.1016%2F0166-3615%2892%2990137-c</a> <a href="#fnref:59" class="footnote-back-ref">↩</a></li>
<li id="fn:60">Thomassen, Carsten (June 1997). "On the Complexity of Finding a Minimum Cycle Cover of a Graph". SIAM Journal on Computing. 26 (3): 675–677. doi:10.1137/s0097539794267255. ISSN 0097-5397. <a href="https://dx.doi.org/10.1137/s0097539794267255" target="_blank">https://dx.doi.org/10.1137/s0097539794267255</a> <a href="#fnref:60" class="footnote-back-ref">↩</a></li>
<li id="fn:61">Corberán, Ángel (2015). Arc Routing: Problems, Methods, and Applications. ISBN 978-1-61197-366-2. <a href="978-1-61197-366-2" target="_blank">978-1-61197-366-2</a> <a href="#fnref:61" class="footnote-back-ref">↩</a></li>
<li id="fn:62">Frederickson, Greg N.; Hecht, Matthew S.; Kim, Chul E. (May 1978). "Approximation Algorithms for Some Routing Problems". SIAM Journal on Computing. 7 (2): 178–193. doi:10.1137/0207017. ISSN 0097-5397. S2CID 7562375. <a href="https://dx.doi.org/10.1137/0207017" target="_blank">https://dx.doi.org/10.1137/0207017</a> <a href="#fnref:62" class="footnote-back-ref">↩</a></li>
<li id="fn:63">Frederickson, Greg N.; Hecht, Matthew S.; Kim, Chul E. (May 1978). "Approximation Algorithms for Some Routing Problems". SIAM Journal on Computing. 7 (2): 178–193. doi:10.1137/0207017. ISSN 0097-5397. S2CID 7562375. <a href="https://dx.doi.org/10.1137/0207017" target="_blank">https://dx.doi.org/10.1137/0207017</a> <a href="#fnref:63" class="footnote-back-ref">↩</a></li>
<li id="fn:64">Eiselt, H (May 1995). "Arc routing problems, part II: The rural postman problem". p. 399. ProQuest 219174102. <a href="https://www.proquest.com/docview/219174102" target="_blank">https://www.proquest.com/docview/219174102</a> <a href="#fnref:64" class="footnote-back-ref">↩</a></li>
<li id="fn:65">Guan, Meigu (1962). "Graphic programming using odd or even points". Chinese Mathematics. <a href="#fnref:65" class="footnote-back-ref">↩</a></li>
<li id="fn:66">Dussault, Benjamin; Golden, Bruce; Groër, Chris; Wasil, Edward (2013-04-01). "Plowing with precedence: A variant of the windy postman problem". Computers & Operations Research. 40 (4): 1047–1059. doi:10.1016/j.cor.2012.10.013. ISSN 0305-0548. <a href="https://www.sciencedirect.com/science/article/pii/S0305054812002250" target="_blank">https://www.sciencedirect.com/science/article/pii/S0305054812002250</a> <a href="#fnref:66" class="footnote-back-ref">↩</a></li>
<li id="fn:67">Dussault, Benjamin; Golden, Bruce; Wasil, Edward (2014-10-01). "The downhill plow problem with multiple plows". Journal of the Operational Research Society. 65 (10): 1465–1474. doi:10.1057/jors.2013.83. ISSN 1476-9360. S2CID 36977043. <a href="https://doi.org/10.1057/jors.2013.83" target="_blank">https://doi.org/10.1057/jors.2013.83</a> <a href="#fnref:67" class="footnote-back-ref">↩</a></li>
<li id="fn:68">Dussault, Benjamin; Golden, Bruce; Wasil, Edward (2014-10-01). "The downhill plow problem with multiple plows". Journal of the Operational Research Society. 65 (10): 1465–1474. doi:10.1057/jors.2013.83. ISSN 1476-9360. S2CID 36977043. <a href="https://doi.org/10.1057/jors.2013.83" target="_blank">https://doi.org/10.1057/jors.2013.83</a> <a href="#fnref:68" class="footnote-back-ref">↩</a></li>
<li id="fn:69">Dussualt, Benjamin (2012). "Modeling and solving arc routing problems in street sweeping and snow plowing". ProQuest. <a href="https://www.proquest.com/dissertations-theses/modeling-solving-arc-routing-problems-street/" target="_blank">https://www.proquest.com/dissertations-theses/modeling-solving-arc-routing-problems-street/</a> <a href="#fnref:69" class="footnote-back-ref">↩</a></li>
<li id="fn:70">Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02). "A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case". International Journal of Geographical Information Science. 32 (1): 169–190. Bibcode:2018IJGIS..32..169C. doi:10.1080/13658816.2017.1380201. ISSN 1365-8816. S2CID 29526595. <a href="https://doi.org/10.1080%2F13658816.2017.1380201" target="_blank">https://doi.org/10.1080%2F13658816.2017.1380201</a> <a href="#fnref:70" class="footnote-back-ref">↩</a></li>
<li id="fn:71">Ghiani, Gianpaolo; Improta, Gennaro (2000-04-01). "An efficient transformation of the generalized vehicle routing problem". European Journal of Operational Research. 122 (1): 11–17. doi:10.1016/S0377-2217(99)00073-9. ISSN 0377-2217. <a href="https://www.sciencedirect.com/science/article/pii/S0377221799000739" target="_blank">https://www.sciencedirect.com/science/article/pii/S0377221799000739</a> <a href="#fnref:71" class="footnote-back-ref">↩</a></li>
</ol>

Arc routing open-in-new

Arc routing