基于改进遗传算法的校园外卖配送路径规划

2021-07-05范立南吕鹏

物流科技 2021年1期

范立南吕鹏

摘要：随着互联网和智能手机的普及，校园外卖也取得了迅速的发展，而如何对校园内各个外卖配送地点进行配送路径的规划是当前校园外卖存在的一大问题。文章选取了沈阳大学北校区的24个外卖配送地点，利用遗传算法和TSP问题的相关理论，通过对比传统的遗传算法与蚁群算法在实验中的优劣，采用改进的自适应遗传蚁群混合算法，对沈阳大学校园内外卖配送路线进行了合理的规划，并通过MATLAB软件对路径做了仿真实验。试验结果表明，文章中算法能有效缩短校园外卖配送路径长度，提供较为合理的优化路径，能够有效提升外卖员的配送效率，具有一定的应用价值。

关键词：校园外卖;遗传算法;TSP问题;蚁群算法

中图分类号：U116 文献标识码：A

Abstract： With the popularity of the Internet and smartphones， campus takeaways have also achieved rapid development， and how to plan the distribution routes of various takeaway locations on campus is a major problem in campus takeaways. This paper selects 24 take-out delivery locations in the north campus of Shenyang University， uses genetic algorithm and related theories of TSP problem， and compared the advantages and disadvantages of traditional genetic algorithm and ant colony algorithm in the experiment， and adopted an improved adaptive genetic ant colony hybrid algorithm， reasonable planning of the take-out delivery route on the campus of Shenyang University， MATLAB software conducts simulation experiments on the path. The test results show that the algorithm can effectively shorten the length of campus takeaway delivery routes， provide a more reasonable optimized route， and can effectively improve the delivery efficiency of takeaways. It has certain application value.

Key words： campus take-out; genetic algorithm; TSP problem; colony algorithm

0 引言

作為大学生群体聚集度高且消费水平强的大学校园，已经成为第三方平台外卖配送的主要区域，而在校园内错综复杂的配送线路是外卖员进行配送需要常常考虑的问题[1]。减少外卖员的配送距离能有效提高外卖员的工作效率并降低配送成本，而外卖配送实际上就是TSP问题[2]。王荃菲[3]基于城市内的复杂道路交通流量对外卖配送寻优路径问题展开了研究。马江涛[4]针对医药产品的物流配送路径采用遗传算法进行了路径寻优。郭丰林[5]针对景区旅游路径规划问题，将所要前往的旅游景点网络抽象成TSP问题，通过传统的遗传算法实现对旅游路径的规划。徐坤[6]选择物流快递配送路线的寻优问题作为研究案例，把配送问题抽象成求解车辆路径规划模型，运用蚁群算法求解该问题并对配送路径进行优化，获得了较好的配送路径。马骏[7]针对旅行商问题，基于遗传算法并通过MATLAB软件编写的程序，得到了较好的优化结果。

本文正是针对校园外卖配送路径展开研究，将沈阳大学北校区的多个地点构成的外卖配送目的地网络作为研究对象，将配送路径规划问题抽象成旅行商问题，利用传统的遗传算法与蚁群算法对此类问题进行求解及讨论，并通过遗传算法的相关设计及改进，借助MATLAB软件对校园内外卖的配送路径进行仿真实验获取最优配送路径，从而实现对校园内外卖配送路径的规划。

1 TSP问题与传统算法

1.1 TSP问题描述

TSP问题可以简单的理解为：一个人想要去往n个目标地点，他需要挑选一条将要出发的路线，而路线的挑选必须严格遵守任一目标地点只能寻历一次的规则，寻历结束后最终要回到刚开始出发的地点。路线的选择所要达到的目标是要求使得行走路线的总距离为所有路线之中的最小值。它是一个复杂程度高且密集的非确定性问题，随着此类问题规模的不断增大，对TSP问题进行求解，在近些年的研究中，国内外一些优秀学者运用的算法主要包括遗传算法[8]、模拟退火算法[9]、蚁群算法[10]、禁忌搜索算法[11]、粒子群算法[12]等。

1.2 遗传算法的基本原理

遗传算法是一种随机检索方法，它沿用了生物世界的进化定律（适者生存，优胜劣汰）。它的主要特点是可以直接对种群空间中的多个解进行搜索，对函数的求导及其连续性的判定没有约束，具有良好的鲁棒性和更全面的全局搜索寻优能力[13]。使用遗传算法来处理寻优问题时，过程中每个可能出现的解决方案都可以被编码成一个“染色体”，也就是一个个体，而多个个体相互之间组成了一个群组（所有可能的解决方案）。因此，遗传算法可以看成多个可能出现的解决方案所构成的一个群组从始到末的演化过程。遗传算法主要过程及流程图如图1所示。

1.3 蚁群算法的基本原理

蚁群算法最开始是根据对蚂蚁种群的观察，分析蚂蚁种群行为信息特点，从中得到启发而设计的算法。在蚁群整个的移动路径中，它们会在其经过的路径上释放仅适用于蚁群之间信息共享和通信的信息素。在蚁群移动过程中，它们能够察觉到释放的物质并以此来追踪这一物质，在后面的移动中，继续产生信息素。一条道路上的信息素踪迹越密，其他蚂蚁沿着该路径行进的可能性就越高，因此该路径上的信息素踪迹将得到加强。蚂蚁种群利用蚁群个体之间的间接信息沟通渠道来达到协同遍历搜索最短路径的目的。蚁群算法这种启发式算法的出现，解决了组合爆炸的问题，其可以在合理的时间范围内找到可接受的最优解[14]。

2 算法设计

2.1 问题描述

本文选取了沈阳大学北校区24个外卖配送地点，依次进行编号为1至24号。对外卖配送地点坐标的选取，本文则通过百度地图生成校园内各个地点的经纬度坐标，由于在地图上各点的经纬度相近，为了更加直观的显示仿真运算结果，对经纬度进行如下处理：（a）只保留经度的小数点后的3、4位生成十位数字坐标;（b）只保留纬度的小数点后的2、3、4位生成百位数字坐标。如1号教学楼的经纬度坐标为（123.464988，41.830611），本文选取坐标为（49，306）。设定完毕的外卖配送地点坐标，如表1所示。

百度地图上外卖配送地点的地址如图2所示。

经上述操作后，本文研究的校园外卖配送的路径规划问题可表示为以沈阳大学北校区的24个配送地点为研究对象，设置1号教学楼为出发地点，求历经其余23个配送地点后，最后回到1号教学楼的一条最短路径的TSP类规划问题。

2.2 遗传算法实现

（1）顺序式编码。在遗传算法的编码过程中，通常使用二进制作为编码方式，但在本文求解最优配送路径问题时，采用的是按节点顺序进行编码的编码方式。例如，对于遍历7个城市的一条旅行路径5-4-2-6-1-3-7可简单表示為向量5426137，表示从城市5出发依次经历城市4，2，6，1，3，7然后返回城市5的一条路径。

（2）初始化种群。设定遗传进化的代数计数器t=0，进化的最大代数为T，并随机产生一定数量的染色体（个体），从所有的个体集中选择出M个个体当作初始种群P0。

（3）适应度函数设计。TSP的目标是路径总长度为最短，在进行选择时适应度值越大则被遗传到下一代的概率越大，为使适应度值最大，故采用路径总长度的倒数值作为TSP的适应度值：

fx= （1）

其中：

disV=dV，V+dV，V （2）

（4）选择运算。遗传选择的目的是对于适应度较大的个体能够有机会直接遗传到下一代或者利用交叉配对的形式生成全新的个体再遗传到下一代。本文采用的是锦标赛选择的方法，即从当代种群中随机选择一定数量的个体，并将所有个体中适应性最强的个体遗传给下一代群体[15]。在本文中，从父代种群中随机选择4个路径个体，通过比较它们各自的适应度值，挑选出当中适应度值最大的一个个体进化到下一代，种群规模popsize=300，也就是说选择运算重复300次，最终得到新一代的种群。

（5）交叉操作。遗传交叉操作中尤为重要的就是交叉算子的设计。本文采用次序杂交OX来设计交叉算子，从父代A中随机挑选任一个编码片段，在子代B的对应位置处插入，而子代B的其他位置由父代A中的编码（去除从父代A中已经选取的编码）按顺序填充。子代B也采用相同的形式获取。求解过程如图3所示。

（6）变异操作。因为TSP问题的限定是旅行路径中的每个地点只能寻访一次，故不能采用传统遗传算法中常用的二进制编码的变异操作方法，不能由简单变量通过翻转操作来实现变异。本文中对种群进行变异操作时采用的是染色体两点交换变异算子，将外卖配送地点的编码序列作为父代染色体，从中随机抽取两个地点作为发生交换变异的对象，然后将这两个地点的位置进行交换，通过交换变异可以得到新一代的染色体[16]，这样就完成了个体的遗传变异操作。

（7）终止条件判断。当t=T时，则将进化过程中产生的适应度值最大的个体当作遗传寻优结果输出，停止计算过程。

2.3 蚁群算法实现

采用基于信息素的蚁周模型处理TSP问题的传统蚁群算法的操作步骤为：

（1）初始化蚁群各项基本参数以及各条配送路径上的信息素，设置蚂蚁的种群数量为m，n表示为校园内配送地点的数量，每一只蚂蚁随机挑选n个校园内配送地点中的任一配送地点作为出发地。

（2）往复迭代。在每一次的路径循环中，k只蚂蚁根据每条配送路径上的信息素量来判断其接下来的移动方向。使用禁忌表的记录形式来记录当前k只蚂蚁所遍历过的校园内的配送地点。随着蚂蚁种群的不断搜索，蚂蚁种群会依照每条配送路径上的信息素量跟当前配送路径上滞留的启发信息来求解当前状态转移概率。pt表示的是在t时刻，蚂蚁k从校园内的配送地点i移动到下一阶段所要前往的配送地点j的状态转移概率[17]：

P= （3）

其中：allowed=C-tabuk=1，2，…，m用来代表蚂蚁k下一阶段所被允许挑选移动的配送地点。α是一种信息启发式因子，代表着移动路径的相对权重，体现了蚁群在其移动路径上所积攒的信息对在蚁群转移时所起到的作用。α通常取值为0，5。β是一种期望值启发式因子，代表着路径能见度的相对权重，体现了蚁群在其移动路径上启发信息为蚁群挑选下一阶段路径时所起到的作用。β通常取值范围为0，5。

τt表示t时刻路径i，j上信息素的强度，i表示为从校园内出发的配送地点，j表示为所要到达的下一个配送地点。

ηt表示启发函数，通常取值为。d表示经过路径i，j的距离。

（3）求解每只蚂蚁遍历过的所有校园内配送地点的路径长度，设定蚂蚁的数量为k，而配送路径长度用L来表示，并保存当前的最短路径。

（4）更新信息素。利用式（4）更新配送路径上的信息素，其中，ρ表示移动路径的持久性，即配送路径上信息素的衰减度，1-ρ表示消失程度。经过n个时刻，蚂蚁完成一次遍历循环，各配送路径上的信息素按照式（5）进行调整[18]。

τt+n=1-ρτt+Δτt+n （4）

Δτt+n=Δτt+n （5）

其中：Δτt+n代表的是當前遍历中路径i，j上的信息素的增量，Δτt+n代表的是第k只蚂蚁在当前遍历中释放在路径i，j上的信息素，其计算方式如式（6）所示。

Δτt+n= （6）

（5）对蚂蚁种群的迭代次数进行判断看其是否满足迭代终止条件，通常当蚂蚁种群迭代次数达到最大即判定为终止条件，若满足条件则跳转到下面步骤（6），反之跳转到上述步骤（2）。

（6）输出当代最优路径。

2.4 算法改进

本文将传统的遗传算法与蚁群算法进行融合，将蚁群算法遍历得到的寻优路径结果当作遗传算法的种群初始值，使得遗传算法的寻优迭代次数大大降低，同时引入自适应交叉算子及变异算子对交叉、变异操作进行改进，使得遗传算法的收敛速度得以大幅提高。与单一的遗传算法和蚁群算法相比，改进后的算法从整体上提高了算法的执行效率。

本文在遗传算法的基础上，通过构建一个指标来对种群的收敛程度进行评价，选取f-作为种群收敛程度的指标。在遗传算法中，若种群收敛程度趋于相同，则该算法可以收敛于全局最优解，也可以收敛于局部最优解，此时f-的值将减小，所以同时应该增加遗传操作的交叉概率p和变异概率p，扩大种群范围及多样性，以便种群能够不局限于局部最优的区域，并可以检索其他的区域。

在任一代的种群中，任何一个个体其对应的p、p都是不同的，为了尽可能地保留较好的个体，此时p、p应该较小，差的个体应该尽可能地进行交叉变异而产生新的个体，此时的p、p应该足够大。所以p、p的计算方法与f-以及每个个体的适应度值都有关。故提出下式计算方法：

p=kf-f/f-， k≤1 （7）

p=kf-f/f-， k≤1 （8）

其中：为当代所有个体适应度值的平均值，f为要即将变异的当代个体的适应度值。

对于适应度值最大的个体，p、p的值应该为零，即最优的个体应该被保留下来，当个体的适应度值在种群平均适应度值以下的时候，根据上面的公式，p、p的值可能会大于1，所以需要进行如下处理：

p= （9）

p= （10）

其中：k，k，k，k≤1。

将改进后得到的自适应交叉算子和变异算子引入到蚁群算法与遗传算法融合后的交叉及变异操作中，直至迭代结束。

改进后的自适应遗传蚁群混合算法求解本文对象的计算流程如下：（1）配送地点信息及蚁群算法的参数初始化。（2）初始化蚂蚁位置，將m只蚂蚁随机分配到n个配送地点中。（3）根据式（2）计算蚂蚁k的当前状态移动概率，挑选下一阶段所要到达的配送地点。（4）将新加入移动路线的配送地点转移到蚂蚁k的禁忌表中，对禁忌表进行更新。（5）重复步骤（3）、（4），分别求出每一只蚂蚁的一次遍历路径。（6）经步骤（1）到（5）处理获得的m只蚂蚁的所有遍历路径当作遗传算法的初始种群，初始化遗传算法参数。此时种群的大小popsize=m，根据自适应交叉算子与变异算子来决定交叉概率p及变异概率

p，以及最大迭代次数maxGEN的值。（7）对初始种群进行编码，将蚁群算法得到的配送地点按照访问顺序依次排列组成编码。（8）确定遗传种群适应度函数，按照TSP理论重新计算种群中每个个体的适应度值fx。（9）选择操作。根据式（8）计算得到的适应度值，按照适应度函数值的大小通过轮盘赌的方式挑选种群下一代的染色体。（10）执行交叉算子，采用前述自适应交叉算子，生成新的子代个体。（11）执行变异算子，利用自适应变异算子得到新的个体。（12）对遗传算法进行终止条件判断。如果i>maxGEN，则结束循环，对每次循环得到的最短路径进行比较，得到算法的最终解即最优路径。

3 实验结果分析

3.1 实验参数选择

在本文中，对传统的遗传算法进行运行参数的选择：种群规模popsize=300，交叉概率和变异概率分别取p=0.95和p

=0.33，最大迭代次数maxGEN=500;蚁群参数包括蚁群最大迭代代数iter_max=100，蚂蚁种群个数m=30，信息素蒸发系数ρ

=0.8，轨迹的重要性α=1，能见度的重要性β=5，迭代计数器nC=1。

3.2 遗传算法与蚁群算法效果测试

根据以上针对遗传算法与蚁群算法运行参数的设定，借助MATLAB软件对校园内的外卖配送路线进行仿真实验，通过对比传统的遗传算法与蚁群算法，得到的优化配送结果如图4和图5所示。图4中横纵坐标分别代表的是处于遗传算法与蚁群算法中经处理变换后得到的校园内外卖配送地点的经纬度坐标。

图5中横坐标表示的是遗传算法的种群代数以及蚁群算法的迭代次数，纵坐标表示的是两种算法所搜索计算的校园内外卖配送路线的最短路径长度。由图5所见，蚁群算法的收敛性明显快于遗传算法，遗传算法虽收敛速度慢，但搜寻到的外卖配送的最短路径长度要优于蚁群算法。

3.3 改进算法效果测试

经遗传算法与蚁群算法融合改进后，引入自适应交叉算子及变异算子，能够以较快的速度提高每一代种群的整体质量，算法的寻优性能得到了快速改善，出现最优解的代数明显缩短。改进算法后得到的优化配送结果如图6和图7所示。迭代次数52，优化路径长度223.60，最优配送路径为：1-2-7-6-8-10-15-14-11-12-13-21-17-20-16-24-23-22-19-18-9-5-4-3-1。

利用本文的三种算法对校园内外卖配送路径规划问题数据进行仿真求解，得到的实验对比结果如表2所示。

通过实验对比结果发现，传统的蚁群算法尽管收敛速度快，但是容易陷入局部最优，无法得到较好的全局优化结果，而传统的遗传算法虽然具有较好的全局寻优路径长度，但收敛速度过慢，而改进后的自适应遗传蚁群混合算法，算法的收敛速度明显提高，大大降低了寻优路径长度，在第52代就找到最優路径长度223.60，因此，改进后的算法在搜索效率跟寻优能力上都能够有较好的效果。

4 总结与展望

本文基于改进的自适应遗传蚁群混合算法来求解校园外卖配送类的TSP问题，有效地解决了校园内外卖配送的线路规划问题，具有较好的应用价值。但本研究结果仍存在许多尚待改进的地方，比如交叉概率、变异概率以及种群规模大小的选取都会影响遗传算法得出的路径规划结果，而且考虑校园内行人行走的不规范性、外卖配送车辆的行驶速度、配送车辆的装载空间等因素也可以影响到路径规划的结果。此外求解TSP问题的相关算法还有很多，将遗传算法和其他算法相互结合从而求解出更加优化的结果，是有待进一步研究的内容。

参考文献：

[1] 秦正雨. 高校校园外卖第三方物流配送问题研究[J]. 商业故事，2016（26）：98-99.

[2] 程荣. 遗传算法求解旅行商问题[J]. 科技风，2017，16（37）：40-51.

[3] 王荃菲. 快餐外卖配送路径方案研究[D]. 北京：北京交通大学（硕士学位论文），2017.

[4] 马江涛. 基于遗传算法的医药配送路径规划[J]. 电脑知识与技术，2010，6（11）：2717-2718.

[5] 郭丰林. 基于遗传算法的旅游线路规划研究[J]. 现代营销（经营版），2019（1）：134.

[6] 徐坤. 基于改进蚁群算法的小区快递配送路径规划研究[D]. 乌鲁木齐：新疆大学（硕士学位论文），2019.

[7] 马骏. 遗传算法TSP的matlab求解分析[J]. 科技视界，2018（16）：37-38.

[8] 赵铁军，罗羽枭. 基于改进自适应遗传算法的点焊机器人TSP路径规划[J]. 机械工程师，2019（10）：7-9.

[9] 汪强. 基于模拟退火算法的超市物流配送路径优化研究[J]. 集美大学航海学院，2019，27（3）：39-41.

[10] 熊沂铖，王栋. 基于蚁群算法的车辆路径问题研究[J]. 信息技术，2019，43（7）：15-17.

[11] 肖驰. 禁忌搜索求解TSP问题[J]. 福建电脑，2011（9）：110-111.