基于离散粒子群算法的车辆路径问题求解
基于离散粒子群算法的车辆路径问题求解[20191213112930]
摘 要
车辆路径问题，是组合优化中的一个热门问题，它有着比较广泛的应用背景。成为交通运输、应用数学、应用数学、图论、计算机应用、网络分析、组合优化及运筹学等学科研究的热点问题。车辆路径问题是一个典型的NP完全问题，一般的VRP问题的定义如下：运输车辆从一个或多个地点到多个分散的客户点，求解一套适当的运输路线，使得运输车辆能够有序的经过它们，同时还要满足设定的约束条件（如货物的需求量、货物发送量、交发货的时间、每辆车的容量限制、时间限制、行驶距离限制等），并需满足一定的要求（如行驶路程最短、使用的车辆数尽量少、所需费用最小、所需时间尽量少等）。
要求解车辆路径问题，就需要搭建一个数据管理系统，系统中要包含主界面、算法求解程序以及数据库。此次毕业设计所要完成的任务是设计与实现车辆路径问题管理系统，其中设计部分主要包括主界面的创建以及主程序的编写，实现部分则包括界面与算法程序的连接。
本文做了以下工作：首先，对车辆路径问题、Visual C++对话框、离散粒子群算法这三个问题进行了简介，并对论文的研究背景与主要研究内容作了概述。其次，对Visual C++对话框的组成和分类进行了简单的介绍，并初步完成搭建应用程序的框架。然后，将对话框与数据进行连接。接着，通过调试，测试整个系统的运行状况。最后，对研究工作进行了总结，指出此次设计存在的问题，并对今后可能的研究方向进行展望。
查看完整论文请+Q: 351916072
关键字:车辆路径问题；离散粒子群算法；VisualC++对话框
目 录
摘要 I
ABSTRACT II
第1章 绪论 1
1.1 车辆路径问题简介 1
1.2粒子群算法简介 2
1.3离散粒子群算法简介 2
1.4 论文背景、主要研究内容和章节安排 4
第2章 离散粒子群算法 5
2.1 基本粒子群算法 5
2.1.1 基本粒子群算法原理 5
2.1.2 基本粒子群算法流程 6
2.2 离散粒子群算法 8
2.3 离散粒子群算法的研究现状 9
第3章 车辆路径问题 11
3.1 基本车辆路径问题 11
3.2 基于智能优化的车辆路径问题求解 12
3.2.1 车辆路径问题的研究现状 12
3.2.2 车辆路径问题研究前景 12
3.3 离散粒子群算法求解车辆路径问题 13
3.3.1简单车辆路径问题应用实例 13
3.3.2时间窗车辆路径问题应用实例 14
3.3.3参数的设置与对结果的影响 15
第4章 车辆路径问题数据管理系统的设计 18
4.1 创建应用程序框架 18
4.2 创建对话框资源 19
4.3 创建对话框类 23
4.3.2 添加成员变量后的过程分析 24
4.3.3 Class Wizard识别和处理映射变量所需要的标识 26
4.4 对话框与程序的连接 26
第5章 总结与展望 29
5.1 论文工作总结 29
5.2 论文工作展望 29
参考文献 30
致 谢 33
附 录 34
第1章 绪论
1.1 车辆路径问题简介
车辆路径问题(Vehicle Routing Problem，简称VRP）：
VRP最早由Ramser和Dantzig在1959年首次提出，它是指有一定数量的客户，他们对货物需求的数量不同，由配送中心向客户来提供货物，并且由一个车队负责分送货物，组织适当的行车路线，目标是满足各个客户的需求，并能在一定的约束条件下，达到诸如成本最小、路程最短、耗费时间最少等目的。
由此定义不难看出，旅行商问题（Traveling Salesman Problem，TSP)是VRP的特例，由于Gaery已证明TSP是NP难题，因此，VRP也属于NP难题。
图1.1即为VRP示意图：
图 1.1 VRP示意图
1.2粒子群算法简介
粒子群(particle swarm)优化算法(PSO)是一种进化计算技术，它模仿了鸟群在觅食过程中迁徙的过程。空中的每一只鸟称为一个“粒子”，每个粒子都有自己的位置和速度，这决定了飞行的方向和距离，并且有一个由优化目标所决定的适应度值。粒子群算法随机初始化为一群粒子(如一个鸟群)，粒子们追随当前的最优粒子和本身的历史最优解在解空间中搜索全局最优解(如同食物)。与遗传算法相比，PSO保留了基于种群的全局搜索策略，避免了复杂的遗传操作，有易实现，简单，调整参数少，收敛速度快等优点。
1.3离散粒子群算法简介
由于PSO拥有的优越性和在函数优化等领域蕴含的广阔的应用前景，很多学者通过研究提出了多种PSO改进算法，使PSO得到了广泛的应用。不过目前大多研究成果还局限在连续领域，利用PSO求解离散问题的研究相对较少。随着很多学者对粒子群算法进行不断的研究，出现了利用离散粒子群优化算法(DPSO)求解离散问题，主要有基于连续空间和基于离散空间的两种离散粒子群算法。
基于连续空间的DPSO以基本的连续PSO为基础，适当的调整PSO算法将问题由离散空间映射到连续空间进行求解，在运算过程中仍采用PSO“速度—位置”更新公式。
1997年，Kennedy和Eberhart等人提出了离散二进制粒子群算法(Binary PSO，BPSO)。BPSO粒子的位置是二进制编码，每一维位置和Pbest用1或0表示，粒子的速度体现粒子位置变化的概率。用速度来更新位置时，如果速度高一些，粒子的位置更有可能选1，速度低一点则选0，阈值在[0,1]之间。其他部分与基本的连续PSO类似。
BPSO优化离散变量是通过优化连续变化的二进制变量为1的概率，而不是直接优化二进制变量本身。所以，对于许多存在有序结构表达和约束条件处理问题的组合优化问题，BPSO不能完全适用。但是由于连续空间里的矢量计算十分简单，消耗时间短，基于连续空间的DPSO算法能保持较快的运算速度。
BPSO是对PSO的直接离散化，还局限在只是对经典的连续PSO算法进行了针对问题的修改，并没有充分考虑到离散型组合优化的特点，由PSO算法生成的连续解与离散问题的目标函数评价值之间存在多对一的映射，以整型变量表示的目标函数不能准确反映算法中连续解的质量，而由此导致的冗余解空间与相应的冗余搜索降低了算法的收敛效率。
基于离散空间的DPSO，是在保存基本PSO信息更新的基本原理下，重新定义粒子离散表示方式与操作算子，对特定的离散问题进行求解。在计算上以离散空间特有的对矢量中的位操作取代传统向量运算，从信息流动机制上看，仍保留了PSO算法特有的信息交换和流动机制。
如Clerc针对旅行商问题(TSP)提出了TSP-DPSO算法。在TSP-DPSO算法中，用城市的一个排列来代表一个粒子的位置，所有排列就构成了问题的解空间，速度被定义为达到目标状态所需要对当前位置状态执行的基本交换序。
基于离散空间的DPSO虽然使用了位操作，增加运算代价，但不会有冗余搜索问题，而且其突出优点就是对离散问题表达自然，易于与其他演化计算方法结合。由此混合粒子群（组合粒子群）算法也成为了中外学者们的研究热点。
PSO的本质是利用本身信息，局部极值信息和全局极值3个信息，指导粒子下一步迭代。将遗传算法的交叉变异进化思想与DPSO相结合。公式(1.1)中 项可看作遗传算法的变异操作， ， 可看作遗传算法的交叉操作，使当前解与全局极值和局部极值分别作交叉操作，产生的解作为新的位置。变异操作和交叉操作后，新的解可能比原来的解要坏，接受准则采用模拟退火算法思想，允许目标函数在有限范围内变坏，这样就形成了基于遗传算法的基本离散粒子群优化算法，简称DPSO算法。
由于基本DPSO算法在引入交叉算子时，没有考虑PSO的算法特点，让当前粒子与局部极值和全局极值进行交叉操作，来产生新粒子，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化(失去了多样性)，使得后期收敛速度明显变慢，同时算法收敛到一定精度时，无法继续优化，所能达到的精度也比GA低。但PSO充分利用各粒子的局部最优和全局最优值而不像组合遗传算法那样随机交叉的思想毫无疑问是合理的。算法求解过程中的收敛速度低的主要原因是没有合适地利用这些局部最优和全局最优粒子。
1.4 论文背景、主要研究内容和章节安排
此次毕业设计主要任务是为车辆路径问题设计数据管理系统，确保用户能在一个简洁的界面上比较方便地计算出最优路径。
要做出一个界面，可选择的编程语言很多，比如Visual Basic、Visual C++、java等等，由于在本科期间接触Visual C++比较多，相对而言更熟悉，再结合Visual C++开发效率、运行效率都不错的优点，所以此次设计的编程语言就选择了Visual C++。
此次设计的主要工作内容，首先是了解离散粒子群算法、粒子群算法、离散粒子群算法，并进行相关的编程，接着是创建对话框，其次是把对话框中各个按钮、编辑框、复选框等与主程序和算法程序中的成员变量对应起来，最后调试和运行程序，输入设定的参数，得出最优路径。
全文共分为五个章节，各章节内容安排具体如下：
第一章：绪论
对车辆路径问题、粒子群算法、离散粒子群算法这三个与此次设计相关的问题进行了简介，并对论文的背景与主要研究内容作了概述。
第二章：离散粒子群算法
对粒子群算法与离散粒子群算法进行了更详细的介绍。
第三章：车辆路径问题
对车辆路径问题进行了更详细的介绍。并介绍了车辆路径问题的研究现状与前景。
第四章：车辆路径问题数据管理系统的设计
搭建应用程序的框架，将对话框与数据进行连接，通过调试，测试整个系统的运行状况。
第五章：总结与展望
对论文的研究工作进行了总结，指出存在的问题，并对今后可能的研究方向进行了展望。
第2章 离散粒子群算法
2.1 基本粒子群算法
2.1.1 基本粒子群算法原理
粒子群算法的初始化种群是随机产生的，所有粒子根据式(1.1)、(1.2)来更新自己的速度和位置，从而产生新的粒子。
(2.1)
(2.2)
与 分别表示为第i个粒子在D维解空间的速度和位置。粒子所经历过的局部最优值为 ，整个群体所经历过的最好位置称为全局最优值 。式(2.1)中的 被称为惯性权重，是一个比例因子，跟前一次速度有关。 、 是加速系数(或称为学习因子)，分别用来调节向全局最好粒子以及局部最好位置方向飞行的步长，太大或太小，都会影响粒子向目标区的飞行，设置合适的 、 可以加快收敛速度且不易陷入局部最优。 是[0,1]之间的随机数。为了防止粒子飞离最好解或者陷入局部最优，粒子每一维速度 都会被限定在[ ， ]之间。
粒子速度的更新公式由三部分构成：第一部分是粒子对前速度的继承；第二部分是粒子对自身的认知和思考，根据自己的经验来影响运动速度；第三部分是各粒子之间的交流合作，粒子的运动状态来源于其他社会成员共享的信息。所有的粒子通过这三部分，在解空间中不断跟踪全局最优点和局部最优点来进行搜索，直至达到优化目标值。
图2.1就是PSO算法的方向示意图：
不难看出粒子在第i+1次迭代的运动轨迹既受到全局最优 、自身第i次迭代速度Vi，又受到局部最优 的综合影响。是否能使粒子具有较平衡的搜索能力，能更快的找到最优解，是由参数 、 和 决定的。因此，在速度更新公式中调整的适当参数值对粒子群算法寻优能力的影响非常明显。
2.1.2 基本粒子群算法流程
下面介绍算法的流程：
① 初始化粒子群，具体包括群体规模N，各个粒子的位置 Xi 和速度Vi；
② 算出每个粒子的适应度；
③ 对每一个粒子将它的适应度值Fit [i]和个体值 比较，若Fit [i] > pbest (i)，则用Fit[i]替换掉 pbest（i）；
④ 对每一个粒子，用它的适应度值Fit[i] 和全局极值 进行比较，若
Fit [i] > (i)，则用Fit [i]替 ；
⑤ 根据公式（2.1），（2.2）更新粒子的速度Vi 和位置 Xi；
⑥ 如果满足结束条件(误差足够好或到达最大循环次数)退出，否则返回②。
图2.2 粒子群算法流程
（2.3）
公式2.3可用来计算适应度值，且在此公式中，pE表示在ETi之前到达任务点等待的单位时间成本，pL表示在LTi之后到达任务点i的单位时间所需的罚金，若将ETi，LTi分别设置为0与无穷大，则转化为简单车辆路径问题。
2.2 离散粒子群算法
PSO算法最初是用于解决连续优化问题，研究也主要集中在连续函数方面，即其速度、加速度等变量都是连续的，它们的运算法则也是连续量的运算。然而许多实际的工程应用问题是离散的，变量是有限的，因而需要将基本PSO 算法在二进制空间进行扩展，构造一种离散形式的PSO算法模型。
摘 要
车辆路径问题，是组合优化中的一个热门问题，它有着比较广泛的应用背景。成为交通运输、应用数学、应用数学、图论、计算机应用、网络分析、组合优化及运筹学等学科研究的热点问题。车辆路径问题是一个典型的NP完全问题，一般的VRP问题的定义如下：运输车辆从一个或多个地点到多个分散的客户点，求解一套适当的运输路线，使得运输车辆能够有序的经过它们，同时还要满足设定的约束条件（如货物的需求量、货物发送量、交发货的时间、每辆车的容量限制、时间限制、行驶距离限制等），并需满足一定的要求（如行驶路程最短、使用的车辆数尽量少、所需费用最小、所需时间尽量少等）。
要求解车辆路径问题，就需要搭建一个数据管理系统，系统中要包含主界面、算法求解程序以及数据库。此次毕业设计所要完成的任务是设计与实现车辆路径问题管理系统，其中设计部分主要包括主界面的创建以及主程序的编写，实现部分则包括界面与算法程序的连接。
本文做了以下工作：首先，对车辆路径问题、Visual C++对话框、离散粒子群算法这三个问题进行了简介，并对论文的研究背景与主要研究内容作了概述。其次，对Visual C++对话框的组成和分类进行了简单的介绍，并初步完成搭建应用程序的框架。然后，将对话框与数据进行连接。接着，通过调试，测试整个系统的运行状况。最后，对研究工作进行了总结，指出此次设计存在的问题，并对今后可能的研究方向进行展望。
查看完整论文请+Q: 351916072
关键字:车辆路径问题；离散粒子群算法；VisualC++对话框
目 录
摘要 I
ABSTRACT II
第1章 绪论 1
1.1 车辆路径问题简介 1
1.2粒子群算法简介 2
1.3离散粒子群算法简介 2
1.4 论文背景、主要研究内容和章节安排 4
第2章 离散粒子群算法 5
2.1 基本粒子群算法 5
2.1.1 基本粒子群算法原理 5
2.1.2 基本粒子群算法流程 6
2.2 离散粒子群算法 8
2.3 离散粒子群算法的研究现状 9
第3章 车辆路径问题 11
3.1 基本车辆路径问题 11
3.2 基于智能优化的车辆路径问题求解 12
3.2.1 车辆路径问题的研究现状 12
3.2.2 车辆路径问题研究前景 12
3.3 离散粒子群算法求解车辆路径问题 13
3.3.1简单车辆路径问题应用实例 13
3.3.2时间窗车辆路径问题应用实例 14
3.3.3参数的设置与对结果的影响 15
第4章 车辆路径问题数据管理系统的设计 18
4.1 创建应用程序框架 18
4.2 创建对话框资源 19
4.3 创建对话框类 23
4.3.2 添加成员变量后的过程分析 24
4.3.3 Class Wizard识别和处理映射变量所需要的标识 26
4.4 对话框与程序的连接 26
第5章 总结与展望 29
5.1 论文工作总结 29
5.2 论文工作展望 29
参考文献 30
致 谢 33
附 录 34
第1章 绪论
1.1 车辆路径问题简介
车辆路径问题(Vehicle Routing Problem，简称VRP）：
VRP最早由Ramser和Dantzig在1959年首次提出，它是指有一定数量的客户，他们对货物需求的数量不同，由配送中心向客户来提供货物，并且由一个车队负责分送货物，组织适当的行车路线，目标是满足各个客户的需求，并能在一定的约束条件下，达到诸如成本最小、路程最短、耗费时间最少等目的。
由此定义不难看出，旅行商问题（Traveling Salesman Problem，TSP)是VRP的特例，由于Gaery已证明TSP是NP难题，因此，VRP也属于NP难题。
图1.1即为VRP示意图：
图 1.1 VRP示意图
1.2粒子群算法简介
粒子群(particle swarm)优化算法(PSO)是一种进化计算技术，它模仿了鸟群在觅食过程中迁徙的过程。空中的每一只鸟称为一个“粒子”，每个粒子都有自己的位置和速度，这决定了飞行的方向和距离，并且有一个由优化目标所决定的适应度值。粒子群算法随机初始化为一群粒子(如一个鸟群)，粒子们追随当前的最优粒子和本身的历史最优解在解空间中搜索全局最优解(如同食物)。与遗传算法相比，PSO保留了基于种群的全局搜索策略，避免了复杂的遗传操作，有易实现，简单，调整参数少，收敛速度快等优点。
1.3离散粒子群算法简介
由于PSO拥有的优越性和在函数优化等领域蕴含的广阔的应用前景，很多学者通过研究提出了多种PSO改进算法，使PSO得到了广泛的应用。不过目前大多研究成果还局限在连续领域，利用PSO求解离散问题的研究相对较少。随着很多学者对粒子群算法进行不断的研究，出现了利用离散粒子群优化算法(DPSO)求解离散问题，主要有基于连续空间和基于离散空间的两种离散粒子群算法。
基于连续空间的DPSO以基本的连续PSO为基础，适当的调整PSO算法将问题由离散空间映射到连续空间进行求解，在运算过程中仍采用PSO“速度—位置”更新公式。
1997年，Kennedy和Eberhart等人提出了离散二进制粒子群算法(Binary PSO，BPSO)。BPSO粒子的位置是二进制编码，每一维位置和Pbest用1或0表示，粒子的速度体现粒子位置变化的概率。用速度来更新位置时，如果速度高一些，粒子的位置更有可能选1，速度低一点则选0，阈值在[0,1]之间。其他部分与基本的连续PSO类似。
BPSO优化离散变量是通过优化连续变化的二进制变量为1的概率，而不是直接优化二进制变量本身。所以，对于许多存在有序结构表达和约束条件处理问题的组合优化问题，BPSO不能完全适用。但是由于连续空间里的矢量计算十分简单，消耗时间短，基于连续空间的DPSO算法能保持较快的运算速度。
BPSO是对PSO的直接离散化，还局限在只是对经典的连续PSO算法进行了针对问题的修改，并没有充分考虑到离散型组合优化的特点，由PSO算法生成的连续解与离散问题的目标函数评价值之间存在多对一的映射，以整型变量表示的目标函数不能准确反映算法中连续解的质量，而由此导致的冗余解空间与相应的冗余搜索降低了算法的收敛效率。
基于离散空间的DPSO，是在保存基本PSO信息更新的基本原理下，重新定义粒子离散表示方式与操作算子，对特定的离散问题进行求解。在计算上以离散空间特有的对矢量中的位操作取代传统向量运算，从信息流动机制上看，仍保留了PSO算法特有的信息交换和流动机制。
如Clerc针对旅行商问题(TSP)提出了TSP-DPSO算法。在TSP-DPSO算法中，用城市的一个排列来代表一个粒子的位置，所有排列就构成了问题的解空间，速度被定义为达到目标状态所需要对当前位置状态执行的基本交换序。
基于离散空间的DPSO虽然使用了位操作，增加运算代价，但不会有冗余搜索问题，而且其突出优点就是对离散问题表达自然，易于与其他演化计算方法结合。由此混合粒子群（组合粒子群）算法也成为了中外学者们的研究热点。
PSO的本质是利用本身信息，局部极值信息和全局极值3个信息，指导粒子下一步迭代。将遗传算法的交叉变异进化思想与DPSO相结合。公式(1.1)中 项可看作遗传算法的变异操作， ， 可看作遗传算法的交叉操作，使当前解与全局极值和局部极值分别作交叉操作，产生的解作为新的位置。变异操作和交叉操作后，新的解可能比原来的解要坏，接受准则采用模拟退火算法思想，允许目标函数在有限范围内变坏，这样就形成了基于遗传算法的基本离散粒子群优化算法，简称DPSO算法。
由于基本DPSO算法在引入交叉算子时，没有考虑PSO的算法特点，让当前粒子与局部极值和全局极值进行交叉操作，来产生新粒子，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化(失去了多样性)，使得后期收敛速度明显变慢，同时算法收敛到一定精度时，无法继续优化，所能达到的精度也比GA低。但PSO充分利用各粒子的局部最优和全局最优值而不像组合遗传算法那样随机交叉的思想毫无疑问是合理的。算法求解过程中的收敛速度低的主要原因是没有合适地利用这些局部最优和全局最优粒子。
1.4 论文背景、主要研究内容和章节安排
此次毕业设计主要任务是为车辆路径问题设计数据管理系统，确保用户能在一个简洁的界面上比较方便地计算出最优路径。
要做出一个界面，可选择的编程语言很多，比如Visual Basic、Visual C++、java等等，由于在本科期间接触Visual C++比较多，相对而言更熟悉，再结合Visual C++开发效率、运行效率都不错的优点，所以此次设计的编程语言就选择了Visual C++。
此次设计的主要工作内容，首先是了解离散粒子群算法、粒子群算法、离散粒子群算法，并进行相关的编程，接着是创建对话框，其次是把对话框中各个按钮、编辑框、复选框等与主程序和算法程序中的成员变量对应起来，最后调试和运行程序，输入设定的参数，得出最优路径。
全文共分为五个章节，各章节内容安排具体如下：
第一章：绪论
对车辆路径问题、粒子群算法、离散粒子群算法这三个与此次设计相关的问题进行了简介，并对论文的背景与主要研究内容作了概述。
第二章：离散粒子群算法
对粒子群算法与离散粒子群算法进行了更详细的介绍。
第三章：车辆路径问题
对车辆路径问题进行了更详细的介绍。并介绍了车辆路径问题的研究现状与前景。
第四章：车辆路径问题数据管理系统的设计
搭建应用程序的框架，将对话框与数据进行连接，通过调试，测试整个系统的运行状况。
第五章：总结与展望
对论文的研究工作进行了总结，指出存在的问题，并对今后可能的研究方向进行了展望。
第2章 离散粒子群算法
2.1 基本粒子群算法
2.1.1 基本粒子群算法原理
粒子群算法的初始化种群是随机产生的，所有粒子根据式(1.1)、(1.2)来更新自己的速度和位置，从而产生新的粒子。
(2.1)
(2.2)
与 分别表示为第i个粒子在D维解空间的速度和位置。粒子所经历过的局部最优值为 ，整个群体所经历过的最好位置称为全局最优值 。式(2.1)中的 被称为惯性权重，是一个比例因子，跟前一次速度有关。 、 是加速系数(或称为学习因子)，分别用来调节向全局最好粒子以及局部最好位置方向飞行的步长，太大或太小，都会影响粒子向目标区的飞行，设置合适的 、 可以加快收敛速度且不易陷入局部最优。 是[0,1]之间的随机数。为了防止粒子飞离最好解或者陷入局部最优，粒子每一维速度 都会被限定在[ ， ]之间。
粒子速度的更新公式由三部分构成：第一部分是粒子对前速度的继承；第二部分是粒子对自身的认知和思考，根据自己的经验来影响运动速度；第三部分是各粒子之间的交流合作，粒子的运动状态来源于其他社会成员共享的信息。所有的粒子通过这三部分，在解空间中不断跟踪全局最优点和局部最优点来进行搜索，直至达到优化目标值。
图2.1就是PSO算法的方向示意图：
不难看出粒子在第i+1次迭代的运动轨迹既受到全局最优 、自身第i次迭代速度Vi，又受到局部最优 的综合影响。是否能使粒子具有较平衡的搜索能力，能更快的找到最优解，是由参数 、 和 决定的。因此，在速度更新公式中调整的适当参数值对粒子群算法寻优能力的影响非常明显。
2.1.2 基本粒子群算法流程
下面介绍算法的流程：
① 初始化粒子群，具体包括群体规模N，各个粒子的位置 Xi 和速度Vi；
② 算出每个粒子的适应度；
③ 对每一个粒子将它的适应度值Fit [i]和个体值 比较，若Fit [i] > pbest (i)，则用Fit[i]替换掉 pbest（i）；
④ 对每一个粒子，用它的适应度值Fit[i] 和全局极值 进行比较，若
Fit [i] > (i)，则用Fit [i]替 ；
⑤ 根据公式（2.1），（2.2）更新粒子的速度Vi 和位置 Xi；
⑥ 如果满足结束条件(误差足够好或到达最大循环次数)退出，否则返回②。
图2.2 粒子群算法流程
（2.3）
公式2.3可用来计算适应度值，且在此公式中，pE表示在ETi之前到达任务点等待的单位时间成本，pL表示在LTi之后到达任务点i的单位时间所需的罚金，若将ETi，LTi分别设置为0与无穷大，则转化为简单车辆路径问题。
2.2 离散粒子群算法
PSO算法最初是用于解决连续优化问题，研究也主要集中在连续函数方面，即其速度、加速度等变量都是连续的，它们的运算法则也是连续量的运算。然而许多实际的工程应用问题是离散的，变量是有限的，因而需要将基本PSO 算法在二进制空间进行扩展，构造一种离散形式的PSO算法模型。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jxgc/zdh/4897.html
