本发明涉及车辆路径规划领域，具体涉及多目标车辆路径规划问题，提出了一种基于拐点的多目标进化算法解决车辆路径问题的方法。
背景技术：
1、车辆路径问题最早由dantzig和ramser于1959年提出，他们给出了一个基于线性规划公式的方法来获得近似最优解。一个典型的车辆路径问题可表述为：对一系列地理位置分散的客户点，在满足一定约束条件下，组织最优的行车路线，使车辆从配送中心出发且有序地到达各个客户点，并达到一定的优化目标。随着车辆路径问题研究的深入，为了适应现实生活的需要，其在新的环境下开始呈现出更多新的特点：一是问题中的信息变得更复杂，更不明确；二是客户对时间、服务质量等要求越来越；三是信息的动态特征越来越明显。
2、为了解决越来越复杂的车辆路径问题，目前研究车辆路径问题主要分为两大类算法，即精确算法和启发式算法。精确算法在求解较大规模问题时非常耗费算力和计算时间，对于实际应用有一定的缺陷性。启发式智能优化算法求解大规模车辆路径问题，常用的包括有遗传算法、差分进化算法、粒子群优化和蚁群优化等等。启发式算法能够更好地运用计算资源从而得到问题的可行解，灵活性大，求解迅速，解的质量较高，但容易陷入局部最优。
3、同时，对于多目标的车辆路径问题，基于遗传算法的多目标优化算法能够针对多目标问题获得一组最优解，即pareto最优解，但是对于获得的这些大量解中，往往只有很少的解决方案符合实际应用并在现实中实现。现有的大多数多目标进化算法，在多目标或高维多目标优化中性能不佳的主要原因之一，是因为在没有决策者偏好的情况下，种群中的大多数解都是非支配解，从大量候选的解决方案中选择可实现的解决方案是具有挑战的。
技术实现思路
1、发明目的：本发明的目的是提供一种基于拐点多目标进化算法的车辆路径规划方法，利用拐点作为最优解的特性，采用基于拐点的多目标进化算法对车辆路径问题进行优化求解，综合实现多个目标的解，保持多样性同时加速收敛，帮助决策者从大量候选的解决方案中选择更优且可行的车辆路径方案。
2、技术方案：一种基于拐点多目标进化算法的车辆路径规划方法，包括以下步骤：
3、s1、根据带时间窗车辆路径规划问题的数据集或实际问题，建立客户点数据模型；
4、s2、根据配送中心以及各客户点坐标信息，计算并构建客户点之间的距离矩阵；
5、s3、根据各客户点实际所需的服务时间需求，在数据表中表现为由最早服务时间和最晚服务时间组成的时间窗，建立时间窗惩罚规则，并构建时间惩罚函数；
6、s4、将最小化车辆使用成本和最小化距离成本、时间惩罚作为模型的目标函数，并确定约束条件，构建带时间窗的车辆路径规划模型，即vrptw模型；
7、s5、通过基于拐点多目标进化算法求解车辆路径问题，对vrptw模型进行优化，求解最佳配送序列
8、进一步，所述s1中建立客户点数据模型包括各个客户点、配送中心及其相关服务信息，并对配送中心和各个客户点分别设置标号，设置如下：
9、设置配送中心的运输车辆数量为k，车辆的额定载重量设置为q，客户数量为n；设置配送中心标号为0，客户点标号为1、2…、n；设置客户点和配送中心位置的横坐标为xi,纵坐标为yi，客户点i的货物需求量为ri，时间窗为[eti,lti]，其中eti为客户点i允许的最早服务时间，lti为最晚服务时间；设置车辆对客户点i的服务持续时间为sti，将以上信息存储在数据表中。
10、期望路径方案能够使用尽量少的车辆服务所有客户，设一个路径方案中使用的车辆数量为v，车辆使用成本函数为：
11、
12、进一步，s2中，计算并构建客户点之间的距离矩阵如下：
13、距离矩阵：计算配送中心以及客户点两两之间的距离，并将计算结果以数组的形式存储，记数组为d，数组元素为dij，表示车辆从客户点i行驶到客户点j的距离，其中dii＝djj＝0,dji＝dij；
14、距离成本函数：
15、
16、其中，k是每个子路径使用的车辆编号，n是所有需要服务的客户数量，xijk为决策变量：
17、
18、进一步，s3中，所述时间窗惩罚规则及函数如下：
19、在惩罚规则中设置惩罚因子，设置车辆早到的惩罚系数epu和晚到惩罚系数lpu；
20、定义时间惩罚函数，车辆在时间窗内到达，时间惩罚值为0，在时间窗之前或时间窗之后到达则接受惩罚，单个客户点惩罚＝(车辆或客户)等待时间*惩罚系数；
21、时间惩罚函数：
22、
23、其中，k是每个子路径使用的车辆编号，nk是第k条子路径车辆所要服务的客户数量，i是客户编号，ki是车辆k服务的第i个客户，tki是车辆k服务到客户i时的当前时间。
24、进一步，s4中，所述构建带时间窗的车辆路径规划模型如下：
25、目标函数表示为：
26、minf＝(f1,f2,f3)t
27、约束条件为：
28、约束1.客户点服务约束：
29、
30、约束2.起点和终点约束：
31、
32、约束3.装载连续性约束：
33、
34、约束4.容量约束：
35、
36、约束5：车辆数量约束：
37、
38、进一步，s5中，通过基于拐点的多目标进化算法求解车辆路径问题，对vrptw模型进行优化，求解最佳配送序列，包括以下步骤：
39、s5-1、种群初始化。设置种群大小为n，优化目标数为m，最大迭代次数为gmax，随机生成初始种群p，得到随机的一组调度路线方案；设定种群中拐点的比率为t；
40、s5-2、根据约束条件的限制，可得到初始种群对应的各车辆子路径，计算该初始路径方案对应的初始目标函数值；
41、s5-3、选择操作。应用二元锦标赛策略从亲本种群中选择个体，使用三种度量进行比较，即支配关系、拐点准则和加权距离度量。通过交叉变异生成n个后代个体，保持种群大小不变；
42、s5-4、将父代和子代种群合并为混合种群，进行非支配排序，判断生成的各个路径方案之间的非支配层级，然后采用自适应策略来识别位于混合群体中每个非支配前沿拐点区域的解；
43、s5-5、生成子代。依据选择策略选择n个个体作为下一代的亲本种群；
44、s5-6、重复s5-3至s5-5，达到最大迭代次数gmax或终止条件时，循环结束，得到最优车辆路径方案及其目标函数值。
45、本发明与现有技术相比，其显著效果如下：
46、1、将带时间窗的车辆路径问题建模为多目标约束优化问题。将最小化距离成本、时间惩罚和最小化车辆数量作为优化的目标函数，结合约束条件，充分考虑了客户点的时间窗要求，更好地贴合了现实生活中的实际服务需求。
47、2、本发明通过基于拐点的多目标进化算法求解带时间窗的车辆路径问题，能够有效地针对多目标的车辆路径问题在没有决策者偏好的情况下，从大量候选的解决方案中选择更优且符合实际应用的车辆路径方案，与其他求解最佳路径的动态规划方法和几何算法方法相比，能够有效地节省计算时间和计算成本。
1.一种基于拐点多目标进化算法的车辆路径规划方法，其特征在于，包括如下步骤：
2.根据权利要求1所述的一种基于拐点多目标进化算法的车辆路径规划方法，其特征在于，s1中，建立客户点数据模型包括各个客户点、配送中心及其相关服务信息，并对配送中心和各个客户点分别设置标号，设置如下：
3.根据权利要求1所述的一种基于拐点多目标进化算法的车辆路径规划方法，其特征在于，s2中，所述计算并构建客户点之间的距离矩阵及距离成本函数如下：
4.根据权利要求1所述的一种基于拐点多目标进化算法的车辆路径规划方法，其特征在于，s3中，所述时间窗惩罚规则和时间惩罚函数如下：
5.根据权利要求1所述的一种基于拐点多目标进化算法的车辆路径规划方法，其特征在于，s4中，所述构建带时间窗的车辆路径规划模型如下：
6.根据权利要求1所述的一种基于拐点多目标进化算法的车辆路径规划方法，其特征在于，s5中，通过基于拐点的多目标进化算法求解车辆路径问题，对vrptw模型进行优化，求解最佳配送序列，包括以下步骤：
