基于Shiny与Leaflet技术的中国邮递员问题网页设计与开发

Development of Web Application for Chinese Postman Problem Based on Shiny and Leaflet

路径优化问题存在于日常生活中的诸多领域,但方便实用的路径优化软件却不多见。中国邮递员问题是一个典型的路径优化问题,要求找出一条经过所有服务边至少一次,且回到起点的最短路径。基于Shiny开发一个求解中国邮递员问题的网页应用程序CPPSolver,其采用整数规划模型寻找奇点之间的最优匹配,添加重复边构建欧拉图,然后采用Fleury算法求解欧拉回路,即中国邮递员问题的解。针对结果路径的重叠问题提出路径分解算法,将重叠路径分解为若干段,避免了路径导航的二义性。此外,CPPSolver程序采用Leaflet工具包实现了地图的可视化与交互性。

Path optimization problems exist in many areas of daily life,but there are few convenient and practical software for these problems.The Chinese Postman Problem(CPP)is a typical path optimization problem,which requires to find the shortest path that passes through all service roads at least once and returns to the starting point.In this paper,based on shiny R,a web application of Chinese Postman Problem Solver is developed.This application uses the integer programming model to find the best match between the singularities,then adds the repeated edge to build the Euler Graph,and uses the Fleury algorithm to find Euler circuit,that is,the so⁃lution of the CPP.To solve the visualization problem of overlapping paths,proposes a path break-up algorithm to make the overlapped paths break up into several segments,avoiding the ambiguity during path navigation.The program uses Leaflet to realize a visual and interactive map.