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

摘要

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