【摘要】

在车辆路径优化问题中，货物的配置和车辆路径的安排是一个典型的难题。传统的最短路径算法因性能原因无法适应大规模VRP问题。本文在建立VRP问题的数学模型的基础上，构造了求解该问题的爬山粒子群混合算法，首先通过编码，将VRP问题转化为两个子问题：任务分配问题和单车路径优化问题。由粒子群算法掌控全局并且进行任务分配，爬山算法则进行各车辆路径优化（适应度）的计算。

最后本文进行了MATLAB-8.0编程实现，通过与节约矩阵法和遗传算法运行结果的比较，证明了该算法求解VRP的效果最好，且简单易实现、实用性较高。

【关键词】爬山粒子群混合算法  VRP   任务分配问题  单车路径优化问题

• 引言

随着物流技术和应用的发展，物流配送过程中的车辆路径优化问题(VehicleRouting Problem．VRP)成为一个研究的热点【1】。它是一个NP难题，不能得到解析解，通常只能通过各种启发式算法得到近似解。

启发式算法求解该问题就成为人们研究的一个重要方向，并出现了多种启发式算法，如Clarke和Wright提出的节约法[1]，Gillett和Miller提出的扫描法等。J.Holland教授模拟达尔文生物进化论提出遗传算法，是自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，目前已广泛应用于各种优化或控制领域。美国的Kennedy和Eberhart于1995年提出了粒子群算法(Particle Swarm Optimization简称PSO)，该算法模拟鸟群飞行觅食的行为，通过鸟之间的集体协作使群体达到最优。【2】

本文将采用混合智能算法去解决VRP问题：1、将VRP问题分解为两个子问题：任务分配问题和单车路径优化问题；2、整体优化以及任务分配由粒子群算法完成；3、每辆车的路径优化（适应度的计算）则由爬山算法求解。改进后的粒子群算法显然不仅保持了其本身固有的能在求解空间中大范围求解的优点，又加强了局部搜索的能力，算法性能将会有所提高。