【蚁群算法在物流路径设计中的应用实证探究（论文）8400字】

蚁群算法在物流路径设计中的应用实证研究摘要物流运输已成为人们生活中的重要角色，消费者期望自己所购买的商品以最快的速度到达自己手中.然而实际配送时间不可避免会出现无法达到消费者的预期的情况.因此，因此在物流行业中消费者的期望送达时间与实际配送时间是该行业的一个主要矛盾，而如何缓解这以一矛盾也成为了物流企业在激烈竞争下存活的关键.本文采用蚁群算法针对同城配送问题对物流配送路径进行规划，建立合理的数学模型并进行实例分析验证.本文首先简要介绍了车辆路径问题以及蚁群算法的进步思想，接着通过结合时间窗改进的蚁群算法进行求解，最终通过一定实例验证模型的可行性，为物流行业的发展提供一定的理论支撑.[关键词]车辆路径；蚁群算法；优化线路 目录引言 61车辆路径问题阐述 61.1车辆路径问题 61.2帯时间窗的车辆路径问题 81.3车辆路径问题的求解方法 92蚁群算法阐述 102.1蚁群算法主要原理 102.2蚁群算法建模 102.3蚁群算法应用 113算法物流路线优化问题求解 133.1一般VRP的应用 133.1.1VRP与TSP之间的差异 133.1.2VRP的应用 133.2基于时间窗的VRP的应用 133.2.2路径的搭建 143.2.3信息素限制 153.2.4信息素更新的改进 153.2.5改进蚁群算法的实现步骤 154求解物流优化路线问题的实例分析 164.1实例分析 16结论 17参考文献 18引言同城物流配送问题多路径物流配送问题，其具体路径的确定一项复杂的系统工程.在这一问题中路径的选择将直接的影响到物流配送的速度、成本等要素.正常工作的物流配送中心工作的基本的配送流程是：确认和所需要配送的所有目的地具体位置以及每个目的地的货物配送量，在参考配送车辆的负载情况，去规划合适的路径，以到达预定的目的（在最大限度地满足客户要求的情况下使得成本最小化）.为了便于简化问题地研究，使得其更具有合理性，本文规定要履行的约束条件为：每个需求点同一时间只会有一辆车开赴，车辆的负载不能低于路径上所有目的的需求之和，路径的长度不能超过规定的最大里程.根据上述描述，针对物流配送中路径选择这一重要问题，本文将从车辆路径问题出发，结合时间窗，应用蚁群算法提出一种路径优化理论方法，在建立一个路径优化的数学模型，最终结合数据，验证改模型的可行性，力求实现利润最大化的同事，提高客户对与服务质量的满意度，从而为企业的发展提供保障.1车辆路径问题阐述1.1车辆路径问题车辆路径问题（VRP）针对以配送中心为起点，向多个的位于不同位置，且物流配送量都有差异的客户运输货物的问题.因此，配送中心必须将满足需求的货物交付给对应的每个客户节点.最基本要求是从配送中心组织一定数量的货运车辆，并将其正确交付给每个客户节点，同时满足某些限制（车辆行驶距离的限制，车辆负载和每个客户节点的限制，货物和顾客取货的时间），最后返回货物配送中心.对这一问题的研究的主要目的便是在满足基本要求的前提下，合理的规划出一条最优的路径，以实现了从运输车辆的路径长度、运输时间最短化车辆路线规划的问题通常与实际交付过程中的限制相关，包括配送中心的数量，服务类型和交付车辆的类型等因素.该问题的研究者根据这些限制因素对该问题进行分类，并建立了相关的数学模型.VRP问题可以分为有时间限制的VRP和没有时间限制的VRP.没有时间限制的事实意味着产品的交付日期没有时间限制.期限意味着必须在客户指定的期限内交货.从这一角度出发，车辆路径问题便可以依据其使用时间窗作为约束条件的具体内容来进行划分，依次为：硬时间窗VRP、软时间窗VRP以及混合时间窗VRP.硬时间窗不允许提前或延迟抵达.软时间窗则允许在合理范围内出现一定的时间偏差.混合时间窗则是前两种的结合.VRP问题的数学建模：假设您有一个配送中心，可以将货物运送到客户点.第i个客户点的要求是：，配送中心发送n辆具有相应负载能力的车辆来运输车辆.物品将被运送到每个客户地点，并最终返回到配送中心.已知，必须满足每个客户的需求，并调整最短的行驶路线以适应车辆类型.要完成上述任务，您需要解决以下约束：（1）配送车辆一次配送路径上所有节点的配送量之和不能超过配送车辆的负载量。（2）多辆车不会同事访问同一个节点，及一个结点只会由一辆配送车辆来访问。（3）配送车辆一次配送的路径长度小于交付车辆所能到达的最大距离.（4）必须在与客户协商的时间内完成约定配送货物的交付.上述条件只是在VRP中可能需要满足的约束条件，依照实际问题，可以只满足上述中的一部分约束条件。如参考所有可能对物流成本可能造成的因素，那么总成本的计算将会变的十分的复杂，因此本文主要从两个角度去考虑如何降低成本的问题：车辆数量最少，总路径之和最短.这两个问题的解决意味着降低了车辆的维护费用，车辆驾驶的人工成本，已经配送过程中的燃料消耗，从而一定程度上的降低的总成本.配送中心号为0，每个客户点为hh（h=1,2,3...，m），车号为s（s=1,2,3..，k.）.通常，配送成本与车辆的行驶方式成正比.行驶时间短、油耗低.、车辆少、驾驶员的工作时间相对少，并总的运输成本也就会更低.以上述两个目的为约束条件，建立下列的数学模型.(1.1)(1.2)(1.3)（1.4）在上面的示例中：变量说明表1.1式minD最小物流配送成本从配送中心到客户点j的配送成本车辆s从点i去往点j(事件发送时取1，否则为0)1.2式节点j的配送由车辆s来完成.当该事件发生时取值1，否则取值0节点i的配送由车辆s来完成.当该事件发生时取值1，否则取值01.3式车辆s的最大承重量节点i的配送量其中，1.1式作为目标函数.1.3式与1.4式作为约束条件.1.3式表明车辆s的一次配送路径上节点配送需求量之和不能大于车辆的负载量.1.4式表明同一节点只会由一辆配送车辆来负责配送.VRP是一个典型的组合优化问题.这是一个具有多个变量，多个约束和多个目标的最短路径问题，这些约束条件主要包括有客户需求、交货时间、发送量、车辆行驶里程限制、车辆容量限制、客户规定的服务时间限制等.选择正确的分配方法将直接影响分配速度和分配成本水平、物流服务质量的好坏以及物流配送的总体经济效益的增减等等.1.2帯时间窗的车辆路径问题带时间窗的车辆路径问题多加入了一个时间窗作为约束条件，使得问题更加复杂，也更加具有现实意义.时间窗规定了客户要求的配送时间范围，不在此范围内，物流企业将受到一定经济损失，这种损失将被计算进入成本中，具体对成本的影响取决于惩罚系数的选定.在实际配送中，配送中心很难在客户设定的时间窗内完成配送任务.除了受到客户分布范围影响外外，还将受到道路车流情况、天气等因素的影响.即使物流配送中心在客户规定时间内完成了配送，也可能造成对车辆资源使用的浪费，从而增加了配送过程总成本[6].时间窗这约束条件的加入，则可以在通过与客户协商过后，根据配送延误的时间来对客户进行补偿，有效的降低客户对于服务的不满，同是量化的成本，方便对总成本进行估算.1）硬时间窗口的定义是：在物流流程和分配计划中，如果产品在指定的时间到达客户指定的位置，假如出现不准时交付产品情况，客户可以拒绝签收产品：（1.6）变量说明表：P(t)[，]惩罚函数值到的惩罚系数晚到的惩罚系数客户期望的时间窗；到达客户i的时间双方之间的函数关系如图1.1所示.图1.12）软时间窗定义：物流企业在客户期望的时间内对将产品交付到约定的地点，如果在期望时间内没有送达，配送企业将受到一定惩罚，用来弥补客户的损失.惩罚函数如下所示：（1.7）变量说明表：早到的惩罚系数晚到的惩罚系数函数的关系如图1.2所示.图1.23）混合时间窗是中上述两个时间窗的组合，如果产品在[ETi，LTi]期间到达，及客户期望时间内到达，配送企业不会受到任何惩罚.如到达时间位于[AETi，ETi]和[LTi，ALTi]中，将会产生一定的罚款，同事影响客户对快递公司服务的满意度，如果商品到达时间处于[-∞，AETi]或[ALTi，+∞]中，客户拒绝接受货物.复合时间框架和相应的罚款之间的关系如图1.3所示..图1.31.3车辆路径问题的求解方法迄今为止，国内外许多研究人员对设备规划解决方案进行了各种研究，并找到了许多有效的解决方案.这些算法按照其研究阶段的不同而产生不同分类，依次可以分为早期的精确算法，到启发性算法，以及当前学者们研究的重点智能算法.精确算法是为了求出问题的最优解，对组合优化问题求解时，但问题规模较小时具有适用性，但是在当今的大数据时代其所面临的局限性便完全展现了出来。启发式算法并非如精确算法一般要求求出最优解，这类算法的目的只是求出问题的次优解，附带一定的几率求出最优解决方案。因此，在面对问题规模扩大时出现对计算量及储存空间的极速增长，也就是所谓的“组合爆炸”，启发性算法提供了一种更优的解决方案本文研究的蚁群算法属于启发示算法，其构造理念来源于蚂蚁在寻找食物的进程中.蚂蚁的行进时盲目的，它们前行依靠的的是路径上信息素的浓度，是用来寻找最优路线的概率型算法.此算法有较强的正反馈机制和求解性能，对问题能够进行有效地求解，获得较好的方案，因此我们在面对旅游路线规划这一问题时考虑使用蚁群算法来提供一种可行的思路.2蚁群算法阐述2.1蚁群算法主要原理蚁群算法模拟了自然界中蚂蚁种群的觅食机制，最早的提出者是学者Marco.Dorigo.这种算法适用于各种复杂的组合优化问题，例如路由通信路由、图片着色等问题.迄今为止的许多研究表明，蚂蚁缺乏视觉能力。那么蚂蚁是如何找到从巢去到食物来源的最短路径？那是因为蚂蚁会在走过的路径上分泌一种信息素，该信息素会随着时间出现挥发，且能够被蚂蚁通过特殊的器官感应到信息素的浓度，让其大概率会选择高浓度路线作为下一个方向，在走过该路径的同时会分泌信息素.这种正反馈机制的存在，使得信息素出现更替，从而使蚂蚁具有寻找的相对跟最优的觅食途径.如下例：图2-1假设蚂蚁的巢是A食物的来源是E，如上面的图2-1所示.蚂蚁想从蚂蚁窝去到食物源，最接近的距离是从蚂蚁的窝A到食物源的直线距离.CD将它们分开.蚂蚁只有两种途径可以从巢中获取食物：ABCE和ABDE.想象一下上图中的距离单位.以米为单位，蚂蚁的爬行速度为1m/min.如果一只蚂蚁在6分钟内沿着这两条路线行走，它将在ABCE线上来回行走，释放出两份信息素，但是ABDE蚂蚁只能够可以通过一次.因此，ABCE线路的信息素浓度将比ABDE线路的信息素浓度高得多.所以，采用ADCE路径的蚂蚁会越来越多，因此随着时间推移，蚁群的正反馈机制，ABCE的信息素浓度也将与ABDE差距也来越大。2.2蚁群算法建模蚁群算法的经典运用是在TSP（Travelingsalesonproblem,旅行商问题），下面将以TSP为例介绍蚁群算法。假设蚁群总数量为m.，表示时间t时所在城市的蚂蚁数量，则，在时间对t中连接城市上信息素浓度等于路径上的最初的信息素浓度，即设(C为常数).蚂蚁K（K=1，2，...，m）根据移动过程中每条路径的信息量来确定路径.要求每只蚂蚁不能访问过已经访问的点。使用禁止列表(k=1，2，…，m)记录蚂蚁K已经访问过的点。在搜索过程中，蚂蚁会根据每条路线上的信息量和路线上的信息素浓度来计算路径选择的概率.（2-1）式中，={0，1，…，n-1)该位置指示在下一步中允许蚂蚁k与真实蚁群不同，人工模拟的蚁群系统具有记忆功能；α为信息启发式因子，，其值越大，则该蚂蚁越倾向与选择其他蚂蚁经过的路径，蚂蚁之间协作性越强；β为期望启发式因子，信息素在路径选择中的重要性，其值越大，则该状态转移概率越接近于贪心规则.信息素的更新类似人脑记忆的特征，新信息不断存储在大脑中，而旧信息存储在大脑中则随着时间的推移逐渐减少，甚至被遗忘.因此，规定t+n在（i，j）的途中.信息素按照以下函数进行更新：（2-2）（2-3）2.3蚁群算法应用基于蚂蚁算法解决期望问题的过程如图2-2所示：图2-2基本蚁群算法流程图（1）算法开始启动m，ρ，α，β，Q和其他相关参数.（2）创建解决方案空间将每只蚂蚁随机放置在不同的起点.对于每个蚂蚁K（k=1、2，...，m），根据路径选择概率公式选择下一个访问节点，直至遍历所有城市。（3）信息素更新在完成当前观看周期后，计算所有路径的总长Lk（且k=1、2，...，m），并找到当前重复次数所需的解（例如，最短解）.）已保存.然后根据公式（2-2）和（2-3）更新Internet信息素的所有值.（4）停止完成判断如果当前的重复次数达到最大循环数，则停止计算.如果不是，返回到步骤2继续执行.（5）输出结果比较每次重复的结果，将在完成整个重复的计算输出每个蚂蚁完成目标的所有最佳路径。3算法物流路线优化问题求解3.1一般VRP的应用通过对举例蚁群算法在TSP中的应用，通过研究比较能够发现VRP问题的根源就是TSP。当不考虑容量这一约束条件，且只有一辆配送车辆，VRP问题便变成了TSP问题。3.1.1VRP与TSP之间的差异（1）起点不同VRP中蚂蚁的初始位置一定要求在配送中心，而STP每只蚂蚁地点是随机的，就像每个旅客居住地点不一致，起始点也就不一样。.（2）不同的路径结构在TSP问题中，依据现实每个旅客最终都是要回到家中，所以在TSP问题中最后都要求在遍历城市回归到起点。而VRP问题时，因为访问节点数的不可预测性，返回初始点便当作是蚂蚁活动结束的标志.（3）定义未访问节点集的规则是不同的.蚁群算法使用禁止列表来作为已经访问过的节点集合.TSP与VRP在对下一节点选择最大的不同时，VRP在决定下一节点的概率函数中多出了配送车辆容量约束这一重要的现实条件。（4）结构不同在TSP问题中，每个蚂蚁在每次迭代后生成的路径都是可行的解决方案，但是在VRP中，只有由多个蚂蚁遍历完所有节点的路径所组成的一个完整的路径地图才是改问题的可行决解方案.3.1.2VRP的应用对于蚁群算法在VRP问题中的应用，可以以蚁群算法在STP中的应用作为基础，依据VRP的特征来进行简单的调整.具体方法是在施加实际负载,当超过车辆的最大负载能力时，车辆必须返回配送中心以指示运输已经完成.之后车辆在离开配送中心为其他客户提供服务，直到完成所有客户服务为止.当所有车辆都经过每个要求的客户节点时所有所走过的路径所组成的路径图便是改问题的决解方案。3.2基于时间窗的VRP的应用与一般的VRP问题不同，VRPTW（带时间窗的车辆路线问题）问题要求在给定的时间窗口将货物交于客户.这让的问题变的更加复杂，主要体现在下列两个方面：限时配送，我们考虑配送路径的将无法可能优先按照客户地理位置的分布去考虑，因为时间要求靠前的很可能会成为第一考虑的条件，具体的影响程度则取决于参考系数的选定.违反时间约定的惩罚值称为目标函数的一部分。本文选择在四个领域中使用最高和最低的蚁群算法来改进算法：创建初始解决方案，创建路线，信息素的定义和信息输速的更新.文本包含对信息素的某些限制.所以在启动系统时必须设置最小值和最大值，用τmin和τmax表示.使用优化的“近邻”方法创建默认解决方案的具体步骤如下：步骤1：根据“近邻”方法随机选择客户节点作为从配从中心出发的第一目标点步骤2：在满足容量约束和时间窗约束的前提下，从未访问客户中选择tjc最小的那个客户.（3-1）（3-2）变量说明表tttb配送车辆到达节点i时间配送车辆在节点i的停留时间从节点i到节点j所消耗的时间节点j时间窗开始时间步骤3：如果未满足容量和时间限制，请返回配送中心，从之前未曾拜访过的所有客户中选择一个新的出发点，然后按照步骤2选择下一个客户，然后进行清晰的服务.步骤4：重复步骤2-3，直至遍历所有节点.步骤5：计算所有路径长度之和.3.2.2路径的搭建由于每个VRPTW查询中的时间限制，因此在为物流配送路径选择潜在客户时必须考虑以下三个因素：（1）到下一个节点的距离和路径信息素浓度.（2）容量限制，沿途所有客户的配送量之和必须在配送车辆的负载量以内.（3）时间窗约束，既到达指定下一节点的时间在其时间窗内，否则依照惩罚函数进行成本计算.基于上述因素，intk的可能替代定律是从城市i中选择城市j：P(3-3)变量说明表Jkωωη蚂蚁K在t时刻访问过的节点集合信息素权重系数时间窗权重系数能见度3.2.3信息素限制为了避免较早地出现停滞现象，本文初始时将信息素浓度设置为最大值.同事还对信息素的浓度加以限制，将每条路径上的信息素浓度的取值范围限制在一个区间τmax，τmin内，若τij≥τmax，则τij=τmax.若τij≤τmax则τij（3-4）（3-5）更新信息素时，其值仍将由公式（3-5）确定，而其值将由以下公式确定：(3-6)3.2.4信息素更新的改进本采用的是局部信息素跟新，具体原则如下：（3-7）式中，ρ为信息素挥发因子，取值在0与1之间；σ为精英蚂蚁的个数；仅当排名第k的精英蚂蚁经过路径i—j时，该路径上的信息素才会更新，增加Δτijk，且Δτijk=σ−kLk，式中L3.2.5改进蚁群算法的实现步骤步骤1：确定约束条件具体数值，根据公式（3-4）和（3-5）设置τmax和，τ步骤2：初始化次数C，蚂蚁I,禁止列表,既设置C=1,K=1，禁止列表设置为空集.步骤3：从状态概率公司（3-3）计算出蚂蚁可能所有去往的下一节点的概率.步骤4：将此时所在结点加入禁止列表.步骤5：重复步骤3，直至禁止列表中包含所有节点.步骤6：重复步骤3-5，直至迭代次数达到最大值.步骤7：输出结果.4求解物流优化路线问题的实例分析4.1实例分析为了验证本文针对VRPTW所建立的数学模型有效性和可行性，本文采取算例分析进行分析验证工作，数据来自Solomon数据库，Solomon数据库中针对VRPTW问题有多种算例，而RC108算例便是被本文所采用的来研究分析的。通过描述，在满足时间窗约束、车辆负载约束以及路径总长度约束的前提下，假定有一个物流配送中心，其需要为80个节点提供物流配送服务，拥有的车辆总数为14.同时假定配送中心的配送工作开始时间为0min，引物流配送工作一般需要耗费大量时间在运输过程，因此设定物流车辆最晚返回时间设定为420min(7h).为了比较有无时间窗约束条件下的路径选择情况，同时方便理解，不考虑惩罚系数的取值变动对实验结果的影响，实验中取惩罚系数a=1.2，b=4.5，记：其中H表示加入时间窗的目标函数，F则表示为不考虑时间窗的目标函数。本文取RC108算例的前10组数据进行研究.相关参数设置为：种群规模Popsize=12，最大迭代次数Maxgen=300，权重系数a=β=0.5，并以其中的一次运算结果作为分析的对象.图4-1中，最小目标函数值Hmin.由第一代的6740收敛到2312，最小目标函数值i.由第一代的1078收敛到932.从图中可以看出，当操作进行到230代时，各代中最优目标函数值下降幅度降低，趋于稳定.图4-1每代中H和F的最小值图4-2中，函数值（H-F）则由第一代的5722收敛到1987从图中可以看出，当进行到240代时，各代中惩罚项函数值下降幅度降低，趋于稳定.图4-2每代中时间惩罚的最小值通过上述的实验研究分析表明，目标函数考虑时间窗后，时间窗的惩罚值基本与目标函数一致，且收敛所需的迭代此次明显增加.这一现象充分表明，时间窗因素对于VRP问题有着重要的影响。结论伴随着网络信息时代的高速发展，物流行业也出现了“井喷式”的发展，物流运输环节所产生的巨大经济效益，促进了物流运输技术的不断提高.但是物流运输途中依旧产生了很多不必要的成本浪费，这是值得研究者们去深入研究的一个方向。本文便是基于蚁群算法，对物流配送中可能的种种情况进行分析，归纳出必要的约束条件，并在此基础上建立出一个可行的数学模型。通过相关实例进行分析验证，进一步证明改数学模型的可行性，为物流配送线路优化问题提供了一定可行的方案。

参考文献[1]杨志清.城市物流配送条件下的多目标车辆路径优化研究[D].哈尔滨工业大学，2015.[2]丁秋雷.客户时间窗变化的物流配送干扰管理模型—基于行为的视角[J].中国管理科学，2015，05:89-97.[3]姜婷.基于改进蜂群算法的模糊需求冷链物流车辆路径优化[J].安徽农业科学,2017,45(21):213-215.[4]丁柏群，姜瑾.基于蚁群算法和动态路阻的物流配送路径优化[J].森林工程，2014，(02):149.[5]丁浩，苌道方.基于Dijkstra算法的物流车辆配送路径优化[J].价值工程，2014，03：14-18.[6]DorigoM，ManiezzoV，ColorniA.AntSystem:OptimizationbyaColonyofCooperatingAgents.ManandCybernetics-PartB，2016，26(1):29.[7]ChristofidesN,MingozziA,TothP.Thevehicleroutingproblem[C].combinationaloptimization,NewYorkJohnlyWiley,2013.[8]ClarkeG,WrightJW.S