Exact Solution Of Rural Postman Problem And Its Application In Epidemic Prevention And Disinfection

Chinese Postman Problem(CPP)is a classic problem in path optimization.When a postman delivers letters in a certain block,he is required to find the shortest path that passes through all streets at least once and returns to the starting point.Rural Postman Problem(RPP)is an extension of CPP.In real life,not all streets has letter delivery task,such as the vast and sparse area like rural areas.RPP only requires passing through the streets having letter delivery task(called target road)at least once and returning to the starting point.Comparatively speaking,RPP has wider applications.Taking COVID-19,which broke out in 2020,as an entry point,this paper studies the application of RPP in road disinfection and indoor disinfection,aiming at finding a shortest path to improve the efficiency of disinfection.At present,heuristic algorithms are often used to solve RPP,because heuristic algorithm can quickly find a reasonable and reliable solution.However,heuristic algorithm can not guarantee to find the optimal solution.In this paper,the exact algorithm of RPP is studied.On the basis of previous studies,an integer programming model based on converting undirected graph to directed graph is proposed.Firstly,the road network is abstracted as a Graph in Graph Theory.If the subgraphs induced by target roads are not connected,that is,the number of subgraphs(connected components)is greater than 1,the graph will be simplified,and then a reverse edge will be added to each edge to convert the undirected graph to directed graph.Then,an Integer Programming model is established for RPP.In the constraint conditions,the in-degree of each vertex is equal to the out-degree firstly,and secondly,the connected components are connected in pairs to construct the Euler Graph.After testing,when there are 8 subgraphs,the optimal solution can be obtained in about 1 minute.When the number of subgraph induced by target roads is 1,RPP can be regarded as CPP.The other integer programming model is established for CPP.According to that one odd point can only match another odd point and only match once,the best odd point matching is found,then a Euler Graph is constructed.After testing,when there are hundreds of odd points in the graph,the model can achieve the optimal matching of odd points in only 26 seconds.Finally,the optimal path is obtained by Fleury algorithm.The exact algorithm is named CUD(Convert?Undirected?to?Directed),and the results of CUD are compared with three heuristic algorithms.The heuristic algorithms are Frederickson's algorithm,Holmberg's CE2 algorithm,and the IP?MST algorithm proposed in this paper,which adds Minimum Spanning Tree(MST)to the integer programming model.12 groups of road networks with increasing graph complexity are designed as cases.CUD algorithm gets the shortest solution compared with the heuristic algorithm in each case,and in the best case,the mileage is saved by 6.4%,13.65% and 7.78% compared with three heuristic algorithms.For application,a web-based disinfection route planning software RPP Solver is developed with R Shiny,which provides exact solutions for route planning.RPP Solver has two versions,one can be used for outdoor road disinfection route planning.The other is used for disinfection route planning of indoor corridor.Two cases are analysed using the two versions.One case is a part of the road network of Chuansha New Town in Shanghai.The data is downloaded from Open Street Map and loaded into the RPP Solver web page after topology correction.29 roads to be disinfected are simulated,and 79 roads(including non-target roads)are included in the optimal route,before returning to the starting point.Another case is Powerlong Shopping Mall in Wu Jing Town,Shanghai.There are four floors in the mall,adjacent to a university and has many customers.It assumes that COVID-19 has been found in the mall and the corridors should be disinfect.There are 85 edges in the Graph model of the mall,and the optimal path obtained by RPP Solver contains 114 edges.In order to make the visual part of the route planning results more intuitive,the planning path of outdoor is decomposed,and sub images without overlapping paths are displayed.In the case of Chuansha New Town road disinfection,the final path are decomposed into 8sections.A new method of rainbow gradient rendering is proposed to make the results more indicative in the indoor route planning.In this paper,the exact solution of rural postman problem(RPP)is studied.The method of converting undirected graph to directed graph is innovative,and the optimal solution of RPP is obtained by integer programming model.Compared with heuristic algorithm,the algorithm can save 13.65% mileage in cases.In the visualization part of the optimal path,a new idea of rainbow gradient rendering is proposed to express the direction of the route more intuitively.The web application RPP?solver developed in this paper has a friendly interface.It can be used in the planning of outdoor road disinfection and indoor corridor disinfection in epidemic prevention and has a positive expansion value.However,the interface needs to be further improved,and it can be combined with indoor positioning technology to achieve real-time positioning and route navigation.