1.一种换电站选址与混合车队路径规划方法,其特征在于,所述方法包括:获取备选数据信息;
构建换电站选址和电动车与燃油车混合车队配送联合决策的整数规划模型;
将所述整数规划模型重构为主问题模型和子问题模型;
对主问题模型和子问题模型进行求解,得到总成本最低的配送方案和换电站选址方案。
2.根据权利要求1所述的换电站选址与混合车队路径规划方法,其特征在于,所述备选数据信息包括:配送中心的数量和地址;电动车数量,电动车每公里配送成本,电动车的最大行驶里程;燃油车数量,燃油车每公里配送成本;每个等待配送客户的位置、需求和服务时间窗;每个备选换电站的位置。
3.根据权利要求1所述的换电站选址与混合车队路径规划方法,其特征在于,所述整数规划模型包括以下公式:模型中公式(4-1)为目标函数,由三项成本组成,第一项为换电站的建设成本,第二项为电动车的运输成本,第三项为燃油车的运输成本;公式(4-2)表示每个客户点及换电站只能同时被一辆车访问;公式(4-3)约束配送车辆可用数量不超过车队规模;公式(4-4)表示启用的换电站才能提供换电服务;公式(4-5)确保每个点流守恒;公式(4-6)及(4-7)表示电动车与燃油车的配送任务总量不超过其最大载重量;公式(4-8)表示车辆从点i到点j的时间逻辑关系;公式(4-9)表示电动车从换电站f到点j的时间逻辑关系;公式(4-10)满足所有点的服务时间窗约束;公式(4-11)满足电动车从点i行驶到点j的电量消耗关系;公式(4-
12)表示电动车在到达及离开客户点时电量不变;公式(4-13)表示电动车从配送中心满充状态出发,且到达换电站后更换满充电池;公式(4-14)约束电动车在任意点的电量大于零,确保电动车能够返回配送中心;公式(4-15)为0-1决策变量约束条件。
4.根据权利要求1所述的换电站选址与混合车队路径规划方法,其特征在于:所述主问题模型,包括以下公式:公式(4-16)至公式(4-20)中,p为车辆行驶路径,Ω为所有满足约束的可行路径集合,p∈Ω;车辆路径组合(p,k)表示路径p由车辆k配送; 为0-1变量,表示最终解方案中是否采用车辆路径组合(p,k); 为0-1变量,表示车辆路径组合(p,k)是否经过弧(i,j); 为0-1变量,表示路径p是否经过点i; 表示车辆路径组合(p,k)的成本,包含路径运输成本及建站成本,λk根据车辆k的类型取λe或λc,所述 可由以下公式计算得到:
5.根据权利要求4所述的换电站选址与混合车队路径规划方法,其特征在于:所述子问题模型,包括以下公式:公式(4-21)和公式(4-22)中,π={πi,πe,πc}分别为主问题模型中公式(4-17)、公式(4-
18)和公式(4-19)对应的对偶变量; 表示主问题模型中Ω的每一条可行路径的检验数。
6.根据权利要求5所述的换电站选址与混合车队路径规划方法,其特征在于,所述对主问题模型和子问题模型进行求解,包括以下步骤:S41.初始化节点信息,令全局上界为正无穷大,活跃节点集合与根节点的值相同,初始化算子池信息;
S42.计算终止判断,判断活跃结点集合是否为空,若为空,当前的上界即为最优解,计算终止,否则转到步骤S43;
S43.根据节点选择策略从活跃节点集合中选出一个节点,并从活跃节点集合中删除选中的节点;
S44.节点求解,求解该节点,若无解,则转到步骤S42;否则将该节点的线性松弛最优解记为该节点的局部下界;
S45.剪枝,若局部下界大于或等于全局上界,转到步骤S42;否则进一步判断该节点所求松弛最优解是否为分数,若为分数,转到步骤S46;若为整数,则更新全局上界为局部下界,并把活跃节点集合中不小于当前全局上界的节点删除,转到步骤S42;
S46.分支,根据分支策略在当前节点的松弛最优解中选取分支变量划分解空间以得到子节点,并将这些新的子节点加入活跃节点集合中,转到步骤S42。
7.根据权利要求6所述的换电站选址与混合车队路径规划方法,其特征在于,所述步骤S44中,包括以下步骤:S4401.构造主问题模型;
S4402.求解主问题模型;
S4403.传递对偶变量;
S4404.将计数器中记录的迭代次数归零,更新算子信息;
S4405.从算子池中随机选出算子,并求解子问题模型;
S4406.判断是否产生检验数为负的列,若产生,则进入步骤S4407,若没有产生,则进入步骤S4409;
S4407.将计数器中记录的迭代次数加1,将算子得分加上打分,将检验数为负的列添加至主问题模型,同时将算子池复原;
S4408.判断迭代次数与小迭代周期数的大小关系,若迭代次数小于小迭代周期数,则进入步骤S4405;反之,则进入步骤S4404;
S4409.将迭代次数加1,将步骤S4405中选出的算子在算子池中删除;
S4410.判断算子池是否为空,若算子池为空,则进入步骤S4411;否则,进入步骤S4405;
S4411.调用精确标签扩展法求解子问题模型;
S4412.判断是否产生检验数为负的列;若产生检验数为负的列,将该检验数为负的列添加进主问题模型,并进入步骤S4402;否则,终止列生成迭代。
8.根据权利要求7所述的换电站选址与混合车队路径规划方法,其特征在于,所述算子池中包括以下7个算子:第一算子,在贪婪算法中将解的当前状态扩大到2个阶段,得到的二阶贪婪算子;
第二算子,待扩展标签的当前节点只向负费用弧的节点扩展,同时保持精确统治规则不变。
第三算子,待扩展标签的当前节点只向费用下降弧的节点扩展,同时保持精确统治规则不变。
第四算子,待扩展标签的当前节点只向负费用弧的节点扩展,同时放松统治规则中电动车电量Q、燃油车到达时间T的约束。
第五算子,待扩展标签的当前节点只向费用下降弧的节点扩展,同时放松统治规则中电动车电量Q、燃油车到达时间T的约束。
第六算子,待扩展标签的当前节点只向负费用弧的节点扩展,同时放松统治规则中电动车与燃油车载重W的约束。
第七算子,待扩展标签的当前节点只向费用下降弧的节点扩展,同时放松统治规则中电动车与燃油车载重W的约束。
9.根据权利要求7所述的换电站选址与混合车队路径规划方法,其特征在于,所述步骤S44中,每经过Ct次迭代计算,更新每个算子的权重,所述Ct为算子数量,所述算子权重可通过以下公式计算:所述公式(4-24)中θ为权重参数,取值为θ∈[0,1];Si为算子得分,其得分情况根据Sn而更新,当选中的算子未能求解当前子问题时Sn=0,否则根据下列情形为算子打分:当小周期内第1次选中的算子能够求解子问题模型时,Sn=10;
当前面选中的算子无法求解子问题模型,本次选中的算子能够求解时,且本次选中的算子非最后一个算子,Sn=20;
当前面选中的算子无法求解子问题模型,直到最后一次选中的算子能够求解时,Sn=
30。
10.一种换电站选址与混合车队路径规划系统,其特征在于,所述系统包括:数据获取模块,用于获取备选数据信息;
模型构建模块,用于构建换电站选址和电动车与燃油车混合车队配送联合决策的整数规划模型;
模型重构模块,用于将所述整数规划模型重构为主问题模型和子问题模型;
计算模块,用于对主问题模型和子问题模型进行求解,得到总成本最低的配送方案和换电站选址方案。