【《末端即时配送路径优化算法选择的案例分析》3200字】

末端即时配送路径优化算法选择的案例分析目录TOC\o"1-3"\h\u18420末端即时配送路径优化算法选择的案例分析 1195201末端即时配送路径优化算法选择 1257951.1路径优化算法的选择 1312201.2遗传算法的关键操作 2290251.2.1编码 2114051.2.2种群初始化 28621.2.3遗传操作 2245381.2.4终止条件 3311782实例分析 4末端即时配送路径优化算法选择1.1路径优化算法的选择随着算法的不断完善与改进，路径优化问题的求解算法主要有精确算法和启发式算法，其中精确算法是指利用数学技术来求解最优解的方法，而启发式算法是从一初始解出发对当前解不断进行局部骚扰然后进行搜索评价寻找相对最优解的方法。由于精确算法对于数据规模的要求以及运算限制，针对复杂程度较高的研究问题和模型的求解，启发式算法具有较强的优势。经常用来求解规模较大、复杂程度较高的路径优化模型的算法主要有粒子群算法、蚁群算法以及遗传算法等。本文选择的求解模型的算法是遗传算法。1.2遗传算法的关键操作1.2.1编码编码是执行遗传算法的基础。遗传算法没有直接处理实际问题空间的参数的能力,所以需采用不同的编码方式将实际问题所有可能解转换成为遗传算法中的种群。本文采用的是实数编码方式，将包含实际问题所有解的解空间映射到遗传算法的搜索空间中进行运算求解。此方式可以直接用实数表达可行方案，适用于求解数据规模较大的问题；这种方式在保证算法求解准确度的同时还能简化编程步骤。本文的客户配送节点数为设定n，因此染色体的基因位数为客户的个数n，即一个基因位对应一个客户配送点；用实数“0”来表示配送中心，并在染色体中客户点集的首尾处分别插入“0”表示车辆从配送中心出发完成配送任务后返回配送中心。比如染色体{0，13，38，67，0，19，9，0，34，56，87，0}代表的就是三条路径：0-13-38-67-0、0-19-9-0和0-34-56-87-0。1.2.2种群初始化初始种群是在所有染色体中随机挑选一定数量的染色体组合构成。完成种群初始化后要对种群进行不同的遗传操作产生新的种群，然后对新的种群进行挑选。由于遗传算法后续的运算效率以及优化过程受到初始种群规模的约束，初始种群规模的设定就显得较为重要。本文的客户配送节点数设定为n，并在客户序列的首尾插入“0”，如{0，i1，i2，…，in，0}，然后根据配送车辆的最大车载容量和时间窗要求初始化染色体。比如，在考虑第m个客户和第m+1个客户是否满足车载容量约束时，如果前m个客户的需求量总和小于或等于车载最大容量，但前m+1个客户的总需求量大于车载最大容量，则需要在第m+1个客户前面插入0或者将客户移动一个位置后插入0；在考虑第m个客户和第m+1个客户是否满足时间窗约束时，按同样的步骤处理。重复以上步骤，直到产生一定数量的种群。1.2.3遗传操作1.选择操作。此操作的目的在于筛选染色体质量，提高全局收敛性和计算效率，同时避免基因缺失。本文的选择操作是锦标赛选择法，是指对选出若干染色体进行适度值的比较，基于比较结果进行“优胜劣汰”，选取一个适度值较高的染色体进入子代种群，然后重复此步骤，直到子代种群规模符合条件。本文的选择操作在每次迭代过程中只在算法刚开始的时候进行一次，然后进行其他的遗传操作产生子代组成新的种群继续进行迭代。2.交叉操作。交叉操作是遗传算法中产生子代染色体的重要途径之一，是通过交换两条染色体中基因片段形成新的染色体。在遗传算法中经常使用的交叉方式有PMX交叉、OX交叉、CX交叉等。本文采用的是OX交叉方式，首先在一对染色体a和b（父代）中随机地选择几个起止位置相同的基因；接着，产生一个被选中的基因位置与父代a相同的子代，同时找出在父代a中选中的基因在另一条父代b中的位置；最后将父代b的其余基因按顺序放入子代染色体中生成新的染色体。比如染色体a为{7,1,6,4,8,3,5,9,2}，染色体b为{5,7,4,9,1,3,6,2,8}，则它们生成的子代染色体为{5,7,6,4,8,3,9,1,2}和{7,6,4,9,1,3,8,5,2}。3.变异操作。变异操作是指变异染色体上的一些基因片段使染色体信息发生改变，产生新的染色体，增加染色体数量，以达到扩大算法搜索范围和防止早熟现象出现的目的。本文选择使用randperm函数完成基本位变异操作，产生新的染色体。例如染色体a为{1,2,3,4,5,6,7,8,9}，经过randperm函数变异生成新的染色体a’为{1,2,4,3,5,6,7,8,9}。1.2.4终止条件终止条件是指为了终止遗传算法的迭代循环而提前设定的条件。在遗传算法中，经常使用的条件包括设定目标、找到最优解自动进行终止以及设定迭代次数，其中第三种方法具有有效控制求解准确性和运行时间的优势。所以，本文选用了设定迭代次数进行终止。

实例分析本文实例分析所采用的数据来自于Solomon标准数据集。在Solomon标准数据集中，一共设计了6类数据，即R1、R2、C1、C2、RC1、RC2，其中R类表示位置随机均匀分布的客户，C类表示位置聚集分布的客户，RC类表示位置混合分布的客户。然后，又将以上三类分别分为1类和2类：1类表示调度范围较小，即要服务的客户量比较少；2类表示调度范围较大，即要服务的客户数量比较多ADDINEN.CITE<EndNote><Cite><Author>李善俊</Author><Year>2020</Year><RecNum>68</RecNum><DisplayText><styleface="superscript">[31]</style></DisplayText><record><rec-number>68</rec-number><foreign-keys><keyapp="EN"db-id="pdtvzvaen5fpa1eee5xx0wtlsz0rd0zfz99d"timestamp="1619724832">68</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>李善俊</author><author>陈淮莉</author></authors></contributors><auth-address>上海海事大学物流科学与工程研究院;</auth-address><titles><title>基于NSGAII的带时间窗生鲜品配送路径优化</title><secondary-title>上海海事大学学报</secondary-title></titles><periodical><full-title>上海海事大学学报</full-title></periodical><pages>58-64</pages><volume>41</volume><number>02</number><keywords><keyword>生鲜品配送</keyword><keyword>多目标优化</keyword><keyword>非支配排序遗传算法(NSGA)</keyword><keyword>带时间窗的车辆路径问题(VRPTW)</keyword></keywords><dates><year>2020</year></dates><isbn>1672-9498</isbn><call-num>31-1968/U</call-num><urls></urls><remote-database-provider>Cnki</remote-database-provider></record></Cite></EndNote>[31]。每一类的数据集内容包括顾客坐标、时间窗开始时刻、时间窗结束时刻、服务时间、客户需求量、车载容量ADDINEN.CITE<EndNote><Cite><Author>李善俊</Author><Year>2020</Year><RecNum>68</RecNum><DisplayText><styleface="superscript">[31]</style></DisplayText><record><rec-number>68</rec-number><foreign-keys><keyapp="EN"db-id="pdtvzvaen5fpa1eee5xx0wtlsz0rd0zfz99d"timestamp="1619724832">68</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>李善俊</author><author>陈淮莉</author></authors></contributors><auth-address>上海海事大学物流科学与工程研究院;</auth-address><titles><title>基于NSGAII的带时间窗生鲜品配送路径优化</title><secondary-title>上海海事大学学报</secondary-title></titles><periodical><full-title>上海海事大学学报</full-title></periodical><pages>58-64</pages><volume>41</volume><number>02</number><keywords><keyword>生鲜品配送</keyword><keyword>多目标优化</keyword><keyword>非支配排序遗传算法(NSGA)</keyword><keyword>带时间窗的车辆路径问题(VRPTW)</keyword></keywords><dates><year>2020</year></dates><isbn>1672-9498</isbn><call-num>31-1968/U</call-num><urls></urls><remote-database-provider>Cnki</remote-database-provider></record></Cite></EndNote>[31]。本文所采用测试实例的数据是Solomon数据集中的C101、R101、RC101与C201，由于Solomon公开的研究数据均无计量单位，故下文所有数据均无计量单位。本文所选择的算法是通过MatlabR2020b在配置为Intel(R)Core(TM)i5-7200UCPU@2.50GHz，运行内存为8GB，操作系统为Windows10的计算机上运行。本文设定种群规模为100，交叉概率为0.8，变异概率为0.05，迭代次数为500，其他参数见表5-1。表5-1模型参数参数意义取值固定成本100单位距离成本1制冷剂有效时间5配送车每次更换制冷剂的成本2配送车在配送过程中的的速度1每辆配送车冷藏箱的最大容量2001、基于测试实例C101的数据，采用本文所建模型和遗传算法计算后，优化结果如下表5-2、图5-1和图5-2所示。表5-2基于测试实例C101数据的遗传算法计算结果车辆使用数目10总成本1260.5116迭代历时（秒）4020.791728最优解出现代数86车辆10-5-3-7-8-10-11-9-6-4-2-1-75-0车辆20-20-24-25-27-29-30-28-26-23-22-21-0车辆30-67-65-63-62-74-72-61-64-68-66-69-0车辆40-90-87-86-83-82-84-85-88-89-91-0车辆50-32-33-31-35-37-38-39-36-34-0车辆60-98-96-95-94-92-93-97-100-99-0车辆70-43-42-41-40-44-46-45-48-51-50-52-49-47-0车辆80-13-17-18-19-15-16-14-12-0车辆90-81-78-76-71-70-73-77-79-80-0车辆100-57-55-54-53-56-58-60-59-0图5-1基于测试实例C101的优化过程图5-2基于测试实例C101的最优配送方案路线图2、基于测试实例R101的数据，采用本文所建模型和遗传算法计算后，优化结果如下表5-3、图5-3和图5-4所示。表5-3基于测试实例R101数据的遗传算法计算结果车辆使用数目11总成本2131.1653迭代历时（秒）5126.6855最优解出现代数486车辆10-28-26-72-75-41-56-74-58-0车辆20-6-89-27-31-88-90-66-1-52-0车辆30-92-44-38-43-95-61-84-37-100-14-15-87-42-91-93-0车辆40-5-83-8-46-48-82-18-7-0车辆50-30-51-9-50-69-63-64-49-19-62-11-10-0车辆60-94-59-98-99-85-60-0车辆70-45-16-86-96-13-2-31-73-22-54-24-80-0车辆80-39-23-67-4-25-55-57-97-17-36-47-0车辆90-77-33-65-71-81-34-35-29-78-20-32-70-0车辆100-12-76-79-3-68-0车辆110-40-53-0图5-3基于测试实例R101的优化过程图5-4基于测试实例R101的最优配送方案路线图3、基于测试实例RC101的数据，采用本文所建模型和遗传算法计算后，优化结果如下表5-4、图5-5和图5-6所示。表5-4基于测试实例RC101数据的遗传算法计算结果车辆使用数目12总成本2370.8086迭代历时（秒）4631.1131最优解出现代数430车辆10-42-44-40-43-37-35-71-94-96-0车辆20-14-47-15-16-73-55车辆30-12-11-9-10-13-17-0车辆40-92-95-62-67-85-84-56-50-34-93-0车辆50-69-88-78-79-46-4-60-0车辆60-91-80-81-5-45-2-7-6-8-3-1-100-0车辆70-82-52-99-86-57-66-64-23-18-48-25-0车辆80-65-83-21-19-49-22-20-24-58-0车辆90-63-51-76-89-29-30-26-32-27-28-31-33-0车辆100-61-70-0车辆110-90-53-59-75-87-97-74-77-0车辆120-72-39-36-38-41-54-68-98-0图5-5基于测试实例RC101的优化过程图5-6基于测试实例RC101的最优配送方案路线图4、基于测试实例C201的数据，采用本文所建模型和遗传算法计算后，优化结果如下表5-5、图5-7和图5-8所示。表5-5基于测试实例C201数据的遗传算法计算结果车辆使用数目10总成本1469.6862迭代历时（秒）4078.9559最优解出现代数488车辆10-75-95-3-4-91-88-84-83-82-87-90-0车辆20-5-2-1-99-100-97-92-94-98-7-89-0车辆30-63-62-74-72-61-66-69-0车辆40-20-22-24-27-30-21-