杨观富 蔡延光

特约论文

解决车辆路径问题及其变体的混合粒子群算法综述

杨观富 蔡延光

（广东工业大学自动化学院，广东 广州 510006）

通过对车辆路径问题的分析总结，得出启发式算法在解决车辆路径问题具有优越性的结论，并以混合粒子群算法为代表，详细阐述混合粒子群在不同车辆路径变形问题中的应用。最后指出车辆路径问题和混合粒子群算法研究的不足与趋势，强调该问题与算法具良好的扩展性，在物流领域有广阔的应用前景。

车辆路径；启发式算法；混合粒子群

0 引言

21世纪以来，随着科学技术与电子商务的快速发展，物流行业已逐渐成为国家经济增长的重要支柱，也成为提高人民生活水平与生活质量的重要保障。同时，物流行业发展的瓶颈——车辆路径问题（vehicle routing problem, VRP）备受研究人员关注。VRP由DANTZING和RAMSER于1959年提出[1]，本意是优化亚特兰大炼油厂的运输路径。经过60多年的发展与历代研究人员的研究，其研究目的、对象和限制条件等都有极大扩充。目前，VRP已从最初的简单车辆安排调度逐步演变为运筹学中一类经典的组合优化问题，是物流管理与运输组织优化中的核心问题，也是一个典型的NP难题。

随着VRP复杂程度不断增加，传统的优化方法在解决该问题时捉襟见肘。研究人员从自然界的一些现象得到启发，利用自然界的规律设置算法，形成一系列的启发式算法，如粒子群算法、人工鱼群算法和共生生物算法等。这些算法结构相对简单，不需要研究人员具备太多相关的专业知识，调节参数较少，容易实现。……