31:
876:
386:
The windy postman problem 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
90:(a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate (or the subset of edges with the minimum possible total weight) so that the resulting
398:: for this problem, some of the edges may be directed and can therefore only be visited from one direction. When the problem calls for a minimal traversal of a digraph (or multidigraph) it is known as the "New York Street Sweeper problem."
270:
in pairs. The paths will be such that the total length or total weight of all of them is as small as possible. In an optimal solution, no two of these paths will share any edge, but they may have shared vertices. A minimum
370:
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.
326:
On a directed graph, the same general ideas apply, but different techniques must be used. If the directed graph is
Eulerian, one need only find an Euler cycle. If it is not, one must find
113:
in 1960, whose
Chinese paper was translated into English in 1962. The original name "Chinese postman problem" was coined in his honor; different sources credit the coinage either to
264:
901:
586:
409:
cycles all starting at a designated location such that each edge is traversed by at least one cycle. The goal is to minimize the cost of the most expensive cycle.
350:
in which there is one unit of supply for every unit of excess in-degree, and one unit of demand for every unit of excess out-degree. As such it is solvable in O(|
302:
should be chosen as the set of all odd-degree vertices. By the assumptions of the problem, the whole graph is connected (otherwise no tour exists), and by the
314:-join causes the given graph to become an Eulerian multigraph (a connected graph in which every vertex has even degree), from which it follows that it has an
632:
318:, a tour that visits each edge of the multigraph exactly once. This tour will be an optimal solution to the route inspection problem.
880:
838:
460:
132:
of evenly many vertices that are to be joined by an edge set in the graph whose odd-degree vertices are precisely those of
896:
673:
432:
395:
756:
287:
in this complete graph. The edges of this matching represent paths in the original graph, whose union forms the desired
671:
Eiselt, H. A.; Gendeaeu, Michel; Laporte, Gilbert (1995), "Arc
Routing Problems, Part 1: The Chinese Postman Problem",
422:
346:
such that they would make in-degree of every vertex equal to its out-degree. This can be solved as an instance of the
99:
106:. It is different from the Travelling Salesman Problem in that the travelling salesman cannot repeat visited nodes.
481:
347:
615:, Optimization stories: 21st International Symposium on Mathematical Programming, Berlin, August 19–24, 2012,
543:
284:
343:
339:
335:
331:
227:
725:
198:-join exists whenever every connected component of the graph contains an even number of vertices in
605:
797:
504:
359:
291:-join. Both constructing the complete graph, and then finding a matching in it, can be done in O(
710:
A. Schrijver, Combinatorial
Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002).
609:
857:
834:
628:
456:
303:
812:
765:
729:
692:
682:
620:
496:
147:, is also solvable in polynomial time by the same approach that solves the postman problem.
87:
83:
63:
861:
779:
642:
556:
775:
721:
638:
552:
160:
114:
95:
38:
Each street must be traversed at least once, starting and ending at the post office at A.
578:
283:, with edges that represent shortest paths in the given input graph, and then finding a
30:
276:
47:
After corresponding edges are added (red), the length of the
Eulerian circuit is found.
213:-join with the minimum possible number of edges or the minimum possible total weight.
82:
is to find a shortest closed path or circuit that visits every edge of an (connected)
890:
770:
508:
118:
55:
427:
388:
379:
378:
A few variants of the
Chinese Postman Problem have been studied and shown to be
103:
59:
17:
751:
538:
315:
110:
91:
521:
866:
412:
The "Rural
Postman Problem": solve the problem with some edges not required.
164:
816:
186:
if the collection of vertices that have an odd number of incident edges in
875:
687:
330:-joins, which in this case entails finding paths from vertices with an in-
624:
41:
Four vertices with odd degree (orange) are found on its equivalent graph.
697:
500:
29:
122:
109:
The problem was originally studied by the
Chinese mathematician
358:|) time. A solution exists if and only if the given graph is
577:
Pieterse, Vreda; Black, Paul E., eds. (September 2, 2014),
34:
A worked example of an undirected
Chinese postman problem:
159:
The undirected route inspection problem can be solved in
541:(1960), "Graphic programming using odd or even points",
798:"Complexity of vehicle routing and scheduling problems"
610:"Euler, Mei-Ko Kwan, Königsberg, and a Chinese postman"
482:"Matching Euler tours and the Chinese postman problem"
232:
230:
94:does have an Eulerian circuit. It can be solved in
258:
44:The pairing with the lowest total length is found.
658:Combinatorial Optimization: Networks and Matroids
475:
473:
471:
224:-join (when it exists) necessarily consists of
619:, Documenta Mathematica Series, Extra: 43–50,
587:National Institute of Standards and Technology
175:be a set of vertices in a graph. An edge set
27:Finding shortest walks through all graph edges
833:(2nd ed.), CRC Press, pp. 642–645,
791:
789:
455:(2nd ed.), CRC Press, pp. 640–642,
310:-join always exists. Doubling the edges of a
8:
583:Dictionary of Algorithms and Data Structures
306:it has an even number of odd vertices, so a
796:Lenstra, J.K.; Rinnooy Kan, A.H.G. (1981),
720:Crescenzi, P.; Kann, V.; Halldórsson, M.;
769:
696:
686:
251:
243:
231:
229:
829:Roberts, Fred S.; Tesman, Barry (2009),
754:(1984), "On the windy postman problem",
731:A compendium of NP optimization problems
451:Roberts, Fred S.; Tesman, Barry (2009),
275:-join can be obtained by constructing a
443:
902:Computational problems in graph theory
128:A generalization is to choose any set
86:at least once. When the graph has an
7:
480:Edmonds, J.; Johnson, E.L. (1973),
298:For the route inspection problem,
259:{\displaystyle {\tfrac {1}{2}}|T|}
25:
522:"The Travelling Salesman Problem"
123:U.S. National Bureau of Standards
874:
266:paths that join the vertices of
405:-Chinese postman problem: find
285:minimum weight perfect matching
252:
244:
1:
433:Mixed Chinese postman problem
396:Mixed Chinese postman problem
771:10.1016/0166-218X(84)90089-1
757:Discrete Applied Mathematics
660:, Holt, Rinehart and Winston
423:Travelling salesman problem
121:, both of whom were at the
100:Travelling Salesman Problem
918:
167:based on the concept of a
140:-join. This problem, the
136:. Such a set is called a
862:"Chinese Postman Problem"
608:; Yuan, Ya-xiang (2012),
579:"Chinese postman problem"
348:minimum-cost flow problem
881:Route inspection problem
489:Mathematical Programming
151:Undirected solution and
80:route inspection problem
544:Acta Mathematica Sinica
334:greater than their out-
295:) computational steps.
72:Chinese postman problem
817:10.1002/net.3230110211
342:greater than their in-
260:
51:
831:Applied Combinatorics
734:, KTH NADA, Stockholm
688:10.1287/opre.43.2.231
656:Lawler, E.L. (1976),
617:Documenta Mathematica
453:Applied Combinatorics
338:to those with an out-
261:
33:
897:NP-complete problems
883:at Wikimedia Commons
228:
68:Guan's route problem
674:Operations Research
562:Chinese Mathematics
279:on the vertices of
190:is exactly the set
858:Weisstein, Eric W.
501:10.1007/bf01580113
360:strongly connected
256:
241:
52:
879:Media related to
634:978-3-936609-58-5
606:Grötschel, Martin
322:Directed solution
304:handshaking lemma
240:
16:(Redirected from
909:
878:
871:
870:
844:
843:
826:
820:
819:
802:
793:
784:
782:
773:
748:
742:
741:
740:
739:
717:
711:
708:
702:
701:
700:
690:
668:
662:
661:
653:
647:
645:
625:10.4171/dms/6/10
614:
602:
596:
595:
594:
593:
574:
568:
567:: 273–277, 1962.
560:. Translated in
559:
535:
529:
528:
526:
518:
512:
511:
486:
477:
466:
465:
448:
265:
263:
262:
257:
255:
247:
242:
233:
88:Eulerian circuit
84:undirected graph
64:computer science
21:
917:
916:
912:
911:
910:
908:
907:
906:
887:
886:
856:
855:
852:
847:
841:
828:
827:
823:
800:
795:
794:
787:
750:
749:
745:
737:
735:
719:
718:
714:
709:
705:
670:
669:
665:
655:
654:
650:
635:
612:
604:
603:
599:
591:
589:
576:
575:
571:
537:
536:
532:
524:
520:
519:
515:
484:
479:
478:
469:
463:
450:
449:
445:
441:
419:
376:
368:
324:
226:
225:
161:polynomial time
157:
115:Alan J. Goldman
96:polynomial time
50:
28:
23:
22:
18:Chinese postman
15:
12:
11:
5:
915:
913:
905:
904:
899:
889:
888:
885:
884:
872:
851:
850:External links
848:
846:
845:
839:
821:
811:(2): 221–227,
785:
743:
712:
703:
681:(2): 231–242,
663:
648:
633:
597:
569:
547:(in Chinese),
530:
513:
467:
461:
442:
440:
437:
436:
435:
430:
425:
418:
415:
414:
413:
410:
399:
392:
387:graphs, it is
375:
372:
367:
364:
323:
320:
277:complete graph
254:
250:
246:
239:
236:
156:
149:
58:, a branch of
49:
48:
45:
42:
39:
35:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
914:
903:
900:
898:
895:
894:
892:
882:
877:
873:
869:
868:
863:
859:
854:
853:
849:
842:
840:9781420099829
836:
832:
825:
822:
818:
814:
810:
806:
799:
792:
790:
786:
781:
777:
772:
767:
763:
759:
758:
753:
747:
744:
733:
732:
727:
723:
722:Karpinski, M.
716:
713:
707:
704:
699:
694:
689:
684:
680:
676:
675:
667:
664:
659:
652:
649:
644:
640:
636:
630:
626:
622:
618:
611:
607:
601:
598:
588:
584:
580:
573:
570:
566:
563:
558:
554:
550:
546:
545:
540:
534:
531:
523:
517:
514:
510:
506:
502:
498:
494:
490:
483:
476:
474:
472:
468:
464:
462:9781420099829
458:
454:
447:
444:
438:
434:
431:
429:
426:
424:
421:
420:
416:
411:
408:
404:
400:
397:
393:
390:
385:
384:
383:
381:
373:
371:
365:
363:
361:
357:
353:
349:
345:
341:
337:
333:
329:
321:
319:
317:
313:
309:
305:
301:
296:
294:
290:
286:
282:
278:
274:
269:
248:
237:
234:
223:
220:, a smallest
219:
214:
212:
209:is to find a
208:
207:-join problem
205:
201:
197:
193:
189:
185:
182:
178:
174:
170:
166:
162:
154:
150:
148:
146:
145:-join problem
144:
139:
135:
131:
126:
125:at the time.
124:
120:
116:
112:
107:
105:
101:
98:, unlike the
97:
93:
89:
85:
81:
77:
73:
69:
65:
61:
57:
46:
43:
40:
37:
36:
32:
19:
865:
830:
824:
808:
804:
764:(1): 41–46,
761:
755:
746:
736:, retrieved
730:
726:Woeginger, G
715:
706:
678:
672:
666:
657:
651:
616:
600:
590:, retrieved
582:
572:
564:
561:
548:
542:
539:Kwan, Mei-ko
533:
516:
492:
488:
452:
446:
406:
402:
377:
369:
366:Applications
355:
351:
327:
325:
311:
307:
299:
297:
292:
288:
280:
272:
267:
221:
217:
215:
210:
206:
203:
199:
195:
191:
187:
183:
180:
179:is called a
176:
172:
168:
158:
152:
142:
141:
137:
133:
129:
127:
119:Jack Edmonds
108:
79:
76:postman tour
75:
71:
67:
56:graph theory
53:
752:Guan, Meigu
698:11059/14013
551:: 263–266,
428:Arc routing
389:NP-complete
380:NP-complete
171:-join. Let
60:mathematics
891:Categories
738:2008-10-22
592:2016-04-26
495:: 88–124,
439:References
316:Euler tour
111:Meigu Guan
92:multigraph
867:MathWorld
165:algorithm
102:which is
805:Networks
509:15249924
417:See also
374:Variants
216:For any
780:0754427
643:2991468
557:0162630
104:NP-hard
837:
778:
641:
631:
555:
507:
459:
344:degree
340:degree
336:degree
332:degree
202:. The
163:by an
155:-joins
70:, the
801:(PDF)
613:(PDF)
525:(PDF)
505:S2CID
485:(PDF)
184:-join
835:ISBN
629:ISBN
457:ISBN
401:The
394:The
194:. A
62:and
813:doi
766:doi
693:hdl
683:doi
621:doi
497:doi
117:or
78:or
54:In
893::
864:,
860:,
809:11
807:,
803:,
788:^
776:MR
774:,
760:,
728:,
724:;
691:,
679:43
677:,
639:MR
637:,
627:,
585:,
581:,
553:MR
549:10
503:,
491:,
487:,
470:^
382:.
362:.
354:||
74:,
66:,
815::
783:.
768::
762:9
695::
685::
646:.
623::
565:1
527:.
499::
493:5
407:k
403:k
391:.
356:E
352:V
328:T
312:T
308:T
300:T
293:n
289:T
281:T
273:T
268:T
253:|
249:T
245:|
238:2
235:1
222:T
218:T
211:T
204:T
200:T
196:T
192:T
188:J
181:T
177:J
173:T
169:T
153:T
143:T
138:T
134:T
130:T
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
