Page 1Page 2Page 3Page 4Page 5Page 6Page 7Page 8Page 9Page 101988-06 Spring 1988 The Chinese Postman Problem - Applied to a Newspaper Delivery Route Steve Feather The Chinese Postman ProblemApplied to A Newspaper Delivery Route by:Steve Feather for: OREM 4390 Senior DesignMay 5, 1988The Chinese Postman ProblemApplied to A Newspaper Delivery Route by:Steve Feather for: OREM 4390 Senior DesignMay 5, 1988 LITable of Contents Acknowledgments... . . . . .. .................... • •. •.•1 Summary. ...... . . . . . . . . ........ . . .......... . . . . . . .2 Technical Description of Problem .....3 Analysis. . . . . . . . . . . . . . . . . . .......... • . . • • . • . • ......•5 Appendix Paper Route Distance Matrix1Acknowledgments I gratefully acknowledge Mr. Douglas Sivertson for his help on this project.Summary I applied the postman problem to an undirected graph that was not even. Since the graph was not even, some of the arcs had to be repeated. The goal of the post-man problem is to find the combination of arcs tobe repeated that would give the shortest distance to be covered. On the route, all arcs must be covered at least once. The total distance of the route is the sum of the distances of all the arcs plus the distances of those arcs that will be repeated. 2Technical Description of Problem In a graph G of the deliveryman's route, the arcs are streets and the nodes are intersections. The num-ber of times that the deliveryman enters a node equals the number of times he leaves that node. Consequently, if node n does not have even degree, then at least one arc of that node must be repeated by the deliveryman. To find which arcs should be repeated, a new graph 0 of just odd degree nodes is constructed. Example:The odd nodes are a,c,cI,f. Graph GGraph 0 Next, the shortest path is found between each pair of odd nodes.ac df 423 c4024 d 2203 f3430 Then, the combination of pairs with the shortest dis-tance is found.(a,c) (d,f)= 4 + 3 = 7 (a,d) (c,f)= 2 + 4 = 6 (a,f) (c,d)= 3 + 2 = 5 3Consequently, the deliveryman should repeat the paths from a to f and from c to d.Analysis After applying the postman problem to Mr. Sivertson's newspaper delivery route, I found that 20 nodes were odd degree which meant that 10 arcs were to be repeated. The route and its distance matrix can be found in the Appen-dix. The arcs to be repeated are: (B,C), (E,H), (G,J), (K,N), (M,Q), (O,P), (R,S), (hT,W), (Y,Z), and (AA,AB). 5Appendix Paper RouteS.- ,j// 29 .L.T .4 0 /.0 /,Lj/0,7 r"s-- 7.9q, 7.110.,2 9.11. ,q :g-1cD 17V 7,7 4/,9 I)/ 3,ä-2,3 -p.2. ).,oI, 1J 7I2/ ,0.' B3.2. C•.2,.0 E1/2-:;.30 c:29 H0•7-J-3k',/,/63 K SX1,117/.5 fl.^32,j70 P:.o5I•S( 3,0x R43'I V12,o/O2/1,0 'WI11517 \,i/J9 Z10. -tS92 44.ioi79 M691/O2..2.94'92hsS3(Jo '7.Tltj,q'2./g41-E-. t 3icTO.2.2'1.97. o6. z•o'.'-/7,.si 6307-.(/1.s-11297 ,•1£706'1.7-1-,l',yr3_ 7.0.1(Q'/0•5;7.73(6.3 ,q.-5;7-c /,c;76-'oc;1.:L3,,/T(L, '/2I/-2.4/33-21-0..-'/4'4'9311/,,,3,'/.—C) 9.3-1, 144,63.cI',2.9-Zz0 2. --261J.z:;..Z.—3.3T-3, V L.2,17.'J2,0(',?3.1/,o1,, 9/0,3;I?' '9'/0-19, &/ ,3/0-07-9,394 ?)7,5.3.I.6.'?;•9 1-.?7.17.7o.f7-5c 1.13773'70 6.9(Q/5Y/2074213 12,o // o -31 eD 4<1 1012 91; ?? 11-03 2,9 349.0 / 7;7 2 /0.3 ,02 ,2Z.1 2? 23 69,q 9s 10.0 i.r .o,/ 7- ?3' 9,3 ?,Iloll 9i 9.q.q .5-0(el) •64•I0 1.j•-co •:3 q,'2.2. 2.7-). q2,3 , - 23 l? 39 3,L4 27- 2,2. UILI,'J