【《基于蚁群算法含接驳点冷链物流配送路径优化案例分析》6500字（论文）】

基于蚁群算法含接驳点冷链物流配送路径优化案例分析目录TOC\o"1-3"\h\u28973基于蚁群算法含接驳点冷链物流配送路径优化案例分析 126051冷链物流车辆配送路径模型的构建 1127291.1问题描述 1256981.2模型问题假设 235011.3变量分析 3221191.1.1决策变量分析 3217871.1.2时间变量分析 367281.1.3成本变量分析 3253661.1.4冷链配送路径优化模型 5274221.4模型分析 6269732基于蚁群算法含接驳点冷链物流配送路径优化 8129442.1蚁群算法原理 8139082.1.1概念原型 8192982.1.2基本原理 8122502.1.3蚁群算法的特点 9188082.2基于蚁群算法对原始策略进行求解 9209272.2.1算法设计 9135362.2.2算法实现 10131582.3考虑接驳点的农产品冷链配送优化模型 1231272.1.1问题描述与模型假设 12146032.1.2构建模型 13121322.4模型分析 141冷链物流车辆配送路径模型的构建1.1问题描述该问题旨在解决配送中心的生鲜农产品，通过车辆配送到用户需求点并设计合理路线。具体表现为：假设配送中心有若干大型冷链专用车，对城市中若干需求点进行生鲜农产品冷链配送，每辆配送车辆从配送中心出发，完成送货运输任务后按照原始路线返回至起点。对其中的原始路线根据各个需求点的具体信息进行优化，根据其配送中心的装货规模，出发时间和行驶路线（线路），以便从配送中心到服务完成为止的所有运输和配送成本，货物损坏成本，冷却能耗，客户（需求点）及总物流成本（例如成本，罚款成本和固定成本）最小为目标函数构建数学模型，设计合理路线进行路径。如图1.1所示:图1.1基于实时路况的农产品冷链物流配送Figure1.1Coldchainlogisticsdistributionofagriculturalproductsbasedonreal-timeroadconditions1.2模型问题假设道路拥挤状态保持相对稳定，即从做出交付决定的时间到运输车辆经过路段时的道路拥挤状态保持不变。（1）各个配送中心中的车辆数量已知。每辆车的重量是有限的，每位客户的总需求不超过单辆车的最大负载能力。该假设便于模型求解。在实际情况中，如果某个客户的总需求大于单个车辆的最大负载，则可以将该客户分为两个或更多客户进行处理。（2）确保为每个客户提供服务，并且只能通过冷藏卡车运送他们需要的新鲜农产品。（3）每个分配路径的总长度不得大于分配车辆的行驶里程，并且分配车辆无需在中间加油。（4）配送中心有足够的新鲜农产品，并且客户的需求，地理位置和时间窗口限制是已知的。（5）新鲜农产品必须在指定的时间范围内交付，如果超过该时间将支付罚款。（6）配送车辆在完成本身的配送任务时，若没有突发任务，必须返回配送中心。1.3变量分析1.1.1决策变量分析假设V0为起点（配送中心），Vi表示该模型中的终点（需求节点）其中i表示各个需求点(i=1，2，．．．，N)。目标决定变量为Xkij，当Xkij为时1说明k辆车经过了该目标点(Vi，Vj)，如果没有经过则Xkij=0。Sign(k)表示是否出发了k辆进行运输送货，出发为1，未出发则为0，即：（1.1）1.1.2时间变量分析参考高德地图、百度地图等软件提供的城市道路实时交通状况界面可用于获取实时路段(Vi，Vj)。Rij表示路况信息指数，其中，rij与rji相等，rij∈[0,1]，从0到1按照数字大小表示堵塞程度，0表示路况达到理想状态，1表示路况条件为最差状态。配送车辆在路段(Vi，Vj)的工作时间为：（1.2）本式中Lij单位时间到配送点的路程距离，V0表示车辆在运输时的速率。该车辆到最终需求点的取货时间为：（1.3）其中，u为卸取货物的平均速度，gi为消费者的收货量。1.1.3成本变量分析（1）配送车辆固定成本（C1）在该冷链物流进行配送运输活动时所固定产生的成本，通常只和专用运输车的数量有关，因此送货车的总固定成本为：（1.4）配送车辆运输变动成本(C2)冷藏运送车辆的运输成本包括车辆燃料成本，维修成本，维护成本等，并且与车辆的里程成正比:（1.5）其中，h是送货车每公里的运输成本。（3）运输过程中车辆制冷成本（C3）冷链配送车辆制冷消耗成本，一般是指车辆中的制冷剂及制冷器械的消耗。但是由于运送车隔室和新鲜农产品的运送具有固定的规格，因此隔室的温度相对较高稳定，且外部因素稳定性强，运输车辆的消耗成本，可以与车辆中制冷剂的消耗及制冷器械的损耗，开门数量和开门时间（卸载时间是在客户点花费的时间）成正比[55]。在整个配送过程中，有必要在每个客户点卸货，只需要打开车门一次。确定每个点的总卸载时间和每个客户的总需求。这样，常数a可以用来表示在整个分配过程中打开门并卸下货物所产生的冷却成本。故整个运输过程中的制冷成本为：（1.6）其中，b是制冷消耗系数。（4）生鲜农产品货损成本（C4）在分配过程中，分配车辆可以使用自己的制冷设备将车厢保持在安全温度以下。因此，新鲜农产品的货物损坏成本仅与运输时间，开门数量和卸货时间有关，它类似于制冷成本分析确定开口总数和总卸载时间，故货损成本可表示为:（1.7）其中q为货物损坏的常数指标，p为货物运输过程中的客观货损常数。（5）未按时送达的惩罚成本（C5）假设消费者可接受的时间范围为[dj,uj]，最迟可接受的时间范围为[Dj,Uj]（Dj≤dj,uj≤Uj）。也就是说如果货物在可接受时间内送达则无惩罚成本；在最迟可接受时间内送达，则有惩罚成本；在超过最大接受时间时，用户可直接退货，则惩罚成本为无限大。惩罚指标w1为在可接受时间之前送达的，惩罚指标w2为最晚接收的时间和可接受时间的时间段之间送达的时刻,Tj为货物到达目的地的时刻，则冷链运输时的惩罚成本可表示为：（1.8）1.1.4冷链配送路径优化模型根据以上对各个成本的分析，建立以最小总成本为目标函数的路径优化模型如下：配送路线的总数不超过配送中心的车辆总数M的条件是：（1.9）设每次运输时的起始点和结束点都为配送中心V0。则构建约束条件为:（1.10）将每个客户点限制为只能由送货车辆送货一次，约束条件表示为:（1.11）（1.12）假设每次消费者的最大订单量不超过冷链专用车的最大承重，则约束条件表示为：（1.13）其中gi表示需求点目标需求的最大值，G代表每一辆物流专用车的最大运输量。确保每辆送货车每次送货的最远驾驶路径不超过额定行驶路径，约束条件表示为:（1.14）要求送货车辆到达客户点的时间必须在最大容许时间范围内，约束条件表示为:（1.15）综上，得原始策略下以最小成本为目标函数的，优化模型如下：（1.16）1.4模型分析本章首先构建用于新鲜农产品冷链物流的车辆路径优化模型。该模型首先阐述了构建新鲜农产品分销路径优化模型的总体思路。它阐明了一系列模型假设和相关参数，分析了冷藏卡车配送过程中的各种因素，并构建了一个以使总成本最小化为目标的系统。该功能的优化模型主要包括因使用车辆而产生的固定折旧成本，因运输距离的变化而引起的可变成本，因时间的增加而对新鲜农产品质量造成的损害成本，以及由于软时间窗口限制而带来的损失成本[56]。为了使求解后的模型结果更符合新鲜农产品的实际交付情况，增加了一些约束以使模型更加完善。现实生活中新鲜农产品的交付过程将更加复杂。因此，影响因素不仅是上述因素，而且是更复杂的因素。本章所述的新鲜农产品冷链物流配送路径规划模型在解决实际的冷链配送车辆路径问题上仍存在一些不足。因此，有必要进行更深入的研究，并在将来找到合适的方法来改进该模型。

2基于蚁群算法含接驳点冷链物流配送路径优化意大利著名数学家Dorigo在上个世纪九十年代初期根据蚂蚁寻找食物的过程并通过其方式进行仿生模拟出了蚁群算法。他提到了蚁群在自然界中成群移动的方式，通过蚂蚁彼此的气味来寻找路径，并最终找到最佳路径[57]。蚁群算法是随机算法。面对选择时，蚁群算法通过模拟蚁群的演化过程来随机搜索最佳路径。该算法的本质是在图中找到一条最佳路径，这些路径的采取方式均为随机产生的。该算法在刚提出时在解决旅行商案例（TSP）时较为快捷准确。TSP问题的要求：在访问期间，每个用户点均经过一次，这是路线的规划的约束条件，最终完成服务后返回起始的出发点，拜访后获得的路径距离是所有拜访路径中的最小值[58]。2.1蚁群算法原理2.1.1概念原型在自然界中，一些蚂蚁（最初）是随机行走的。起初，蚂蚁不知道寻找食物时哪个路径会更好，所以他们随机选择了一条路径，找到食物后回到了根据地，然后呆在那里。信息素的痕迹减少了，整个觅食过程路线的不同可以通过其分泌的特殊气味来分辨。如果剩余蚂蚁也发现该最佳路线，这些蚂蚁可能不会继续随机行走，而是遵循这条路径。如果他们最终找到食物，他们将更有可能沿着这条道路寻找食物，而蚂蚁将沿着这条道路前进。路径花费的时间越长，返回所花费的时间就越长。可以看出，如果蚂蚁选择的路径较短，则信息素挥发的时间相对较短。但是还有其他蚂蚁不会选择这条路。他们找到食物后会采取其他方式离开信息素。如果这些蚂蚁发现的路径比以前的蚂蚁发现的路径短，那么将会有很多“蚁群”正在沿着这条新的最短路径移动，并且在如此大规模的蚁群运动之后，它已经发现最短的路径。如果信息素没有挥发，则每个剩余的蚂蚁都有很高的可能性选择该移动路径。如果是这种情况，解决方案空间将受到干扰，解决方案的空间也将受到限制。尽管我们不知道信息素蒸发对实际蚂蚁的优化路径的影响，但对于人工系统而言，具有此功能非常重要。结果，当一只蚂蚁在觅食过程中找到一条最优路线，则会通过其自身气味正向传播给其同类，使剩余同类也通过此路线进行觅食活动。蚁群算法的思想是通过在要解决的问题图上行走的“模拟蚂蚁”来模拟这种行为。2.1.2基本原理蚁群算法（ACO）通过大自然生物的日常行为而衍生出的算法。一般在觅食过程中的蚂蚁，它们会将信息素留在其移动路径中。该信息素代表蚂蚁菌落的一般用途。如果其他蚂蚁感知通过信息素浓度的距离，他们将更有可能选择该路径[59]。这种大规模的行为表达了一种正向的反应模式，即选择此路径的蚂蚁数量越多，在此路线所分泌的信息素就越浓烈，然后其他蚂蚁就会在移动过程中移动。选择此路径的可能性更大。2.1.3蚁群算法的特点蚁群算法不同于传统的编程方法。它的优点是它不需要像传统的编程模式那样冗长的编程和计划工作。该程序本身是根据一些随机操作规则来找到最佳配置的。我们可以理解，当程序第一次执行时，找到的路径是最佳路径的可能性很小，并且可能有错误的选择和很长的计算时间[60]。但是，指的是蚂蚁在寻找食物时，该程序可以通过信息素原理不断修改原始路径，从而使整个路径越来越短。也就是说，如果在优化目标的过程中执行程序的时间更长，则找到的路径为“最佳路径”的可能性越大。这似乎与我们看到的过程相似，在此过程中，使用了许多示例来总结并形成最佳路径。2.2基于蚁群算法对原始策略进行求解2.2.1算法设计在该算法中模拟蚂蚁为配送车辆同时，模拟客户的需求点为食物，起始的出发点为蚁穴。蚂蚁每次进行觅食的过程中所产生的标记气味及道路信息计入tabuk中。设Pijk(T)表示第k只蚂蚁在T的时间节点由某个节点iij向kij某节点j进行觅食的几率，则Pijk(T)定义如下:ijij（2.1）式（2.1）中，allowk={1，2，…，N}蚂蚁在模拟觅食时，存在的重复路径及复合路径进行模拟运行，遇到重复路径时，对禁忌表进行及时更新并应用。α和β分别是算法中的两个重要参数，前者是信息素浓度的影响，后者为优先检验因素，表示提升算法的准确度。ηij(T)是算法公式，表示单个蚂蚁在觅食时的概率：（2.2）这里Lij表示起点到各个终点的路程，rij为该地区白天的路况系数。在算法运行时，信息素的效率程度尤为重要，则信息素优化公式为:（2.3）式(2.3)中，ρ信息素接受强度系数，Δτij(T)配送过程中信息素的变量。通常，在蚂蚁启动前的初始算法，对以下步骤进行模拟得到的，初始信息素的计算步骤如下：（2.4）（2.5）（2.6）在蚂蚁访问完上述所有路径后，对上述过程进行反复进行成对比较，以找到综合配送成本较小的路径，这是更好的路径。然后继续重复该循环，直到找不到更好的解决方案为止。2.2.2算法实现合理模拟产生一定数量的蚁群，让该蚁群中的个体从起点（配送中心）出发，进行模拟觅食（运输），并在返回时留下气味刺激信息得到最佳路线，每条路径的优化结果进行详细分析，重复并循环直到找到最佳解决方案。算法实现步骤为：Step1：初始化各个参数，令初始的距离数为0，原始运行次数为系统默认，设置最大运行次数为1000，原始的信息素记为常数C，信息素增量为默认值，定义和清空禁忌表；Step2：模拟M只蚂蚁进行模拟觅食了N条路径；Step3：开始循环计数Nco=Nco+1；Step4：令禁忌表索引号k=1；Step5：k=k+1；Step6：根据上述（18）的公式计算需求点经过的概率；Step7：比较每个路径的概率，选择最大的概率，并把此条信息录入禁忌表tabuk；Step8：如果k＜N，表示仍有需求点没被访问，则转到Step5，否则继续下一步Step9；Step9：计算得到总成本之和，并进行比较看是否最优Step10：如果迭代次数Nco＜maxNco，清空禁忌表、转至Step3，若否，则停止运算过程，输出具体结果。上述求解最优路径的算法流程图如图2.1所示。图2.1最优路径的算法流程图Figure2.1Algorithmflowchartofoptimalpath2.3考虑接驳点的农产品冷链配送优化模型2.1.1问题描述与模型假设根据上述模型的问题描述，当对整个城市进行配送时，单纯的基于道路的状态及基本最小成本进行优化时，得到的优化结果仍不是最佳的优化结果。以各个城市配送过程中设置接驳点为启示[61]。在城市冷链物流配送中，可以把某些用户需求点看做接驳点，冷藏配送卡车可以暂时停在接驳点，并将车辆上全部或部分农产品转移到一个或多个衔接卡车上，而接驳小车可以进行后续的冷链物流配送活动达到最后一公里的目标要求。含接驳方式的冷链配送示意图如图2.2所示。图2.2考虑接驳点的冷链配送示意图Figure2.2Coldchaindistributiondiagramconsideringtheconnectionpoint优化的目标是基于实时道路拥堵状况，现有分配资源，替代连接点，客户需求和需求时间窗口等构建数学模型，以建立数学模型，使用适当的算法，快速选择连接点，并找到一种分配策略：从新鲜农产品的冷链物流配送中心开始，安排冷藏送货车的出发顺序，出发规模，出发时间和行驶路线，以及接送时间，送货顺序，皮卡车的交付规模和行驶路线。中心或连接点开始为客户完成服务（需求点）后，所产生的总成本最佳。基于构建接驳点路径优化模型，在原始策略的基础上增加如下条件：（1）每个需求点都提供了送货服务，所需的新鲜农产品只能通过冷藏卡车或接驳点的小型货车来送货。如果激活了接驳点，则只有冷藏卡车可以停下来运送，并且冷藏卡车在接驳点处不等待（2）已知需求点，配送点，及所选择的接驳点三者的地图平面距离，满足几何不等式：dij≤dik+dkj；（3）忽略运输车辆在起始点的启动消耗时间，但计算该过程中到周转时间，运输到接驳点的泊车时间，及从专用冷链大车到接驳专用小车的装卸时间；（4）冷藏配送卡车在运输生鲜农产品的过程中始终可以保持农产品的安全存储温度，而与配送过程中冷藏卡车的温度变化无关。但是接驳的小型卡车采用隔热隔