英语原文共 21 页，剩余内容已隐藏，支付完成后下载完整资料

基于遗传算法的物流配送路线优化研究

摘要

在当代社会，物流越来越受到各国的关注，是企业创造利润的有效途径。 本文主要研究物流配送的一个方面，即车辆路径优化问题。 在遗传算法的基础上，建立了车辆路径优化的数学模型和配送路线的约束条件。 遗传算法采用常用的整数编码对染色体进行编码，在个体选择中采用最优个体保留策略和轮盘赌法。 最后利用该方法进行实验计算，借助matlabR2016软件进行实验计算。 最终结果表明，利用遗传算法对物流配送车辆路径进行优化，可以方便有效地获得问题的最优解或近似最优解。

关键词

物流配送；路线优化；遗传算法。

第1章 导言

在国内外，物流业的发展水平已成为衡量一个国家现代化程度的重要指标之一。 近年来，我国物流业进入了快速发展时期。 在规模快速增长的同时，配送压力和配送成本也显著增加，成为物流业持续快速发展的主要瓶颈。 合理高效的配送路线规划是解决这一问题的有效手段。 刘丽等。 [1,2] 利用遗传算法计算了解决农机部署问题的全局最优路径。 黄玉文[3] 通过自适应地调整杂交速率和突变率，并对接收算子进行退火，有效地提高了全局优化能力。 李伯豪[4] 在算法中添加了每个需求点的需求和时间窗口。 该算法在解决需求点的无序排列问题和时间窗问题的路径问题上具有较高的精度。 冯伟华等。 [5,6] 设计了一种改进的遗传算法，通过添加自适应突变算子来解决早熟收敛问题。 徐伦辉等。 [7,8] 通过多层编码扩展了遗传算法的使用。 Lamini等人。 [9] 提出了一种改进的交叉算子来解决静态环境下遗传算法路径规划问题。 陈光利等。 [10-12] 有效地解决了遗传编码中的多类型混合路径优化问题。 郑丽娜等。 [13-15] 采用自适应交叉变异率和优势个体保留的方法，有效地改进了算法。 本研究有效提高了物流配送效率，在智慧物流发展趋势中具有良好的应用前景。

第2章 研究背景及意义

研究背景

随着科学技术的飞速发展和全球经济一体化进程的加快，企业日常经营活动中的物流活动对全球经济的发展起着越来越重要的作用，其地位越来越突出。它对全球经济活动的各个方面都很重要，影响日益明显。特别是随着电子商务网站的发展，物流逐渐成为当前企业竞争的重要领域。物流配送是指对配送、装卸、储存、运输、包装和信息传递等物流活动进行综合、系统的管理，协调和对应企业的生产、采购、供应和销售等日常业务活动。其目的是以最低的成本为客户提供最好的服务，从而提高企业的整体经济效益，提高企业的整体竞争水平。据相关统计，在不考虑货物损失和各环节的附加成本的情况下，我国的仓储和运输成本约占GDP的17%

随着市场经济的发展和物流技术专业水平的提高，物流配送行业也得到了迅速的发展。在物流配送业务中，存在许多优化决策问题。本文讨论了物流配送路径优化问题，即通过制定合理的配送路径，使货物能够快速、经济地交付给客户。配送路线的选择是否合理，对加快配送，提高服务质量，降低配送成本，增加经济效益有很大影响。

研究意义

物流配送是从运输中衍生出来的一种功能，是市场不断发展的必然产物，是经济发展的重点之一。为了尽可能降低成本，增加效益，物流配送中更重要的是如何合理调度车辆。配送中心的地理位置，每个客户的地理位置也已知，每个客户的需求，配送车辆的有限容量和最远的配送距离都已知。要求合理安排车辆行驶路线。调度中心出发，依次到达每个客户，最后返回配送中心，使行车距离最短，成本最低，效益最大化。物流配送路径的优化研究对于提高整个物流系统的性能和物流业的智能化和现代化具有重要意义。

第3章 物流配送路线优化问题的数学模型

问题描述

车辆配送路线的选择对产品物流的配送成本有着极其重要的影响。选择不同的配送路线，结果有很大的不同。在实际情况下，有不同的配送环境，如不同类型的配送车辆，多个配送中心，以及满足客户要求所需的时间窗口。这些都会影响分布路径S选择。产品物流流通模式需要根据产品的特点和客户的具体要求，合理安排配送车辆的行驶路线和配送产品的质量，从而降低配送成本，提高配送效率，找到最优的配送方案，以获得最优的目标值。影响产品配送路径的因素主要有：客户点的位置，客户的产品需求，所需的配送服务时间，产品的特性，以及地点的交通状况。假设的条件：本文研究的车辆路径问题有：配送中心和多个客户位置。为了便于研究，本文不考虑配送中心的建设成本和现场、天气和道路条件的通常维护成本。在产品销售平台上接到各销售点的订单后，配送中心应根据客户点的地理位置和产品需求，合理安排车辆装载和行驶路线。尽快制定最优配送方案，并在客户要求的时间段内完成产品的配送。 本文主要以某一城市的产品配送为研究对象，根据配送原则和相关约束，合理规划每个客户需求点的驱动路线，其中配送时间忽略了到达客户点的停滞时间，主要考虑了道路旅行所花费的时间。一定的配送中心会安排统一的车辆，为一定区域的客户完成优质的配送服务，找到最优的路线，使配送路线最短。

物流配送路线优化问题的数学模型构建

物流配送路线优化问题可以描述为：从一个配送中心配送到多辆车的多个需求（客户），每个需求点都有一定的位置和需求，每辆车都有一定的承载能力，并要求合理安排车辆路线，使总运输距离最短，并满足以下约束条件：

1.配送路线上任何客户对货物的一次性需求不能超过车辆的额定负荷；

2.每条交付路线的长度不超过一次交付车辆的最大旅行距离；

3.每个需求点的需求必须满足，交付只能由一辆车进行。

参考文献建立的车辆路由问题数学模型，并考虑上述物流配送路由优化问题的约束条件和优化目标，建立物流配送路由优化问题数学模型。

假设配送中心有K辆车，每辆车的承载能力为Qk(k=1，2...，K)。 一次交付的最大驱动距离是Dh，它需要交付到L需求点。 需求点的需求为qi(i=1，2.，L)，从需求点i到j的距离为dij，从配送中心到每个需求点的距离为d0j(ij=1，2.，L)。 设nk为第k车交付的需求点数(nk=0表示不使用第k车)，用集合rk表示第k路径，其中元素rki表示路径k中需求点rki的顺序为i（不包括配送中心），设rk0=0表示配送中心，则可建立以下物流配送路线优化问题的数学模型：

在上述模型中：

方程（1）是目标函数，即总传递距离；

方程（2），保证每条路线上各需求点的需求之和不超过车辆的承载能力；

方程（3）确保每个交付路线的长度不超过一次交付的车辆的最大旅行距离；

方程（4）表明，每条路径上的需求点数量不超过总需求点；

方程（5)表明每个需求点获得交付服务；方程(6）是每个路径的需求的组成；

方程（7）限制每个需求点只由一辆车交付；

方程（8）是当第k车服务的客户数量大于1时，表示该车已参与交付，则签(nk)=1。当第k车服务的客户数量小于1时，表示该车未被使用，所以签(nk)=0。

第4章 物流配送路线优化的遗传算法构建

编码

本文研究了选择最优路径的问题，一般采用实数编码来执行可行解的编码操作。 路线优化问题有两个问题需要解决。 一是送货时需要送多少辆车，每辆车如何配送到哪个客户点，采用直接编码。

根据物流配送路线优化问题的特点，采用简单直观的自然数编码方法，用0表示配送中心，1，2，...，L表示客户点，随机排列1到L 1之间的自然数。 假设配送中心有K车，将K-1零随机插入序列中，使1，2，...，L K-1，L K-1，非重复自然数的随机排列，构成个体对应一个配送路线计划。

形成初始人口

随机产生L K-1不重复自然数从1到L K-1的排列，形成个体。 假设群体大小为N，则随机生成N个这样的个体，形成一个初始群体。 本文研究的路径优化问题需要多次迭代，因此初始种群定义为100。

健身价值的评价

对于个体所对应的分配路线方案，要判断其优劣，一是看其是否满足分配的约束；二是计算其目标函数的值（即各分配路线长度之和）。 根据配送路线优化问题的特点确定的编码方法意味着它可以满足每个需求点可以得到一个配送服务，每个需求点只由一辆车交付的约束，但它不能保证每个路线上的每个需求都得到满足。 点需求之和不超过车辆的承载能力，每条交付路线的长度不超过车辆一次最大行驶距离的约束。 为此，对于每个个体对应的配送路线计划，必须逐一判断每个路线是否满足上述两个约束条件。 如果不是，则确定为不可行路线，最后计算其目标函数值。 为了一个个人j，让相应的交付路径计划的不可行路径数是mj(mj=0表示个体对应一个可行解)，及其目标函数值是zj然后是适应度值Fj个人可以是表达方式：

fj=1/(zj 米jg) (9)

其中：G为每次罚的权重，可以根据目标函数的取值范围选择一个相对较大的正数，本文采用100。 (G值过小会影响适应度的比较)

选择行动

将每一代群体中的N个个体按健身降序排列，排名第一的个体表现最好，直接复制到下一代中，排名第一。 下一代群体的其他N-1个体需要根据上一代群体的N个个体的适应度，通过轮选方法生成。 即同时采用最优个体保留法和轮盘赌法，先计算和所有个人的健康状况在上一代组得到(sum;Fj)，然后计算每个人的适应度在总适应度值比，得到(Fj/sigma;fj)，用这个作为概率被选中。

交叉作业

本文采用了类似的OX交叉方法。 在交叉操作中，本文选择交叉概率为0.9，随机和非重复选择需要交叉的位置，并分别在交叉位置上交换代码值；由于新代码可能与未交换位的值包含相同的部分，因此需要替换相同的值来形成一个新的个体。

举例如下：①在亲本个体之间随机选择一个交配区域，例如，如果两个亲本个体和交配区域分别为：A=47|8563，921，B=83|4691，257；②将B的交配区域添加到A的前面，A的交配区域被添加到B的前面，得到：Alsquo;=4691|478563921，Brsquo;=8563，834691257|；③在Arsquo;和Brsquo;的交配区域之后，删除与交配区域相同的区域。 自然数，最后两个个体是：A“=469178532，B”=856349127。 与其他交叉方法相比，该方法在双亲相同时仍能产生一定程度的变异效应，对保持群体的多样性特征有一定的影响。

变异操作

由于选择机制采用保留最佳样本的方法，为了保持群体中个体的多样性，采用多个连续互换的突变技术，使个体的顺序发生更大的变化。 突变操作发生概率为Pm=0.05。 一旦发生突变操作，通过随机方法产生交换J数，并将突变操作所需个体的基因交换J次（交换基因的位置也随机产生）。

终止程序。

本文将最大迭代次数设置为100。 当迭代次数达到100次，或者找到最优解时，可以终止程序。

第5章 实验结果分析

本文编写了基于上述遗传算法的matlabR2016代码程序，并对选定的100个需求点和一个配送中心进行了实验计算，以进行物流配送路线优化问题的交付示例。 最多可安排25辆车，最大载重量200kg。 配送中心与各需求点的距离，各需求点的距离及各需求点的需求量见附录1。 实验计算采用以下参数：交叉概率和变异概率分别为0.9和0.05，迭代次数为100，生成间隙GGAP为0.9，违反容量约束的惩罚权重为10，违反时间窗约束的惩罚权重为100。 随机求解上述问题100次后，优化过程图。 图1和最佳分配计划路线图。 2如下：

图1 优化工艺图

图2 最优分配计划路线图

图3 最后结果的截图

根据图3 在matlabR2016解的最终结果中的3个(每次迭代的具体结果见附录II)，我们可以看到最优使用的车辆数为10辆，最短的总车辆距离为828.9369km。 也就是说，配送中心需要发出10辆车才能送货到100个需求点。 具体服务车辆如图所示。 配送完成后，需要返回配送中心。

第6章 结论和总结

本文选择的遗传算法求解路径优化模型，设计适合解决问题的遗传算法步骤并做详细的程序设计，设计具体的计算实例，设置相关参数，使用matlab实现模型算法，并通过多次迭代叠加遗传算法，算法的最优解导致最优分配方案。 验证了模型的合理性和算法的有效性。 同时，从实验结果可以看出，首先随机建立物流配送模型，然后利用遗传算法解决问题，是一种相对方便、快速的解决方法。 可以在相对较短的时间内得到物流配送路径。 最佳解决方案。 根据本文的研究成果，总结如下：

1.在物流配送业务中，合理确定配送路线是提高服务质量，降低配送成本，增加经济效益的重要手段。 利用遗传算法解决VRP问题是一个重要的研究方向。

2.在建立物流配送路线优化问题数学模型的基础上，构建了求解物流配送路线优化问题的遗传算法。 实验计算结果表明，遗传算法是一种性能优异的启发式搜索方法，可以方便有效地获得物流配送路线优化问题的最优解或满意解。

3.构建的优化物流配送路径的遗传算法，包括巧妙设计的个体编码方法，个体适应度的计算方法，以及选择，交叉和变异算子，对于解决类似组合优化问题具有一定的参考价值。

最后，虽然遗传算法对于研究VRP问题有很大的价值，但我们也应该知道，遗传算法也有缺点。 虽然全局搜索能力相对较强，但局部搜索能力很弱，可以在短时间内接近最优解。 接近最优解后，需要一段时间才能达到最优解。 如果可以用其他算法计算，可以快速提高效率。

参考资料

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[605684]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

1. 刘丽，刘烨，王新丽.基于遗传算法的农机配置研究[J].农机化研究，2019年，41（11）：1-7.
2. 梁潇，周祥珍。 引用该报告.基于遗传算法的小麦收获机路径智能优化控制研究[J]。 农机化研究，2018,40（2）：56-60。