Vray渲染技术室内设计论文提纲

论文题目：乡村邮递员问题的精确算法求解及其在防疫消毒中的应用

摘要：中国邮递员问题（Chinese Postman Problem,CPP）是路径优化中的经典问题,一个邮递员在某个街区派送信件,要求找出一条经过所有街道至少一次并回到起点的最短路径。乡村邮递员问题（Rural Postman Problem,RPP）是CPP的一个扩展,在现实生活中,并不是每条街道都会有信件派送任务,比如像乡村这样地广人稀的区域。RPP只要求经过有信件派送任务的街道（称之为目标道路）至少一次并回到起点。相对而言,RPP有更广泛的应用。本文以2020年爆发的新冠疫情为切入点,研究RPP在道路消毒和室内消毒中的应用,旨在寻找一条最短的路径,以提高消毒作业的效率。目前RPP的求解多采用启发式算法,因为启发式算法能快速找出一个合理可靠的解。然而启发式算法不能保证找到最优解。本文研究RPP的精确解算法,在前人研究的基础上,提出了一个基于无向图转换为有向图的整数规划模型。首先将道路网抽象为图论中的图（Graph）,若目标道路构成的子图不连通,即连通子图（连通分量）的个数大于1时,对Graph进行化简,然后为每条边均添加一条反向边,将无向图转换为有向图;之后为RPP建立整数规划模型,约束条件中首先保证每个顶点的入度等于出度,其次保证各连通分量两两连通,即可构造出欧拉图,经测试,当连通分量多达8个时,模型可在一分钟左右求出最优解。当目标道路构成的子图连通时,RPP可以视为CPP,为CPP建立整数规划模型,按照一个奇点只能和另外一个奇点匹配且只能匹配一次为原则寻找最佳的奇点匹配,并以此构造欧拉图。经测试,图中多达上百个奇点时,模型仅用26秒就完成奇点的最优匹配。欧拉图最终用Fleury算法求得最优路径。本文将精确算法命名为CUD（Convert＿Undirected＿to＿Directed）,并将CUD与三个启发式算法求解结果进行比较,分别是Frederickson算法、Holmberg的CE2算法、以及本文提出的IP＿MST算法,该算法将最小生成树（Minimum Spanning Tree,MST）加入了整数规划模型,并设计了复杂程度逐渐提高的12组道路网作为案例,CUD算法在每组案例中均求出了最短距离,相对三个启发式算法,最好的情况分别相对节约了6.4%、13.65%、7.78%的里程。从应用的角度出发,本文借助R语言包Shiny,开发了一个基于Web的消毒路线规划软件——RPP Solver,为路线规划提供精确解。RPP Solver有两个版本,一个可用于室外道路的消毒路线规划,另一个用于室内走廊的消毒路线规划。本文分别用这两个版本进行案例研究。一个案例是上海市川沙新镇部分道路网,数据从Open Street Map下载,经拓扑改正后加载到RPP Solver网页。模拟要消毒的道路29条,最终求出的最优路线需要途径79条道路（包括非目标道路）,最后回到出发点。另一个案例选取了上海市吴泾镇的宝龙购物广场,该广场共有四层,毗邻一高等院校,人气颇旺,本文假设该广场发现了新冠疫情,需要进行走廊消毒。室内走廊建立模型后共有85条边,用RPP Solver求出的最优路径需要途径114条边。由于邮递员问题有可能出现重复走某条边的情况,为了使路线规划结果的可视化部分更直观,本文对室外道路的规划结果进行分解,用没有重叠路径的子图分幅展示,川沙新镇道路消毒案例中最终结果被分解为八段;对于室内的路线规划结果,则提出了用彩虹色渐变渲染的新方法,使得结果有更好的指示性。本文研究了乡村邮递员问题（RPP）的精确解算法,所提出的无向图转有向图方法具有创新性,并用整数规划模型求出了RPP的最优解。该算法求解能力足以应对现实中的路径优化问题,在案例中相对于启发式算法能最高节约13.65%的里程。在最优路径的可视化环节,提出了用彩虹色渲染的新思路,直观表达出了路线的行进方向。本文开发的Web应用RPP Solver界面友好,在疫情防控领域,可用在道路消毒路径的规划和室内消毒路径的规划,具有积极的扩广价值,但界面直观性有待进一步完善,以后可以与室内定位技术结合,实现实时定位与路线导航。

关键词：乡村邮递员问题;欧拉图;整数规划模型;Shiny;防疫消毒

学科专业：地图学与地理信息系统

摘要

abstract

第一章 绪论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 论文研究工作

1.3.1 论文研究内容

1.3.2 论文创新点

1.3.3 论文结构框架

第二章 邮递员问题

2.1 欧拉图

2.2 中国邮递员问题

2.3 乡村邮递员问题

2.4 本章小结

第三章 乡村邮递员问题的精确算法

3.1 用整数规划模型求解CPP

3.2 用整数规划模型求解RPP

3.3 精确算法流程

3.4 与启发式算法的对比

3.5 本章小结

第四章 RPP Solver的开发

4.1 开发工具与技术

4.1.1 R shiny

4.1.2 Leaflet

4.1.3 道路网向Graph转换

4.1.4 室内导航

4.2 网页设计

4.2.1 室外道路网页

4.2.2 室内道路网页

4.3 案例分析

4.3.1 室外道路消毒案例

4.3.2 室内商场消毒案例

4.4 本章小结

第五章 总结与展望

5.1 归纳总结

5.2 不足与展望

参考文献

致谢