《基于蚁群算法的物流车辆路径优化问题的研究》由会员分享，可在线阅读，更多相关《基于蚁群算法的物流车辆路径优化问题的研究（65页珍藏版）》请在金锄头文库上搜索。
1、 -I - 基于蚁群算法的物流车辆路径优化问题的研究 基于蚁群算法的物流车辆路径优化问题的研究 摘 要 配送车辆路径优化，是物流系统优化中关键的一环。对配送车辆路线进行优化，可以提高经济效益、实现物流科学化。对配送车辆线路优化的理论与方法进行系统研究是物流集约化发展、 构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。 蚁群算法是受自然界中真实蚁群觅食行为的启发而提出的一种模拟进化算法，在求解 VRP(Vehicle Routing Problem，车辆路径优化)等组合优化问题上取得了很好的效果。本文研究的主要目的，就在于改进已有的蚁群算法，使之适合不同类型的车
2、辆路径优化问题，得到质量更好的解。本文主要完成以下几方面的工作： 第一， 详细介绍了物流系统中车辆路径优化问题， 对 VRP 问题进行了分类，并说明了各自的涵义、限制条件及应用范围，在吸取现有研究成果的基础上，对有容量限制的车辆路径优化问题(Capacitated Vehicle Routing Problem, CVRP)进行建模，并阐述了用于解决 VRP 问题的各种优化方法。 第二， 深入讨论了蚁群算法的基本原理，建立了数学模型，包括转移概率的计算、信息素更新的各种规则、参数的取值范围等。并从解的质量、时间/空间复杂度、实现难度、算法的优点及不足之处等各项指标对蚁群算法进行全面的分析，并以
3、 TSP(Travelling Saler Problem，旅行商问题)为例，介绍了蚁群算法在路径优化问题领域的应用。 第三， 针对有容量限制的车辆路径优化问题 CVRP，改进基本蚁-II - 群算法，采用确定性选择和随机选择相结合的选择策略，以及基于吸引力的信息素更新规则，大蚂蚁数策略、蚂蚁初始分布均匀策略、 近似解可行化策略得到 CVRP 问题的可行解。 第四， 针对带时间窗的车辆路径优化问题(VRP with Time Windows, VRPTW)，建立其数学模型，并对已有蚂蚁算法加以改进， 包括新的路径构造选择策略、 信息素局部更新、基于 2-opt 法的局部优化、信息素全局更新等因
4、素，利用近似解可行化策略，整合了可行解分支的三种类型，并对遗漏客户点做了归属处理，克服了基本蚁群算法在VRPTW 模型下可能得到非可行解的问题。 关键词：车辆路径优化，蚁群算法，信息素，CVRP，VRPTW -III - VEHICLE ROUTING OPTIMIZATION PROBLEMS IN LOGISTICS BASED ON ANT COLONY ALGORITHM Abstract Vehicle routing optimization in logistics is one of the most critical parts in logistics. It can im
5、prove the economic benefit and realize the scientific process of logistics. The study of vehicle scheduling optimization theory and method definitely has its significant importance. It can enhance the intensive development of logistics; construct integrated logistics system and modern scheduling sys
6、tem of command; develop intelligent traffic transportation system and be a basic platform of electronic business. Ant colony algorithm is a new fuzzy logic algorithm enlightened by the foraging behavior of ants. Great effects have been achieved by applying this ant algorithm to vehicle routing probl
7、em. The main theme of this thesis is to improve the existing ant algorithm and make it suitable to various kinds of vehicle routing optimization problem and gain high quality results. The main tasks are the following four aspects: 1. Give a specific description of VRP, classifies it and gives out th
8、e meaning, limitation and application scope. Then, establish a model for the VRP with capacity limitation and expatiate a number of solving methods. 2. Make further study of basic principle of ant algorithm, overall analysis and set up mathematic model for it, including transfer -IV - probability ca
9、lculation, time and space complexity, realization problem, advantages and disadvantages and so on. 3. Conduct a deep research on capacitated vehicle routing problem, and present an improved ant colony algorithm to solve it. In this method, we adopt the strategy combined defined selection and random
10、selection, big ant number strategy, mean initial distributing method and a strategy of feasible approximate solution and so on. So we can get the feasible solutions of the CVRP problem. 4. Study the VRP with time windows and establish its mathematic model. Then we present an improved ant colony algo
11、rithm, including the new selection strategy of the construction path, local pheromone update method, and local optimization based on 2-opt method, global pheromone update method and so on. A strategy of feasible approximate solution is put forward. In the strategy, three types of branch circuits are
12、 established and the ownership of skipped clients is processed to make sure a feasible solution is created in each time of iteration. In this way, feasible solution is created in each time of iteration. KEY WORDS: Vehicle Routing Problem, Ant Colony Optimization Algorithm, Pheromone, CVRP, VRPTW 上海交
13、通大学上海交通大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：于芹 日期：2008 年 2 月 18 日 上海交通大学上海交通大学 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查
14、阅和借阅。 本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 保密，在 年解密后适用本授权书。 本学位论文属于 不保密 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 于芹 指导教师签名：翁正新 日期： 2008 年 2 月 18 日 日期： 2008 年 2 月 18 日 -1 - 第一章 绪论 第一章 绪论 1.1 物流行业发展现状 物流行业发展现状 1.1.1 现代物流的经济地位现代物流的经济地位 伴随着 20 世纪 90 年代以来现代物流理论与信息技术的兴起， 物流逐步被企业视作在市场中
15、获取和保持竞争力优势的有力管理手段， 引起了国内外学者和企业界的极大重视。目前被普遍接受的“物流”定义是美国仓储与采购协会 1998年提出的：“所谓物流是以满足客户需求为目的，为提高原料、在制品、以及相关生产， 从供应到消费的流动和存储的效率和效益， 并对其进行的计划、 执行 （实现）和控制的过程”。现代物流(Logistics)，是指为了实现顾客满意，连接供给主体和需求主体，克服空间和时间阻碍的有效、快速的商品、服务流动经济活动过程，是指以现代信息技术为基础，整合运输、包装、装卸、搬运、仓储、流通加工、 配送、 回收加工及物流信息处理等各种功能而形成的综合性物流活动模式。 一个国家的物流业发
16、展水平，反映了这个国家综合国立和企业竞争能力。在现代社会中，物流与商流、信息流并称为经济的三大支柱，系统化、合理化的物流管理将创造巨大的经济利润。 物流领域已成为继降低资源 （人工和材料） 消耗，提高劳动生产率及通过扩大市场销售获取更多利润之后的“第三利润源泉”。大量数据表明， 经济发达国家或地区的物流产值在国民经济中处于一个十分重要的地位。 现代物流是一个全新的系统概念， 它包含了产品生命周期的整个物理性位移的全过程， 从采购物流开始， 经过生产物流， 再进入销售物流， 到达消费者手中，最后还有回收物流。在这整个物流过程中，要经过包装、运输、装卸搬运、仓储、流通加工、配送、信息处理等作业环节。因此，现代物流涵盖了国民经济的若干个行业，它既是经济发展的产物，又是经济发展的支柱：既是一种增值性的经济活动，又是增加成本、影响生态环境的经济活动。 现代物流作为一种先进的组织方式和管理技术， 被广泛认为是企业在降低物资消耗、提高劳动生产率以外的重要利润源泉，是对流通业的一场革命。现代物-2 - 流产业在国家经
