1. 研究目的与意义（文献综述）

中国邮递员问题chinese postman problem(也称邮路问题，route inspection problem，或中国邮路问题，chinese route inspection problem)是一个图论问题。该问题旨在一个连通的无向图中找到一条最短的封闭路径，且该路径须通过所有边至少一次。简单来讲，邮路问题就是在一个已知的地区，邮差要设法找到一条最短路径，可以走过此地区所有的街道，且最后要回到出发点。

1.1 研究目的及意义：

图论是一种应用十分广泛的运筹学分支，已广泛地应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。而中国邮递员问题作为图论问题的一种，也是被广泛地应用在实际生活、生产和科学研究中，解决了很多问题。例如，一个抄表人员如何规划出一条在自己所负责区域挨家挨户抄表最后回到单位的总路线最短的省时省力的路径；在遭受水灾的地区,由于灾情的严重性,使得在某些道路上抗洪抢险部队只能保证通讯员安全通过一次，那么通讯员从总部出发后，如何选择一条不重复经过这些道路且保证遍历受灾地区的最快最短路径得以完成投递返回总部。

2. 研究的基本内容与方案

中国邮递员问题Chinese Postman Problem作为一个典型的图论问题，可以广泛应用在实际生产生活及科学研究中，将实际问题数据模式化，解决很多现实问题。这里我们拟建立一个冬季路面扫雪线路优化模型，并尝试使用中国邮递员问题的解题思路来对冬季路面扫雪线路优化模型进行求解。

技术方案：管梅谷先生为我们回顾了中国邮递员问题提出和解决的历史，同时，介绍了对此问题研究的发展概况^[1];解决中国邮递员问题的方法有很多，比如采用遗传算法求解中国邮递员问题^[2,3,4]；利用线图的概念，把中国邮递员问题转化成求顶点赋权图的最优完全子图的问题^[5]；而文献^[21]一书中提出了应对冬季路面结冰措施的路面铺沙防滑保养模型，基于题设前提条件：卡车不需要中途加沙；该数学模型也可看做中国邮递员问题的一种类型。这里，我们为了解决冬季路面扫雪线路优化模型，可以参考以上的算法，分别在精确方法上使用LINGO软件进行数学建模、编程及求解，以及使用遗传算法等启发式方法对问题进行研究，并希望加以引申，得到求解类似问题的基本模型。

3. 研究计划与安排

第1－6周：查阅相关文献资料，明确研究内容，确定方案，完成开题报告。

第7－9周：熟悉建模工具以及系统建模阶段。

第10周：中期检查。

4. 参考文献（12篇以上）

[1] 管梅谷. 关于中国邮递员问题研究和发展的历史回顾[j]. 运筹学学报, 2015,19(3):1-7.

[2] 曹鱼, 陈传波. 遗传算法求解邮递员问题的探讨[j]. 计算机与数字工程, 2000(3):28-30.

[3] 李玮, 王雷. 中国邮递员问题的dna计算[j]. 计算机应用,2009, 29(7):1880-1883.