基于改进蚁群算法的物流配送路径优化研究.doc

摘要 经济的快速发展，促成了物流产业的迅猛前进，物流配送中运输成本的至关 重要性使得人们不断寻求节约运输成本的方法，通过配送路线的优化来降低成本的 方法理所当然地成为了国内外学者研究的热点问题蚁群算法是i种仿生算法，是 受到生物界中蚂蚁的群体行为的启发并经过进一步研究得到的一种随机搜索方法， 它的鲁棒性较强，分布式特征使得算法可靠性和全局搜索能力都较强，而且该算法 还易于与其他方法相结合但是，该算法还存在两个突出的不足z处：搜索时间长、 易限入局部最优解本文通过对蚁群算法进行改进，在此基础上研究了两类不同运 输网络下的路径优化问题，主耍工作如下：(1)分析了国内外物流配送路径优化 问题以及蚁群算法的研究现状，说明了现在物流配送中存在的问题，反映了车辆路 径优化问题研究的必要性2)介绍了物流配送车辆路径优化问题的定义、分类、 常用的求解算法以及本文所建立的配送车辆路径优化模型说明了蚁群算法的儿种 经典的改进方式并提出本文的改进策略：对信息素挥发系数和能见度改进，以优化 算法的搜索能力，避免产生过早收敛与停滞现象3)基于配送运输网络完全连 通和不完全连通两类环境进行路径优化研究，对不完全连通网络设定用0・1矩阵来 表示节点间的连接关系，使用最短路径算法(Dijkstra矩阵算法)对数据进行预处 理，再结合改进的蚁群算法來进行求解，并在Matlab软件平台下通过编程用算例 验证了算法的有效性，解决了存在不直接相连的边的网络下的路径优化问题。

关键 词：物流配送；路径优化；蚁群算法；Matlab I ABSTRACT The rapid development of economy has contributed to the high-speed innovationof logistics industry and we have continually looked for the method oftransportation-cost reduction because of the great importance of transportation-cost inlogistics distribution as a result the way that decrease the cost by optimizingdistribution path has naturally became the hot issue researched by the scholars athome and abroad. Ant Colony AlgorithmACA is a kind of bionic algorithm and it is a randomsearch method obtained by inspiration and further study of biological group behaviorin ants moreover its high robust and distributed feature severely strengthen thereliability and global search capabilities which makes it a easily-combined method .However there are still two prominent defects one is the searching period it takes theother is that it is likely to be tripped in partial optimal solution. The paper have studied the optimization problems of the transport network undertwo different path by improving the Ant Colony Algorithm. The main work is asfollows: 1 Analysis of the optimization issue of domestic and international logistics anddistribution path and research status of Ant Colony Algorithm description of thepresent logistics distribution problems reflecting the necessity of researching on theVehicle Routing Problem • 2 Introduction of the definition classification common solving method anddistribution vehicle routing optimization model of the optimization of logistics anddistribution vehicle routing issue. Illustration of several classical improvement met hod and the proposition strategies of this paper: improving the pheromoneevaporation coefficient and visibility to optimize the searching ability which canavoid premature convergence and stagnation. 3 Study on CVRP under two types of distribution and transportation networkcircumstances one is fully connected the other is partially connected. As to thepartially connected network the paper has used a 0-1 matrix to indicate theconnection relationship between nodes and used the shortest path algorithm Dijkstramatrix algorithm to pre-process the data then obtained the solution with combiningthe improved Ant Colony Algorithm finally proved the effectiveness of the algorithm Illby programming under the Matlab software platformand realized the VRP in thenetwork with existence of non-directly connected edge. Key Words: Logistics Distribution Routing Optimization Ant Colony Algorithm Matlab IV H 录摘要 I AB STR ACT Ill 第究背景及意义究现状优化国内外研究现状状 技术路线 容 点 线 结 配送路径优化问题概述 知识 义 题 述 其要素分析 类 法 法 法 情况分析 结 群算法研究车辆路径优化问题 问题模型 的参数及其含义 图 进 System, AS) System, EAS) System, MMAS) 25ASrank) 26 3.3.5较 施 1 1.2国内外研 2 1.2.1物流配送路径 2 1.2.2蚁群算法国内外研究现 4 1.3本文的主耍研究内容、研究重难点及 6 1.3.1研究内 6 1.3.2本文研究的重难 6 1.3.3本文的技术路 7 1.4本章小 X第二章物流配送及 9 2.1物流配送相关理论 9 2.1.1物流配送的定 9 2.1.2物流配送中存在的问 9 2.2配送车辆路径优化问题概 102.2.1配送车辆路径优化问题描述及.10 2.2.2物流配送路径优化问题的分...11 2.3配送路径优化的方 12 2.3」精确算 13 2.3.2启发式算 13 2.3.3各种启发式算法研究 15 2.4本章小 15第三章 应用改进蚁 173.1配送车辆路径优化 173.1.1问题描 173.1.2参数变 183.1.3冃标函数及约朿条 19 3.2基本蚁群算 20 3.2.1基本蚁群算法中 21 3.2.2基本蚁群算法的流程 23 3.3蚁群算法的改 23 3.3.1蚁群系统（Ant 24 3.3.2 精英蚁群系统（ElifislAnt 25 3.3.3最大最小蚁群系统（Max・MinAnt3.3.4 排序蚁群系统（Rank・Based Ant System, 儿种改进的蚁群算法的比•……26 3.4本文对蚁群算法的改进及实 27 V 3.4.1对信息素挥发因子的改进进骤现结络亠31 3.5 28 3.4.2对启发函数（能见度）的改28 3.4.3改进后的蚁群算法的计算步30 3.4.4改进后的蚁群算法的Matlab软件实 本章小 32第四章两类运输网输网络图下的CVRP问题研究 述 析 CVRP问题研究 33 4.1 弓 | 33 4.2完全连通运.33 4.2.1问题描 33 4.2.2算法实现与结果分…・•34 4.3不完全连通运输网络图下的36 4.3.1问题描述析结望论点望献 37 4.3.2算法实现与结果分39 4.4本章小 43第五章结论与展 45 5.1主要结 45 5.2本文的创新 45 5.3局限与展45参考文 47附录 50附录 52附录四 54攻读学位期间发表学术论文及科研情况 59致谢 61 VI第一章 绪论 第一章 绪论1.1研究背景及意义21世纪，谁掌握了物流谁就掌握了市 场，充分说明了作为“第三利润源泉"的物流产业的重要性所在。

物流配送在整个物 流系统中有着不可替代的作用，而物流运输系统乂是物流配送系统中最重要的一个 子系统，加Z运输费用在企业物流总消耗中占较大比例，因此，降低物流成本首先 要从降低物流配送的运输成本开始近二十年來相关部门对于社会物流总费用的统 计显示，该费用的总体呈现出较高的增长趋势，1991年至2010年的物流总费用以 及运输费用具体情况对比如图1」所示（详细数据见附录一）8000（） 70000 60000 50000 40000管理费用 保管费用30000运输费用20000 10000 0 2007年2008年 1991 年 1992年 1993年 1994年 1995年 1996年 1997年 1998年 1999年 2000年。