《基于改进蚁群算法的物流配送路径优化》由会员分享，可在线阅读，更多相关《基于改进蚁群算法的物流配送路径优化（16页珍藏版）》请在金锄头文库上搜索。
1、基于改进蚁群算法的物流配送路径优化 项目基金：本文受国家重点基础研究发展规划（973）项目（2002CB312106）和浙江省重大科技攻关项目（2005C13023）支持童若锋 作者简介：童若锋（1969.4-），男（汉族），浙江金华人，教授，博士，主要研究方向为CAD&CG等。E-mail：。 张维泽 许星 董金祥（浙江大学人工智能研究所，杭州 310027）摘要：本文建立了带约束条件的物流配送问题的数学模型，运用蚁群算法解决物流配送路径优化问题，并将遗传算法的复制、交叉、变异等遗传算子引入蚁群算法，同时改进信息素的更新方式、客户点选择策略，以提高算法的收敛速度和全局搜索能力。经过多次实验和
2、计算，证明了用改进的蚁群算法优化物流配送线路，可以有效而快速地求得问题的最优解或近似最优解。关键词：物流配送；路径优化；蚁群算法；蚁群系统Optimizing Logistic Distribution Routing Problem Based on Improved Ant Colony AlgorithmRuoFeng Tong, Weize Zhang, Xing Xu, Jinxiang Dong(Institute of Artificial Intelligence, ZheJiang University, HangZhou 310027)Abstract: After con
3、structing 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 pher
4、omone 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; an
5、t colony algorithm (ACA); ant system (AS)1 引言物流配送路径优化问题1是典型的组合优化问题，属于一类NP完全难问题，具有很高的计算复杂性。随着市场经济的繁荣，物流配送业迅猛发展，越来越多的企业看到了物流配送在企业生产销售流程中的重要作用。传统的手工配送路线选择完全是依靠劳动者的经验和智慧，需要耗费很多的时间和精力。随着企业规模的逐渐壮大，业务规模也不断扩大，配送网点的数量也逐渐增多，安排配送路线的复杂度越来越高，手工安排配送线路已经很难满足企业的业务需求，采用计算机进行路线安排势在必行。求解配送路径优化问题的方法很多，常用的有旅行商法、动态规划法、节约
6、法、扫描法、分区配送算法、方案评价法等。这些算法虽然能够解决此类问题，但也存在一定的缺陷，节约法的组合点零乱、边缘点难以组合的问题，扫描法非渐进优化等2。如何针对物流配送路径优化问题的特点，构造运算简单、寻优性能优良的启发式算法，是一个值得深入研究的课题。近年来遗传算法、禁忌搜索算法3等都在此问题上进行了运用，并取得了成功2, 4, 5。但也存在各自的问题，如遗传算法局部搜索能力不强，总体上可行解的质量不是很高6，禁忌搜索算法对于初始解具有较强的依赖性3等等。目前研究的热点是混合算法6, 7，通过混合在一定程度上弥补算法的缺陷。蚁群算法是受到人们对自然界中真实蚁群的集体行为的研究成果的启发而在
7、近年来提出的一种基于种群的模拟进化算法，属于随机搜索算法，由意大利学者M. Dorigo8, 9等人首先提出。M. Dorigo等人首次提出该方法时，充分利用了蚁群搜索食物的过程与著名的旅行商问题（TSP）之间的相似性，通过人工模拟蚂蚁搜索食物的过程（即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP。蚁群算法可用来解决各种不同的组合优化问题，特别适合于在离散优化问题的解空间进行多点非确定性搜索，如旅行商问题（TSP）、二次分配问题（QAP）、作业安排调度问题（JSP）等等；此外在通信网络负载问题和水科学10等应用研究中也被广泛应用。它具有通用性和鲁棒性，是基于总
8、体优化的方法。蚁群算法原型本身就是一个寻找最短路径的模型，因此它在路径优化方面有着天然的优势，目前已经有不少蚁群算法在TSP问题中成功运用的例子，如Ant-Q11、MMAS12等。物流配送路径优化问题和TSP问题相比有共同点都是寻找遍历所有客户点的最短路径的问题，也有其特性有更多更复杂的约束条件和优化目标。本文就是针对这种特点，研究一种基于蚁群算法的优化路径算法，通过引入遗传算子，在局部搜索过程中能够避免算法早熟、停滞，同时改进信息素的更新方式、客户点选择策略，增强蚁群算法的正反馈作用，从而提高收敛速度和全局搜索能力，使得其在物流配送路径优化问题中有较好的实际效果。2 物流配送的数学模型2.1
9、 问题的描述一般配送路径问题可描述如下：有L个客户点，已知每个客户点的需求量及位置，至多用K辆汽车从配送中心到达这批需求点，并且在完成配送任务后，返回物流中心，每辆汽车载重量一定。要求安排车辆行驶线路使得运输距离最短，且满足以下几个约束条件：1) 每条线路上的客户点需求量之和不超过汽车载重量；2) 每条配送路径的总长度不超过汽车一次配送的最大行驶距离；3) 每个客户点的需求必须且只能由一辆汽车来完成。其目的是使总成本（如距离、时间等）为最小。2.2 数学模型的建立2.2.1 符号的定义L：客户点总数；qi：客户点i的货物需求量，其中i=1，2，L；dij：从客户点i到客户点j的距离。特别的，当
10、i，j=0时，表示配送中心，例如：d0,3表示从配送中心到客户点3的距离，d2,0表示从客户点2到配送中心的距离。i，j=0，1，2，L；K：车辆的总数；Qk：车辆k的最大装载量，其中k=1，2，K；Dk：车辆k的最大行驶距离，其中k=1，2，K；nk：车辆k配送的客户总数，当nk=0时，表示车辆k没有参与配送。k=1，2，K；Rk：车辆k配送的客户点的集合。当nk=0时，Rk=；当nk0时，其中rki表示该客户点在车辆k的配送线路中顺序为i。k=1，2，K。2.2.2 约束条件根据前文对物流配送路径优化问题的描述，我们可以提取出以下几个约束条件：1) 每条线路上的客户点需求量之和不超过汽车载
11、重量：，nk02) 每条配送路径的总长度不超过汽车一次配送的最大行驶距离：， nk03) 每个客户点的需求必须且只能由一辆汽车来完成：，k1k24) 配送线路遍历所有客户点：2.2.3 优化目标根据本文中物流配送路径优化问题的优化目标，我们列出优化目标的数学形式：3 优化配送路线的蚁群算法3.1 基本蚁群算法蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法。它是从对蚁群行为的研究中产生的。蚁群中的蚂蚁以“信息素”（pheromone）为媒介的间接的异步的联系方式是蚁群算法的最大的特点。蚂蚁在行动（寻找食物或者寻找回巢的路径）中，会在它们经过的地方留下一些化学物质（我们称之为“信息”
12、）。这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后到者的行动（具体表现在后到的蚂蚁选择有这些物质的路径的可能性，比选择没有这些物质的路径的可能性大得多），而后到者留下的信息会对原有的信息素进行加强，并且如此循环下去。这样，被越多蚂蚁选择的路径，在后到蚂蚁的选择中被选中的可能性就越大（因为残留的信息浓度较大的缘故）。由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因而积累的信息量也就越多，在下一个时间内被其他的蚂蚁选中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路径为止。我们用人工蚂蚁代替车辆对客户点进行配送，蚂蚁在i客户点选择服务的下一个客户点j时，主要考虑
13、两个因素，一是i，j两顾客点之间的关系的亲密程度，称为可见度，记为hij；另外考虑的是由迄今完成的循环所得路径方案体现出来的由i到j的可行性，即信息素浓度tij。在t时刻蚂蚁k由客户点i转移到客户点j的概率：其中，allowedk=0,1,n-1-tabuk表示蚂蚁k尚未服务的客户点。可见度当下一个要服务的客户点会使运载总量超出汽车载重量，或者使运距超过一次最大行驶距离时，就返回到配送中心，人工蚂蚁代表下一辆车出发，继续配送。当一次循环结束后，蚂蚁遍历了所有客户点，完成一次配送。当所有蚂蚁完成一次循环后，根据各蚂蚁遍历的好坏（目标函数值），计算信息素增量，更新相关路径上的信息素，更新规则：3.
14、2 蚁群算法的改进3.2.1 遗传算法对蚁群算法的改进遗传算法的操作算子是遗传算法的核心内容，我们将复制、交叉、变异这些遗传算子引入蚁群算法中，以提高算法的收敛速度和全局搜索能力。复制遗传算法中，复制的主要思想是认为父代中的优质个体可能更接近全局最优解，应该在子代中继承并继续进化。复制操作使得父代中优质的个体能够在子代中得以保存，避免交叉变异等操作导致优质个体在种群中丢失。蚁群算法中，在每一代搜索完成后，我们将当前父代中最优的解复制到子代中，使得最优的个体能在子代中继续积累信息素，这样能加快算法的收敛速度。编码遗传算法中的交叉和变异操作是建立在基因编码上的，因此在引入交叉和变异操作之前，我们首
15、先对物流配送模型进行编码。假设有L个客户点，K辆配送车辆，本文采用的编码方式是将这L个客户点分别用1到L这L个自然数标识；第一辆车从配送中心出发时用0标识，其他车辆则分别用L+1，L+2，L+K-1表示。由于同一辆车可以多次配送，所以，2次以上配送的车辆出发时，依次用L+K，L+K+1，表示。新的一辆车从配送点出发，或者编码结束，就表示前一辆的路线结束，返回配送中心。这样就将一次配送表示为一组由0和自然数组成的编码。例如，有6个客户点，我们分别用1至6表示，3辆车负责，那么编码：0，1，2，3，7，4，5，8，6表示3辆车的配送线路分别是：车辆101230，车辆20450，车辆3060。又如编码：0，1，2，3，8，4，5，9，6表示的配送线路为：车辆101230，车辆30450，车辆1第二次配送060。交叉交叉操作是遗传算法中增加种群多样性，防止算法早熟、停滞的操作。在蚁群算法中引入交叉操作，可以有效地扩大搜索空间，避免算法陷入局部最优解。在蚁群算法每一代搜索完成之后，我们将其中的最优解和次优解进行编码交叉操作，交叉规则如下：1) 假设两组编码分别是S1和S2，首先随机生成交叉段的长度和交叉段起始位置；2) 找出
