毕业设计（论文）-外卖路线最优化研究.pdf

南京邮电大学 毕 业 设 计（论 文） 题 目 外卖路线最优化研究 专 业 网络工程 学生姓名 李宝龙 班级学号 B13070226 指导教师 许斌 指导单位 物联网学院 日期： 2017 年 1 月 15 日至 2017 年 6 月 16 日 毕业设计（论文）原创性声明 本人郑重声明：所提交的毕业设计（论文） ，是本人在导师指导下，独立进行 研究工作所取得的成果。除文中已注明引用的内容外，本毕业设计（论文）不包 含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献 的个人和集体，均已在文中以明确方式标明并表示了谢意。 论文作者签名： 日期： 年 月 日 摘 要 随着互联网的发展，人们的生活方式也随之发生了改变，越来越多的学生和 白领倾向于订外卖来解决用餐问题。与此同时，外卖行业迎来了极大的发展，这 也促进了外卖送餐行业的兴起。送餐服务可以节约客户大量的排队时间，也可以 省去客户在厨房忙碌的时间。随着科技的进步，外卖送餐的通知方式也发生了很 大改变，从原始的口头订餐发展的现在的网络订餐，效率已经有了极大的提高， 但是送餐速度和准确性仍没有得到明显提高。 所以我们研究外卖路线的优化是极有必要的，这样可以提高外卖送餐的速度 与效率。外卖路线规划问题可类比为旅行商问题，是一个非确定多项式问题，使 用常规算法效率不高，而使用智能优化算法解决该问题效果较好。本文对外卖路 线和传统物流路线进行了简单的对比，将现有的物流模型调整为外卖送餐路线模 型并对外卖送餐过程中道路拥堵的情况进行了研究。在研究外卖路线的过程中， 本文提出了一些新的情况；同时本论文利用遗传算法研究外卖路线，用来实现外 卖路线的规划和道路拥挤时外卖的配送路线的规划方案，并给出了实验结果。 关键词：外卖路线规划；遗传算法；旅行商问题；优化问题；路径问题 ABSTRACT With the development of the Internet, peoples life styles get also changed, more and more students and white-collar workers tend to order takeout to have a meal. At the same time, takeout industry has a great development, which also promotes the rise of take-out delivery industry. Delivery service can save customers much queuing time and cooking time. With the development of the technology, the way of takeout notification also has a great change, from original verbal order develop to current online order. The efficiency has been greatly improved, but the speed and accuracy of delivery has not been obvious improved. So its very necessary for us to research takeout route, because this can improve the speed and accuracy of the delivery. Traveling salesman problem can analogue for takeout route planning problem, so takeout route planning problem is a Non-Deterministic Polynomial problem. Its inefficient for us using conventional algorithms to solve takeout route planning problem, its more efficient for solving this problem to use Intelligent optimization algorithm. In this paper, we compare the takeout route to traditional logistics route. Then we adjust current logistics model to takeout route model and research the case of road congestion when happened at takeout delivery process. In the process of researching takeout routes, this paper put forward some new situation. At the same time, this paper use Genetic algorithm to research takeout route planning problem. This research plans takeout route when road is congested. Key words：Takeout route Planning; Genetic Algorithm; Travelling Salesman Problem; Optimization Problem; Routing Problem 目 录 第一章 绪论 . 1 1.1 研究的背景和意义 . 1 1.2 国内外研究现状 . 3 1.3 主要研究内容和章节安排 . 6 第二章 外卖路线优化问题概述 . 7 2.1 优化问题概述 . 7 2.2 路线优化问题概述 . 8 2.3 外卖路线介绍 . 8 2.3.1 外卖路线特点 8 2.3.2 外卖路线基本假设 . 10 2.4 本章小结 11 第三章 遗传算法研究 12 3.1 遗传算法基本思想 12 3.2 遗传算法的优缺点 12 3.2.1 遗传算法的优点 . 13 3.2.2 遗传算法的缺点 . 13 3.3 遗传算法的参数设置 13 3.3.1 种群规模设置 . 13 3.3.2 变异概率设置 . 14 3.3.3 迭代次数设置 . 14 3.4 遗传算法的专有名词 14 3.5 遗传算法实现所需的步骤 15 3.6 本章小结 16 第四章 外卖路线优化算法设计与实现 17 4.1 问题描述与分析 17 4.1.1 问题描述 . 17 4.1.2 选择条件分析 . 17 4.1.3 约束条件分析 . 18 4.2 模型建立 18 4.3 设计算法 19 4.4 仿真案例 21 4.4.1 一般情况下的外卖路线规划 . 21 4.4.2 拥堵情况下的外卖路线问题 . 25 4.5 本章小结 27 结束语 28 致谢 29 参考文献 30 南京邮电大学 2017 届本科生毕业设计（论文） 1 第一章 绪论 1.1 研究的背景和意义 据调研数据显示：我国 2016 年外卖市场交易量达到 1662.4 亿元，2017 年预 计交易量将达到 2045.6 亿元 1。从图 1.1 中可以看出，近几年来，我国外卖市场 交易量逐年上升，外卖市场呈上升趋势。但是从增长率的走势来看，我国的外卖 市场已经越发的趋于稳定，已经从早年的爆发式增长，逐渐转变为平稳增长，商 家、平台、客户都已趋向于稳定，短时间内不会再有外来资本入局，同时一线城 市的市场也已被全面覆盖。现在正是各个第三方平台努力转变的时候，从当初的 红包战术即赔本赚吆喝转变为现在的盈利模式即努力做大做强。 图 1.1 近年来外卖市场发展情况 每个城市的外卖行业发展程度是与城市本身的经济、科技发展息息相关的。 大城市经济发展好、互联网普及程度高，那自然外卖市场规模就相对大；中小城 市因经济发展情况较大城市有所不如，互联网普及程度不高，那相对的外卖市场 就小。现在大城市的外卖市场早已趋于饱和，所以平台就开始把目光放在中小型 城市中，努力提升自己的城市覆盖率。与此同时，互联网餐饮企业在提升城市覆 盖率的同时也在考虑提升自己的服务质量，探索并满足客户的需求。此外，面对 蓬勃发展的外卖市场，资本界更是对外卖餐饮行业十分看好，2015 年中国各大外 卖平台都陆续获得了投资 2，如表 1.1 所示。 216.8 335.5 502.6 860.8 1250.3 1662.4 2045.6 2413.8 54.80% 49.80% 71.30% 45.20% 33.00% 23.10% 18.00% 0.00% 10.00% 20.00% 30.00% 40.00% 50.00% 60.00% 70.00% 80.00% 0 500 1000 1500 2000 2500 3000 20112012201320142015201620172018 中国外卖市场交易量走势图 市场交易量/亿元增长率 南京邮电大学 2017 届本科生毕业设计（论文） 2 表 1.1 2015 年外卖平台融资情况 融资时间公司名称融资金额投资方 2015年1月 饿了么3.5亿美元 中信产业基金、腾讯、京东、大众点评以及红杉 资本联合投资 2015年1月 零号线3千万美元腾讯领投，红杉资本及戈壁资本跟投 2015年7月 一号外卖3千万人民币领投方为天使投资人薛蛮子、麦涛 2015年8月 百度外卖2.5亿美元 2015年8月 生活半径3亿人民币投资方为阿里巴巴旗下口碑 2015年8月 饿了么6.3亿美元 由中信产业基金、华联股份领投，华人文化产业 基金、歌斐资产等投资方以及腾讯、京东、红杉 资本等跟投 2015年9月 点我吧阿里口碑领投，获创新工场追加投资 2015年10月 风先生1.3千万美金投资方经纬中国，光速安振跟投 2015年11月 一号外卖5.8千万人民币 领投方为乡村基创始人、鑫濠投资李红，跟投方 永丰好友投资、圈子壹号投资等 、 正因为有了如此广阔的市场前景，越来越多的商户加入到了外卖餐饮行业当 中。现在大量的商户通过加入第三方外卖平台来获得收益，他们大多是一些提供 快餐、小吃、汉堡、面食、饮料之类的小店。他们的消费人群主体是白领和学生。 其中学生喜欢点外卖是因为外卖方便，而且有很多口味和种类可供选择，相比于 学校的食堂而言， 食堂的饭菜种类单一， 而且口味也不能满足学生们刁钻的胃口。 而白领们喜欢外卖的原因也不外乎这些。他们工作繁忙，中午的时候没有充足的 时间前往商家店面中进行用餐，而到了晚上，在外打拼的年轻白领们身边一没有 家人，二自己的做饭手艺也不好，更何况有时公司业务繁忙，白领们还要加班加 点的完成自己的工作，所以外卖成了解决他们问题的最好方法。据悉，2015 年中 学生市场份额占比达 30.52%，白领商务市场份额占比达 62.99% 2。可以看出，白 领商务市场将作为我国外卖市场的领头羊继续壮大下去。然而在生活小区中，外 卖市场的发展情况就远不如白领市场的好。那是因为小区中有许多的人已经成家 立业，有了自己的伴侣和后代，他们会更加珍惜自己的家庭，他们喜欢自己去市 场中买菜、做饭，喜欢一家人聚在一起的感觉，喜欢家的温馨感。还有一些中老 年人对外卖的了解还不够，他们几乎不会订购外卖。虽然生活社区的市场份额只 有 6.49%0，但生活社区市场的潜力绝对不止这些。通过发展合适的业务，生活区 外卖市场会成为外卖市场的又一支柱。 而随着外卖餐饮行业的发展，问题也随之而来。从客户的角度来看，送餐慢 是作为消费主体的白领和学生对外卖服务最为直观的感受。从订餐开始，客户便 在期盼着外卖的到达。但是外卖的送餐速度往往不尽如人意，在我们身边经常会 有外卖送迟的现象。原因有以下几种情况：第一，送餐员不熟悉客户地址，停车 向行人和客户打听，耽误了送餐；第二，路况不好导致送餐延误。虽然第三方外 卖平台规定了外卖的送达的时间，但是上有政策，下有对策。外卖员经常会在来 不及送达的时候，先行点击送达，并打电话给客户告知其先行点击了送达，但外 卖将会晚点。客户拿他并没有办法，只能接受。这样子，虽然第三方外卖平台没 南京邮电大学 2017 届本科生毕业设计（论文） 3 有察觉问题，但对客户而言，这样的服务质量是极差的。服务质量的下降会减少 商家的回头客，会大大的降低商家以及第三方平台的用户人数。 从商户的角度来看，送餐问题也是令人颇为头疼的一个问题。因为，第一， 第三方平台只是提供一个平台给商户和客户进行交易，并不负责提供完善的送餐 服务，如果你要求提供专门的配送服务，那配送的成本也是一笔不小的开支；第 二，外卖相对于快递等其他物流行业而言，它的集中性和及时性要求更为严格。 作为消费主体的白领和学生的用餐时间往往相对集中，这就造成了大量订单在一 两个小时内大量涌现，送餐人员处理订单的效率往往又不尽如人意。这就会造成 送餐人员在用餐时间过于忙碌，而在空闲时间他们的订单量又很少，造成劳动力 的局部过剩。而且外卖市场的高峰期与道路上人流的高峰期大体不差多少，中午 随着白领的下班、学生的放学，人流变充斥着整条道路，而往往这时候也是外卖 生意最好的时候，这就会造成道路的拥堵，进一步的降低外卖的送餐效率。 现在商户的送餐方式大体分为两种：一种是商户自行组织人员进行送餐，另 一种是加入第三方平台提供的团队进行统一送餐。自行送餐的商户需要在这一两 个小时内组织大量的人力物力来进行送餐，这会导致配送的成本会大大提高，这 成本又会进一步体现在客户的订单中，无形中提高了外卖的价格，造成客户的流 失。而等待统一配送的商家为了利益最大化往往加入了多个平台，这就造成了送 餐的复杂化。从现在市场的反应来看，统一送餐只是减少的小规模商户的人力， 但并没有提高外卖的送餐效率，也没有对送餐的路径进行优化。 本文根据现在外卖行业的火热程度和外卖配送中存在的问题，从规划路径方 面着手，使用遗传算法对送餐路程进行规划，使得成本降低，可以提高外卖送餐 服务质量，使客户更早的吃到餐点，具有一定的理论和现实意义。 （1）理论意义。外卖行业现在发展的十分火热，各大资本纷纷注资，外卖平 台大量使用红包和减免政策来吸引用户。但是，这样的发展模式令人堪忧，这样 固然可以让客户的人数规模爆增，只有服务质量是维持服务业兴盛的唯一指标。 本文中使用遗传算法规划外卖送餐路线，建立了外卖配送模型，为日后的外卖配 送路线规划的理论和使用打下基础。 （2）现实意义。外卖行业的长远发展是需要依赖新客户的加入和老客户的留 存才能实现。对客户而言，最重要的是饭菜的质量，其次便是外卖送达的时间。 饭菜的质量需要依靠商家自觉与市场的能动性来解决。外卖送达的时间是我们现 在可以调节的最好因素。通过规划路径，使得外卖配送路径的距离减少，从而使 客户早一步的拿到外卖，从而使自己的外卖更具竞争力。这对现在的外卖行业具 有一定的参考意义，对促进外卖行业的良性发展具有一定的现实意义。 1.2 国内外研究现状 国外的外卖市场相对成熟许多，消费观念较国内而言也有所不同。国内的消 费者们大都集中在在外求学的学生和在外打拼的年轻白领，国内的家庭一般都喜 南京邮电大学 2017 届本科生毕业设计（论文） 4 欢自己做饭吃，这也是中国的一个传统。但国外的家庭则不同，他们经常会订外 卖，比如披萨、汉堡，所以外卖在国外的普及率比较高，而在国内市场的基数大。 国外的成功外卖商家事实上可以分成两种 1，一种如 GrubHub、Just-Eat。这 种公司身处的外卖市场已经发育成熟，市场的交易量均已发展到百亿美元以上， 成熟的市场培育出了他们这样巨大规模的外卖商家。时势造英雄，这句话放在外 卖市场上也是行的通的。这些公司踏着互联网发展的浪潮，早早的便将目光放在 外卖市场上。随着公司的发展和时代的进步，逐渐建立和完善自己公司的商业体 系，大力发展技术，从而在外卖市场中建立坚实的竞争壁垒。他们凭借完善的商 业体系和领先同行业的技术，在外卖市场这块巨大的利益蛋糕中占据了很大一部 分。 另一种则如 Delivery Hero 和 FoodPanda。这种公司没有赶上外卖市场最初发 展的大好时光，但英雄也可以造时势，他们没有赶上互联网发展的浪潮，便将眼 光放在一些互联网刚刚发展的国家上，凭借其雄厚的资本力量占据市场。他们占 据新兴市场时，直接复制欧美成熟的外卖市场的模式，避免开拓新市场时多走弯 路。 在欧美国家中，许多家庭都有私人汽车，而他们国家的人工费用普遍较高， 从而使得私人汽车业务与外卖业务的联系日益紧密，逐渐发展出了一种新型的外 卖配送方式：共享型外卖配送。 共享型外卖配送是建立在私人汽车共享业务上的一种新型业务。在 2014 年 7 月，发商机网就整理过一篇关于 10 家美国新兴的餐饮公司的文章。其中，外卖公 司 Doordash 和 Gesoo 均成立于 2013 年 4。 Doordash 4外卖公司位于旧金山，这家公司的运营模式与 Uber（国外一款打 车软件）的模式相类似，通过网络平台使得线上的要求与线下的资源紧密的结合 在一起。Doordash 公司自己并没有专门的配送人员，而是通过手机软件整合配送 人员即私人汽车的车主。车主可以通过手机在客户端上申请成为一名送餐人员， 客户则通过手机或者电脑客户端向服务器发送订单需求。 伴随着中国信息技术的蓬勃发展，互联网产业与人们的衣食住行的联系越来 越来紧密。乘着这股发展的浪潮，我国的网上外卖订餐市场也发展的十分红火。 就现在我国的外卖发展的情况来说，因为外卖发展的繁荣度与城市的经济发展程 度和年轻人群体的多少息息相关，所以我国一二线城市的外卖发展情况较好。现 在， 外卖平台正在深入挖掘一二线城市的潜力， 同时也正在努力向中小城市进军， 开拓新的市场。伴随着市场的开辟，用户的数量将会不断的增长，用户的需求也 会不断的丰富，市场的反应会更好，这是一个良性循环。 目前我国外卖配送分为两种情况 5， 一种是知名连锁企业自行组建配送队伍进 行送餐服务，另一种是小型商家依托于外卖平台组建的配送队伍进行外卖送餐服 务。第一种配送方案中，主要是以肯德基、必胜客、麦当劳等大型连锁企业为主。 南京邮电大学 2017 届本科生毕业设计（论文） 5 它们企业规模大，客户分布广，培养自己的配送队伍，可以变相的提高自己的上 座率，更可以利用此对自己进行宣传，扩大自己的影响力，提高自身的市场覆盖 率。 而在另一种方案中，众多需求配送服务的外卖商家催生了国内众多的外卖平 台中，占据领先优势的是美团外卖、饿了么、百度外卖。三家外卖平台实力对比 分析如下表 1.2 所示。 表 1.2 外卖平台对比分析 饿了么美团外卖百度外卖 成立时间2009年4月2013年11月2014年5月 覆盖城市数量300+300+130+ 平均客单价40+35+45+ 物流配送自营+社会化物流社会化物流百度骑士 重点客户定位白领 学生学生 白领白领 家庭 主要盈利模式 佣金 增值服务 物流 费 竞价排名 广告费 佣金 服务费 竞价排 名 广告费 佣金 服务费 广告费 物流费 竞价排名 领域渗透率47.03%42.78%11.17% 支付方式 微信，支付宝，qq钱 包，到付 微信，银行卡，支付 宝，到付 百度钱包，支付宝， 到付 美团外卖的送餐模式为三位一体 6。在一线城市中，因为外卖市场发育成熟， 客户多，订单多，所以美团通常会自己组织送餐队伍来进行送餐以满足客户与商 户的双重需求；而在二三线城市中，因其市场开发程度低，如果自建团队的话成 本大，得不偿失，所以美团选择与送餐合作伙伴共同开拓送餐市场。百度外卖建 有自己的外卖配送团队百度骑士。其采用服务器指派订单的模式。骑士与商家 处于同一外卖区域中，当该区域中有客户点单时，服务器会按照某种规则指派合 适的外卖送餐员前往送餐，提高送餐效率，减少不必要的团队多余竞争。但是， 在国内的配送体系中，还是经常发生送餐慢，送错餐的情况，这是因为第三方虽 然规定了送达时间，但并没有解决送餐员的问题。送餐员的路线规划通常是自己 决定的，这样送餐效率就是建立在送餐员的经验上，不够稳定。综上所述，外卖 规划问题使用传统运算方法在有限时间内无法得到合适的解，所以外卖问题是一 个 NP（Non-Deterministic Polynomial）问题，使用传统运算方法难以解决，需 要使用智能优化算法解决该问题。所以我认为通过遗传算法完成外卖路线最优化 研究是很有必要的。 赵祯7在文献中提出建立智能云柜来解决送餐问题，立足于当前的科技前沿， 利用无人配送技术来进行送餐服务；深圳市迅享科技有限公司创建了新型的拼单 系统来提高送餐效率 8，即首先第一客户在网上发出拼单申请，写明外卖商家、送 达时间、送达地点等关键词，如若有人想要接受这笔拼单，点击接受，写好信息， 反馈给商家。A. Gupta,C.K.9通过引入通用优化框架来优化路线问题在现实的应用。 我研究的外卖路线规划并不是从交通方式、接单方式进行研究，而是从最基础的 南京邮电大学 2017 届本科生毕业设计（论文） 6 送餐路线上着手，研究生活中最常见拥堵情况下的路线规划。 1.3 主要研究内容和章节安排 本文主要是针对送餐员的送餐路线进行规划，使送餐员可以更好，更快的把 外卖送的客户手中，要完成的研究内容有： 第一点：建立外卖送餐模型：根据现在外卖送餐的实际情况，结合现有约束 条件和假设，建立外卖送餐模型。 第二点：使用遗传算法对外卖送餐路线模型尝试进行解决； 第三点：对外卖送餐路径中道路拥挤情况进行了解，改进外卖模型，并对该 现象提出了解决方案。 论文共分为为四章，组织结构如下： 第一章，分析了当前外卖送餐行业发展的前景以及发展中出现的一些问题， 阐述了国内外外卖巨头在送餐方式的处理方法，最后提出了外卖路线最优化研究 这个课题。 第二章，介绍了优化问题的概况和外卖路线问题的具体情况，具体分析了外 卖路线的特点以及外卖配送的常见要求； 第三章，描述了常见解决优化问题的方法以及我使用的遗传算法的具体情况， 包括其基本思想、特点、解决问题的步骤； 第四章，构建了外卖模型，完成了一般情况下的算法设计和案例仿真和拥堵 情况下的道路规划情况。 南京邮电大学 2017 届本科生毕业设计（论文） 7 第二章 外卖路线优化问题概述 2.1 优化问题概述 优化问题指的是人们在面对问题的多种选择时，从中找到最优的方法用来解 决问题 10。优化问题经常出现在科学研究、工程技术、经济管理等方面中，与我 们的学习、研究、工作息息相关。生活中，人们经常碰到优化问题，例如前往某 地，有多种交通方式可以选择，那具体选择哪种就是一个优化问题。人们最常用 的解决问题的方法有以下三种 11： （1）生活经验法：人们凭借其经验做出判断； 比如针对上述的去往某地的问题，解决时，就会有人说这地方我去过，坐地铁比 公交快，还舒服。 （2）实验分析法：人们可以做实验从理论上比较几种方案的优 劣；该方法在解决上述问题时，可以描述为现在我们中没人去过那，我们可以先 坐地铁和公交试试，实验证明地铁比公交舒服，那我们选择地铁。 （3）模型求解 法：人们对相对应的问题建立数学模型，求解最优解决方案。我们已知地铁和公 交的路程长短和平均时速，分别求出他们所花费的时间，比较他们的大小，选择 交通工具。在生活中，我们常常使用前两种方法解决问题，那是因为我们在生活 中遇到的问题一般是比较小规模的，比较简单的。当我们在遇到较复杂问题时， 这两种方法就不能够很好的解决了，比方说我们这次前往的就不是市区内了，这 次我想要环游中国，中国的每一个省，我都要去 10 个景点游玩，这个问题就比较 复杂，前两种方法不太方便解决，因为前人的经验很少，比较片面，这时候使用 模型求解法就可以很好的解决问题。 所以，在科研中我们通常面对的数据都比较大，比较这三种方法，使用模型 求解法来解决问题更加有效。虽然建立模型时，问题经过了一定的简化，可能会 使结果不一定非常完善 13。但是数学模型是建立在客观数据上的，相比经验判断 法，它的结果更加客观，更加贴近真实情况。而且使用数学模型可以解决大规模 问题，而实验法不行，实验只能解决小规模问题（即实验并不具有一般性，实验 通常是研究人员提出的特例） 。数学模型法还可以结合其他两种方法：人们可以从 实际生活中提取出问题的约束，通过实验来完善建立的数学模型。而随着科技水 平的提高和人们在研究数学上方法的进步，使用建立模型这种方法来解决优化问 题的效果也得到了显著的提高，从而更多的研究人员使用这种方法来解决科研问 题。 近几十年来，由于计算机技术的飞速发展，计算机的运算能力不断提高，各 种最优化问题的研究理论和方法不断的产生和进步，使得最优化研究这个古老的 话题又一次诞生了新的活力，逐渐形成了一个新的学科。至今已出现线性规划、 整数规划、非线性规划、几何规划、动态规划等许多分支。近年来，有着广泛应 用背景的随机规划、网络流、模糊规划等分支也相继出现 10。同时，一些优化算 法如模拟退火算法、遗传算法、人工神经网络、蚁群算法、粒子群优化算法等也 南京邮电大学 2017 届本科生毕业设计（论文） 8 相继发展起来。 2.2 路线优化问题概述 外卖路线最优化问题实际上是旅行商问题（Travelling Salesman Problem，即 TSP 问题） 。TSP 问题的一般形式为：给定一组城市及它们两两之间的距离，求经 过每座城市并返回出发地的最短路线。如图 2.1 所示，该问题可简单描述为：给 定加权图 G，要求在加权图 G 中找出一条累加权最小的回路。TSP 问题是一个 NP 问题。假设城市数目为 n 时，那么就有（n-1） ！条组合的路径数。当城市的数量 不多时，寻找最佳路线显然没有难度，但如果城市的数量规模一旦变大，组合路 径的可能数量则呈指数型增长，呈现出爆炸组合特征。所以人们一致致力于寻找 新的方法来解决 TSP 问题，启发式算法、仿生智能算法应运而生。 图 2.1 TSP 问题示意图 TSP 问题现在已被广泛应用在诸如交通运输、通信、建筑规划、道路规划、电 力规划、农业、水利灌溉等方面。不仅仅在上述生产活动方面，TSP 问题的应用比 较广，TSP 问题的价值更多的体现在科研项目上，例如机器人设计中的路径规划、 数学研究中的地图着色问题、物流配送中的调度问题等。这些问题的规模一般比 较大，使用传统运算方法在规定的时间内求解较为困难，而使用启发式算法求解 则可以获得满意解。TSP 问题可以理解为一个从点集中的某点出发，遍历所有点然 后回到原点的过程。凡是可以抽象为这个过程的问题都可以套用 TSP 问题模型来 求解。 2.3 外卖路线介绍 2.3.1 外卖路线特点 外卖路线，顾名思义就是送餐员配送外卖时，所经过的路线。外卖路类似于 传统的物流配送路线，但是与其相比又有很多细致的区别。相似点是外卖路线与 物流路线的总体上的目标是一致的，都是要求配送员把商品准时送达客户手中。 但是外卖路线相较于物流路线，多出了许多新的要求，造成两者之间有很多的区 南京邮电大学 2017 届本科生毕业设计（论文） 9 别。相比而言，外卖路线比物流路线的要求更加细腻，着眼小处，而物流路线总 是要求着眼大局，要求比较宽泛。在传统的物流路线上，研究人员作出了很多研 究。文献12研究了禁忌搜索算法在物流仓储问题上的应用；文献13研究了华 冠联合公司物流配送路线；文献14研究了中央红连锁超市物流配送路径；文献 15研究了多车型物流模型；文献16研究了在有限燃料情况下加油站的分布对 于车辆路线的影响。 外卖路线与传统物流路线的区别如下： （1）首先外卖送餐路线与传统物流路线最大的区别便在于路径规模上的不同。 外卖路线通常是对一个送餐区域进行送餐活动，而一般来说这个送餐区域大概处 于餐饮店的周围三公里，范围不会太大。范围如果太大的话，会导致配送时间过 长，餐点的质量下降等问题，影响客户的服务体验和商家的声誉。传统物流路线 则截然不同，他们的配送规模相当大，远可以进行跨国运输，规模小的也是进行 市区一级的商品送达。 （2）外卖路线与传统物流路线不仅在路径规模差别很大，而且在运输量上也 有区别。传统物流路线一般是把大量的商品一次性的送到几个固定客户手中。物 流路线上运输的商品数量多，但是商品所需运到的地址较少，所以在物流配送中 单个客户需求量大，相对的客户也比较固定。但是外卖路线则恰恰相反，外卖路 线一般是把大量的外卖食品送到多个客户手中。其配送的外卖商品总量较大，客 户数目较多，当时单个客户的需求量小，每次客户通常都不一样。所以一般而言， 物流路线可以一次规划，多次使用因为它的客户和进货源相对固定，而外卖路线 截然不同，其路线每次使用都需要重新规划，于是外卖路线需要使用运算较为迅 速的优化算法来计算路线。 （3）而规模的不同带来的另一个区别就是交通方式的不同。现在外卖送餐员 大都使用电动自行车进行外卖食品的配送。使用电动自行车可以更方便的到达客 户所指定的送餐地点。传统物流路线上，运输的商品不仅数量大，而且地域跨度 广，所以配送员大多驾驶的是货车。这两者的区别主要是由运输的商品属性不同 所引起的。 （4）规模不同，交通方式的不同，随之而来的是配送的时间也不同。外卖是 一种生命力十分短暂的商品，从商家到客户，都希望外卖送达时间越早越好。外 卖路线的送达时间是以小时为单位的，而传统的物流路线的配送时间是以天、周 甚至以月为单位的。这是因为外卖路线上运输的商品是客户所点的餐点。客户的 目的是通过选择外卖服务解决自己的饮食问题，所以一般都要求在一小时内送达。 而传统的物流路线上运输的大多是企业生产所使用的原材料、商店里所将要出售 的商品以及特殊时期一些物资的配送。又因为其路径距离相对于外卖路线而言要 远的多，所以通常来说，传统物流路线所花费的时间要比外面路线多。 （5）外卖路线与传统物流路线的货物损耗要求不一样。在外卖路线中，货物 南京邮电大学 2017 届本科生毕业设计（论文） 10 即外卖食品是不能够出现损耗的。通常客户点单是为了解决自己的用餐问题，所 以他只点自己那一份。那么一旦出现损耗，对客户而言，这不是损耗，而是配送 失败，这会极大的影响到商家在客户中的声誉。而传统物流则不同，一方面客户 会主动的多订购商品以满足自己的生产活动需要，因为客户在使用原材料进行生 产活动时，就会有所损耗；另一方面，运输的地域跨度大，运输时间长，这不可 避免的会对货物有所损耗。 （6）外卖配送路线与物流配送的道路情况不一样。传统的物流配送中，配送 员大都行驶在高速公路上，行驶时间也往往与上下班高峰期错开。而且因为驾驶 的是货车，所以也不受一般刮风下雨天气的影响。但是外卖送餐则不同，外卖配 送的高峰期往往就是人们下班的高峰期，行驶的道路也不是高速，而是城市间的 主干道和小弄堂，路况较物流配送复杂的多。所以，我们在制定外卖路线优化方 案的时候，道路状况是我们必须要考虑到的因素。 综上所述，外卖路线的要求与物流路线相比，时间维度跨度小、空间维度跨 度小、订单频繁、客户流动性强、客户规模大。我们在设计外卖路线模型时需要 考虑到上述的外卖路线的特征。 2.3.2 外卖路线基本假设 鉴于一些客观因素，如天气状况（降雪、降雨） ，某必经路段的突发性交通事 故等， 不能人为控制 14， 则列出下述基本假设,让我们的实验减少外部因素的影响, 让我们重点研究本文中所研究的内容，即这些因素不在本文的研究范围内。 （1）假设商家商店中外卖菜品齐全，不存在餐点短缺的问题。也就是说只要 是客户所订购的外卖，我们商店里都有，不会影响送餐员进行送餐，以至于从这 点上影响客户的感受。 （2）假设每一个送餐员都至少可以向一个客户送餐，即每个客户所需的送餐 量都少于送餐车的最大送餐量 14，不会发生客户点大量餐点的情况，确实这种情 况生活中我们也很少遇到。 （3）在此假设送餐车辆型号统一，送餐车辆的载重量也固定，运输费用与行 驶路程线性相关；根据各个客户的送餐需求分配车辆 14，使同一车辆回路可以服 务数量不等的客户；并且一个客户只能接受一个外卖员送餐即送餐员之间可以进 行外卖送餐的接力但最后外卖送到客户手中时只有一个送餐员。 （4）在单个送餐员的送餐线路上送餐的所有客户所需的外卖的总量不得超过 对应送餐车辆的最大载重量，也就是说外卖员不能为了多送单，就使送餐车辆超 载，影响外卖质量。 （5）由于车辆在行进过程中的速度在不可控范围内，则将行驶速度规定成某 固定值，这样可以方便的计算路线的规划效果 14。 （6）由于城市道路情况复杂，通常情况下，两地之间有多种路径可供选择， 但在本文中，不考虑其他情况，只考虑两点之间最近的一条路线即为送餐员选择 南京邮电大学 2017 届本科生毕业设计（论文） 11 的路径。 2.4 本章小结 在这一章中，我介绍了优化问题的起源，阐述了 TSP 问题的情况，着重描述 了外卖路线的特征，与传统配送路线的区别，同时也考虑到建立外卖模型时的所 需假设，为下一步算法的实现与仿真打下基础。 南京邮电大学 2017 届本科生毕业设计（论文） 12 第三章 遗传算法研究 经过多年的发展，人们对于解决路线规划问题的思路大致可以分成以下两种 情况：构造式优化算法和启发式优化算法。构造式优化算法中有最近邻算法、贪 心算法、插入算法、割平面法、分支切割法等，启发式算法中有爬山算法、模拟 退火算法、链式局部最优化、蚁群算法、粒子群算法、遗传算法等。在本文中我 们主要研究启发式优化算法中的遗传算法。启发式优化算法便是指研究人员借鉴 生活中的直观感受或者尝试经验去求解优化问题的算法。通常情况下，启发式算 法会在人们可以接受的范围内，给出带求解问题的一个可行解。该可行解不一定 是实际上的最优解，而且该解与最优解的误差也同样的不一定可以预测。自 20 世 纪 90 年代以来，许多研究人员把寻求解决方案的目光放在了自然界上，通过观察 自然界的一些现象和生活中的行为，研究人员提出了许多基于人工智能的启发式 算法。遗传算法就是其中一种模仿生物进化过程的搜索算法。其主要包含了编码 过程、设定初始种群、适应度函数、遗传算子、交叉变异以及控制参数设置等环 节；遗传算法的计算能力确实比较强 16，并且使用起来特别便利，促使其在现代 智能算法中占据了重要的位置。文献17使用遗传算法对微网能量进行管理，卓 有成效；文献18利用遗传算法对云计算环境下任务调度进行了优化；文献19 利用遗传算法对车间中的作业与机器之间的调度进行优化，效果明显；文献20 则对项目中多个模式之间的调度进行了研究。综上所述，遗传算法对于优化问题 的求解是有效的。 3.1 遗传算法基本思想 遗传算法是 Holland J H 21于 1975 年提出的。其算法的大致思想如下：自然 界中，在一个固定的时间内，草原上生活着一群“羊” ，其中有一些“羊”比另外 的一些“羊”跑的更快、脑子更加灵活，所以理所应当的这群“羊”在面对捕食 者的捕猎时获得更高的生存机会， 比别的“羊”有更多的繁殖机会。 当然慢 “羊” 、 蠢“羊”也有机会活下来， 也有机会繁殖出跑的快的“羊”、 更加机智的“羊”。 到最后，能够生存下来的“羊”总是跑的更快、脑子更加灵活。这就是自然界中 物竞天择的物种遗传规律。物竞天择的基本观点就是：生物进化是以种群为基本 单位的，而具体的细节则是每一个生物的基因决定的。研究人员针对这种现象加 以利用，于是便产生了一种智能优化算法遗传算法。遗传算法就是利用了自然 中物种遗传的规律，对问题进行解决的方法。在遗传算法中，一群“羊”代表着 种群，每一只“羊”代表着算法中的每一个解，每一只“羊”的跑的快慢、脑子 灵活与否代表着解中的单个性状，即基因。 3.2 遗传算法的优缺点 遗传算法是根据自然界中生物的物竞天择规律来解决问题的。所以遗传算法 南京邮电大学 2017 届本科生毕业设计（论文） 13 的优缺点也与生物界的特点相类似。 3.2.1 遗传算法的优点 遗传算法的优点有以下几点： （1）遗传算法的理论基础是建立在自然界生物的传承规律上的。自然界中物 竞天择规律适用于大多数物种，所以遗传算法的适用性很广。遗传算法可以套用 在几乎任何的问题模型中。 （2）遗传算法的运行过程十分简单。因为遗传算法在运行过程中只使用适应 度函数作为评价指标， 所以我们的观察指标也就是这一个， 不需要观察其他指标， 相对于其他算法，所以遗传算法的运行过程十分简单。 （3）遗传算法运算的基本单位是物种中的种群。而种群中有包含了各种各样 的解，所以遗传算法搜索解是从种群中出发的，并不是从单个解的角度求解，所 以遗传算法具有并行性，可以同时获得多个较优解。 （4）遗传算法是建立在自然界基础上的，而现行的许多智能算法都是建立在 自然界中生物的具体现状上的，所以遗传算法与现行的许多智能算法结合度较好， 遗传算法的可扩展性较好。 3.2.2 遗传算法的缺点 遗传算法的缺点有以下两点： （1）遗传算法中评价指标是只有一个，十分简单，但是其中的具体参数设置 较为复杂，参数具体有变异概率、交叉概率。其中变异概率设置十分关键，这些 参数的设置关系着算法的具体性能。所以遗传算法的参数设置较为复杂，我们在 设置时需要考虑到具体的问题，然后对参数进行专门的设置。 （2）遗传算法参照自然界中生物传承情况进行运算。算法在运行的时候，会 导致有一批较好的解提前占领种群，造成种群的构成单一。这种情况放在“羊群” 中，就是近亲繁殖，会造成种群的整体质量下降。所以遗传算法在运行的过程中 存在着“早熟”现象。 3.3 遗传算法的参数设置 在运行遗传算法时，遗传算法参数的设置十分重要22，如果参数设置的不合 适，会造成遗传算法不收敛或者是过早的收敛。所以一般我们在设置参数时会参 考以下原则： 3.3.1 种群规模设置 （1）种群的规模使我们在遗传算法中设置的第一个值，这个值代表着具体问 题的解集的规模23。 当我们把规模设置的过小时， 遗传算法中解集的规模就较小。 而解集的规模较小就会造成解的多样性的缺失，造成遗传算法运行过程中的近亲 繁殖，导致算法的解的性能下降，过早收敛。而如果种群的规模如果设置的太大， 南京邮电大学 2017 届本科生毕业设计（论文） 14 则会破坏物竞天择这个物种传承原则，造成种群中良莠不齐。这种情况会浪费大 量的计算资源，严重的情况下会导致算法无法收敛，给不出一个合适的解。所以 本文中的种群规模是 100。 3.3.2 变异概率设置 （2）变异概率24是我们在设置参数时需要着重考虑到的值。这个值代表着种 群中的解发生异变的可能性。如果设置的太低，那就是让遗传算法中的解发生异 变的可能性大大降低，会导致种群如同一潭死水，没有新的基因出现，必然会导 致种群的过早收敛。而如果变异概率是指的太大，那种群中的良性基因的保留可 能会大大降低，会导致算法的解的波动性太大，无法收敛到一个合适的解。本文 把变异概率的值设置为 0.2。 3.3.3 迭代次数设置 （3）迭代次数25代表着算法的重复运行次数，在自然界中代表的是一个物种 的生存时间。如果迭代次数太小，那代表着这个物种的生存时间非常短，物种是 没有办法在很短的时间内进化的非常完美的，会造成算法的性能下降。而如果迭 代次数太大，会导致算法在后半段时间内做无用功，浪费大量的计算机资源。所 以本文选择的迭代次数是 1000 次。 3.4 遗传算法的专有名词 基因：基因在生物中指的就是具体的表现现状，在算法中就代表了解的可能 情况。物种的丰富性指的就是物种中的基因的多样性，在遗传算法中，正是有解 的多样性才能够通过一系列的运算，得出最优解。在本文中，我们采用的是自然 数序号编码，则编码中的数字序号段就是算法中的基因。在遗传算法中，基因是 最基本的单位。在计算过程中，基因的缺失便代表着算法的早熟，文献26提出 了一种预防基因缺失的策略基因补偿 染色体：染色体由基因组构成。评价一个生物的性状不能只看他的单个基因 段，单个基因并不能够起到决定性因素。自然界中， “羊”具有不同的体态特征， 那是因为他们具有不同的基因段组合，即他们的染色体不同。所以评价“羊”的 性状需要通过检验整个染色体来完成。算法中不同的染色体代表研究时产生的各 种各样的解。因此可以通过遗传和变异获得适应度不同的解。同时针对不同的寻 优问题，就要对解集进行不同精度的编码 27。 种群： 种群指的就是待求解问题的解集。 种群中包含了该问题的已知可能解， 算法就是在解集中寻找最优解，并不断的生成新解的过程。所以种群指的就是在 算法运行过程中产生的解集。 基因、 染色体与种群的关系示意图如下图 3.1 所示。 文献28提出了种群的跃迁现象，使染色体在低适应度函数中加速变异的方法解 决早熟问题。 南京邮电大学 2017 届本科生毕业设计（论文） 15 适应度：适应度在算法中指的就是解对于问题的回答的合适程度。在自然界 中，生物对于环境的适应情况就是适应度。自然界中，决定一个种群能否生存下 来的，恰恰就是适应度。一个种群对环境的适应程度高，那种群的传承下来的可 能性就越高。 种群 染色体4 基因 基因基因 基因 染色体3 基因 基因基因 基因 染色体1 基因 基因基因 基因 染色体2 基因 基因基因 基因 图 3.1 基因、染色体与种群示意图 3.5 遗传算法实现所需的步骤 遗传算法的实现步骤如下所示 （1）编码：遗传算法中进行比较变化并不是问题中某个个体，而是一个一个 的解（即问题的解决方法） ，就是这些解组成了种群。所以我们要对这些解进行编 号，这样既方便研究人员看出解的构成，也方便遗传算法对解的性能的评估。这 种编号的过程就叫做编码。 （2）初始化种群：种群是遗传算法的基础。正如自然界中种群产生的一样， 遗传算法中我们使用随机方法来生成一批解构成种群。具体过程如下，首先我们 使用随机的方法生成固定数量的解的个体，接着算法参考问题中的前提条件，对 产生的染色体进行审核，将符合要求的染色体加入到初始种群中，如果初始种群 的数量未达到要求，那么重复上一步骤，一直到我们获取到相应数量的解，组成 初始种群。 （3）编写适应度函数：每一个染色体所代表的解对问题的解答合适与否称为 适应度。适应度函数就是用来衡量每一条染色体合适与否的方法。通过适应度函 数，我们可以将染色体的优劣势直观的展示出来。又因为遗传算法运算时基本不 考虑外部因素，通常情况下仅仅以适应度函数为唯一评估指标，所以适应度函数 的选择对于遗传算法的影响很大。一般我们都将问题的目标函数作为最后的适应 南京邮电大学 2017 届本科生毕业设计（论文） 16 度函数，但是适应度函数的值往往又会与选择的概率相挂钩，所以一般我们又都 会将函数做一些处理用来保证适应