时间依赖的无向中国邮路问题分支切割算法的任务书.docx

时间依赖的无向中国邮路问题分支切割算法的任务书
任务书
题目：时间依赖的无向中国邮路问题分支切割算法
背景
在邮政物流系统中，如何找出最优的邮路方案一直是一个重要的研究领域。中国邮路问题（ChinesePostmanProblem，CPP）是一种经典的优化问题，它的求解可以应用于邮政、交通、电力等领域。CPP的输入是一张无向图，其顶点表示景点或交叉口，边表示道路或路径，每条边都有一个权重和一个时间限制。问题的目标是找到一条经过所有边的回路，使得该回路的总权重最小且时间限制内。
CPP问题可以用分支切割算法进行求解。本项目的目标是设计一种时间依赖的无向中国邮路问题分支切割算法，通过理论推导和实验验证，提高算法的求解效率和准确性。
任务描述
1.比较常规的CPP求解方法的优缺点，深入分析CPP的特点并确定分支切割算法中的分支策略和切割策略。
2.设计时间依赖的无向中国邮路问题分支切割算法，并编写正确高效的算法程序。
3.利用现成的CPP求解数据集，通过计算模拟的方式进行算法性能评估，对比本算法在求解时间和最优解方面的表现。
4.根据评估结果，对算法进行分析和改进，并提出深入研究的方向。
5.撰写实验报告，详细介绍算法的设计思路、程序实现、性能评估和改进方案等内容。报告应具备较高的可读性和规范性，格式需符合国际通行的学术论文写作要求。
任务要求
1.具备扎实的计算机算法设计和分析基础，熟练掌握图论和动态规划等相关知识。
2.熟悉分支切割算法的原理和基本思路，了解其常见的分支策略和切割策略。
3.具备良好的编程能力，能够使用C++、Python等编程语言设计和实现算法程序。
4.每个小组由2-3人组成，应具备优秀的团队合作能力，能够高效协作完成实验任务。
5.实验报告内容需独立完成，不得抄袭他人作品，必要引用参考文献。
任务进度安排
1.第1周：完成任务书编写，学习分支切割算法的基本理论和相关算法。
2.第2周：进一步研究CPP问题的特点及分支策略和切割策略的选择，并开始编写算法程序。
3.第3-4周：逐步完善算法程序和相关文档，进行算法的性能评估和结果分析。
4.第5周：整理实验报告，并进行报告的完成和提交。
参考文献
1.Li,H.,&Lim,A.(2009).SolvingtheChinesepostmanproblemonmixedgraphs.INFORMSJournalonComputing,21(2),252-268.
2.Kwan,M.Y.(2020).Atime-dependentChinesepostmanproblemmodelforthedeliveryofpostalitems.InternationalJournalofProductionEconomics,223,107517.
3.Zhang,M.,Wu,F.,&Zhu,X.(2015).Aheuristicalgorithmfortime-dependentChinesepostmanproblem.GlobalJournalofComputerScienceandTechnology,15(8),6-15.
4.Ramezanian,R.(2013).ThenewmethodtosolvetheChinesepostmanproblembasedonthedynamicparametersetting.InternationalJournalofModernEducationandComputerScience,12(4),1-10.
5.Al-Ghadhban,A.,&Al-Taiar,H.(2017).AnefficientalgorithmfortheChinesepostmanproblemingridgraphs.JournalofInformationScienceandTechnology,15(4),1-13.