下载文档原格式
基于改进蚁群算法的物流配送路径优化研究作者：夏鹏张玮来源：《科学与财富》2017年第12期摘要：本文首先通过对传统蚁群算法在物流配送路径优化问题中的研究，得出蚁群算法存在如收敛速度较慢、算法易陷于局部最优等缺点，进而对蚁群算法进行优化改进，使物流配送路径优化研究得到更好的解决。
关键词：蚁群算法物流配送路径优化一、引言互联网在不断地发展，这一时代慢慢兴起，网购逐渐走进我们的生活大当中。
伴随着网购而不断兴盛的就是物流行业。
物流行业越来越繁荣，对物流配送路径进行优化也显得尤为重要，因为这直接关系到物流行业的成本控制、盈利水平及配送效率。
调查显示，目前在我们国家物流行业的总成本一半以上花费在运输当中，这一项花费远远高于西方的一些发达国家。
在研究物流配送路径的时候，我们常将其归属于组合优化，即是一个NP完全问题。
研究过程中，针对路径优化人们经常会用到诸如方案评价法、动态规划法、遗传算法等各类方法。
不过就目前的一些研究而言，这些算法都存在着一定程度的缺点，并不是特别完美，比如遗传算法局部搜索能力不强，蚁群算法容易呈现停滞征象，等等。
现在的研究中，针对以往在物流配送路径优化方面的一些算法进行改进完善，以便于原有算法的所存在的缺点和不足之处能够得到弥补。
近些年来，受到生物进化展现出来的先进特点的启发，部分学者研究发现了一些像遗传算法、蚁群算法等的智能算法，并常常将这些算法运用到一些复杂优化问题中去。
在进行物流配送路径问题研究的时候，遗传算法具有收敛到全局最优的优点，不过在描述所求问题的约束条件时，这一算法往往表现的不尽如人意，而物流配送路径优化又是一种多约束问题。
和遗传算法一样，蚁群算法也是一种随机搜索算法，不过蚁群算法有其自身的优点，比如其能同时兼顾解的局部构造和整体性能，适合用来求解具有复杂约束条件以及解的组成元素之间关联性较强的优化问题。
二、蚁群算法与物流配送路径问题2.1 蚁群算法描述蚁群算法（ant colony optimization， ACO）是由意大利的著名学者Marco Dorigo最先提出来的，它是一种随机搜索算法。
基于改进混合蚁群算法的物流配送路径优化研究1. 引言1.1 背景介绍物流配送是现代社会中不可或缺的重要环节，随着电子商务的兴起和物流需求的增加，物流配送的效率和成本已经成为企业和个人关注的焦点。
传统的物流配送路径规划方法存在着路径较长、成本较高、效率较低等问题，因此急需一种高效、智能的优化方法来解决这些问题。
蚁群算法是一种模拟自然界蚂蚁觅食行为而提出的启发式算法，其具有全局搜索能力和分布式计算能力，能够有效地解决组合优化问题。
传统的蚁群算法在处理物流配送路径优化问题时容易陷入局部最优解，导致路径规划结果并不是最优的。
基于改进混合蚁群算法的物流配送路径优化研究具有重要的实际意义。
通过引入多种优化策略和算子，可以有效提高算法的全局搜索能力和收敛速度，从而得到更优的路径规划结果。
本文将研究混合蚁群算法在物流配送路径优化中的应用，提出改进的混合蚁群算法，并通过实验验证其有效性，为提高物流配送效率和降低成本提供技术支持。
1.2 研究意义物流配送是现代社会经济运作的重要环节，其效率和成本直接影响到企业的运营和客户的满意度。
针对物流配送路径优化问题，传统的优化算法存在着局限性，难以充分考虑到复杂的实际情况。
基于改进混合蚁群算法的物流配送路径优化研究具有重要的意义。
改进的混合蚁群算法通过引入新的启发式信息和更新策略，对传统的混合蚁群算法进行了优化和改进。
这种改进能够提高算法的搜索速度和收敛性，进一步提高物流配送路径的优化效果。
本文旨在研究基于改进混合蚁群算法的物流配送路径优化方法，旨在提高物流配送的效率和降低成本，具有重要的实际意义和实用价值。
1.3 研究现状目前，物流配送路径优化领域已经引起了广泛的关注和研究。
传统的物流配送路径规划方法多依赖于人工经验和规则，效率低下并且难以适应复杂多变的现实环境。
基于智能算法的路径优化方法逐渐受到重视。
近年来，研究者们提出了各种改进的蚁群算法，如混合蚁群算法，通过引入其他算法的思想和技术，使得算法具有更好的收敛速度和搜索能力。
基于蚁群算法的物流配送路径规划方法在现代物流中，物流配送路径规划是一个非常重要的问题。
随着网络购物的兴起，物流配送变得越来越复杂，如何优化配送路径是一个挑战。
蚁群算法是一种启发式算法，可以用来解决这个问题。
蚁群算法是模拟蚂蚁觅食路径的算法，它可以用来解决优化问题。
蚂蚁觅食时会释放一种信息素，其他蚂蚁会按照信息素的浓度选择前进方向。
在蚁群算法中，蚂蚁的行为被模拟成一组搜索路径的行为。
蚂蚁在搜索过程中会释放信息素，而其他蚂蚁会按照信息素的浓度选择前进方向。
通过不断的迭代，信息素会不断积累在最优路径上，其它蚂蚁也会更加倾向于选择最优路径。
这样，最终就能找到问题的最优解。
在物流配送中，我们可以把物流网络抽象成一个图，每个节点代表一个配送站点，每条边代表两个站点之间的配送路径。
我们可以通过蚁群算法来找到最优的配送路径。
首先，我们需要将每个站点看成一个节点，并记录它们之间的距离信息（即两个站点之间的配送距离）。
然后，我们需要确定一个合适的起点和终点，这样就可以根据这个起点和终点建立一颗搜索树。
每个节点都可以选择向下扩展到哪个节点，即向哪台车或者哪个配送站点配送。
每个节点都有一个信息素值，这个值可以根据节点所在路径的优异程度进行更新。
之后我们可以按照信息素浓度的大小来选择下一步的路径。
当所有的蚂蚁搜索完毕之后，我们可以更新所有节点的信息素。
这个过程会不断地迭代，直到找到一条最优路径。
蚁群算法有几个参数需要注意。
第一个参数是α，它的值决定了信息素挥发速度的大小。
当α=0时，信息素不会挥发，而当α=1时，信息素会立即挥发掉。
第二个参数是β，它的值决定了信息素浓度和距离的影响权重。
当β=0时，信息素浓度不会影响蚂蚁选择路径，而当β=∞时，只会根据最短路径来选择。
第三个参数是Q，它的值决定了信息素的量级大小。
当Q的值越大，信息素的影响力就越大。
在实际应用中，使用蚁群算法进行物流配送路径规划是非常有效的。
蚁群算法会通过不断迭代找到最优路径，这对物流配送效率提升有很大帮助。
蚁群有效的多物流配送选址算法因素在物流系统的运作中，配送中心的选址决策发挥着重要的影响。
配送中心是连接工厂与客户的中间桥梁，其选址方式往往决定着物流的配送距离和配送模式，进而影响着物流系统的运作效率。
因此，研究物流配送中心的选址具有重要的理论和现实应用意义。
本文对近年来国内外有关物流配送中心选址方法的文献进行了梳理和研究，并对各种方法进行了比较。
选址方法主要有定性和定量的两种方法。
定性方法有专家打分法、Delphi法等，定量方法有重心法、P中值法、数学规划方法、多准则决策方法、解决NP hard问题（多项式复杂程度的非确定性问题）的各种启发式算法、仿真法以及这几种方法相结合的方法等。
由于定性研究方法及重心法、P中值法相对比较成熟，因此，本文将主要分析定量方法中的数学规划、多准则决策、解决NP hard问题的各种启发式算法、仿真在配送中心选址中应用的研究状况。
数学规划方法数学规划算法包括线性规划、非线性规划、整数规划、混合整数规划和动态规划、网络规划算法等。
在近年来的研究中，规划论中常常引入了不确定性的概念，由此进一步产生了模糊规划、随机规划、模糊随机规划、随机模糊规划等等。
不确定性规划主要是在规划中的C(价值向量)、A(资源消耗向量)、b(资源约束向量)和决策变量中引入不确定性，从而使得不确定规划更加贴近于实际情况，得到广泛地实际应用。
国内外学者对于数学规划方法应用于配送中心的选址问题进行了比较深入的研究。
姜大元(2005)应用Baumol-wolf模型，对多物流节点的选址问题进行研究，并通过举例对模型的应用进行了说明，该模型属于整数规划和非参数规划结合的模型。
各种规划的方法在具体的现实使用中，常常出现NP hard问题。
因此，目前的进一步研究趋势是各种规划方法和启发式算法的结合，对配送中心的选址进行一个综合的规划与计算。
多准则决策方法在物流系统的研究中，人们常常会遇到大量多准则决策问题，如配送中心的选址、运输方式及路线选择、供应商选择等等。
基于改进混合蚁群算法的物流配送路径优化研究
随着物流行业的发展，物流配送路径的优化问题日益引起人们的关注。
但是，物流配
送路径优化问题本质上是一个NP难问题，传统的优化算法常常无法有效地解决这个问题。
为了解决这个问题，研究者们提出了各种各样的算法，其中蚁群算法是解决物流配送路径
优化问题的有效方法之一。
然而，传统的蚁群算法的局限性在于它容易陷入局部最优解，并且算法运行时间较长。
因此，本文提出一种基于改进蚁群算法的物流配送路径优化算法，以进一步提高算法的效
率和优化结果。
首先，本文构建了一个基本的物流网络模型，该模型包含各种物流节点和物流路径。
对于每个物流节点，本文选择了适当的参数表示节点的相关属性，例如节点的位置、需求量、送货时间等。
对于每个物流路径，本文选择了适当的参数表示路径的相关属性，例如
路径长度、路径拥堵程度等。
其次，本文提出了一种改进的蚁群算法，该算法结合了贪心和全局更新策略。
具体来说，每只蚂蚁将根据其当前位置和信息素浓度选择下一个节点。
然后，蚂蚁将在路径上留
下信息素，以便其他蚂蚁更有可能选择该路径。
在每次迭代后，全局信息素会被更新，使
得信息素浓度更加均衡。
最后，为了验证本算法的有效性，我们基于一个真实的数据集对该算法进行了测试，
并与其他优化算法进行了对比。
实验结果表明，本算法能够在更短的时间内获得更优的物
流配送路径，比传统蚁群算法具有更好的性能和效率。
基于改进蚁群算法的物流配送路径优化1童若锋2张维泽许星董金祥（浙江大学人工智能研究所，杭州310027）摘要：本文建立了带约束条件的物流配送问题的数学模型，运用蚁群算法解决物流配送路径优化问题，并将遗传算法的复制、交叉、变异等遗传算子引入蚁群算法，同时改进信息素的更新方式、客户点选择策略，以提高算法的收敛速度和全局搜索能力。
经过多次实验和计算，证明了用改进的蚁群算法优化物流配送线路，可以有效而快速地求得问题的最优解或近似最优解。
关键词：物流配送；路径优化；蚁群算法；蚁群系统Optimizing Logistic Distribution Routing ProblemBased on Improved Ant Colony AlgorithmRuoFeng Tong, Weize Zhang, Xing Xu, Jinxiang Dong(Institute of Artificial Intelligence, ZheJiang University, HangZhou 310027)Abstract: After constructing the expressions of the constraints in logistic distribution and building the mathematical model, this paper proposes an improved ant colony algorithm to solve distribution problem. Several genetic operators such as crossover and mutation are inducted into the ant colony algorithm, and pheromone updating strategy is ameliorated to improve the efficiency. The result of experiments demonstrates that the optimal or nearly optimal solutions to the logistic distribution routing can be quickly obtained by improved ant colony algorithm.Key words:logistic distribution; optimizing routing; ant colony algorithm (ACA); ant system (AS)1项目基金：本文受国家重点基础研究发展规划（973）项目（2002CB312106）和浙江省重大科技攻关项目（2005C13023）支持2作者简介：童若锋（1969.4-），男（汉族），浙江金华人，教授，博士，主要研究方向为CAD&CG等。
基于蚁群算法的物流优化策略随着物流行业的发展，物流优化已经成为了提高效率、降低成本和提升服务质量的关键。
而基于蚁群算法的物流优化策略正是一种新兴的方法，它可以通过模拟蚁群在寻找食物过程中的行为来寻找最优化的路径，从而帮助企业优化物流运输路线、减少成本和提高效率。
本文就将从蚁群算法的基本原理、在物流领域的应用以及优势和挑战等方面进行探讨。
一、蚁群算法的基本原理蚁群算法是一种仿生算法，它模拟了蚂蚁在寻找食物过程中的行为，通过蚂蚁之间释放信息素和寻找最优化路径来达到最优化的目的。
蚂蚁在寻找食物的过程中常常会留下一种化学物质，这就是信息素。
当蚂蚁发现食物后，它会释放出更多的信息素，而其他蚂蚁通过感知这些信息素来找到食物的位置。
随着时间的推移，更多的蚂蚁会选择最短的路径来获取食物，从而形成了一条最优化的路径。
蚁群算法将这种行为模拟成一个数学模型，通过不断迭代、更新信息素浓度和路径选择来求解最优化问题。
这种算法的优点是可以处理复杂的最优化问题，而且在寻找全局最优解时也有一定的效果。
二、蚁群算法在物流领域的应用在物流领域，蚁群算法可以应用于多个方面，比如路径规划、车辆调度、货物配送等。
它可以帮助企业优化物流运输路线，找到最短的路径以减少行驶距离和时间，从而降低成本。
它还可以帮助企业进行车辆调度，按照最优的方式来安排车辆的运输任务，提高运输效率。
它还可以应用于货物配送，通过优化配送路径来降低成本和提高服务质量。
三、蚁群算法的优势相比传统的优化方法，蚁群算法具有以下几个优势：1. 全局寻优能力强：蚁群算法可以寻找全局最优解，而不是局部最优解，这在处理复杂的物流优化问题时非常有优势。
2. 鲁棒性强：蚁群算法对于初始条件和参数的选择并不敏感，因此具有较强的鲁棒性，不易陷入局部最优解。
3. 可并行化：蚁群算法的并行性较强，可以快速地求解大规模的优化问题。
4. 简单易实现：蚁群算法的原理相对简单，易于实现和应用于实际的物流优化问题。
基于蚁群算法的物流配送优化研究随着互联网的快速发展，电商的崛起，物流配送也逐渐成为一个重要的话题。
高效的物流配送系统可以大幅缩短货物运输时间，降低物流成本，提升企业竞争力。
然而，如何实现这一目标，却是一个艰巨的挑战。
基于蚁群算法的物流配送优化研究，成为了当前的一项热门课题。
一、蚁群算法的概念蚁群算法是一种模拟蚂蚁群集在食物源之间搜索路径的算法。
它模拟了蚂蚁的行为，通过蚂蚁在空间中留下的信息素以及蚂蚁本身的搜索、移动、辨别等行为来寻找最优解。
在物流配送问题中，提供给蚂蚁的信息素包括地理位置、道路拓扑等基础信息，以及配送订单等业务信息。
对于每一个配送订单，蚂蚁根据任务的距离、紧急程度等信息决定路径和配送的优先级，以此实现效率最大化的配送策略。
二、蚁群算法的应用蚁群算法已被广泛应用于各种优化问题中，如TSP（旅行商问题）、VRP（车辆路径问题）、FJSP（柔性作业车间调度问题）等。
在物流配送中，蚁群算法主要应用于：1、配送路径规划传统的配送路径规划方法往往基于启发式算法或运筹学等理论，它们尝试通过给定的约束条件生成一组可接受的配送路线。
但实际配送问题往往具有极其复杂的业务约束，使得制定一种可行的算法变得异常困难。
而蚁群算法在此方面表现出色，它可以很好地处理高度复杂的路径规划问题，通过大量迭代和试错来求解最优解。
2、车辆调度在物流配送中，车辆调度是一项非常重要的工作。
由于客户需求的不同，每个车辆的负载量、行驶距离以及配送耗时都必须考虑到。
在传统的车辆调度算法中，往往采用“分区贪心法”或“遗传算法”等方法，但它们都可能会导致调度的不确定性。
而蚁群算法则可以在保证配送质量的同时，实现车辆调度的高效性。
3、全局多目标优化物流配送本质上是一种复杂的全局多目标优化问题。
在许多情况下，如何在达到最佳配送质量的同时，最大化配送效率，是物流配送中需要解决的难点。
而蚁群算法则可以帮助企业实现可持续发展，通过动态调整配送策略，不断提高配送质量的同时，实现物流成本的最小化。
2006年4月系统工程理论与实践第4期 文章编号:100026788(2006)0420120205基于蚁群优化的多物流配送中心选址算法秦 固(深圳职业技术学院经济管理学院,深圳广东518055)摘要: 提出了一种解决多物流配送中心选址问题的蚁群算法模型,该模型将物流配送中心选址映射成一个聚类过程,利用蚁群系统中蚂蚁通过信息素寻找最优路径的机制,以物流配送的总成本最低为聚类准则,结合蚂蚁将物体聚堆的行为模式来定义蚂蚁的转移概率、禁忌列表和信息素更新方式,实现基于蚁群优化的物流配送中心选址算法.对多配送中心选址进行了仿真实验,实验结果表明本算法能获得与实际情况相符的配送中心最优解,且适合多种不同的配送中心模型和大规模的配送中心选址,具有较强的灵活性.关键词: 物流;配送中心选址;蚁群算法;智能优化中图分类号: F525;TP18 文献标识码: A Logistics Distribution Center Allocation Based on Ant C olony OptimizationQI N G u(School of Economics and Management,Shenzhen P olytechnic,Shenzhen518055,China)Abstract: A new m odel is proposed for logistics distribution center allocation based on the ant colony optimization inthis paper.Inspired by the ability of real ants to find the shortest path through the laying down of pherom one and tocluster corpse in the nest,we mapped the problem of the logistics distribution center allocation to the process ofclustering objects with emphasis on the lowest logistics costs and appropriately designed the transition probability,thetabu list as well as the way pherom one was updated.A detailed logistics distribution center allocation alg orithm basedon the ant colony optimization is experimented and the experimental results show that the new alg orithm can acquire theoptimal s olution that is accord with the practice,M oreover,the new alg orithm has much m ore flexibility which adapts tomany kinds of logistic distribution m odel and large2scale logistic distribution center allocation.K ey w ords: logistics;distribution center allocation;ant colony alg orithm;intelligent optimization1 引言在物流系统分析与设计时,物流配送中心选址需要模型化、数量化,合理地选择配送中心地点能够减少货物运输费用,降低运营成本,也会消除不同城市或同一城市的不同地点的地价差别带来的负面影响,降低建造成本,促进生产和消费两种流量的协调与配合,保证物流系统的平衡发展.基于配送中心及其位置的重要作用,大量科研人员对这一问题开展了研究工作,建立了一系列的选址模型与算法,如重心法、数值分析法、线性规划法和启发式算法等[1～3].其中重心法和数值分析法主要用于单一配送中心选址模型;线性规划法和启发式算法主要用于多个配送中心选址模型,但线性规划法在解决选址问题时对目标函数的“线性”要求严格,启发式算法虽然克服了线性规划的不足,但对规模较大的实际问题求解比较困难.近年从生物进化机理中受到启发而发展起来的一些智能计算新方法,如遗传算法[4]、蚁群算法[5,6]等,常用于解决一些复杂优化问题.遗传算法应用在物流配送中心选址上虽具有收敛到全局最优的能力,但对所求解问题的约束条件的描述能力较差,而配送中心选址模型又属于多约束问题.蚁群算法与遗传算法一样同属于作为一种随机搜索算法,但蚁群算法是以构造解的方式搜索整个解空间,能同时兼顾解的局部构收稿日期:2005206210资助项目:广东省社会科学“十五”规划课题(03104L04):“‘珠三角地区’物流园区运作模式研究”基金资助 作者简介:秦固(1974-),男(汉族),重庆市人,讲师,大连海事大学交通信息工程及控制专业硕士毕业.造和整体性能,适宜求解具有复杂约束条件以及解的组成元素之间关联性较强的优化问题.本文提出了一种基于蚁群优化的物流配送中心选址算法,该算法在建立的物流配送模型的基础上,将物流配送中心选址问题看成一个聚类过程,利用蚁群系统中蚂蚁通过信息素留存寻找最优路径的机制,结合蚂蚁使物体聚堆的行为模式,合理设计转移概率、禁忌列表及信息素更新方式,把使系统成本最低的配送点和配送中心聚为一类,从而确定配送中心的位置、规模和配送中心的数量.2 多物流配送中心选址模型的建立从现代物流发展的趋势看,为了加速商品的流通,更好地使物流系统顺应客户需求的特点,物流配送中心逐渐从周转型转向分销型,因此在本文中以对多个分销型的配送中心选址为研究对象[7],物流配送总成本包括配送运营成本(含配送中心到配送点的运输成本和工厂到配送中心运输成本)和配送中心建造成本.配送中心选址问题描述为在有限的位置(m 个)中选择一定数量的地点(p 个),以合理的规模建立配送中心,为n 个配送点配送物品,使得在选出点建立的配送中心在满足配送需求的前提下,成本(包括建造成本和运营成本)最低.设第i 个配送点的坐标为(x i ,y i ),需求量为a ij ;工厂的坐标为(Z x ,Z y );配送中心候选位置有m 个,其中第j 个配送中心候选位置的坐标为(X j ,Y j ),s ij =(x i -X j )2+(y i -Y j )2为配送中心j 到配送点i 的距离,d j =(Z x -X j )2+(Z y -Y j )2为工厂到配送中心j 的距离,则配送中心j 的运营成本为:f j =∑n i =1a ij ×s ij ×k +d j ×∑ni =1a ij ×k ,(1)其中k 为运费率.假定配送中心的用地面积与配送量成正比,且配送中心位置不同地价等建设成本不同,因此设配送中心j 每单元配送规模所需的成本为h j ,则配送中心j 的建造成本为:g j =∑ni =1a ij ×h j (2)配送中心选址依据系统总成本D =∑m j =1(f j +g j )最小.3 蚁群优化算法Dorig o 和Denebourg 等人分别受蚂蚁寻找食物的行为和蚂蚁聚集尸体的模式的启发,提出了两类不同的蚂蚁算法模型———基于路径寻优的蚁群算法和基于聚类的蚁群算法,下面简要介绍这两类蚁群算法及其工作原理.311 基于路径寻优的蚁群算法[8]以经典的TSP 问题来说明基于路径寻优的蚁群算法的基本原理.TSP 问题就是在n 个城市中找到从城市i 到城市j 之间的最短距离.假设m 为蚁群中蚂蚁的数量,τij (t )为t 时刻路径(i ,j )上的信息素强度,在初始时刻各条路径上信息素数量相等,蚁群算法的寻优就是每只蚂蚁在移动过程中借助信息素更新准则τij (t +h )=ρτij (t )+Δτij 调整路径上的信息素强度和转移概率准则p kij (t )=ταij ηβij∑s |tabu k ταis ηβsj ,j |tab u k 0,otherwise. 调整蚂蚁的路径方向,使每只蚂蚁依据信息素强度经过n 次移动完成一次循环,所有蚂蚁走过的最短封闭路径就构成了TSP 问题的解.其中Δτij 表示路径ij 上的信息量的增量,ρ表示路径上信息素的保留程度;p kij (t )表示由i 城市到j 城市的转移概率,ηij 表示由城市i 转移到城市j 的期望程度,称为启发式因子,α、β分别表示第k 只蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用,tabu k (k =1,2,…,m )用来记录蚂蚁k 当前所走过的城市,并随时间做动态调整.121第4期基于蚁群优化的多物流配送中心选址算法可见基于路径寻优的蚁群算法就是通过m个蚂蚁间的信息交流与相互协作,即单个蚂蚁在自己行走的路径下留下信息激素,后来的蚂蚁根据前进道路上信息数量的多少选择前进方向,在经过一个长的过程后,在较短路径上蚂蚁留下的信息激素的量变得较多,最终找到从蚁穴到食物源的最短路径.312 基于聚类的蚁群算法[9]该算法主要思想是:一只随机移动的无负载蚂蚁在遇到一个物体时,周围与这个物体相同的物体较少,则拾起这个物体的概率越大;一只随机移动的有负载蚂蚁如果周围的与所背负物体相同的物体越多,则放下这个物体的概率越大.该模型主要通过以下三个参数来控制完成:1)各物体之间的相似函数f,该函数的选取必须由实际解决的问题来决定;2)拾起概率p p=[k1Π(k1+f)]2,其中k1为门限常数;3)放下概率p d=[fΠ(k2+f)]2,其中k2为另一门限常数.可见该模型通过对单只蚂蚁拾起、放下物体的行为模式进行建模,保证了不破坏大堆的物体,且能收集小堆的物体,完成了物体的聚类.与基于路径寻优的蚁群算法不同,在该模型中,蚂蚁依据聚堆的形状与所聚集的物体来决定选择放下背负的物体或者拾起零散的物体的概率,从而完成物体的聚类.4 基于蚁群算法的多物流配送中心选址通过对两种蚁群算法的简述,可以看出蚁群算法本质上是一个利用全局信息作为反馈的正反馈过程,在这个过程中通过对系统演化过程中较优解的正反馈机制,使得问题的解向着全局最优的方向不断进化,最终能有效地获得相对较优的解,解决全局最优化问题.物流系统中的多配送中心选址问题本质上就是一个多目标的最优化问题,但基于路径寻优的蚁群算法解决的是单目标问题,因此不能简单的套用基于路径寻优的蚁群算法模型.另外,单纯的采用基于聚类的蚁群算法又使待优化问题复杂化,即很难确定各类之间的相似函数.因此本文提出了一种基于聚类思想的结合蚁群路径寻优算法的多配送中心选址算法.算法的基本思路是将配送中心选址看成聚类问题,将多个候选配送中心当成聚类中心,各个配送点看作待分类量,目标就是利用多只蚂蚁以配送中心选址模型的系统成本最低为依据将各个配送点分配到配送中心,形成多个胞腔,若以配送中心为聚类中心的胞腔中不为空(即胞腔中含有配送点),则保留该配送中心;若胞腔为空(即胞腔中不含有配送点)则该配送中心是多余的,予以去除,从而确定配送中心的地址和数量.具体算法如下所示:1)设有r只蚂蚁,初始化蚁群算法中的几个关键参数α、β和ρ,并初始化能见度函数ηij =1d ij,if d ij≠01,if d ij=0,(3)其中dij 表示配送点i和配送中心j的距离,ηij表示了配送点i和配送中心j聚为一类的期望程度;2)设置禁忌搜索表tab u k(t),用以记录在[t,t+1]时间内蚂蚁k已经拾起过的配送点列表,并清空禁忌搜索表;3)以候选配送中心为蚂蚁的蚁巢中心z j(j=1,2,…,m);4)各蚂蚁以蚁巢中心为中心,在允许的配送点中随机选择一配送点,将该配送点以概率p k ij(t)放入蚁巢中心zj中,并将该配送点放入禁忌表内.若禁忌表满,则转步骤5),否则重复步骤4).其中概率p k ij(t)=ταijηβij∑s|tabukταisηβsj;j|tab u k0;otherwise.(4) 5)记录第k只蚂蚁的信息增量ΔτkijΔτkij =1E k,E K=∑mj=1f j+∑mj=1g j.(5)221系统工程理论与实践2006年4月蚂蚁完成一次循环记录分类结果;6)若r 只蚂蚁都完成了一次循环则转步骤7),否则转步骤2);7)更新信息量τij (t +h )=ρτij (t )+Δτij ,Δτij =∑mk =1Δτk ij .(6)并记录最优解;8)满足收敛条件则停止算法,输出最优解;否则转步骤2).收敛条件为连续多次物流配送成本未有改善.在这个算法中的一个关键问题就是算法参数的适当选取,从式(4)中可以看出,α值的大小表明了某配送点聚到任一个配送中心之间的信息量受重视的程度,其值越大蚂蚁将其聚为同一类别的可能性越大,不过α值过大会导致搜索过早限于局部最小点.β值的大小则反映了启发式信息受重视的程度,在算法运行初期起主要作用,和α值的选取存在一个折中.另一方面参数ρ表示信息的保留程度,其大小会影响算法的收敛速度与搜索效果,过大则信息量“挥发”过慢,算法很容易在较短时间内停滞;过小则信息量“挥发”过快,导致过去较好的结果未能充分予以利用.本文通过大量的实验仿真确定相应的参数,图1是本算法中的三个参数对算法性能的影响曲线,从曲线图中可以看出选取α=113,β=1,ρ=0195是较合理的选择.不失一般性假设算法收敛终止条件为连续多次物流配送成本未有改善.图1 不同参数取值对算法的影响曲线5 实验仿真及分析为了验证本算法的正确性,在Matlab 平台上对其进行了仿真实验.设有一物流配送矩形区域,范围为(0,0)到(100,100),其中散布10个配送点,配送点坐标和需求量如表1所示.有4个候选配送中心,其坐标和地价如表2所示.运费率为1,工厂坐标为(54,48),用本文算法得最后结果如表3所示.表1 配送网络中的配送点情况表配送点12345678910坐标(x ,y )(25,80)(30,23)(70,60)(92,51)(42,64)(87,45)(39,7)(28,71)(55,20)(14,56)需求量 1.50.60.5 2.00.7 1.4 1.0 2.0 3.0 1.0从表3可见,候选配送中心3是空胞腔,因此候选中心3是多余的,这和传统的多物流配送中心选址算法得到的结果是一致的,证明本算法模型是正确的.另外本算法不仅能确定配送中心的位置、数量,同时也能确定各个配送中心的规模,如配送中心1的规模为配送点1、5、8、10的需求量.且本算法本质上是一种并行算法,不仅能克服传统算法的局限性,解决大规模的多物流配送中心选址问题,还具有很好的灵活性,适合更加复杂的物流配送中心选址模型,如在配送中心选址模型中需要考虑管理成本,只需在信息素更新的失真函数中加入管理成本项即可,不需改变整个算法,适合现今多样的物流配送模型.321第4期基于蚁群优化的多物流配送中心选址算法表2 配送网络候选配送中心分布表配送中心1234坐标(23,74)(88,46)(72,90)(45,16)地价 1.3 1.20.9 1.5表3 配送中心选址方案配送中心1234所供配送点(1,5,8,10)(3,4,6)()(2,7,9)配送规模 5.2 3.90.0 4.66 结论物流配送中心选址是一个成功物流系统的关键环节,本文将物流配送中心选址优化模型映射成一个聚类过程,以物流配送总成本最低为聚类准则,结合蚂蚁的聚堆行为模式,将蚁群算法应用到物流配送中心选址问题.由于蚁群算法自身所具有的鲁棒性和较高的计算效率,适于进行并行计算,对于解决大规模、复杂的物流配送网络具有很大的实用价值.且本算法有很强的灵活性,只需根据不同的物流配送模型修改相应的信息素更新中的失真函数,就能适合现今多样的物流配送的发展.参考文献:[1] Y uan Y axiang.A scaled central path for linear programming[J].Journal of C omputational Mathematics,2001,19(1):35-40.[2] K onstantinos G Z,K onstantinos N A.A heuristic alg orithm for s olving hazardous materials distribution problems[J].EuropeanJournal of Operational Research,2004,152:507-519.[3] Zhang Qian,G ao Liqun.A tw o2phase heuristic approach to the location routing problem[J].C ontrol and Decision,2004,19(7):773-777.[4] Qian Jing,Pang X iaohong,Wu Zhiming.An improved genetic alg orithm for allocation optimization of distribution centers[J].Journalof Shanghai Jiaotong University(Science),2004,E9(4):73-76.[5] D orig o M,G ambardella L M.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEET rans.on Ev olutionary C omputation,1997,1(1):53-66.[6] Wen Y u,Wu T iejun.Real2time rolling horizon optimization of urban traffic con troll based on ant alg orithm[J].C ontrol andDecision,2004,19(9):1057-1063.[7] Liu Zhingqiang,Ding Peng.Design of Logistics Distribution System[M].Beijing:Tsinghua University Press,2004,2.[8] Deneubourg J L,G ross S,Franks N,et al.The dynamics of collective s orting robot2like ants and ant2like robots[A].Proceedings ofthe1st C on ference on S imulation of Adaptive Behavior[C].1990:356-363.[9] D orig o M,Maniezzo V,C olomi A.Ant system:Optimization by a colony of cooperating agents[J].IEEE T rans on Systems,Man andCybernatics,1996,26(1):28-41.421系统工程理论与实践2006年4月。
