本发明涉及电动汽车充电技术领域，特别是一种电动汽车充电路径规划方法和存储介质。
背景技术：
电动汽车作为一种减少温室气体排放和其他污染物的手段，在政策制定、汽车制造和公共利益方面越来越受欢迎。出于这一趋势，车辆路径社区最近已经开始投入相当大的精力对模型和算法的发展和电动汽车的使用商品分布进行研究，这项工作大部分致力于研究经典的车辆路径问题的变体，为客户提供存储仓库中的货物。而由于电动汽车的电池容量有限，如何规划电动汽车充电路径，使电动汽车在行驶途中充电，从而实现电动汽车参与物流高效经济，对于电动汽车的大规模投入物流具有重要意义。
技术实现要素：
本发明的目的是提供一种电动汽车充电路径规划方法和存储介质，能够对电动汽车进行行驶和充电路径的规划，提高电动汽车的物流运输效率，降低电动汽车用于物流中的用电成本，提高电能源的有效利用率。
一方面，本发明提供一种电动汽车充电路径规划方法，包括：
获取电动汽车将要到达的拾取点和交付点位置信息，以及充电站位置信息；
基于获取到的信息，利用预先构建的电动汽车充电路径规划模型进行路径规划，得到使得电动汽车的总路线数和总行驶距离最小的初始行驶充电路径；
对所得到的初始行驶充电路径中的各路线弧进行简化；
基于简化后的路线弧组合，利用广义目标函数计算最佳路径；
在电动汽车行驶过程中，在起点以及每个充电站，依次进行实时充电规划，对初始充电路径进行优化，得到规划时刻之后的行驶充电路径。
可选的，所述预先构建的电动汽车充电路径规划模型的优化目标函数及约束条件为：
ui qi-c(1-xij)≤uj(4)
0≤uj≤c(5)
式中，m表示一个足够大的数；
以上方案中，约束(2)和(3)确保每个用户只访问一次，约束(4)和(5)保证不超过车辆运输能力，约束条件(6)更新电池充电，当到达一个顶点，约束(7)表明两个顶点之间的最大可充电量满足充电需求电量，约束(8)确保电池容量足以达到充电路径上的第一站，约束(9)确保电池容量达到最后一站。
可选的，所述对所得到的初始行驶充电路径中的各路线弧进行简化包括：通过收缩时间窗得到更合理的时间窗，然后生成简约图减少弧集，最后创建了一个额外的稀疏图，由可能成为高质量解决方案候选的弧组成。
具体的，定义有向图
所述收缩时间窗通过在提取的时间窗口和到交付的旅行时间定义一个时间间隔，在此期间可以到达交付来实现；
交付顶点i∈d的时间窗为：
ei:＝max(ei,ei-n ti-n,i)
li:＝min(li,li-n ti-n,i)
拾取顶点i∈p的时间窗为：
ei:＝max(ei,ei n-ti,i n)
li:＝min(li,li n-ti-n,i)
式中ei为在顶点i开始的最早服务时间；li为在顶点i开始的最近服务时间。
可选的，所述简约图a'由不可行解构成，每条弧(i,j)∈a满足下述条件之一的即为不可行解：
(i∈p)∩(j＝2n 1)(10)
(j∈d)∩(i＝0)(11)
(i∈d,j∈p)∩(j＝i-n)(12)
i,j∈v∩ei tij＞lj(13)
式中，i为拾取顶点集合的点；j为交付顶点集合的点；前三式表明路径中的出发和到达顺序；最后一式由时间窗推导而来；其中，式(10)(11)与路径上的出发与交付顺序有关，只要路径包含仓库以外的顶点时，将条件(10)(11)中删除的弧重新插入到a'中；条件(11)与i和j的时间窗有关；
所述稀疏图a′-生成规则包括：
在创建时使用两组弧，简约集a′不变，稀疏集
求解目标函数(1)的线性松弛，且
集合a′-初始为空，往a′中反复添加具有最低分数的弧线直到|a′-|＝min(|a′|,α·|a|)。
可选的，所述利用广义目标函数计算最佳路径包括：
使用广义目标函数fgen(s)来求解s，以获取最佳路径：
其中s＝{rk|k∈k}；f(s)为总行程距离，s的解表示为一组路径；能力zcap(s)、电池容量zbatt(s)、时间窗ztw(s)、拾取和交付配对zpair(s)及拾取和交付优先zprec(s)的违反zx(s)是根据惩罚因素σx限定的，惩罚类型为x。
可选的，所述实时充电规划的充电策略为：如果充电路线r满足能耗和时间窗的要求，则作为一个可行的充电计划；如果无法提供一个可行的充电计划，则首先减少对电池容量的限制，其次是对时间窗进行限制。
可选的，所述进行实时充电规划，对初始充电路径进行优化包括：
将遇到的所有可行路径存储在一个集合r中，将每条路径r∈r与一个二元决策变量xr关联起来，该变量表示该路径是否是新解决方案的一部分，系数bri表示i∈p是否包含在r中，其对目标函数值的贡献为f(r)；
令变量yi＝1，即i∈p不是任何选定路线的一部分，让ζi作为动态更新的惩罚因子，实时规划阶段的优化目标函数如下：
其中，目标函数为最小化路径成本和为服务请求的惩罚成本之和；第一个约束确保所有的路径都被覆盖；第二个约束限制路径数量为可用车辆数量；ζi设定到10000 1000λi，其中，λi是一个变量，用于计算在集合覆盖问题的解决方案中有多少次请求没有得到服务；yi为二元决策变量；k为可用车辆数量。
第二方面，本发明提供一种计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时，实现如第一方面所述的电动汽车充电路径规划方法。
有益效果
本发明提出的电动汽车充电路径规划方法，其基本思路是首先构造电动汽车充电路径规划模型。其次对充电路径的路线弧进行简化，然后构建广义目标函数，设计适用于本模型的充电策略，最后根据是否完成所有服务需求进行惩罚机制从而优化函数。测试结果表明，本发明提出的电动汽车路径规划模型准确高效，具有较强的通用性和实用性。
附图说明
图1所示为本发明的方法流程示意图；
图2所示为本发明方法的一种具体实施方式流程示意图；
图3所示为充电速率g＝1时的充电策略；
具体实施方式
以下结合附图和具体实施例进一步描述。
本发明
本发明的电动汽车充电路径规划方法具体设计以下内容。
一、构造电动汽车充电路径规划模型
进一步地，作为本发明的一种优选技术方案：所述步骤1中，模型目标是确定车辆开始和结束的路线，以便使总路线数和总行驶距离最小，其目标函数及约束条件如下所示：
ui qi-c(1-xij)≤uj(4)
0≤uj≤c(5)
式中，m表示一个足够大的数；
层次目标函数(1)用足够大的m表示，约束(2)和(3)确保每个用户只访问一次，约束(4)和(5)保证不超过车辆运输能力，约束条件(6)更新电池充电，当到达一个顶点，约束(7)表明两个顶点之间的最大可充电量满足充电需求电量，约束(8)确保电池容量足以达到充电路径上的第一站，约束(9)确保电池容量达到最后一站。
定义有向图
二、对充电路径的路线弧进行简化
首先通过收缩时间窗得到更合理的时间窗，然后生成简约图减少弧集，最后创建一个额外的稀疏图，由可能成为高质量解决方案候选的弧组成。
收缩时间窗通过在提取的时间窗口和到交付的旅行时间定义一个时间间隔，在此期间可以到达交付来实现。对交付顶点i∈d到ei:＝max(ei,ei-n ti-n,i)和li:＝min(li,li-n ti-n,i)以及出发顶点i∈p到ei:＝max(ei,ei n-ti,i n)和li:＝min(li,li n-ti-n,i)的时间窗进行了重新定义。其中ei为在顶点i开始的最早服务时间；li为在顶点i开始的最近服务时间。
每条弧(i,j)∈a满足下述条件之一的即为不可行解，由不可行解构成简约图a'：
(i∈p)∩(j＝2n 1)(10)
(j∈d)∩(i＝0)(11)
(i∈d,j∈p)∩(j＝i-n)(12)
i,j∈v∩ei tij＞lj(13)
式中，i为拾取顶点集合的点；j为交付顶点集合的点；前三式表明路径中的出发和到达顺序；最后一式由时间窗推导而来。其中，式(10)(11)与路径上的出发与交付顺序有关，只要路径包含仓库以外的顶点时，将条件(10)(11)中删除的弧重新插入到a'中。条件(11)与i和j的时间窗有关。
稀疏图a′-生成规则为：在创建时使用两组弧，即保持简约集a′不变，稀疏集
三、构建广义目标函数
使用广义目标函数fgen(s)来求解s，以获取最佳路径：
其中s＝{rk|k∈k}。f(s)为总行程距离，s的解可以表示为一组路径；能力zcap(s)、电池容量zbatt(s)、时间窗ztw(s)、拾取和交付配对zpair(s)及拾取和交付优先zprec(s)的违反zx(s)是根据惩罚因素σx限定的，惩罚类型为x。
四、设计充电策略
为了生成一个每次访问充电站充电路线r计划，提出了一个充电站策略，该策略具有以下特性：如果充电路线r满足能耗和时间窗的要求，该策略提供一个可行的充电计划；如果无法提供一个可行的充电计划，将首先减少对电池容量的限制，其次是对时间窗的限制。
充电策略表述如下：
受电池容量的限制，需要在每个站点为到达下一个站点所需的能量充电。此外，在不增加任何时间窗口冲突的情况下，收取相应的额外费用。首先，从路线上的第一次充电访问开始，然后考虑后面的充电访问。为了有效计算所有候选解，预先计算当前解路径上每对顶点之间的松弛时间和总等待时间。松弛时间是指在到达第二个顶点之前，可以延迟第一个顶点的离开，而不会增加后续任何顶点的时间窗冲突。总等待时间是第一个(排除)和第二个(包含)顶点之间的所有单独等待时间的总和。这两个值的计算都假设我们从它的时间窗口开始的第一个顶点开始，因此与之前访问过的顶点无关。在做任何充电决定之前，需要从实际情况出发，然后再做充电决定，即，
1)松弛时间
2)总等待时间为
3)每次充电站访问w∈f′(r)和仓库vn(r)之间的松弛时间
此外，令
本发明为了确定充电的能量
其中，充电速率g＝1，γ(aw,w )为直到下一个访问或仓库所需的能量；
五、充电路径规划结果优化
为了得到更好的解决方案，将遇到的所有可行路径存储在一个集合r中，然后将每条路径r∈r与一个二元决策变量xr关联起来，该变量表示该路径是否是新解决方案的一部分，系数bri表示i∈p是否包含在r中(因为路线是可行的，所以也包括交付顶点i)，其对目标函数值的贡献为f(r)。在某些情况下，可能很难获得一个服务于所有客户的可行解决方案，因此允许不处理所有请求，但是会惩罚它们。为此，令变量yi＝1表明，i∈p不是任何选定路线的一部分，让ζi作为动态更新的惩罚因子，优化函数及求解约束如下：
其中，目标函数为最小化路径成本和为服务请求的惩罚成本之和；第一个约束确保所有的路径都被覆盖；第二个约束限制路径数量为可用车辆数量。ζi设定到10000 1000λi，其中，λi是一个变量，用于计算在集合覆盖问题的解决方案中有多少次请求没有得到服务。yi为二元决策变量；k为可用车辆数量。
本发明提出的电动汽车充电路径规划方法，其基本思路是首先构造电动汽车充电路径规划模型。其次对充电路径的路线弧进行简化，然后构建广义目标函数，设计适用于本模型的充电策略，最后根据是否完成所有服务需求进行惩罚机制从而优化函数。测试结果表明，本发明提出的电动汽车路径规划模型准确高效，具有较强的通用性和实用性。
本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、cd-rom、光学存储器等)上实施的计算机程序产品的形式。
本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
以上结合附图对本发明的实施例进行了描述，但是本发明并不局限于上述的具体实施方式，上述的具体实施方式仅仅是示意性的，而不是限制性的，本领域的普通技术人员在本发明的启示下，在不脱离本发明宗旨和权利要求所保护的范围情况下，还可做出很多形式，这些均属于本发明的保护之内。
1.一种电动汽车充电路径规划方法，其特征是，包括：
获取电动汽车将要到达的拾取点和交付点位置信息，以及充电站位置信息；
基于获取到的信息，利用预先构建的电动汽车充电路径规划模型进行路径规划，得到使得电动汽车的总路线数和总行驶距离最小的初始行驶充电路径；
对所得到的初始行驶充电路径中的各路线弧进行简化；
基于简化后的路线弧组合，利用广义目标函数计算最佳路径；
在电动汽车行驶过程中，在起点以及每个充电站，依次进行实时充电规划，对初始充电路径进行优化，得到规划时刻之后的行驶充电路径。
2.根据权利要求1所述的方法，其特征是，所述预先构建的电动汽车充电路径规划模型的优化目标函数及约束条件为：
ui qi-c(1-xij)≤uj(4)
0≤uj≤c(5)
式中，m表示一个足够大的数；
3.根据权利要求2所述的方法，其特征是，所述对所得到的初始行驶充电路径中的各路线弧进行简化包括：通过收缩时间窗得到更合理的时间窗，然后生成简约图减少弧集，最后创建了一个额外的稀疏图，由可能成为高质量解决方案候选的弧组成。
4.根据权利要求3所述的方法，其特征是，定义有向图
所述收缩时间窗通过在提取的时间窗口和到交付的旅行时间定义一个时间间隔，在此期间可以到达交付来实现；
交付顶点i∈d的时间窗为：
ei:＝max(ei,ei-n ti-n,i)
li:＝min(li,li-n ti-n,i)
拾取顶点i∈p的时间窗为：
ei:＝max(ei,ei n-ti,i n)
li:＝min(li,li n-ti-n,i)
式中ei为在顶点i开始的最早服务时间；li为在顶点i开始的最近服务时间。
5.根据权利要求4所述的方法，其特征是，所述简约图a'由不可行解构成，每条弧(i,j)∈a满足下述条件之一的即为不可行解：
(i∈p)∩(j＝2n 1)(10)
(j∈d)∩(i＝0)(11)
(i∈d,j∈p)∩(j＝i-n)(12)
i,j∈v∩ei tij＞lj(13)
式中，i为拾取顶点集合的点；j为交付顶点集合的点；前三式表明路径中的出发和到达顺序；最后一式由时间窗推导而来；其中，式(10)(11)与路径上的出发与交付顺序有关，只要路径包含仓库以外的顶点时，将条件(10)(11)中删除的弧重新插入到a'中；条件(11)与i和j的时间窗有关；
所述稀疏图a′-生成规则包括：
在创建时使用两组弧，简约集a′不变，稀疏集
求解目标函数(1)的线性松弛，且
集合a′-初始为空，往a′中反复添加具有最低分数的弧线直到|a′-|＝min(|a′|,α·|a|)。
6.根据权利要求5所述的方法，其特征是，所述利用广义目标函数计算最佳路径包括：
使用广义目标函数fgen(s)来求解s，以获取最佳路径：
其中s＝{rk|k∈k}；f(s)为总行程距离，s的解表示为一组路径；能力zcap(s)、电池容量zbatt(s)、时间窗ztw(s)、拾取和交付配对zpair(s)及拾取和交付优先zprec(s)的违反zx(s)是根据惩罚因素σx限定的，惩罚类型为x。
7.根据权利要求6所述的方法，其特征是，所述实时充电规划的充电策略为：如果充电路线r满足能耗和时间窗的要求，则作为一个可行的充电计划；如果无法提供一个可行的充电计划，则首先减少对电池容量的限制，其次是对时间窗进行限制。
8.根据权利要求7所述的方法，其特征是，所述进行实时充电规划，对初始充电路径进行优化包括：
将遇到的所有可行路径存储在一个集合r中，将每条路径r∈r与一个二元决策变量xr关联起来，该变量表示该路径是否是新解决方案的一部分，系数bri表示i∈p是否包含在r中，其对目标函数值的贡献为f(r)；
令变量yi＝1，即i∈p不是任何选定路线的一部分，让ζi作为动态更新的惩罚因子，实时规划阶段的优化目标函数如下：
其中，目标函数为最小化路径成本和为服务请求的惩罚成本之和；第一个约束确保所有的路径都被覆盖；第二个约束限制路径数量为可用车辆数量；ζi设定到10000 1000λi，其中，λi是一个变量，用于计算在集合覆盖问题的解决方案中有多少次请求没有得到服务；yi为二元决策变量；k为可用车辆数量。
9.一种计算机可读存储介质，其上存储有计算机程序，其特征是，该计算机程序被处理器执行时，实现如权利要求1-8任一项所述的电动汽车充电路径规划方法。
技术总结