粒子群优化算法(PSO)是一种新兴的智能化启发式全局随机搜索法，它能够有效 的解决各种路径规划问题，由于它的简单易行，效率高，因此也被广泛应用于各种科 学研究和工业领域。

1。2 国内外研究现状 

1。2。1 国外研究现状 

国外学者对于车辆路径问题(VRP)的研究起步较早，自 1959 年 Dantzig 和 Ramser 就初次提出了车辆路径这个问题，并提出了一种较为有用的算法[3]，经过几十年的发 展，对于这类问题的研究，已经取得了较大的进展。

1962 年，Balinski 等人对求解车辆路径问题，最早提出了集分割的方式，针对可 行解集合进行优化，建立了较为简单的数学模型[4]。1964 年 Clarke 和 Wright 针对 Dantzig 和 Ramser 提出的算法做出了改进，提出了一种节流算法[5]，随后 Rao 等人将 列生成的方法引人其中，将问题进行简化，缩小考虑范围，针对所有可行解的子集进 行反复求解，从而找到最优解[6]。20 世纪末，随着电子信息化的发展，数学规划和网

络分析技术取得了巨大的进步，国外学者们因此提出了精确的数学规划方法，用来解 决 VRP 问题，也由此产生了一系列的基于人工智能的优化算法[7-8]，譬如：模拟退火 法、遗传算法、粒子群算法、禁忌搜索法、蚁群优化算法、人工神经网络法等。

1。2。2 国内研究现状 

1。3 本文研究内容 

车辆路径规划是常见的路径规划问题，在电子地图和导航软件中广泛存在。当路 径中节点较多时，难以使用经典方法求解，进化计算方法近年来广泛的用于解决 NP困难问题，具有较好的应用价值。本文主要的研究内容有：

1。对车辆路径规划问题及 PSO 算法进行综述。

2。阐述 PSO 算法求解这类问题的详细步骤。

3。通过使用 MATLAB 编程实现算法运行。

4。通过多组实验，证实 PSO 算法对于求解路径规划问题的适用性。

5。通过实验证实 PSO 算法优化方法的可行性。文献综述

1。4 后续章节安排

1。阐述车辆路径规划问题的定义概念及解决思路。

2。简要介绍几种常见的算法。

3。阐述粒子群优化算法的概念定义。

4。说明 PSO 算法的特点，算法步骤以及算法改进方式。

5。阐述 PSO 算法应用于车辆路径规划问题时的详细步骤。

6。提出 PSO 算法的优化方式——自适应惯性权重。

7。实验部分，将算法应用到解决实际问题中，证明算法的可行性，改变问题规模， 优化算法操作，证实优化操作的可行性。

8。总结实验结论，展望未来。

第二章 预备知识

2。1 路径规划问题的一般定义

车辆路径问题（Vehicle Routing Problem,VRP）最早由 Dantzig 和 Ramser 于 1959 年首次提出，它指的是:对于一系列给定的客户，客户各自有着不同数量的货物需求， 配送中心要向这些客户运送货物以满足他们的需求，交由一个车队负责货物运送，选 择适当的路径将货物送达目的地，并能在一定的约束条件下，达到诸如路程最短、耗 时最短、成本最低、使用车辆数最少等目的。由定义可以看出 VRP 问题和旅行商问 题（TSP）一样属于一种 NP-hard 问题即非确定性多项式难题。来,自.优;尔:论[文|网www.youerw.com +QQ752018766-

路径规划问题被提出后，国内外很多学者从各个方向，各个角度对它进行了深入 剖析与研究，并且研究的问题类型也越来越丰富，最近几年研究较多的问题类型有：

①多供货点问题；②带时间窗的问题；③随机问题；④分批交货问题；⑤回程时集货 问题；⑥集货供货一体化问题等等。研究主要针对问题的静态和动态问题分析，近些 年，以对动态问题的研究较多。 粒子群优化算法车辆路径规划软件实现+源程序(3):http://www.youerw.com/zidonghua/lunwen_101058.html