全文总字数：1492字
1. 毕业设计（论文）主要内容：
带资源约束的基本最短路问题（elementary shortest pathproblem with resource constraints，ESPPRC）是使用经典的列生成算法求解车辆路径问题（Vehicle Routing Problem，VRP）的子问题：给定网络中两点（s, t），寻找由s点出发至t点的最短路径，路径上不允许重复的点，且该路径花费的资源不应超过给定资源的上限。有研究发现在某些VRP问题的场景中，对ESPPRC进行精确求解的效果优于对该问题的松弛情况，即允许路径上出现重复点的求解效果。但由于该问题的强NP难特性，目前围绕ESPPRC问题使用整数线性规划求解的研究还非常有限。近来有学者针对ESPPRC问题提出了新的有效不等式，但并未进行系统的计算实验，对不等式的效果和加入方法进行论证。基于此，设计和研究ESPPRC问题的割平面（cutting plane）算法有较好的理论和实践意义。
2. 毕业设计（论文）主要任务及要求
1） 文献综述：查找和阅读近5年来国内外研究VRP和ESPPRC问题的相关文献，重点在使用数学规划的精确求解方法的综述，文献数量不少于20篇；
2） 数学建模：学习使用ILOG CPLEX求解器为ESPPRC问题建立整数线性规划模型，并学会通过CPLEX中的Callback机制实现数学模型中有效不等式的灵活加入和删除；
3） 算法实验：了解和掌握割平面算法的基本实现框架，并能针对ESPPRC问题的几组有效不等式，设计具体的算法，对基准测试（benchmark）算例开展计算实验，寻找各组不等式在ESPPRC求解中的最佳组合方案，验证其有效性。
3. 毕业设计（论文）完成任务的计划与安排
2019年12月23-2020年1月23: 文献查找和阅读
2020年1月24-2020年3月24: ILOG CPLEX软件学习和建模
2020年3月25-2020年4月25: 算法实验与分析
4. 主要参考文献
1. A polyhedral study of the elementary shortest path problem with resource constraints, J. Da, L. Zheng. and X. Tang, T. Bekts et al. (Eds.), ICCL 2017, LNCS 10572, pp. 79-93, 2017;
2. Integer programming formulations for the elementary shortest path problem, L. Taccari, European Journal of Operations Research, January 2016;
3. A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint, M. K. Jepsen, B. Peterson and S. Spoorendonk, Technical Report no. 08/01 ISSN: 0107-8283;
以上是毕业论文任务书，课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
