开题报告-外卖路线最优化研究.docx

南京邮电大学毕业设计(论文)开题报告题目外卖路线最优化研究学生姓名班级学号B13070226专业网络工程1、 对指导教师下达的课题任务的学习与理解通过对任务书的学习和与指导老师的交流，了解了这次毕业设计的主要任务：(1)学习Travelling Salesman Problem(TSP)问题，掌握TSP问题的分类，并能够使用所学知识建立外卖路线的数学模型；(2)学习并掌握遗传算法的原理及其应用方法；(3)了解当前外卖的送餐区域和路线规划特性；(4)在MATLAB上尝试使用遗传算法解决动态TSP问题，并对模拟出来的结果进行分析，总结和改进；(5)在总结的结果上给出送餐路线最优化问题的路线规划方案。2、 阅读文献资料进行调研的综述（10篇左右）TSP问题（又称货郎担问题、旅行商问题），可叙述如下：一个旅行商要访问n个城市中的每个城市，若任意两个城市间的路程已知，现要找一条经过所有城市且每个城市只经过一次的最短闭合路径1。如图1所示，该问题可简单描述为：给定加权图 G，要求在加权图 G中找出一条累加权最小的回路。TSP问题是组合优化问题中最经典的问题之一，是一个Non-deterministic Polynomial（NP）问题2。如果在TSP问题中涉及的节点间的权值、节点的数目随着时间的变化而变化，则可称之为动态TSP问题。动态TSP问题早已广泛运用于车辆选路、路由选择、机器人路线规划等实际领域3。旅行推销员问题（TSP）已被用于建模许多现实世界的应用程序。在这个问题中，销售员使用城市之间的路线旅行，他必须访问每个城市并返回车辆出发点。如果需要在解决方案中使用多个销售员，则该问题被称为多个旅行销售人员问题，目标是最小化他们行进的整体距离4。外卖送餐路线规划，就是在考虑道路状况、新增单等情况下，选取价值最高的送餐员行进的路线。图1 tsp问题示意图近年来，随着网上订餐平台的越发繁荣，外卖送达的效率提高也越发的重要。外卖不同于其他货物，它必须在一定的时间内送达，否则不仅外卖的质量会受到影响，消费者的用餐体验也会变差。而现在的外卖送餐员还存在着问题，譬如送餐太慢。优化外卖路线，将有利于网上订餐平台的发展，也将提高顾客们的用餐体验5。外卖路线最优化研究就是利用遗传算法计算送餐员的路线，达到路线配送价值最大，以实现商家和客户的双赢。通过阅读中外文献进行调研，结果如下：当前，赵桢6提出采用智能化调度来解决外卖送餐慢的问题；王帅7提出建立时间窗的方法来提高送餐效率。1.外卖送餐情况调研1.1外卖送餐模式现在外卖送餐模式主要分两种8：一种是商家自主配送，例如肯德基；另一种是由外卖平台上的送餐员统一配送。统一配送的过程如图2所示：首先消费者先从平台上订餐；商家接单，做好餐点，与此同时送餐员接单，赶往商家拿到外卖；最后送餐员将外卖送到消费者手上。图2 外卖路线示意图1.2外卖送餐现状现在送餐员在接到单后，按照自己的习惯路线拿餐、送餐，但效率低下问题一直存在。由于送餐时间过长，消费者常常会打电话催单，送达的餐点也会变得冰凉，影响消费体验和商家的口碑。2.TSP问题解决算法2.1传统构造算法传统构造算法有：最近邻算法、贪心算法、插入算法等。它们的思路是先选取一个点作为出发点，然后找到下一个点，以此类推，逐步构造出一条路线9。2.2路线改进算法路线改进算法有：边交换算法，Lin-Kernighan(LK)算法等。它们的思路是先选取一条路径，然后查漏补缺，对其进行修改，使该条路径更加接近最优路径。2.3启发式算法启发式算法有：爬山算法、模拟退火算法、局部最优化算法、遗传算法、蚁群算法等。TSP问题是一个NP完全问题。随着问题规模的增大，其解空间呈指数增长，无法在短时间内完成问题的求解。近几十年来,人们提出了许多基于生物理论的解决该问题的新方法。这些方法多是参考现实生活中的行为，例如爬山、退火、染色体等，从而受到启发研究出的算法。因其简单易行，容易被使用者理解，该类算法在各个领域均有很好的应用。 2.4遗传算法遗传算法9( Genetic Algorithms,简称 GA) 就是 J.Holland于1975 年受生物进化论的启发而提出的。遗传算法10是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”的适者生存过程,通过“染色体”群的一代代不断进化 ,包括复制、交叉和变异等操作 ,最终收敛到“最适应环境”的个体,从而求得问题的最优解或满意解。遗传算法对优化对象的限制很少，且其搜索到全局最优解的能力相对于其他算法有竞争性11。虽然遗传算法能够较为成功的解决TSP问题，但也存在早熟问题。所以我们需要对其进行改进，加快其收敛速度，避免其早熟12。 3、 根据任务书的任务及文献调研结果，初步拟定的执行（实施）方案（含具体进度计划） 根据调研所得，我将使用遗传算法作为解决送餐问题的方法。首先，根据送餐问题建立模型，实现问题的数据化，然后将数据进行编码，使用遗传算法处理该问题，分析结果与现实是否相符，不符则改进模型，相符则给出方案。1.执行（实施）方案： 1.1理解TSP问题和遗传算法的原理，以动态TSP问题以及相关遗传算法为主；1.2在1.1的基础上，分析外卖问题，分析构建模型和求解模型时需要用到的理论工具和优化方案，探讨问题求解的可能性；1.2.1确定决策变量及各种约束条件对问题进行抽象化描述，进而确定变量时间，路径，目的地；根据现实情况确定约束条件：所有客户必须在限定时间内送达；所载外卖量必须小于车辆最大承载量；外卖路径总长度必须小于车辆最大行驶里程；考虑跨区域送餐时外卖交接问题。1.2.2建立数学模型首先定义四个集合，中存放所有点，中存放已经送达的点,中存放所有未送达的点，中存放正在送餐的点。当时，送餐结束。依据1.2.1的变量与约束条件建立数学模型: 公式（1-1）中表示当前时刻，表示目的地，表示目的地的序号，表示当前正在送餐的目的地序号，表示路径中的距离函数，表示当前时刻下目的地的最大序号，表示两地之间的距离，表示未走过的路程，表示已走过的路程；公式（1-2）中表示车辆一次送餐可以行驶的最大距离；公式（1-3）中表示两个目的地的正常行驶距离，表示在天气及道路状况影响下的系数，公式（1-4）中表示该点需要送达的单数，表示该条路径中单数的总和；公式（1-5）中表示衡量路径适应度的函数，表示距离与单数在送餐价值中占的比例；公式（1-6）中表示最后选择的合适的路径适应度，表示路径，表示最后选择的路径。1.3选择遗传算法解决问题1.3.1确定染色体编码和解码方法编码时以目的地为基因组，把送餐员的目的地按出现的时间来安排序号，用这个序号来编码，一串染色体即代表一个送餐员的送餐路线选择。1.3.2个体适应度的量化评价方法以送餐路线上总路程的倒数为个体适应度。1.3.3设计遗传算子我们选择部分匹配交叉。首先在染色体上随机选择两个交叉点A,B（AB），介于A与B之间的叫做匹配区，列出匹配区内两个个体基因对应关系；然后交换匹配区内的基因串；最后按照匹配区内父串上的对应关系换掉匹配区外的重复位。先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。具体方法如下所示：父代A：872 |130 | 9546父代B：983 | 567 | 1420 变为：TEMP A: 872 | 567 | 9546TEMP B: 983 | 130 | 1420对于 TEMP A、TEMP B匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：153670子代A：802 | 567 | 9143子代B：986 | 130 | 5427综上，遗传算法的具体流程图如图4所示：图4 遗传算法流程图 1.3.4在MATLAB上模拟算法图5 MATLAB R2015b界面示意图如图5所示，MATLAB是一种主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案。1.4分析仿真结果观察并分析实验结果，判断其有无陷入局部最优化。1.5改进实验根据分析结果，改进使用的算法，之后再次仿真实验，直到找到解决方案。1.6形成外卖路线最优化方案整理实验结果，形成外卖路线最优化方案。2.进度计划（1）2017年3月13日-24日：依据任务书，通过查阅文献了解TSP问题的分类和遗传算法的原理，分析当前外卖的路线规划特性,完成开题报告； （2）2017年3月25日-4月23日：认真学习TSP问题和遗传算法；完成外文文献的翻译；建立送餐路线最优化问题模型，尝试使用遗传算法解决该问题并进行仿真实验； （3）2017年4月24日-4月28日：进行中期检查； （4）2017年4月29日-5月19日：完善模型，完成仿真实验，对结果进行分析，给出送餐路线最优化问题的路线规划方案；修改外文文献的翻译稿； （5）2017年5月20日-5月29日：撰写毕业设计(论文)报告；（6）2017年6月1日-6月11日：整理毕业设计资料，准备答辩；（7）2017年6月12日-6月16日：毕业论文答辩。4、 参考文献1 William J.Cook. In Pursuit of the Traveling Salesman: Mathematics at the Limits of ComputationM.隋春宁.北京：人民邮电出版社，2013:106-111.2 窦全胜，陈姝颖.演化计算方法及应用M.北京：电子工业出版社，2016:3-4. 3 郭靖扬. 旅行商问题概述J.大众科技，2006,08:229-2304 Raulczar M. F. Alves, Carlos R. Lopes Using genetic algorithms to minimize the distance and balance the routes for the multiple Traveling Salesman ProblemC. IEEE Conference Publications. 2015.7257285 .3171 3178.5 田世峰. 华冠联合公司物流配送路线优化研究 D.山东：山东大学，2011-09-15.6 赵桢.餐饮O2O外卖配送方法研究J.市场周刊(理论研究).2016,08:33-347 王帅, 赵来军,胡青蜜.随机旅行时间的外卖O2O配送车辆路径王帅J.物流科技.2017,01:93-1018 郭月,张涵.校园外卖配送体系研究J.中国市场，2016,20:67-69.9 Holland J H. Adaptation in natural and artificial systemsM. MIT Press, 1992. 10 许智宏,宋勃,董建波. 用蚂蚁算法和模拟退火算法解大规模TSP问题的研究J. 计算机工程与科学，2008，10:43-44,57.11 边霞,米良遗传算法理论及其应用研究进展J. ApplicationR esea