详情

原文传递车辆路径问题的粒子群算法研究与应用

论文题名：	车辆路径问题的粒子群算法研究与应用
关键词：	车辆路径问题;粒子群算法;遗传算法;人工鱼群算法;客户满意度;动态网络;第三方物流;软件开发
摘要：	物流被称为“第三利润源泉”，越来越受到人们的关注，日益成为国民经济的基础产业。运输是物流中的重要环节，占物流成本的60％以上。车辆路径问题主要研究物流配送中车辆线路优化以降低运输成本。该问题是运筹学和组合优化领域中的著名NP问题，在航班调度、列车编组等众多领域都有应用。由于NP问题求解的复杂性，目前车辆路径问题的求解方法主要使用各种智能优化算法。本文主要研究了以下四种模型的车辆路径问题：有能力约束的车辆路径问题，开放式车辆路径问题，基于客户满意度的开放式车辆路径问题，开放式动态网络车辆路径问题。研究了粒子群及其改进算法对上述模型的求解。具体的研究内容如下： (1)首先介绍了本论文的研究背景及意义，给出了车辆路径问题的定义，分析了车辆路径问题的组成要素。然后在对国内外大量文献总结提炼的基础上，从车辆路径问题的模型和求解算法两方面，深入分析了车辆路径问题的国内外研究现状。 (2)系统研究了基于粒子群算法的有能力约束车辆路径问题(CapacityVehicle Routing Problem，CVRP)。提出了整数编码、实数编码两种求解CVRP的方法。在整数编码中，以交换数为基础，对粒子的速度重新定义，并对速度的加、减等操作进行了定义，提出了“换位减”算子作为整数编码的速度计算方法：针对整数编码算法存在的问题，提出了一种实数编码方法求解CVRP，用实数的整数部分表示客户所在的车辆，小数部分表示在该车辆中配送的次序，融合遗传算法的思想，引入交叉算子以增加种群的多样性，详细讨论了粒子群算法的各个参数对算法结果的影响。为了与其他智能优化算法比较，研究了遗传算法、人工鱼群算法在CVRP中的应用。将双种群遗传算法用于CVRP的求解；提出了人工鱼群算法在CVRP中的应用，针对车辆路径问题的特点，定义了鱼群的距离、领域等概念，提出了人工鱼根据自身在鱼群中的排序，自适应选择移动算子的策略。 (3)通过引入虚拟配送中心的概念，建立了开放式车辆路径问题的三下标数学模型。提出了开放式车辆路径问题的粒子群求解方法，将最邻近插入、最远插入、2-Opt、3-Opt 等启发式算法作为再优化过程引入粒子群算法，通过这些启发式算法调整线路内和线路间的客户来改进解，从理论上分析了这些算法的计算复杂度。通过实验分析，找出合适的启发式算子，并和其他的算法进行了比较。 (4)以客户满意度为首要优化目标，建立了基于客户满意度的开放式车辆路径问题的数学模型，使用梯形模糊数表示客户满意度。综合考虑距离、等待时间、客户的满意度等因素，定义了广义的距离和节约费用的概念，提出了改进的最邻近法和最廉价插入法，将这两个算法作为初始化和改进算子结合粒子群算法进行优化求解。分析了算法的复杂度，对算法的各个参数进行了讨论，通过实验仿真对这几种方法进行了分析比较。 (5)动态网络车辆路径问题目前研究的热点和难点问题，将动态网络与开放式两个因素结合起来研究车辆路径问题还未见报道。本文针建立了开放式动态网络车辆路径问题的数学模型，提出了一种连续时间依赖函数模型。提出了自适应惯性权重调整的粒子群算法，定义了粒子的“位置比”概念，充分利用粒子的已有知识，动态的调整惯性权重。在算法中，引入公告板策略，根据粒子适应度的高低分类更新粒子状态，对于优秀粒子使用一种新的状态更新公式，以使其跳出局部极值点。对于适应度低的粒子，通过统计其在公告板中出现的频率，用新的粒子替换以保持种群的多样性。通过实验讨论了算法的参数设置，对几种惯性权重方案进行了分析比较，实验结果证明了算法的有效性。 (6)在上述理论工作的基础上，针对第三方物流在国内的迅速发展，而相应的车辆调度软件功能不够完善，开发了智能车辆调度系统。该系统包括智能车辆调度、承运单的管理、电子地图的显示等功能。该系统可以处理有时间窗、有能力约束等多种情况的车辆调度问题，提供遗传算法、粒子群算法等多种优化算法供用户使用。系统在杭州某物流公司应用，取得了良好的效果。最后，对全文研究工作进行了总结，展望了车辆路径问题的模型和算法研究的前景。
作者：	吴斌
专业：	控制理论与控制工程
导师：	王万良;赵燕伟
授予学位：	博士
授予学位单位：	浙江工业大学
学位年度：	2007
正文语种：	中文