最小化成本为目标的混合车辆路径优化方法和系统

摘要

本发明提供一种最小化成本为目标的混合车辆路径优化方法、系统、存储介质和电子设备，涉及车辆路径优化领域。本发明中，获取车辆、配送中心、客户节点的任务数据；根据所述任务数据，构建以最小化成本为目标的混合车辆协同配送模型；采用基于遗传和鲸鱼混合算法求解所述混合车辆协同配送模型，获取混合车辆路径优化方案。通过构建以最小化成本为目标的混合车辆协同配送模型，采用现代新兴的鲸鱼算法结合遗传算法并加入局部搜索的功能在算法的求解下，兼顾了混合车辆协同配送效率和成本。

说明书

技术领域

本发明涉及车辆路径优化技术领域，具体涉及一种最小化成本为目标的混合车辆路径优化方法、系统、存储介质和电子设备。

背景技术

近年来能源成本稳步上升，同时通过了越来越多的法律来规范交通运输部门的温室气体排放。这些外部因素以及社会不断上升的环境和社会意识已经在企业中引发了许多绿色倡议。在物流领域，电动商用车现在被认为是传统内燃机商用车的一个重要的替代品。由于电动商用车使用距离的限制，只能对一定范围内的顾客进行货物的配送，且成本较高，因此使用纯电动商用车配送货物仍有较大局限。

目前，将电动商用车与传统内燃机商用车结合起来进行配送能够很好的解决续航与环境污染的问题，并解决一次性替换电动商用车所带来的巨额成本，起到中间过渡的作用，在混合车辆协同配送过程中，如何选择最佳的配送节点与合适的时机进行电动汽车的换电保证充足的电量，优化混合车辆的行驶路线，以此在尽量降低对环境污染的前提下提高混合车辆协同配送效率和成本是一个值得探讨的研究方向。建立合理的优化问题描述模型，并为模型寻找高效求解算法对提高混合车辆协同配送效率具有重要意义。

但是在现有的方案设计中，只有纯燃油汽车模型优化、纯电动汽车模型优化或无换电站的混合模型优化，如何兼顾混合车辆协同配送效率和成本是一个值得探讨的研究方向。

发明内容

(一)解决的技术问题

针对现有技术的不足，本发明提供了一种最小化成本为目标的混合车辆路径优化方法、系统、存储介质和电子设备，解决了无法兼顾混合车辆协同配送效率和成本的技术问题。

(二)技术方案

为实现以上目的，本发明通过以下技术方案予以实现：

一种最小化成本为目标的混合车辆路径优化方法，包括：

S1、获取至少包括车辆、配送中心、客户节点信息的任务数据；

S2、根据所述任务数据，构建以最小化成本为目标的混合车辆协同配送模型；

S3、采用基于遗传和鲸鱼混合算法求解所述混合车辆协同配送模型，获取混合车辆路径优化方案。

优选的，所述S2中混合车辆协同配送模型包括：

考虑最小成本的目标函数：

min z＝f

其中，f

K为汽车集合，下标为k；F

f

C

f

优选的，所述S2中混合车辆协同配送模型还包括约束条件：

(1)∑

表示进入某节点的车辆必须离开该节点，车辆最终回到配送中心；

(2)

表示一个客户点只能有一辆车进行配送服务且只服务一次；

(3)

表示每辆车服务的总需求不能超过车辆的载重量；u

(4)

表示车辆从配送中心出发时，时刻为0；

(5)t

表示计算行驶时间，speed表示车辆速度；

(6)

表示车辆到达节点h的时间等于该车辆离开前一节点g的时间加上其从节点g行驶到节点h所需要的时间；

(7)

表示如果车辆到达客户节点g的时间早于客户节点g要求的最早服务时间e

(8)

表示车辆离开客户节点的时间等于到达客户节点的时间加上等待时间和服务时间。

优选的，所述S3具体包括：

S31、根据所述任务数据，初始化鲸鱼种群；

S32、根据所述混合车辆协同配送模型，计算每一个鲸鱼个体对应的目标函数值，获取局部最优个体，并作为全局最优个体；

S33、引入的遗传算法交叉操作完成鲸鱼个体的更新；

S34、将更新后的鲸鱼种群进行局部搜索后，获取当前局部最优个体，并更新所述全局最优个体；

S35、判断是否达到最大更新迭代次数，若是，转入S36；否则，转入S33；

S36、输出最终的全局最优个体，解码获取所述混合车辆路径优化方案。

优选的，所述S31包括：

S311、根据所述任务数据，采用实数编码方式对鲸鱼个体进行编码，具体包括用数字0表示配送中心；1，...，n表示客户节点；配送中心能够使用的总计最大车辆使用数目K等于最大燃油汽车使用数量maxfv加上电动汽车使用数量maxev，则个体的编码为可以用1，...，n+K-1的实数随机产生，其中实数n+1，...，n+K-1为车辆分割点；

S312、将所述鲸鱼个体进行解码，分别获取燃油汽车、以及电动汽车的车辆配送方案；

S3121、获取燃油汽车的车辆配送方案，

根据燃油汽车最大使用数量maxfv，提取出现第maxfv个车辆分割点以前的编码片段，在该前部分编码片段中利用大于n的数值把选取的片段最多至多分割为maxfv份，每一份分割的片段代表每一辆燃油汽车访问的客户节点；

S3122、获取电动汽车配送方案，

提取出现第maxfv个车辆分割点以后的编码片段，在该后部分编码片段中利用大于n的数值把选取的片段最多至多分割为maxev份，每一份分割的片段代表每一辆电动汽车访问的客户节点；

S313、组合燃油汽车的车辆配送方案和电动汽车的车辆配送方案，获取初始鲸鱼种群中任一鲸鱼个体对应的解。

优选的，所述S33具体包括：

定义局部最优个体为X

其中，rand表示生成介于0到1之间的一个随机数；

cross

S10、随机选择鲸鱼个体1的位置i1上元素e1，找到个体2相同位置i1的元素e2，再回到个体1中找到元素e2所在的位置i2，重复工作直至达到一个闭环；

v11、按顺序依次替换两个个体上数值的位置，完成当前鲸鱼个体的更新；

cross

S100、随机选择鲸鱼个体1中任意个个体的位置，并记录对应的数值位置顺序，在个体2中选择相同数值，并记录个体2的位置顺序；

S101、将个体1选中的数值位置顺序按照个体2数值位置顺序重新插回个体1中，个体2选择的数值按照个体1选中数值的顺序重新插回个体。

优选的，所述S34具体采用逆转操作和/或插入操作局部搜索方法，包括：

定义一个鲸鱼个体可表示为：

R＝[R(1)，R(2)，...，R(i)，R(i+1)，...，R(j-1)，R(j)，...，R(N+K-2)，R(N+K-1)]；

(1)所述逆转操作局部搜索方法是指逆转鲸鱼个体上两个位置之间所有元素的排序，若选择的逆转位置为i和j，逆转第i个和第j个位置之间所有元素，排序后的解可表示为：

R＝[R(1)，R(2)，...，R(j)，R(j-1)，...，R(i+1)，R(i)，...，R(N+K-2)，R(N+K-1)]；

(2)所述插入操作局部搜索方法是指将第i个位置元素插入第j个位置元素之后，排序后的解表示为：

R＝[R(1)，R(2)，...，R(i+1)，...，R(j-1)，R(j)，R(i)，...，R(N+K-2)，R(N+K-1)]。

一种最小化成本为目标的混合车辆路径优化系统，包括：

数据获取模块，用于获取至少包括车辆、配送中心、客户节点信息的任务数据；

模型构建模块，用于根据所述任务数据，构建以最小化成本为目标的混合车辆协同配送模型；

方案求解模块，用于采用基于遗传和鲸鱼混合算法求解所述混合车辆协同配送模型，获取混合车辆路径优化方案。

一种存储介质，其存储有用于最小化成本为目标的混合车辆路径优化的计算机程序，其中，所述计算机程序使得计算机执行如上任一项所述的混合车辆路径优化方法。

一种电子设备，包括：

一个或多个处理器；

存储器；以及

一个或多个程序，其中所述一个或多个程序被存储在所述存储器中，并且被配置成由所述一个或多个处理器执行，所述程序包括用于执行如上所述的混合车辆路径优化方法。

(三)有益效果

本发明提供了一种最小化成本为目标的混合车辆路径优化方法、系统、存储介质和电子设备。与现有技术相比，具备以下有益效果：

本发明中，获取车辆、配送中心、客户节点的任务数据；根据所述任务数据，构建以最小化成本为目标的混合车辆协同配送模型；采用基于遗传和鲸鱼混合算法求解所述混合车辆协同配送模型，获取混合车辆路径优化方案。通过构建以最小化成本为目标的混合车辆协同配送模型，采用现代新兴的鲸鱼算法结合遗传算法并加入局部搜索的功能在算法的求解下，兼顾了混合车辆协同配送效率和成本。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例提供的一种最小化成本为目标的混合车辆路径优化方法的流程示意图；

图2为本发明实施例提供的一种鲸鱼个体的编码示例；

图3为本发明实施例提供的一种燃油汽车配送方案的解码示例；

图4为本发明实施例提供的一种电动汽车配送方案的解码示例；

图5为本发明实施例提供的一种循环交叉方式示意图；

图6为本发明实施例提供的一种顺序交叉方式示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本申请实施例通过提供一种最小化成本为目标的混合车辆路径优化方法、系统、存储介质和电子设备，解决了无法兼顾混合车辆协同配送效率和成本的技术问题。

本申请实施例中的技术方案为解决上述技术问题，总体思路如下：

本发明实施例提出了一种燃油电动混合的车辆优化模型，在电动汽车技术与配套设施日益发达的今天，电动汽车已经可以替代燃油汽车进行物流配送，但是运用电动汽车配送前期需要投入巨大成本，需要存在过渡阶段，在现如今碳排放这一热门形式下，如何均衡前期巨大投入与绿色出行势在必行，建立基于降低碳排放混合车辆路径优化模型，采用现代新兴的鲸鱼算法结合遗传算法并加入局部搜索的功能在算法的求解下，很好的解决的了在电动汽车替换燃油汽车这一大形势下尴尬境地。

为了更好的理解上述技术方案，下面将结合说明书附图以及具体的实施方式对上述技术方案进行详细的说明。

实施例：

如图1所示，本发明实施例提供了一种最小化成本为目标的混合车辆路径优化方法，包括：

S1、获取至少包括车辆、配送中心、客户节点信息的任务数据；

S2、根据所述任务数据，构建混合车辆协同配送模型；

S3、采用基于遗传和鲸鱼混合算法求解所述混合车辆协同配送模型，获取混合车辆路径优化方案。

本发明实施例通过构建以最小化成本为目标的混合车辆协同配送模型，采用现代新兴的鲸鱼算法结合遗传算法并加入局部搜索的功能在算法的求解下，兼顾了混合车辆协同配送效率和成本。

下面将结合具体内容以及附图详细介绍上述技术方案地各个步骤：

S1、获取至少包括车辆、配送中心、客户节点信息的任务数据。

定义如下：

集合：

C为客户节点集合,下标为c；

{o}为配送中心；

V为所有节点集合，V＝C∪{o}；

K为汽车集合，下标为k。

参数：

U—车载容量

u

d

F

C

tw

tf

e

l

t

epu/lpu早到/晚到惩罚成本

决策变量：

x

y

S2、根据所述任务数据，构建混合车辆协同配送模型；

所述混合车辆协同配送模型包括：

考虑最小成本的目标函数：

min z＝f

其中，f

K为汽车集合，下标为k；F

f

C

f

所述混合车辆协同配送模型还包括约束条件：

(1)∑

表示进入某节点的车辆必须离开该节点，车辆最终回到配送中心；

(2)

表示一个客户点只能有一辆车进行配送服务且只服务一次；

(3)

表示每辆车服务的总需求不能超过车辆的载重量；u

(4)

表示车辆从配送中心出发时，时刻为0；

(5)t

表示计算行驶时间，speed表示车辆速度；

(6)

表示车辆到达节点h的时间等于该车辆离开前一节点g的时间加上其从节点g行驶到节点h所需要的时间；

(7)

表示如果车辆到达客户节点g的时间早于客户节点g要求的最早服务时间e

(8)

表示车辆离开客户节点的时间等于到达客户节点的时间加上等待时间和服务时间。

S3、采用基于遗传和鲸鱼混合算法求解所述混合车辆协同配送模型，获取混合车辆路径优化方案；

需要强调的是，本发明实施例提供的混合车辆协同配送模型中，是假设电动车行驶里程满足配送里程的，不包含换电站的位置。

鲸鱼算法是模仿自然界中鲸鱼捕食行为新型群体智能优化算法，鲸鱼捕食可以划分为三种行为①包围猎物；②发泡网攻击；③搜索捕食。鲸鱼捕食行为是通过发射的声纳来获取猎物的位置，当一群鲸鱼捕猎时，一定会存在某一只鲸鱼首先发现猎物的大概的位置，通过群体交流朝猎物方向靠近形成包围并组织进攻，最后达到捕食的目的。此算法在保留了鲸鱼算法参数简单的同时，结合车辆路径问题(Vehicle Routing Problem,VRP)问题特性，将遗传算法中的交叉步骤引入到了鲸鱼算法鲸鱼位置的更新中，混合了遗传算法强大的搜索能力，并加入局部搜索来提高解的质量。

具体的，所述S3包括：

S31、根据所述任务数据，初始化鲸鱼种群，包括：

S311、根据所述任务数据，采用实数编码方式对鲸鱼个体进行编码，具体包括用数字0表示配送中心；1，...，n表示客户节点；配送中心能够使用的总计最大车辆使用数目K等于最大燃油汽车使用数量maxfv加上电动汽车使用数量maxev，则个体的编码为可以用1，...，n+K-1的实数随机产生，其中实数n+1，...，n+K-1为车辆分割点；

如图2所示，假设0代表配送中心，1-14为客户节点，燃油汽车最大3辆，电动汽车最大3辆，则分割点的个数为3+3-1＝5个，其中15-19为车辆分割点，即大于14的点为车辆分割点。

S312、将所述鲸鱼个体进行解码，分别获取燃油汽车、以及电动汽车的车辆配送方案；

S3121、获取燃油汽车的车辆配送方案，

如图3所示，根据燃油汽车最大使用数量maxfv，提取出现第maxfv个车辆分割点以前的编码片段，在该前部分编码片段中利用大于n的数值把选取的片段最多至多分割为maxfv份，每一份分割的片段代表每一辆燃油汽车访问的客户节点；

S3122、获取电动汽车配送方案，

如图4所示，提取出现第maxfv个车辆分割点以后的编码片段，在该后部分编码片段中利用大于n的数值把选取的片段最多至多分割为maxev份，每一份分割的片段代表每一辆电动汽车访问的客户节点；

S313、组合燃油汽车的车辆配送方案和电动汽车的车辆配送方案，获取初始鲸鱼种群中任一鲸鱼个体对应的解。

S32、根据所述混合车辆协同配送模型，计算每一个鲸鱼个体对应的目标函数值，获取局部最优个体，并作为全局最优个体；

特别的，该步骤中还可以将车辆载重约束转换成惩罚成本，如若违反则给予无穷大的惩罚，用于计算鲸鱼个体距离猎物的距离(目标值越小距离猎物的距离越近)。

v33、引入的遗传算法交叉操作完成鲸鱼个体的更新；包括：

定义局部最优个体为X

其中，rand表示生成介于0到1之间的一个随机数；

cross

S10、随机选择鲸鱼个体1的位置i1上元素e1，找到个体2相同位置i1的元素e2，再回到个体1中找到元素e2所在的位置i2，重复工作直至达到一个闭环；

S11、按顺序依次替换两个个体上数值的位置，完成当前鲸鱼个体的更新；

cross

v100、随机选择鲸鱼个体1中任意个个体的位置，并记录对应的数值位置顺序，在个体2中选择相同数值，并记录个体2的位置顺序；

S101、将个体1选中的数值位置顺序按照个体2数值位置顺序重新插回个体1中，个体2选择的数值按照个体1选中数值的顺序重新插回个体。

S34、将更新后的鲸鱼种群进行局部搜索后，获取当前局部最优个体，并更新所述全局最优个体；

本步骤中具体采用逆转操作和/或插入操作局部搜索方法，包括：

定义一个鲸鱼个体可表示为：

R＝[R(1)，R(2)，...，R(i)，R(i+1)，...，R(j-1)，R(j)，...，R(N+K-2)，R(N+K-1)]；

(1)所述逆转操作局部搜索方法是指逆转鲸鱼个体上两个位置之间所有元素的排序，若选择的逆转位置为i和j，逆转第i个和第j个位置之间所有元素，排序后的解可表示为：

R＝[R(1)，R(2)，...，R(j)，R(j-1)，...，R(i+1)，R(i)，...，R(N+K-2)，R(N+K-1)]；

(2)所述插入操作局部搜索方法是指将第i个位置元素插入第j个位置元素之后，排序后的解表示为：

R＝[R(1)，R(2)，...，R(i+1)，...，R(j-1)，R(j)，R(i)，...，R(N+K-2)，R(N+K-1)]。

具体而言，如果当前局部最优个体对应的目标值大于全局最优个体的目标值，则将全局最优个体替换为该当前局部最优个体，否则保留上一循环过程中确定的全局最优个体。

S35、判断是否达到最大更新迭代次数，若是，转入S36；否则，转入S33；

S36、输出最终的全局最优个体，解码获取所述混合车辆路径优化方案。

本发明实施例提供了一种最小化成本为目标的混合车辆路径优化系统，包括：

数据获取模块，用于获取至少包括车辆、配送中心、客户节点信息的任务数据；

模型构建模块，用于根据所述任务数据，构建混合车辆协同配送模型；

方案求解模块，用于采用基于遗传和鲸鱼混合算法求解所述混合车辆协同配送模型，获取混合车辆路径优化方案。

本发明实施例提供了一种存储介质，其存储有用于最小化成本为目标的混合车辆路径优化的计算机程序，其中，所述计算机程序使得计算机执行如上所述的混合车辆路径优化方法。

本发明实施例还提供了一种电子设备，包括：

一个或多个处理器；

存储器；以及

一个或多个程序，其中所述一个或多个程序被存储在所述存储器中，并且被配置成由所述一个或多个处理器执行，所述程序包括用于执行如上所述的混合车辆路径优化方法。

可理解的是，本发明实施例提供的最小化成本为目标的混合车辆路径优化系统、存储介质和电子设备与本发明实施例提供的最小化成本为目标的混合车辆路径优化方法相对应，其有关内容的解释、举例和有益效果等部分可以参考混合车辆路径优化方法中的相应部分，此处不再赘述。

综上所述，与现有技术相比，具备以下有益效果：

本发明实施例中，获取车辆、配送中心、客户节点的任务数据；根据所述任务数据，构建以最小化成本为目标的混合车辆协同配送模型；采用基于遗传和鲸鱼混合算法求解所述混合车辆协同配送模型，获取混合车辆路径优化方案。通过构建以最小化成本为目标的混合车辆协同配送模型，采用现代新兴的鲸鱼算法结合遗传算法并加入局部搜索的功能在算法的求解下，兼顾了混合车辆协同配送效率和成本。

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。