799:
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. 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, also referred to as Multi-objective Cuckoo Search and abbreviated by MOCS. 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.
823:
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. 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.
792:, 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).
127:
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.
484:
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.
1513:
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).
373:. 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.
827:
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.
802:
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
99:
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
1631:
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
1512:
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
487:
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
368:
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,
302:
The work on the
Eulerian circuits was popularized with Scientific American on July 1, 1953. 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
822:
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
339:
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
126:
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
483:
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
26:
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
1640:
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
690:
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
798:
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
826:
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
356:. 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.
327:. 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
108:
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.
694:
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
298:
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.
340:
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.
152:(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
303:
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."
117:
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.
100:
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.
1648:
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.
87:
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.
1460:
135:
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.
82:
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
270:. 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.
2070:
1632:
Directed Rural Postman Problem with Turn Penalties (DRPP-TP). Benevant's algorithm approximated the solution by transforming the DRPP-TP into an asymmetrical traveling salesman problem (ATSP).
806:
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.
323:
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
814:
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.
331:. 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.
687:, 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.
2141:
795:
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.
1885:
790:
685:
649:
1617:
952:
248:
481:
2221:
2340:
2279:
1945:
1803:
1746:
1254:
1165:
1076:
987:
866:
731:
524:
443:
410:
757:
584:
554:
1507:
1362:
1335:
1308:
1281:
1219:
1192:
1130:
1103:
1041:
1014:
616:
202:
803:
cost of plowing uphill is greater than the cost of plowing downhill. This is modeled by a variant studied by Dussault et al, the Downhill Plowing Problem (DPP).
144:
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
1480:
906:
886:
2407:"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."
1462:. In practice, downhill plowing time is two times as efficient as uphill plowing and deadheading is twice as efficient as plowing. The algorithm finds
2908:
4289:
3980:
3139:
4646:
1367:
91:
There are generalizations of arc routing problems that introduce multiple mailmen, for example the k Chinese Postman Problem (KCPP).
618:
starting from i and j, respectively. G is the windy graph and we are interested in the subset of edges, or in mathematical symbols,
1641:
single, non-required edge, regardless of the number of edges in the path, provided that there were no required edges in the path.
376:
The windy postman problem is an arc routing problem (ARP) that contains the Mixed Chinese Postman Problem MCPP as a special case.
1953:
379:
The problem can be defined in the following manner: "Given an undirected and connected graph G=(V,E) with two non-negative costs
2893:
4527:
2388:
279:
4651:
2898:
691:
found solutions that deviated by less than 2% when implemented on networks with hundreds of nodes and thousands of edges.
149:
3471:
2756:
Certain arcs must be traversed at least once in one direction but can be traversed as many times in the other direction
153:
3225:"Capacitated Windy Rural Postman Problem with Several Vehicles: A Hybrid Multi-Objective Simulated Annealing Algorithm"
4641:
2992:
2883:
165:
3374:
2903:
2873:
72:
4549:"A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case"
2937:"A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case"
169:
2077:
2878:
48:
3224:
1809:
4360:
353:
3118:
Delgado Serna, Cristina R.; Pacheco Bonrostro, JoaquĂn (2001), VoĂ, Stefan; Daduna, Joachim R. (eds.),
4597:
4394:
762:
657:
621:
311:
Arc routing problems (ARPs) differ in their goal and heuristics. However, all of them are known to be
1571:
1509:, plow the arc two times because the left side and right side of the street take two passes to plow.
251:
2383:
Determine a least-cost traversal of a specified arc subset of a graph, with or without constraints.
4010:
1653:
911:
267:
263:
255:
207:
161:
448:
4578:
4508:
4461:
4337:
4127:
3986:
3958:
3889:
3801:
3692:
3664:
3620:
3602:
3575:
3509:
3356:
3042:
2966:
2856:
2177:
84:
3546:
Corberån, Angel; Oswald, Marcus; Plana, Isaac; Reinelt, Gerhard; Sanchis, José M. (April 2012).
2299:
2238:
1904:
1762:
1705:
1224:
1135:
1046:
957:
3637:
A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002).
1552:
is contained in at least one of them and the total weight of the edges in the walks is at most
833:
698:
491:
4617:
4570:
4500:
4453:
4414:
4329:
4285:
4260:
4221:
4181:
4119:
4080:
4036:
3976:
3928:
3881:
3840:
3793:
3731:
3684:
3567:
3348:
3247:
3135:
3100:
3034:
2958:
654:
If the WRPP includes the additional constraint that a certain set of vertices must be visitedâ
349:
3161:
415:
382:
4609:
4560:
4492:
4445:
4406:
4321:
4252:
4211:
4173:
4111:
4070:
4026:
3968:
3920:
3871:
3832:
3785:
3723:
3674:
3612:
3559:
3524:
3480:
3448:
3415:
3338:
3330:
3291:
3283:
3239:
3198:
3173:
3127:
3120:"Minmax Vehicle Routing Problems: Application to School Transport in the Province of Burgos"
3090:
3080:
3026:
3014:
2948:
736:
559:
529:
157:
32:
3494:
1485:
1340:
1313:
1286:
1259:
1197:
1170:
1108:
1081:
1019:
992:
589:
175:
4015:"Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width"
3490:
76:
250:. In addition to these algorithms, these classes of problems can also be solved with the
1659:
1465:
891:
871:
283:
60:
31:
time, the time it takes to reach a destination. Arc routing problems can be applied to
4613:
4635:
4216:
4199:
4131:
4075:
4058:
3836:
3547:
3485:
3318:
3271:
2888:
287:
278:
The earliest documented reference to the area of arc routing problems is the classic
4582:
4512:
4465:
3805:
3624:
3579:
3360:
3046:
2970:
4341:
3990:
3893:
3696:
3270:
Benavent, E.; Corberån, A.; Piñana, E.; Plana, I.; Sanchis, J. M. (December 2005),
44:
28:
4565:
4548:
3950:
3820:
2953:
2936:
1532:-Chinese Postman can be stated as follows: "given a connected edge-weighted graph
3972:
3131:
1672:
This is a list of computational complexities for different arc routing problems.
348:
The URPP was first introduced in 1974 and was proven to be an NP-hard problem by
4364:
1645:
370:
291:
259:
68:
4528:"Modeling and solving arc routing problems in street sweeping and snow plowing"
4240:
3908:
3616:
3119:
4410:
4256:
4031:
4014:
3924:
3679:
3648:
3563:
3466:
3334:
3287:
64:
36:
4621:
4574:
4504:
4457:
4418:
4393:
Dussault, Benjamin; Golden, Bruce; Groër, Chris; Wasil, Edward (2013-04-01).
4356:
4333:
4264:
4225:
4185:
4123:
4084:
4040:
3932:
3885:
3844:
3797:
3735:
3688:
3571:
3352:
3319:"A metaheuristic for the minâmax windy rural postman problem with K vehicles"
3251:
3192:
3104:
3038:
2962:
4161:
1652:
Methods of solving the URPP after the pre-processing is done consist of the
4177:
3711:
3528:
3223:
Rabbani, Masoud; Alamdar, Safoura Famil; Farrokhi-Asl, Hamed (2016-02-01).
3177:
3876:
3859:
3727:
3595:
International Journal of Mathematical Modelling and Numerical Optimisation
3452:
3420:
3403:
3085:
3068:
4532:
4496:
4449:
3750:
3030:
2861:
295:
4598:"An efficient transformation of the generalized vehicle routing problem"
4099:
3773:
3343:
4480:
4433:
4115:
3789:
3296:
3243:
3202:
3095:
1644:
Once the pre-processing is done, the problem can be generalized into a
1560:-CPP is NP complete. Gutin, Muciaccia, and Yeo proved in 2013 that the
312:
40:
2993:"Efficient routing of snow r outing of snow removal vehicles vehicles"
4309:
1455:{\displaystyle c_{ij}^{+}\gg c_{ji}^{+}\gg c_{ij}^{-}\geq c_{ji}^{-}}
4378:
Guan, Meigu (1962). "Graphic programming using odd or even points".
4325:
3957:, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 530â541,
3436:
4308:
Frederickson, Greg N.; Hecht, Matthew S.; Kim, Chul E. (May 1978).
3593:
Yang, Xin-She (2010). "Engineering Optimisation by Cuckoo Search".
3963:
3669:
3607:
3317:
Benavent, Enrique; CorberĂĄn, Ăngel; Sanchis, JosĂ© M. (July 2010).
4395:"Plowing with precedence: A variant of the windy postman problem"
3013:
Dussault, Benjamin; Golden, Bruce; Wasil, Edward (October 2014).
2421:
Traverse a subset of the edges E at least once with minimum cost
294:, wanted to find a way to cross all seven bridges over the river
3067:
Eiselt, H. A.; Gendreau, Michel; Laporte, Gilbert (April 1995).
56:
52:
4479:
Dussault, Benjamin; Golden, Bruce; Wasil, Edward (2014-10-01).
4432:
Dussault, Benjamin; Golden, Bruce; Wasil, Edward (2014-10-01).
4241:"On the Complexity of Finding a Minimum Cycle Cover of a Graph"
3951:"Parameterized Complexity of the k-Arc Chinese Postman Problem"
3647:
Gutin, Gregory; Muciaccia, Gabriele; Yeo, Anders (2013-11-18).
2281:-time algorithm with post office vertex, otherwise NP-complete
3272:"New heuristic algorithms for the windy rural postman problem"
16:
Category of routing problem minimizing total distance and time
3909:"A 3/2-Approximation Algorithm for the Mixed Postman Problem"
3907:
Raghavachari, Balaji; Veerasamy, Jeyakesavan (January 1999).
4547:
Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02).
3069:"Arc Routing Problems, Part I: The Chinese Postman Problem"
2935:
Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02).
2065:{\displaystyle O(\max\{|V|^{3},|A|(\max\{|A|,|E|\})^{2}\})}
4357:"Arc routing problems, part II: The rural postman problem"
4162:"Postman tour on a graph with precedence relation on arcs"
3821:"A new algorithm for the directed chinese postman problem"
3404:"Arc Routing Problems, Part II: The Rural Postman Problem"
1564:-CPP is fixed-parameter tractable. The authors prove the
4553:
International Journal of Geographical Information Science
3232:
International Journal of Supply and Operations Management
2941:
International Journal of Geographical Information Science
3712:"The Directed Rural Postman Problem with Turn Penalties"
2857:
Arc Routing Problems Search page at Lancaster University
2418:
undirected graph G with Vertices V and weighted edges E
2401:
undirected graph G with Vertices V and weighted edges E
4303:
4301:
3510:"Complexity of vehicle routing and scheduling problems"
3191:
Bodin, Lawrence D.; Sexton, Thomas R. (February 1983).
759:, representing the depot, a subset of required edges
2302:
2241:
2180:
2080:
1956:
1907:
1812:
1765:
1708:
1574:
1488:
1468:
1370:
1343:
1316:
1289:
1262:
1227:
1200:
1173:
1138:
1111:
1084:
1049:
1022:
995:
960:
914:
894:
874:
836:
765:
739:
701:
660:
624:
592:
562:
532:
494:
451:
418:
385:
210:
178:
4310:"Approximation Algorithms for Some Routing Problems"
4160:
Dror, Moshe; Stern, Helman; Trudeau, Pierre (1987).
3008:
3006:
3004:
3002:
2404:
Traverse every edge at least once with minimal cost
2286:
In FPT with respect to k without post office vertex
4596:Ghiani, Gianpaolo; Improta, Gennaro (2000-04-01).
3162:"Classification in vehicle routing and scheduling"
3126:, Berlin, Heidelberg: Springer, pp. 297â317,
2596:Min-Max Downhill Plow Problem with Multiple Plows
2334:
2273:
2215:
2135:
2064:
1939:
1879:
1797:
1740:
1611:
1501:
1474:
1454:
1356:
1329:
1302:
1275:
1248:
1213:
1186:
1159:
1124:
1097:
1070:
1035:
1008:
981:
946:
900:
880:
860:
784:
751:
725:
679:
643:
610:
578:
548:
518:
475:
437:
404:
242:
196:
4100:"On the Windy Postman Problem on eulerian graphs"
3710:Benavent, Enrique; Soler, David (November 1999).
4281:Arc Routing: Problems, Methods, and Applications
4200:"12th world computer congressâ IFIP congress'92"
3949:Gutin, Gregory; Jones, Mark; Sheng, Bin (2014),
3437:"The Chinese Postman Problem for Mixed Networks"
3194:The Multi-Vehicle Subscriber Dial-A-Ride Problem
2554:Rural Downhill Plow Problem with Turn Penalties
2008:
1963:
1556:?" The process of obtaining the solution to the
39:route planning, package and newspaper delivery,
4481:"The downhill plow problem with multiple plows"
4434:"The downhill plow problem with multiple plows"
3774:"Matching, Euler tours and the Chinese postman"
3197:(Technical report). Naval Postgraduate School.
3015:"The downhill plow problem with multiple plows"
1627:Rural postman problem (RPP) and generalizations
3819:Yaxiong, Lin; Yongchang, Zhao (January 1988).
1947:-time solvable if each vertex has even degree
586:associated with the cost to traverse the edge
488:go up than down. Consider an undirected graph
4147:Approximation algorithms for Postman problems
3124:Computer-Aided Scheduling of Public Transport
2821:Min-Max Multiple-Depot Rural Postman Problem
2223:-time solvable if precedence relation linear
1482:routes will each begin and end at the depot
8:
4149:(PhD thesis). University of Texas at Dallas.
3375:"Leonhard Euler and the Koenigsberg Bridges"
2056:
2043:
2011:
1966:
908:is the set of arcs. Each arc represented by
855:
843:
720:
708:
513:
501:
464:
452:
63:, police and security guard patrolling, and
4485:Journal of the Operational Research Society
4438:Journal of the Operational Research Society
3541:
3539:
3537:
3508:Lenstra, J.K.; Rinnooy Kan, A.H.G. (1981),
3019:Journal of the Operational Research Society
2779:Undirected Capacitated Arc Routing Problem
3548:"New results on the Windy Postman Problem"
2540:Downhill Plow Problem with Turn Penalties
2442:Rural Postman Problem with Turn Penalties
335:Undirected capacitated arc routing problem
4564:
4215:
4074:
4030:
3962:
3875:
3772:Edmonds, Jack; Johnson, Ellis L. (1973).
3678:
3668:
3606:
3484:
3419:
3342:
3295:
3094:
3084:
2952:
2694:Extended Capacitated Arc Routing Problem
2323:
2318:
2309:
2301:
2262:
2257:
2248:
2240:
2204:
2199:
2190:
2179:
2124:
2119:
2110:
2100:
2092:
2091:
2079:
2050:
2038:
2030:
2022:
2014:
2000:
1992:
1983:
1978:
1969:
1955:
1928:
1923:
1914:
1906:
1868:
1863:
1854:
1846:
1838:
1830:
1822:
1811:
1786:
1781:
1772:
1764:
1729:
1724:
1715:
1707:
1619:vertices and the directed version of the
1585:
1573:
1493:
1487:
1467:
1446:
1438:
1425:
1417:
1404:
1396:
1383:
1375:
1369:
1348:
1342:
1321:
1315:
1294:
1288:
1267:
1261:
1240:
1232:
1226:
1205:
1199:
1178:
1172:
1151:
1143:
1137:
1116:
1110:
1089:
1083:
1062:
1054:
1048:
1027:
1021:
1000:
994:
973:
965:
959:
935:
922:
913:
893:
873:
835:
770:
764:
738:
700:
665:
659:
629:
623:
591:
567:
561:
537:
531:
493:
450:
423:
417:
390:
384:
286:proved to be impossible. The resident of
231:
221:
209:
177:
4602:European Journal of Operational Research
3858:Papadimitriou, Christos H. (July 1976).
3469:(1984), "On the windy postman problem",
3402:H. A., Eiselt; Michel, Gendreau (1995).
3397:
3395:
2354:
1674:
3160:Bodin, Lawrence; Golden, Bruce (1981).
2920:
2909:Chinese Postman Problem Complexity List
2638:Min-Max Extended Downhill Plow Problem
2136:{\displaystyle O(2^{|E|}\cdot |V|^{3})}
4052:
4050:
4009:Fernandes, Cristina G.; Lee, Orlando;
3944:
3942:
3860:"On the complexity of edge traversing"
3767:
3765:
3763:
3218:
3216:
3214:
3212:
2722:Mixed Capacitated Arc Routing Problem
989:, defined as the cost of plowing from
3312:
3310:
3308:
3306:
2708:Hierarchical Chinese Postman Problem
1548:closed walks such that every edge of
888:is the set of vertices and nodes and
148:-Chinese postman problem (KCPP), the
7:
3913:SIAM Journal on Discrete Mathematics
3265:
3263:
3261:
3062:
3060:
3058:
3056:
2986:
2984:
2982:
2980:
2930:
2928:
2926:
2924:
2835:Generalized Vehicle Routing Problem
2652:Capacitated Chinese Postman Problem
2610:Min-Max Windy Rural Postman Problem
1544:, decide whether there are at least
4399:Computers & Operations Research
3825:Computers & Operations Research
2582:k-Plow Windy Rural Postman Problem
1880:{\displaystyle O((|E|-|V|)|V|^{2})}
360:Windy postman problem and variants
325:undirected chinese postman problem
14:
3276:Computers and Operations Research
2793:Undirected Rural Postman Problem
2666:Directed Chinese Postman Problem
4239:Thomassen, Carsten (June 1997).
3323:Computational Management Science
2624:Plowing with Precedence Problem
2568:Capacitated Arc Routing Problem
2148:In XP with respect to treewidth
1364:, which leads to the statement:
830:Considering an undirected graph
785:{\displaystyle E_{R}\subseteq E}
680:{\displaystyle V_{R}\subseteq V}
644:{\displaystyle E_{R}\subseteq E}
319:Undirected rural postman problem
4145:Veerasamy, Jeyakesavan (1999).
2894:Capacitated arc routing problem
2680:Directed Rural Postman Problem
2428:Directed Rural Postman Problem
1612:{\displaystyle O(k^{2}\log(k))}
1256:, the cost of deadheading from
1167:, the cost of deadheading from
4059:"On the windy postman problem"
4057:Guan, Meigu (September 1984).
3756:. Ecole Polytechnique â GERAD.
3751:"Recent trends in arc routing"
2736:Mixed Chinese Postman Problem
2329:
2319:
2310:
2306:
2268:
2258:
2249:
2245:
2210:
2200:
2191:
2184:
2130:
2120:
2111:
2101:
2093:
2084:
2059:
2047:
2039:
2031:
2023:
2015:
2005:
2001:
1993:
1979:
1970:
1960:
1934:
1924:
1915:
1911:
1874:
1864:
1855:
1851:
1847:
1839:
1831:
1823:
1819:
1816:
1792:
1782:
1773:
1769:
1735:
1725:
1716:
1712:
1606:
1603:
1597:
1578:
941:
915:
605:
593:
237:
214:
191:
182:
154:heuristic optimization methods
1:
4614:10.1016/S0377-2217(99)00073-9
4566:10.1080/13658816.2017.1380201
3649:"Parameterized complexity of
3435:Minieka, Edward (July 1979).
2954:10.1080/13658816.2017.1380201
2899:List of graph theory problems
947:{\displaystyle (v_{i},v_{j})}
243:{\displaystyle O(2^{n}n^{2})}
150:mixed Chinese postman problem
4217:10.1016/0166-3615(92)90137-c
4210:(1): 124â126. January 1992.
4076:10.1016/0166-218x(84)90089-1
4063:Discrete Applied Mathematics
4019:Discrete Applied Mathematics
3973:10.1007/978-3-662-44777-2_44
3837:10.1016/0305-0548(88)90053-6
3657:Theoretical Computer Science
3486:10.1016/0166-218X(84)90089-1
3472:Discrete Applied Mathematics
3132:10.1007/978-3-642-56423-9_17
2470:Windy Rural Postman Problem
2351:List of arc routing variants
1661:branch & cut methodology
476:{\displaystyle \{i,j\}\in E}
122:Vehicle routing problems/VRP
67:. Arc routings problems are
4647:Travelling salesman problem
4526:Dussualt, Benjamin (2012).
2884:Travelling salesman problem
2765:Traveling Salesman Problem
2389:Seven Bridges of Konigsberg
2216:{\displaystyle O(k|V|^{4})}
2145:In FPT with respect to |A|
1078:, the cost of plowing from
268:dynamic programming methods
4668:
3617:10.1504/IJMMNO.2010.035430
2335:{\displaystyle O(|V|^{3})}
2274:{\displaystyle O(|V|^{3})}
1940:{\displaystyle O(|V|^{3})}
1798:{\displaystyle O(|V|^{3})}
1741:{\displaystyle O(|V|^{3})}
1568:-CPP admits a kernel with
1520:-Chinese postman problem (
1249:{\displaystyle c_{ji}^{-}}
1160:{\displaystyle c_{ij}^{-}}
1071:{\displaystyle c_{ji}^{+}}
982:{\displaystyle c_{ij}^{+}}
733:, a distinguished vertex,
445:associated with each edge
172:makes an improvement from
166:traveling salesman problem
162:integer linear programming
4411:10.1016/j.cor.2012.10.013
4314:SIAM Journal on Computing
4257:10.1137/s0097539794267255
4245:SIAM Journal on Computing
4032:10.1016/j.dam.2007.10.032
3925:10.1137/s0895480197331454
3680:10.1016/j.tcs.2013.10.012
3653:-Chinese Postman Problem"
3564:10.1007/s10107-010-0399-x
3335:10.1007/s10287-009-0119-2
3288:10.1016/j.cor.2004.04.007
2904:Snow plow routing problem
2512:Capacitated Plow Problem
1636:Heuristics and algorithms
1310:. The setup assumes that
861:{\displaystyle G=\{V,A\}}
726:{\displaystyle G=\{V,E\}}
519:{\displaystyle G=\{E,V\}}
73:route inspection problems
4278:CorberĂĄn, Ăngel (2015).
4104:Mathematical Programming
3778:Mathematical Programming
3552:Mathematical Programming
2807:Vehicle Routing Problem
2395:Chinese Postman Problem
2159:P in some special cases
158:branch-and-bound methods
2879:Vehicle routing problem
2874:Chinese postman problem
2484:Street Sweeper Problem
1694:Parametrized complexity
1655:cutting plane algorithm
1337:has a higher elevation
438:{\displaystyle c_{j,i}}
405:{\displaystyle c_{i,j}}
252:cutting plane algorithm
168:algorithms such as the
113:Chinese postman problem
59:, network maintenance,
49:winter service vehicles
4355:Eiselt, H (May 1995).
4178:10.1002/net.3230170304
3716:Transportation Science
3529:10.1002/net.3230110211
3178:10.1002/net.3230110204
2750:Stacker Crane Problem
2526:Downhill Plow Problem
2456:Windy Postman Problem
2412:Rural Postman Problem
2336:
2275:
2217:
2137:
2066:
1941:
1881:
1799:
1742:
1613:
1503:
1476:
1456:
1358:
1331:
1304:
1277:
1250:
1215:
1188:
1161:
1126:
1099:
1072:
1037:
1010:
983:
948:
902:
882:
862:
786:
753:
752:{\displaystyle 1\in V}
727:
681:
645:
612:
580:
579:{\displaystyle c_{ji}}
550:
549:{\displaystyle c_{ij}}
520:
477:
439:
406:
244:
198:
164:, and applications of
75:that can be solved in
4204:Computers in Industry
4098:Win, Zaw (May 1989).
3955:Algorithms - ESA 2014
3877:10.1145/321958.321974
3728:10.1287/trsc.33.4.408
3453:10.1287/mnsc.25.7.643
3421:10.1287/opre.43.3.399
3086:10.1287/opre.43.2.231
2991:Omer, Masoud (2007).
2862:Trends in Arc Routing
2337:
2276:
2218:
2138:
2067:
1942:
1882:
1800:
1743:
1623:-CPP is NP complete.
1614:
1504:
1502:{\displaystyle v_{0}}
1477:
1457:
1359:
1357:{\displaystyle v_{i}}
1332:
1330:{\displaystyle v_{j}}
1305:
1303:{\displaystyle v_{i}}
1278:
1276:{\displaystyle v_{j}}
1251:
1216:
1214:{\displaystyle v_{j}}
1189:
1187:{\displaystyle v_{i}}
1162:
1127:
1125:{\displaystyle v_{i}}
1100:
1098:{\displaystyle v_{j}}
1073:
1038:
1036:{\displaystyle v_{j}}
1011:
1009:{\displaystyle v_{i}}
984:
949:
903:
883:
863:
787:
754:
728:
682:
646:
613:
611:{\displaystyle (i,j)}
581:
551:
521:
478:
440:
407:
366:windy postman problem
280:bridges of Königsberg
245:
199:
197:{\displaystyle O(n!)}
131:Rural postman problem
4652:NP-complete problems
4497:10.1057/jors.2013.83
4450:10.1057/jors.2013.83
4011:Wakabayashi, Yoshiko
3031:10.1057/jors.2013.83
2377:Arc Routing Problem
2342:-time factor(2-1/k)
2300:
2239:
2178:
2078:
1954:
1905:
1810:
1763:
1706:
1684:Classical complexity
1572:
1486:
1466:
1368:
1341:
1314:
1287:
1260:
1225:
1198:
1171:
1136:
1109:
1082:
1047:
1020:
993:
958:
912:
892:
872:
834:
763:
737:
699:
658:
622:
590:
560:
530:
492:
449:
416:
383:
264:Lagrange multipliers
208:
176:
4380:Chinese Mathematics
3408:Operations Research
3379:Scientific American
3073:Operations Research
2356:
1451:
1430:
1409:
1388:
1245:
1156:
1067:
978:
256:convex optimization
170:HeldâKarp algorithm
4642:Routing algorithms
4116:10.1007/bf01587080
3864:Journal of the ACM
3790:10.1007/bf01580113
3441:Management Science
3244:10.22034/2015.4.03
2498:m-Plowing Problem
2355:
2332:
2291:Min-max k postmen
2271:
2233:Min-sum k postmen
2213:
2133:
2062:
1937:
1877:
1795:
1738:
1609:
1499:
1472:
1452:
1434:
1413:
1392:
1371:
1354:
1327:
1300:
1273:
1246:
1228:
1211:
1184:
1157:
1139:
1122:
1095:
1068:
1050:
1033:
1006:
979:
961:
944:
898:
878:
858:
782:
749:
723:
677:
641:
608:
576:
546:
516:
473:
435:
402:
240:
194:
33:garbage collection
4491:(10): 1465â1474.
4444:(10): 1465â1474.
4291:978-1-61197-366-2
3982:978-3-662-44776-5
3141:978-3-642-56423-9
3025:(10): 1465â1474.
2848:
2847:
2348:
2347:
2072:-time factor 3/2
1475:{\displaystyle k}
901:{\displaystyle A}
881:{\displaystyle V}
282:challenge, which
274:Eulerian circuits
4659:
4626:
4625:
4593:
4587:
4586:
4568:
4544:
4538:
4537:
4523:
4517:
4516:
4476:
4470:
4469:
4429:
4423:
4422:
4405:(4): 1047â1059.
4390:
4384:
4383:
4375:
4369:
4368:
4352:
4346:
4345:
4305:
4296:
4295:
4275:
4269:
4268:
4236:
4230:
4229:
4219:
4196:
4190:
4189:
4157:
4151:
4150:
4142:
4136:
4135:
4095:
4089:
4088:
4078:
4054:
4045:
4044:
4034:
4013:(January 2009).
4006:
4000:
3999:
3998:
3997:
3966:
3946:
3937:
3936:
3904:
3898:
3897:
3879:
3855:
3849:
3848:
3816:
3810:
3809:
3769:
3758:
3757:
3755:
3746:
3740:
3739:
3707:
3701:
3700:
3682:
3672:
3644:
3638:
3635:
3629:
3628:
3610:
3590:
3584:
3583:
3558:(1â2): 309â332.
3543:
3532:
3531:
3514:
3505:
3499:
3497:
3488:
3463:
3457:
3456:
3432:
3426:
3425:
3423:
3399:
3390:
3389:
3387:
3386:
3371:
3365:
3364:
3346:
3314:
3301:
3300:
3299:
3267:
3256:
3255:
3229:
3220:
3207:
3206:
3188:
3182:
3181:
3157:
3151:
3150:
3149:
3148:
3115:
3109:
3108:
3098:
3088:
3064:
3051:
3050:
3010:
2997:
2996:
2988:
2975:
2974:
2956:
2932:
2357:
2341:
2339:
2338:
2333:
2328:
2327:
2322:
2313:
2280:
2278:
2277:
2272:
2267:
2266:
2261:
2252:
2222:
2220:
2219:
2214:
2209:
2208:
2203:
2194:
2143:-time algorithm
2142:
2140:
2139:
2134:
2129:
2128:
2123:
2114:
2106:
2105:
2104:
2096:
2071:
2069:
2068:
2063:
2055:
2054:
2042:
2034:
2026:
2018:
2004:
1996:
1988:
1987:
1982:
1973:
1946:
1944:
1943:
1938:
1933:
1932:
1927:
1918:
1887:-time algorithm
1886:
1884:
1883:
1878:
1873:
1872:
1867:
1858:
1850:
1842:
1834:
1826:
1805:-time algorithm
1804:
1802:
1801:
1796:
1791:
1790:
1785:
1776:
1748:-time algorithm
1747:
1745:
1744:
1739:
1734:
1733:
1728:
1719:
1675:
1618:
1616:
1615:
1610:
1590:
1589:
1508:
1506:
1505:
1500:
1498:
1497:
1481:
1479:
1478:
1473:
1461:
1459:
1458:
1453:
1450:
1445:
1429:
1424:
1408:
1403:
1387:
1382:
1363:
1361:
1360:
1355:
1353:
1352:
1336:
1334:
1333:
1328:
1326:
1325:
1309:
1307:
1306:
1301:
1299:
1298:
1282:
1280:
1279:
1274:
1272:
1271:
1255:
1253:
1252:
1247:
1244:
1239:
1220:
1218:
1217:
1212:
1210:
1209:
1193:
1191:
1190:
1185:
1183:
1182:
1166:
1164:
1163:
1158:
1155:
1150:
1131:
1129:
1128:
1123:
1121:
1120:
1104:
1102:
1101:
1096:
1094:
1093:
1077:
1075:
1074:
1069:
1066:
1061:
1042:
1040:
1039:
1034:
1032:
1031:
1015:
1013:
1012:
1007:
1005:
1004:
988:
986:
985:
980:
977:
972:
954:has four costs:
953:
951:
950:
945:
940:
939:
927:
926:
907:
905:
904:
899:
887:
885:
884:
879:
867:
865:
864:
859:
791:
789:
788:
783:
775:
774:
758:
756:
755:
750:
732:
730:
729:
724:
686:
684:
683:
678:
670:
669:
650:
648:
647:
642:
634:
633:
617:
615:
614:
609:
585:
583:
582:
577:
575:
574:
555:
553:
552:
547:
545:
544:
525:
523:
522:
517:
482:
480:
479:
474:
444:
442:
441:
436:
434:
433:
411:
409:
408:
403:
401:
400:
249:
247:
246:
241:
236:
235:
226:
225:
203:
201:
200:
195:
71:, as opposed to
4667:
4666:
4662:
4661:
4660:
4658:
4657:
4656:
4632:
4631:
4630:
4629:
4595:
4594:
4590:
4546:
4545:
4541:
4525:
4524:
4520:
4478:
4477:
4473:
4431:
4430:
4426:
4392:
4391:
4387:
4377:
4376:
4372:
4359:. p. 399.
4354:
4353:
4349:
4326:10.1137/0207017
4307:
4306:
4299:
4292:
4277:
4276:
4272:
4238:
4237:
4233:
4198:
4197:
4193:
4159:
4158:
4154:
4144:
4143:
4139:
4110:(1â3): 97â112.
4097:
4096:
4092:
4056:
4055:
4048:
4008:
4007:
4003:
3995:
3993:
3983:
3948:
3947:
3940:
3906:
3905:
3901:
3857:
3856:
3852:
3818:
3817:
3813:
3771:
3770:
3761:
3753:
3748:
3747:
3743:
3709:
3708:
3704:
3646:
3645:
3641:
3636:
3632:
3592:
3591:
3587:
3545:
3544:
3535:
3512:
3507:
3506:
3502:
3465:
3464:
3460:
3434:
3433:
3429:
3401:
3400:
3393:
3384:
3382:
3373:
3372:
3368:
3316:
3315:
3304:
3282:(12): 3111â28,
3269:
3268:
3259:
3227:
3222:
3221:
3210:
3205:. NPS55-83-002.
3190:
3189:
3185:
3159:
3158:
3154:
3146:
3144:
3142:
3117:
3116:
3112:
3066:
3065:
3054:
3012:
3011:
3000:
2990:
2989:
2978:
2934:
2933:
2922:
2917:
2870:
2853:
2353:
2317:
2298:
2297:
2256:
2237:
2236:
2198:
2176:
2175:
2170:k-Hierarchical
2118:
2087:
2076:
2075:
2046:
1977:
1952:
1951:
1922:
1903:
1902:
1862:
1808:
1807:
1780:
1761:
1760:
1723:
1704:
1703:
1670:
1638:
1629:
1581:
1570:
1569:
1526:
1489:
1484:
1483:
1464:
1463:
1366:
1365:
1344:
1339:
1338:
1317:
1312:
1311:
1290:
1285:
1284:
1263:
1258:
1257:
1223:
1222:
1201:
1196:
1195:
1174:
1169:
1168:
1134:
1133:
1112:
1107:
1106:
1085:
1080:
1079:
1045:
1044:
1023:
1018:
1017:
996:
991:
990:
956:
955:
931:
918:
910:
909:
890:
889:
870:
869:
832:
831:
820:
812:
766:
761:
760:
735:
734:
697:
696:
661:
656:
655:
625:
620:
619:
588:
587:
563:
558:
557:
533:
528:
527:
526:with two costs
490:
489:
447:
446:
419:
414:
413:
386:
381:
380:
362:
346:
337:
321:
309:
276:
227:
217:
206:
205:
174:
173:
142:
133:
124:
115:
106:
97:
77:polynomial-time
61:street sweeping
17:
12:
11:
5:
4665:
4663:
4655:
4654:
4649:
4644:
4634:
4633:
4628:
4627:
4588:
4559:(1): 169â190.
4539:
4518:
4471:
4424:
4385:
4370:
4347:
4320:(2): 178â193.
4297:
4290:
4270:
4251:(3): 675â677.
4231:
4191:
4172:(3): 283â294.
4152:
4137:
4090:
4046:
4025:(2): 272â279.
4001:
3981:
3938:
3919:(4): 425â433.
3899:
3870:(3): 544â554.
3850:
3831:(6): 577â584.
3811:
3759:
3749:Hertz, Alain.
3741:
3722:(4): 408â418.
3702:
3639:
3630:
3601:(4): 330â343.
3585:
3533:
3500:
3458:
3447:(7): 643â648.
3427:
3414:(3): 399â414.
3391:
3366:
3329:(3): 269â287.
3302:
3257:
3238:(4): 1003â20.
3208:
3183:
3152:
3140:
3110:
3079:(2): 231â242.
3052:
2998:
2976:
2947:(1): 169â190.
2919:
2918:
2916:
2913:
2912:
2911:
2906:
2901:
2896:
2891:
2886:
2881:
2876:
2869:
2866:
2865:
2864:
2859:
2852:
2851:External links
2849:
2846:
2845:
2843:
2841:
2839:
2836:
2832:
2831:
2829:
2827:
2825:
2822:
2818:
2817:
2815:
2813:
2811:
2808:
2804:
2803:
2801:
2799:
2797:
2794:
2790:
2789:
2787:
2785:
2783:
2780:
2776:
2775:
2773:
2771:
2769:
2766:
2762:
2761:
2759:
2757:
2754:
2751:
2747:
2746:
2744:
2742:
2740:
2737:
2733:
2732:
2730:
2728:
2726:
2723:
2719:
2718:
2716:
2714:
2712:
2709:
2705:
2704:
2702:
2700:
2698:
2695:
2691:
2690:
2688:
2686:
2684:
2681:
2677:
2676:
2674:
2672:
2670:
2667:
2663:
2662:
2660:
2658:
2656:
2653:
2649:
2648:
2646:
2644:
2642:
2639:
2635:
2634:
2632:
2630:
2628:
2625:
2621:
2620:
2618:
2616:
2614:
2611:
2607:
2606:
2604:
2602:
2600:
2597:
2593:
2592:
2590:
2588:
2586:
2583:
2579:
2578:
2576:
2574:
2572:
2569:
2565:
2564:
2562:
2560:
2558:
2555:
2551:
2550:
2548:
2546:
2544:
2541:
2537:
2536:
2534:
2532:
2530:
2527:
2523:
2522:
2520:
2518:
2516:
2513:
2509:
2508:
2506:
2504:
2502:
2499:
2495:
2494:
2492:
2490:
2488:
2485:
2481:
2480:
2478:
2476:
2474:
2471:
2467:
2466:
2464:
2462:
2460:
2457:
2453:
2452:
2450:
2448:
2446:
2445:RPP-TP, RPPTP
2443:
2439:
2438:
2436:
2434:
2432:
2429:
2425:
2424:
2422:
2419:
2416:
2413:
2409:
2408:
2405:
2402:
2399:
2396:
2392:
2391:
2386:
2384:
2381:
2378:
2374:
2373:
2370:
2367:
2364:
2361:
2352:
2349:
2346:
2345:
2343:
2331:
2326:
2321:
2316:
2312:
2308:
2305:
2295:
2292:
2288:
2287:
2284:
2282:
2270:
2265:
2260:
2255:
2251:
2247:
2244:
2234:
2230:
2229:
2227:
2225:
2212:
2207:
2202:
2197:
2193:
2189:
2186:
2183:
2171:
2167:
2166:
2164:
2161:
2155:
2151:
2150:
2132:
2127:
2122:
2117:
2113:
2109:
2103:
2099:
2095:
2090:
2086:
2083:
2073:
2061:
2058:
2053:
2049:
2045:
2041:
2037:
2033:
2029:
2025:
2021:
2017:
2013:
2010:
2007:
2003:
1999:
1995:
1991:
1986:
1981:
1976:
1972:
1968:
1965:
1962:
1959:
1949:
1936:
1931:
1926:
1921:
1917:
1913:
1910:
1898:
1894:
1893:
1891:
1889:
1876:
1871:
1866:
1861:
1857:
1853:
1849:
1845:
1841:
1837:
1833:
1829:
1825:
1821:
1818:
1815:
1794:
1789:
1784:
1779:
1775:
1771:
1768:
1758:
1754:
1753:
1751:
1749:
1737:
1732:
1727:
1722:
1718:
1714:
1711:
1701:
1697:
1696:
1691:
1686:
1681:
1669:
1666:
1637:
1634:
1628:
1625:
1608:
1605:
1602:
1599:
1596:
1593:
1588:
1584:
1580:
1577:
1525:
1515:
1496:
1492:
1471:
1449:
1444:
1441:
1437:
1433:
1428:
1423:
1420:
1416:
1412:
1407:
1402:
1399:
1395:
1391:
1386:
1381:
1378:
1374:
1351:
1347:
1324:
1320:
1297:
1293:
1270:
1266:
1243:
1238:
1235:
1231:
1208:
1204:
1181:
1177:
1154:
1149:
1146:
1142:
1119:
1115:
1092:
1088:
1065:
1060:
1057:
1053:
1030:
1026:
1003:
999:
976:
971:
968:
964:
943:
938:
934:
930:
925:
921:
917:
897:
877:
857:
854:
851:
848:
845:
842:
839:
819:
816:
811:
808:
781:
778:
773:
769:
748:
745:
742:
722:
719:
716:
713:
710:
707:
704:
676:
673:
668:
664:
640:
637:
632:
628:
607:
604:
601:
598:
595:
573:
570:
566:
543:
540:
536:
515:
512:
509:
506:
503:
500:
497:
472:
469:
466:
463:
460:
457:
454:
432:
429:
426:
422:
399:
396:
393:
389:
361:
358:
345:
342:
336:
333:
320:
317:
308:
305:
290:, now part of
275:
272:
239:
234:
230:
224:
220:
216:
213:
193:
190:
187:
184:
181:
141:
138:
132:
129:
123:
120:
114:
111:
105:
102:
96:
93:
65:snow ploughing
51:that sprinkle
15:
13:
10:
9:
6:
4:
3:
2:
4664:
4653:
4650:
4648:
4645:
4643:
4640:
4639:
4637:
4623:
4619:
4615:
4611:
4607:
4603:
4599:
4592:
4589:
4584:
4580:
4576:
4572:
4567:
4562:
4558:
4554:
4550:
4543:
4540:
4535:
4534:
4529:
4522:
4519:
4514:
4510:
4506:
4502:
4498:
4494:
4490:
4486:
4482:
4475:
4472:
4467:
4463:
4459:
4455:
4451:
4447:
4443:
4439:
4435:
4428:
4425:
4420:
4416:
4412:
4408:
4404:
4400:
4396:
4389:
4386:
4381:
4374:
4371:
4366:
4362:
4358:
4351:
4348:
4343:
4339:
4335:
4331:
4327:
4323:
4319:
4315:
4311:
4304:
4302:
4298:
4293:
4287:
4283:
4280:
4274:
4271:
4266:
4262:
4258:
4254:
4250:
4246:
4242:
4235:
4232:
4227:
4223:
4218:
4213:
4209:
4205:
4201:
4195:
4192:
4187:
4183:
4179:
4175:
4171:
4167:
4163:
4156:
4153:
4148:
4141:
4138:
4133:
4129:
4125:
4121:
4117:
4113:
4109:
4105:
4101:
4094:
4091:
4086:
4082:
4077:
4072:
4068:
4064:
4060:
4053:
4051:
4047:
4042:
4038:
4033:
4028:
4024:
4020:
4016:
4012:
4005:
4002:
3992:
3988:
3984:
3978:
3974:
3970:
3965:
3960:
3956:
3952:
3945:
3943:
3939:
3934:
3930:
3926:
3922:
3918:
3914:
3910:
3903:
3900:
3895:
3891:
3887:
3883:
3878:
3873:
3869:
3865:
3861:
3854:
3851:
3846:
3842:
3838:
3834:
3830:
3826:
3822:
3815:
3812:
3807:
3803:
3799:
3795:
3791:
3787:
3784:(1): 88â124.
3783:
3779:
3775:
3768:
3766:
3764:
3760:
3752:
3745:
3742:
3737:
3733:
3729:
3725:
3721:
3717:
3713:
3706:
3703:
3698:
3694:
3690:
3686:
3681:
3676:
3671:
3666:
3662:
3658:
3654:
3652:
3643:
3640:
3634:
3631:
3626:
3622:
3618:
3614:
3609:
3604:
3600:
3596:
3589:
3586:
3581:
3577:
3573:
3569:
3565:
3561:
3557:
3553:
3549:
3542:
3540:
3538:
3534:
3530:
3526:
3522:
3518:
3511:
3504:
3501:
3496:
3492:
3487:
3482:
3478:
3474:
3473:
3468:
3462:
3459:
3454:
3450:
3446:
3442:
3438:
3431:
3428:
3422:
3417:
3413:
3409:
3405:
3398:
3396:
3392:
3380:
3376:
3370:
3367:
3362:
3358:
3354:
3350:
3345:
3340:
3336:
3332:
3328:
3324:
3320:
3313:
3311:
3309:
3307:
3303:
3298:
3293:
3289:
3285:
3281:
3277:
3273:
3266:
3264:
3262:
3258:
3253:
3249:
3245:
3241:
3237:
3233:
3226:
3219:
3217:
3215:
3213:
3209:
3204:
3200:
3196:
3195:
3187:
3184:
3179:
3175:
3172:(2): 97â108.
3171:
3167:
3163:
3156:
3153:
3143:
3137:
3133:
3129:
3125:
3121:
3114:
3111:
3106:
3102:
3097:
3092:
3087:
3082:
3078:
3074:
3070:
3063:
3061:
3059:
3057:
3053:
3048:
3044:
3040:
3036:
3032:
3028:
3024:
3020:
3016:
3009:
3007:
3005:
3003:
2999:
2994:
2987:
2985:
2983:
2981:
2977:
2972:
2968:
2964:
2960:
2955:
2950:
2946:
2942:
2938:
2931:
2929:
2927:
2925:
2921:
2914:
2910:
2907:
2905:
2902:
2900:
2897:
2895:
2892:
2890:
2889:Eulerian path
2887:
2885:
2882:
2880:
2877:
2875:
2872:
2871:
2867:
2863:
2860:
2858:
2855:
2854:
2850:
2844:
2842:
2840:
2837:
2834:
2833:
2830:
2828:
2826:
2823:
2820:
2819:
2816:
2814:
2812:
2809:
2806:
2805:
2802:
2800:
2798:
2795:
2792:
2791:
2788:
2786:
2784:
2781:
2778:
2777:
2774:
2772:
2770:
2767:
2764:
2763:
2760:
2758:
2755:
2752:
2749:
2748:
2745:
2743:
2741:
2738:
2735:
2734:
2731:
2729:
2727:
2724:
2721:
2720:
2717:
2715:
2713:
2710:
2707:
2706:
2703:
2701:
2699:
2696:
2693:
2692:
2689:
2687:
2685:
2682:
2679:
2678:
2675:
2673:
2671:
2668:
2665:
2664:
2661:
2659:
2657:
2654:
2651:
2650:
2647:
2645:
2643:
2640:
2637:
2636:
2633:
2631:
2629:
2626:
2623:
2622:
2619:
2617:
2615:
2612:
2609:
2608:
2605:
2603:
2601:
2598:
2595:
2594:
2591:
2589:
2587:
2584:
2581:
2580:
2577:
2575:
2573:
2570:
2567:
2566:
2563:
2561:
2559:
2556:
2553:
2552:
2549:
2547:
2545:
2542:
2539:
2538:
2535:
2533:
2531:
2528:
2525:
2524:
2521:
2519:
2517:
2514:
2511:
2510:
2507:
2505:
2503:
2500:
2497:
2496:
2493:
2491:
2489:
2486:
2483:
2482:
2479:
2477:
2475:
2472:
2469:
2468:
2465:
2463:
2461:
2458:
2455:
2454:
2451:
2449:
2447:
2444:
2441:
2440:
2437:
2435:
2433:
2430:
2427:
2426:
2423:
2420:
2417:
2414:
2411:
2410:
2406:
2403:
2400:
2397:
2394:
2393:
2390:
2387:
2385:
2382:
2379:
2376:
2375:
2371:
2369:Output Notes
2368:
2365:
2363:Abbreviation
2362:
2359:
2358:
2350:
2344:
2324:
2314:
2303:
2296:
2293:
2290:
2289:
2285:
2283:
2263:
2253:
2242:
2235:
2232:
2231:
2228:
2226:
2224:
2205:
2195:
2187:
2181:
2172:
2169:
2168:
2165:
2162:
2160:
2156:
2153:
2152:
2149:
2146:
2125:
2115:
2107:
2097:
2088:
2081:
2074:
2051:
2035:
2027:
2019:
1997:
1989:
1984:
1974:
1957:
1950:
1948:
1929:
1919:
1908:
1899:
1896:
1895:
1892:
1890:
1888:
1869:
1859:
1843:
1835:
1827:
1813:
1787:
1777:
1766:
1759:
1756:
1755:
1752:
1750:
1730:
1720:
1709:
1702:
1699:
1698:
1695:
1692:
1690:
1689:Approximation
1687:
1685:
1682:
1680:
1677:
1676:
1673:
1667:
1665:
1663:
1662:
1657:
1656:
1650:
1647:
1642:
1635:
1633:
1626:
1624:
1622:
1600:
1594:
1591:
1586:
1582:
1575:
1567:
1563:
1559:
1555:
1551:
1547:
1543:
1539:
1536:and integers
1535:
1531:
1523:
1519:
1516:
1514:
1510:
1494:
1490:
1469:
1447:
1442:
1439:
1435:
1431:
1426:
1421:
1418:
1414:
1410:
1405:
1400:
1397:
1393:
1389:
1384:
1379:
1376:
1372:
1349:
1345:
1322:
1318:
1295:
1291:
1268:
1264:
1241:
1236:
1233:
1229:
1206:
1202:
1179:
1175:
1152:
1147:
1144:
1140:
1117:
1113:
1090:
1086:
1063:
1058:
1055:
1051:
1028:
1024:
1001:
997:
974:
969:
966:
962:
936:
932:
928:
923:
919:
895:
875:
852:
849:
846:
840:
837:
828:
824:
817:
815:
809:
807:
804:
800:
796:
793:
779:
776:
771:
767:
746:
743:
740:
717:
714:
711:
705:
702:
692:
688:
674:
671:
666:
662:
652:
638:
635:
630:
626:
602:
599:
596:
571:
568:
564:
541:
538:
534:
510:
507:
504:
498:
495:
485:
470:
467:
461:
458:
455:
430:
427:
424:
420:
397:
394:
391:
387:
377:
374:
372:
367:
359:
357:
355:
351:
343:
341:
334:
332:
330:
329:covering tour
326:
318:
316:
314:
307:Problem types
306:
304:
300:
297:
293:
289:
285:
281:
273:
271:
269:
265:
261:
257:
253:
232:
228:
222:
218:
211:
188:
185:
179:
171:
167:
163:
159:
155:
151:
147:
139:
137:
130:
128:
121:
119:
112:
110:
103:
101:
94:
92:
89:
86:
80:
78:
74:
70:
66:
62:
58:
57:mail delivery
55:on the road,
54:
50:
46:
42:
38:
34:
30:
25:
21:
4608:(1): 11â17.
4605:
4601:
4591:
4556:
4552:
4542:
4531:
4521:
4488:
4484:
4474:
4441:
4437:
4427:
4402:
4398:
4388:
4379:
4373:
4350:
4317:
4313:
4282:
4279:
4273:
4248:
4244:
4234:
4207:
4203:
4194:
4169:
4165:
4155:
4146:
4140:
4107:
4103:
4093:
4069:(1): 41â46.
4066:
4062:
4022:
4018:
4004:
3994:, retrieved
3954:
3916:
3912:
3902:
3867:
3863:
3853:
3828:
3824:
3814:
3781:
3777:
3744:
3719:
3715:
3705:
3660:
3656:
3650:
3642:
3633:
3598:
3594:
3588:
3555:
3551:
3523:(2): 221â7,
3520:
3516:
3503:
3479:(1): 41â46,
3476:
3470:
3461:
3444:
3440:
3430:
3411:
3407:
3383:. Retrieved
3378:
3369:
3344:10251/100790
3326:
3322:
3279:
3275:
3235:
3231:
3193:
3186:
3169:
3165:
3155:
3145:, retrieved
3123:
3113:
3076:
3072:
3022:
3018:
2944:
2940:
2366:Description
2294:NP-complete
2174:
2173:NP-complete
2158:
2157:NP-complete
2147:
2144:
1901:
1900:NP-complete
1806:
1693:
1688:
1683:
1678:
1671:
1660:
1654:
1651:
1643:
1639:
1630:
1620:
1565:
1561:
1557:
1553:
1549:
1545:
1541:
1537:
1533:
1529:
1527:
1521:
1517:
1511:
829:
825:
821:
813:
810:Applications
805:
801:
797:
794:
693:
689:
653:
486:
378:
375:
365:
363:
347:
338:
328:
324:
322:
310:
301:
277:
260:convex hulls
145:
143:
134:
125:
116:
107:
98:
90:
81:
45:snow removal
23:
19:
18:
3663:: 124â128.
3467:Guan, Meigu
3381:. July 1953
3297:10251/94488
3203:10945/63226
3096:11059/14013
2163:Factor 3/2
1700:Undirected
1646:convex hull
371:NP-complete
292:Kaliningrad
29:deadheading
27:minimizing
20:Arc routing
4636:Categories
3996:2022-05-09
3385:2022-04-30
3147:2022-05-01
2915:References
2641:MM k-DPPE
2613:MM k-WRPP
1679:CP variant
1668:Complexity
818:Snow plows
288:Konigsberg
266:and other
140:Algorithms
95:Background
37:school bus
4622:0377-2217
4575:1365-8816
4505:1476-9360
4458:1476-9360
4419:0305-0548
4365:219174102
4334:0097-5397
4265:0097-5397
4226:0166-3615
4186:0028-3045
4132:206800125
4124:0025-5610
4085:0166-218X
4041:0166-218X
3964:1403.1512
3933:0895-4801
3886:0004-5411
3845:0305-0548
3798:0025-5610
3736:0041-1655
3689:0304-3975
3670:1308.0482
3608:1005.2908
3572:0025-5610
3353:1619-697X
3252:2383-1359
3105:0030-364X
3039:0160-5682
2963:1365-8816
2599:MM k-DPP
2372:Examples
2108:⋅
1836:−
1757:Directed
1595:
1448:−
1432:≥
1427:−
1411:≫
1390:≫
1242:−
1153:−
777:⊆
744:∈
672:⊆
636:⊆
468:∈
22:problems
4583:29526595
4533:ProQuest
4513:36977043
4466:36977043
4361:ProQuest
4166:Networks
3806:15249924
3625:34889796
3580:12808962
3517:Networks
3361:41426793
3166:Networks
3047:36977043
2971:29526595
2868:See also
2824:MMMDRPP
2557:RDPP-TP
2360:Problem
1658:and the
4342:7562375
3991:3472348
3894:8625996
3697:2867281
3495:0754427
2585:k-WRPP
2543:DPP-TP
350:Lenstra
344:History
313:NP-hard
69:NP hard
41:deicing
4620:
4581:
4573:
4511:
4503:
4464:
4456:
4417:
4363:
4340:
4332:
4288:
4263:
4224:
4184:
4130:
4122:
4083:
4039:
3989:
3979:
3931:
3892:
3884:
3843:
3804:
3796:
3734:
3695:
3687:
3623:
3578:
3570:
3493:
3359:
3351:
3250:
3138:
3103:
3045:
3037:
2969:
2961:
2782:UCARP
2725:MCARP
2697:ECARP
2154:Windy
1897:Mixed
1221:, and
868:where
369:it is
296:Pregel
85:Burgos
4579:S2CID
4509:S2CID
4462:S2CID
4338:S2CID
4128:S2CID
3987:S2CID
3959:arXiv
3890:S2CID
3802:S2CID
3754:(PDF)
3693:S2CID
3665:arXiv
3621:S2CID
3603:arXiv
3576:S2CID
3513:(PDF)
3357:S2CID
3228:(PDF)
3043:S2CID
2967:S2CID
2838:GVRP
2796:URPP
2739:MCPP
2711:HCPP
2683:DRPP
2669:DCPP
2655:CCPP
2571:CARP
2515:C-PP
2501:m-PP
2473:WRPP
2431:DRPP
1524:-CPP)
284:Euler
104:Basis
47:with
24:(ARP)
4618:ISSN
4571:ISSN
4501:ISSN
4454:ISSN
4415:ISSN
4330:ISSN
4286:ISBN
4261:ISSN
4222:ISSN
4182:ISSN
4120:ISSN
4081:ISSN
4037:ISSN
3977:ISBN
3929:ISSN
3882:ISSN
3841:ISSN
3794:ISSN
3732:ISSN
3685:ISSN
3568:ISSN
3349:ISSN
3248:ISSN
3136:ISBN
3101:ISSN
3035:ISSN
2959:ISSN
2810:VRP
2768:TSP
2753:SCP
2627:PPP
2529:DPP
2487:SPP
2459:WPP
2415:RPP
2398:CPP
2380:ARP
1540:and
1528:The
556:and
412:and
364:The
352:and
53:salt
43:and
4610:doi
4606:122
4561:doi
4493:doi
4446:doi
4407:doi
4322:doi
4253:doi
4212:doi
4174:doi
4112:doi
4071:doi
4027:doi
4023:157
3969:doi
3921:doi
3872:doi
3833:doi
3786:doi
3724:doi
3675:doi
3661:513
3613:doi
3560:doi
3556:132
3525:doi
3481:doi
3449:doi
3416:doi
3339:hdl
3331:doi
3292:hdl
3284:doi
3240:doi
3199:hdl
3174:doi
3128:doi
3091:hdl
3081:doi
3027:doi
2949:doi
2009:max
1964:max
1592:log
1283:to
1194:to
1105:to
1016:to
354:Kan
204:to
4638::
4616:.
4604:.
4600:.
4577:.
4569:.
4557:32
4555:.
4551:.
4530:.
4507:.
4499:.
4489:65
4487:.
4483:.
4460:.
4452:.
4442:65
4440:.
4436:.
4413:.
4403:40
4401:.
4397:.
4336:.
4328:.
4316:.
4312:.
4300:^
4284:.
4259:.
4249:26
4247:.
4243:.
4220:.
4208:20
4206:.
4202:.
4180:.
4170:17
4168:.
4164:.
4126:.
4118:.
4108:44
4106:.
4102:.
4079:.
4065:.
4061:.
4049:^
4035:.
4021:.
4017:.
3985:,
3975:,
3967:,
3953:,
3941:^
3927:.
3917:12
3915:.
3911:.
3888:.
3880:.
3868:23
3866:.
3862:.
3839:.
3829:15
3827:.
3823:.
3800:.
3792:.
3780:.
3776:.
3762:^
3730:.
3720:33
3718:.
3714:.
3691:.
3683:.
3673:.
3659:.
3655:.
3619:.
3611:.
3597:.
3574:.
3566:.
3554:.
3550:.
3536:^
3521:11
3519:,
3515:,
3491:MR
3489:,
3475:,
3445:25
3443:.
3439:.
3412:43
3410:.
3406:.
3394:^
3377:.
3355:.
3347:.
3337:.
3325:.
3321:.
3305:^
3290:,
3280:32
3278:,
3274:,
3260:^
3246:.
3234:.
3230:.
3211:^
3170:11
3168:.
3164:.
3134:,
3122:,
3099:.
3089:.
3077:43
3075:.
3071:.
3055:^
3041:.
3033:.
3023:65
3021:.
3017:.
3001:^
2979:^
2965:.
2957:.
2945:32
2943:.
2939:.
2923:^
1664:.
1132:,
1043:,
651:.
315:.
262:,
258:,
254:,
160:,
156:,
79:.
35:,
4624:.
4612::
4585:.
4563::
4536:.
4515:.
4495::
4468:.
4448::
4421:.
4409::
4382:.
4367:.
4344:.
4324::
4318:7
4294:.
4267:.
4255::
4228:.
4214::
4188:.
4176::
4134:.
4114::
4087:.
4073::
4067:9
4043:.
4029::
3971::
3961::
3935:.
3923::
3896:.
3874::
3847:.
3835::
3808:.
3788::
3782:5
3738:.
3726::
3699:.
3677::
3667::
3651:k
3627:.
3615::
3605::
3599:1
3582:.
3562::
3527::
3498:.
3483::
3477:9
3455:.
3451::
3424:.
3418::
3388:.
3363:.
3341::
3333::
3327:7
3294::
3286::
3254:.
3242::
3236:2
3201::
3180:.
3176::
3130::
3107:.
3093::
3083::
3049:.
3029::
2995:.
2973:.
2951::
2330:)
2325:3
2320:|
2315:V
2311:|
2307:(
2304:O
2269:)
2264:3
2259:|
2254:V
2250:|
2246:(
2243:O
2211:)
2206:4
2201:|
2196:V
2192:|
2188:k
2185:(
2182:O
2131:)
2126:3
2121:|
2116:V
2112:|
2102:|
2098:E
2094:|
2089:2
2085:(
2082:O
2060:)
2057:}
2052:2
2048:)
2044:}
2040:|
2036:E
2032:|
2028:,
2024:|
2020:A
2016:|
2012:{
2006:(
2002:|
1998:A
1994:|
1990:,
1985:3
1980:|
1975:V
1971:|
1967:{
1961:(
1958:O
1935:)
1930:3
1925:|
1920:V
1916:|
1912:(
1909:O
1875:)
1870:2
1865:|
1860:V
1856:|
1852:)
1848:|
1844:V
1840:|
1832:|
1828:E
1824:|
1820:(
1817:(
1814:O
1793:)
1788:3
1783:|
1778:V
1774:|
1770:(
1767:O
1736:)
1731:3
1726:|
1721:V
1717:|
1713:(
1710:O
1621:k
1607:)
1604:)
1601:k
1598:(
1587:2
1583:k
1579:(
1576:O
1566:k
1562:k
1558:k
1554:p
1550:G
1546:k
1542:k
1538:p
1534:G
1530:k
1522:k
1518:k
1495:0
1491:v
1470:k
1443:i
1440:j
1436:c
1422:j
1419:i
1415:c
1406:+
1401:i
1398:j
1394:c
1385:+
1380:j
1377:i
1373:c
1350:i
1346:v
1323:j
1319:v
1296:i
1292:v
1269:j
1265:v
1237:i
1234:j
1230:c
1207:j
1203:v
1180:i
1176:v
1148:j
1145:i
1141:c
1118:i
1114:v
1091:j
1087:v
1064:+
1059:i
1056:j
1052:c
1029:j
1025:v
1002:i
998:v
975:+
970:j
967:i
963:c
942:)
937:j
933:v
929:,
924:i
920:v
916:(
896:A
876:V
856:}
853:A
850:,
847:V
844:{
841:=
838:G
780:E
772:R
768:E
747:V
741:1
721:}
718:E
715:,
712:V
709:{
706:=
703:G
675:V
667:R
663:V
639:E
631:R
627:E
606:)
603:j
600:,
597:i
594:(
572:i
569:j
565:c
542:j
539:i
535:c
514:}
511:V
508:,
505:E
502:{
499:=
496:G
471:E
465:}
462:j
459:,
456:i
453:{
431:i
428:,
425:j
421:c
398:j
395:,
392:i
388:c
238:)
233:2
229:n
223:n
219:2
215:(
212:O
192:)
189:!
186:n
183:(
180:O
146:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.