文摘
能源和环境问题日益突出,电动车(电动车)已经成为了物流配送的重要交通工具。在实际城市道路网络,经常存在多条路径之间的任何两个位置(仓库、客户和充电站)因为时间旅行时间。,电动车在每条路径的旅行速度可能是不同的在不同的时期,因此,本文明确考虑路径选择两个地点之间的时间电有时间窗车辆路径问题,表示路径的灵活性。因此,集成的决策应该不仅包括路由计划路径选择,和感兴趣的问题是一个依赖于时间的电有时间窗车辆路径问题和路径的灵活性(TDEVRP-PF)。为了确定任意两个地点之间的最优路径,建立一个优化模型以最小化的目标距离和与旅游相关的电池能源消耗速度和货物装载。的基础上的最优路径模型,然后制定一个0 - 1混合整数规划模型以最小化总疏散距离。以下,一个改进版本的变邻域搜索算法(VNS)是解决拟议的模型,利用多线程技术的采用大大提高解决方案的效率。最终,一些数值试验进行测试的性能迷走神经刺激法,以改善迷走神经刺激法是有效的结论,找到高质量的分布方案包括路线,旅行路径,和收费计划,实际意义的选择和安排电动汽车物流企业。
1。介绍
1.1。背景
在过去的二十年里,随着经济的快速发展和电子商务在中国,每年的包裹交付不断增长,带来了机遇和挑战,物流行业的发展。例如,快递服务企业的年度业务数量在2018年达到507.1亿件,比上年增长26.6%(在中国1]。
物流车辆的特点是能耗高、排放和污染。经济合作与发展组织指出,发达国家的主要城市货运交通占10%,城市交通总量的-15%,而造成的环境污染货运车辆占40%(城市交通总量的-60%2]。因此,作为发射活动的重要参与者,物流企业应履行的社会责任。
日益突出的能源和环境问题,电动汽车(EVs)脱颖而出的环境保护的特点,节能,低成本,他们逐渐成为物流行业的重要交通工具。因此,电动车辆路径问题(EVRP)已成为一个热门的研究领域,吸引了许多学者的关注。然而,电动汽车总是有一些局限性,如有限的电池容量和长时间充电。随着先进技术的快速发展,充电时间短,电池耐力的提高为电动汽车的广泛应用带来的机会。此外,本文是符合中国交通运输部的目标实现的任务的成功完成解决交通污染预防和控制的关键问题是在2020年,它还对促进科技创新的电话在交通和智能交通的发展,以及强化物流。
1.2。文献综述
我们所知,Dantzig和公羊3)首次提出的车辆路径问题(VRP)。克拉克和赖特4)然后Dantzig公羊和提出的改进方法提出了北京市节约算法。与近年来不断发展,研究人员已经考虑不同影响约束形成了许多分支。
有时间窗车辆路径问题(VRPTW)是一个经典VRP问题时间窗约束。所罗门(5)首先考虑时间窗约束车辆路径和插入启发式算法提出了一个令人满意的结果。之后,大量的meta-heuristic提出解决蚁群算法。加西亚et al。6]使用禁忌搜索(TS)算法来解决VRPTW和构造初始解的插入启发式算法。Gambardella et al。7解决VRPTW]设计了蚁群算法。Ombuki et al。8)提出了一种基于遗传算法的混合启发式算法和TS,用于优化车辆的数量和旅行的距离。Braysy [9)提出了一个四级启发式算法解决VRPTW根据可变邻域搜索(VNS)。佩莱格里尼et al。10]研究了VRP受制于不同的车辆和多个时间窗口,使用蚁群算法来求解该模型。最近,Alzaqebah et al。11]介绍了人工蜜蜂殖民地的解决方案,使用的侦察蜂记住这个废弃的解决方案。Binart et al。12)解决路由问题随机旅行和服务时间给一个两阶段的解决方案的方法。Hiermann et al。13)考虑时间窗在客户点,这是一种常见的和重要的实际约束路由规划问题和解决了这个问题通过branch-and-price算法。黄等。14]用route-path近似和北京道路网络为例,计算在不同时期独特的地区的平均速度。他和李15)调查的路由优化问题的目标减少燃料消耗在时间窗和异构舰队,这是通过使用禁忌搜索算法来解决。
自21世纪以来,环境污染和能源短缺问题已经吸引了人们的注意力。当人们开始寻找更多的节能和清洁汽车,绿色车辆出现历史性的时刻。在过去的几年里,人们的进一步关注,电动车技术的不断创新使其成为近年来流行,成为主流的绿色汽车。因此,大多数大型物流企业也开始开发电动汽车分布。因此,EVRP, EVs和VRP的结合,成为一个新的研究方向。
林等。16]认为EVRP可比的旅行时间和距离与柴油卡车VRP相比。作者强调了车辆荷载对能耗的影响,提出了一个方法,最低成本包括旅游成本和能源成本。Goeke和施耐德(17富裕舰队混合问题进行了研究,这是传统燃油汽车和电动汽车混合舰队,旅行速度,斜率和加载被认为建立一个更实际的能耗模型。他们开发了一种自适应大型社区搜索(ALNS)方法使用嵌入式本地搜索过程是通过代孕函数来评估有效地改变。Bruglieri et al。18)提出了一个混合整数线性规划公式假设电池充电水平在每个车站是一个决策变量为保证更灵活的路线。模型的目标是最小化总旅行,等待和充电时间,使用电动汽车的数量。陈和日本村田公司19)提供了一个新颖的模型为解决电动车辆路径问题最小化总电力消耗的目的。对于电动汽车的能源消耗,郑(20.)提出了一个能源消耗模型与轮胎的滚动阻力系数有关,空气阻力系数和迎风面积,汽车的一个常数。
EVRP在这项研究中,由于交通拥堵的影响和服务需求问题,有流研究电动汽车的问题随着时间的推移,寡妇,我们称之为E-VRPTW。Penna et al。21)提出了迭代局部搜索算法加上一组分区模型解决电动机队规模和有时间窗车辆路径问题和充电站。几种类型的电动汽车不同练习场,能力,和固定成本应该成为一组客户他们的时间范围内,在他们的旅行,每辆车可以充电。刘等人。22]介绍了绿色VRPTW-PF模型,以加速度的燃料消耗和等待红绿灯的考虑。Keskin和Catay23制定一个混合整数线性规划模型,允许部分充电与充电三配置可称为正常,快,超高速充电。解决更大的问题,本文开发了一种matheuristic方法夫妇自适应大型小区搜索方法和准确的方法。
也有大量的研究对电动汽车的充电。施耐德et al。24]认为车辆和电池容量有限;汽车消耗的电池能量根据常数沿弧旅行时消费的因素。此外,车辆可以访问沿线的充电站,充电时间取决于当前的电池充电在到达车站。作者提出了一种混合算法结合VNS和TS和测试其性能的实例multidepot VRP interdepot路线。康拉德和Figliozzi25)提出了充电车辆路径问题,由路由的电动汽车,车辆容量限制和时间窗口和有限的练习场。菲利普et al。26]研究绿色VRP的延伸,这被认为是与不同的成本和不同类型的充电站充电速度。本文构造启发式,启发式算法和模拟退火算法提出了几个本地搜索。Keskin和Catay27)允许所有电动汽车充电部分(不完全)在运输途中充电站。提出了一种数学模型,设计了ALNS算法来求解该模型。邵et al。28)提出了混合遗传算法的路线和收费计划。Koc et al。29日]介绍了电动汽车充电站共享路由问题最小化成本的固定开放的和充电站和司机的成本。
1.3。本文的贡献
在本文中,我们致力于规划合理的配送路线节约物流成本,提高企业经济效益。具体地说,我们认为EVRP时间窗和灵活的路径。此外,车辆在本研究假定为完全充电的充电站。
论文的主要贡献可以概括如下:(1)本文首先考虑了路径EVRP中的任何两个地点之间的灵活性。在分配的过程中,路径选择主要取决于出发的时间地点和交通拥堵水平在当前的道路网络。在这种情况下,电动汽车可能会沿着不同的路径,因为时间速度在实际道路条件下,它被定义为路径的灵活性(PF)。此外,考虑路径的灵活性,它能够节省电池能源,因此扮演着一个很重要的角色,节约成本。(2)本文提供了两种数学模型来制定时间电有时间窗车辆路径问题和路径的灵活性(TDEVRPTW-PF)。第一个模型是用于选择任意两个地点之间的最优路径包括消费者和充电站实现最短路径和最小的能源消耗。第二个模型给多个电动汽车的总体旅游路线的分布,考虑到路径的灵活性和时间窗口。总目标是最小化总距离旅行期间,为企业节约成本,增加利润。(3)本文提出了一种有效解决TDEVRPTW-PF迷走神经刺激法算法。通过虚拟配送中心插入序列代表多个车辆的路线旅行,结果可以更加直观地看到。此外,考虑到算法的时间和空间复杂性,旅游顺序和收费记录分离,采用多线程,大大提高了效率。提前测试充电条件时,两个位置是用来确定充电条件以确保车辆有足够的电力继续服务并提供保护车辆的耐力。
本文的其余部分组织如下:部分2给出了一个声明,问题描述,提出了两种数学模型。部分3提出了一种改进的迷走神经刺激法算法的解决方案。数值实验给出了部分4。最后,我们总结我们的工作与结束语部分5。
2。问题陈述
本文专注于电动汽车的路由优化时间窗口和时间旅行时间,也包括充电和电池能源消耗。前制定多个EVs的路由和时间窗和路径优化模型的灵活性,我们第一次做以下假设:
假设1。电动汽车被认为是均匀的舰队。所有车辆因此有相同的负载和体积。此外,电动汽车与相同最大的电池容量和充电率。
假设2。电动汽车总是完全充电,它可以多次充电。除此之外,同时许多电动汽车充电站可以容纳,我们不需要考虑队列时间充电。
假设3。根据物流企业的实际分布情况,我们把工作时间分成几个时间段,因此,任意两个地点之间的每个路径上的速度是恒定在一定时间内,用平均速度来表示。
基于上述假设,可以制定问题研究的电动汽车充满电,离开一个配送中心,可以提供一系列的客户有不同的要求。每辆车在预定的时间内交付货物到客户窗口。此外,为了防止电动车需要充电不到达充电站,能源消耗分析应提前进行。
接下来,我们将给出一个例子,如何分析能源消耗,保证车辆需要充电可以到达充电站。图1展示了一个例子涉及三个电动汽车(EV1, EV2 EV3),八个客户(C1-C8),三个充电站(S1-S3),和一个配送中心(D)。箭头线表示任意两个地点之间的最优路径,和百分比值的箭头线表示能源消耗。此外,盒子里的百分比值显示电池状态当车辆到达客户。从图1,我们可以看到EV1第一服务顾客C1和C2并返回到配送中心没有任何收费;EV2服务客户C3和C4之后需要收费;然而,它不能到达目前最近的充电站S2。因此,EV2应该在S1 C3服役后,充电然后EV2继续C4和C5。因此,EV3需要在S3服务后收取C6维修C7后再访问S3。最后,它返回到服务C8后配送中心。从图1,我们也可以观察到电动车可以多次(比如EV3),并且每个充电站不一定是访问(例如S2)。
为了方便起见,列出相关的模型中使用的符号表1。让表示客户和表示充电站,我们集
。为简单起见,符号和都表示配送中心,每个路线开始结束
。集分销网络中的节点可以用
,我们组
,
。因此,实际道路网络所描述的图
,在哪里一个代表弧的集合。每个弧
可以对应于一组中的多个路径图,标记成吗
。一个路径
,
连接节点我和j在
。每个路径与距离有关和旅行时间
。电动汽车到达客户我,
,在和重量有需求吗和体积
,服务时间
,和时间窗口
。根据交付的实际情况,我们把一天的工作时间R时期,每个时期是由符号r,
。平均速度和旅行时间r被假定为和
,分别,当汽车旅行的道路
。因此,我们的目标是优化分配方案通过最小化总旅行距离和能源消费的考虑时间窗和路径的灵活性。在下面,我们提出两个问题的0 - 1混合整数规划模型。
2.1。分析电动汽车的能源消耗
指的是郑(20.]本文分析了电动汽车的能源消耗(见图2)。单位距离的能耗主要包括两个方面,即:,推动能源和车辆配件。此外,一些电动车可以恢复的一部分电能通过制动时的动能。开车期间能源消耗主要是受到三个元素的影响。(1)工作环境,如温度和湿度,会影响电池的能量转换效率。(2)驾驶风格也会影响能源消耗。例如,一个司机喜欢刹车突然会消耗更多的能量。(3)车辆通过克服阻力,包括滚动阻力和空气阻力。汽车配件的能源消耗主要受到两个因素的影响,包括车辆的平均速度在不同的工作环境和舒适的电能消费配件、安全附件、和功能配件。
基于上述讨论,能量消耗的驾驶风格和车辆配件是很难计算的。因此,能源消耗的工作,克服阻力是首先计算,然后这个能源消耗能源消费总量的比例是基于经验和预测。最后,能源消费总量可以根据这个比例。
从节点能耗的计算过程我来j在路径p在时间内r在方程(4)。
充电过程中,我们假设充电时间常数,和电动汽车总是完全充电。此外,它可以多次充电。电动汽车的动态性能的影响反映在动态分配过程速度和不同的道路选择。
2.2。任意两个地点之间的最优路径选择模型
为了确定任意两个地点之间的最优路径包括客户、充电站,和配送中心,我们将建立一个0 - 1混合整数规划模型来减少能源消耗和距离。
首先,可以定义为决策变量
由于车辆从一个位置到另一个可以覆盖多个时期,它的总时间是在这些时间旅行时间的总和。例如,我们假设两个地点之间的距离是10公里,和时间的持续时间是一个小时,也就是说。,60分钟,因此,步速度函数图所示3。当电动车到达客户我,14日,它不能到达下一个客户j以当前速度40 km / h在这个时间段,它必须改变速度60公里/小时,保持在第二次旅行的时间从9点到10点。因此,位置之间的距离我和j也可以表示为
相应地,电动车的能源消费总量和消费的所有的时间。因此,我们可以得到方程
选择最优路径弧(我,j),时间旅行速度,我们可以制定模型如下:
目标函数(5)是减少能源消耗和距离,每个权重和( )。约束(6)保证车辆选择一个路径,如果旅行弧 。约束(7)和(9)执行车辆可能经过多个时间段。约束(8)代表流保护。最后,约束(10)- (12)定义二进制决策变量。
2.3。多个电动汽车路由编程模型随着时间的窗口
任意两个地点之间的速度在不同的路径在不同时期并不总是相同的,从而导致不同的能源消耗。我们可以用最少的能源消耗和最优路径最短的任意两个地点之间的距离在任何起飞时间从上面的模型。因此,我们可以使用变量之间的最优路径我和j定义弧上的变量 ,如
最优路径选择模型的基础上,按时间的电动有时间窗车辆路径问题和路径的灵活性(TDEVRP-PF)可以作为制定
目标函数(14)是最小化总行驶距离。约束(15)处理客户的连接,确保每个客户只有一个车。约束(16)强加,没有超过K车辆。车辆流守恒约束(17)提出了汽车的数量,到达一个节点的数量必须等于车辆离开所有节点包括客户和充电站。约束(18)和(19)确保时间弧离开客户的可行性和充电站,分别。约束(20.)执行客户的时间窗口。约束(21)和(23)保证重量和体积的货物满足所有客户的需求。约束(22)和(24)确保每辆车的重量和体积不应超过车辆的能力。约束(25)和(26)电池电荷状态的跟踪,确保它从来不是消极的。最后,约束(27)定义了二进制决策变量。
3所示。一个变量为TDEVRPTW-PF邻域搜索算法
该模型是一个np难问题,它涉及到许多因素,如multivehicle同时交付、硬时间窗,在路由路径的灵活性,和充电。通过综合考虑各种启发式算法的优缺点(禁忌搜索算法,遗传算法,模拟退火算法,变邻域搜索算法,等等),我们最后选择可变邻域搜索(VNS)算法解决该模型更具包容性。基于迷走神经刺激法算法的概念,我们根据实际需要改进和完善,以便有效地解决该模型。算法的目标是最小化总旅行距离,同时满足约束。
本节的其余部分可以分为四个部分。第一部分显示了PF方法解决问题。根据解决多目标决策模型的想法,我们收集的数据动态道路网络和选择任意两个地点之间的最优路径为TDEVRPTW-PF生成数据库。在第二部分,我们提出一种最初的解决方案同时分配多个车辆,这是一个重要的部分算法和实验数据的先决条件。第三部分是分析目标问题的特点,提出了模型中(也就是说,约束)和过滤解决方案。最后,整个VNS框架和算法的终止条件介绍了第四部分。
3.1。一个方法来解决PF的问题
如图4,任何两个节点之间我和j,每一部分的旅行速度在不同时期可能会有交通状况的影响下,也就是说,车辆行驶的速度在两个节点在同一时间不同的路径可能不同,和车辆的速度旅行在相同的两个节点之间的路径在不同的时间也会不同。旅行速度的变化,两个节点之间的最优路径也可能改变。
为了选择动态路径,我们构建一个最优路径选择模型。算法解决它,我们商店的平均速度任意两个地点之间的多个可选路径对应于不同时期在数据库中。换句话说,灵活性(PF)的路径问题受到时间因素的影响已经被很好地解决了通过最优路径选择模型。
3.2。代的最初的解决方案
在传统VRP、车辆路线的形式通常表现在客户点序列。然而,解决方案形式的传统路线规划不能解决多个电动汽车的问题适当的迷走神经刺激法算法。在TDEVRPTW-PF,我们的目标是提出一个路线规划方案为多个电动汽车同时发布,既可以满足约束和充电方案。因此,我们提出一个概念,虚拟配送中心和多个车辆的水滴分布路线融入一个圆形分布路径,具体解释图5。
给出图表示传统VRP的解决方案6。
后的解决方案表示生成虚拟配送中心在图给出7。
网站在这项研究中,组成分布路线包括客户网站和充电站的网站。传统的解决方案来解决VRP表示(如图6)与配送中心作为一个序列两端和中间的客户网站,这是难以满足旅游多个序列车辆在这项研究。基于传统VRP的解决方案的形式,我们使用混合的顺序排序的客户网站和虚拟DCs(配送中心)来表示车辆路线(见图7)。考虑到算法的时间和空间复杂性,充电站网站并不包含在解决方案,但收费记录,即。,a vehicle chooses to go to a charging station for charging at a certain customer site, based on the traveling route and charging record stored separately. Instead of performing neighborhood transformation on the entire sequence including the charging station sites, we can transform the sequence containing only customer points and then generate a charging history based on the customer point sequence. In this way, the transformation operation of the solution is simpler, and it is made more convenient to carry out large-scale data experiments, and meanwhile, the time and space efficiency of the algorithm are improved. Ultimately, the form of the solution can be organized by two parts: traveling sequence and charging record.
在生成初始序列,序列中的虚拟配送中心的总数等于汽车的数量- 1(见图7)。同时,序列中的配送中心的总数等于汽车的数量加1。首先,序列的两端必须是0,代表实际的配送中心。然后,虚拟配送中心随机插入到炒客户站点序列同时确保他们不相邻。
为了获得一个初始可行解,进行可行性测试生成的初始行驶路线(见部分3.3),充电记录初始可行解。以下,一个具体的例子将说明初始解的生成。假设有10个客户,编号从1到10,3均匀车队服务的特点,B和c,车辆离开虚拟配送中心2 0和收费在5充电站标志着从11到15。
生成初始解的过程可以介绍如下。首先,顾客们是随机安排5-2-4-6-9-7-8-10-3-1。此外,两端,两个0插入代表实际的配送中心。然后,根据nonadjacency的原则,两个0表示虚拟配送中心分别插入序列。最后,最初的解决方案包括充电通过可行性检查记录。
最初的解决方案包括两个部分:一是旅游路线,另一个是收费记录。现在,0代表了虚拟配送中心,每个两个0之间的序列代表一个单一车辆的旅行路线。在这种情况下,序列(0-5-2-4-0-6-9-7-0-8-10-3-1-0)意味着第一汽车服务顾客5,2,4序列。同样,车辆B服务客户6 9和7,C和车辆服务客户8、10、3和1。此外,根据车辆的充电历史,服务客户9后,车辆12 B去充电站充电,和车辆在充电站15 C应该得到能量服务客户3。
3.3。可行的解决方案的判别
为了检查生成的可行性解决方案,检查过程应用于区分是否初始序列是可行的,可以分为以下四个部分(见图左边的部分8)。
3.3.1。决策的车辆数量
对于初始序列,如果两个0是相邻的旅行路线序列,它表明车辆的实际数量减少,和车辆的数量在这样一个初始序列不满足约束条件,也就是说,它是一个不可行的序列。
3.3.2。决定车辆的容量和负载
总重量的货物交付客户站点之间的两个相邻0旅行路线序列与车辆的最大负载。如果超过了最大负载负载,序列是不可行的。体积的测量是类似于负载。
3.3.3。生成和决定收费记录
我们指的是郑20.)计算能量消耗在两个地点之间的旅行,这节中介绍了2.1。考虑的因素如行驶速度与时间和路径改变,实际的负载,滚动阻力,能源消费和能源转换效率,计算更接近现实。
如图9,检查电分为以下两个方面:(1)旅行期间根据能源消耗来确定车辆是否需要充电。作为显示在图9假设车辆的当前节点我,当前的电量是SOC。让以前的节点的能量消耗我−1到当前节点我E0。节点的能量消耗我到节点我+ 1 E2。客户我+ 1我+ 2 E4消耗电力。节点的能量消耗我最优充电站(的总和充电站和节点之间的距离我和站和收费我+ 1是最低,这是使最小距离车辆偏离原来的路线和返回到原始路线)是E0。如果SOC < (E2 + E4)和SOC < (E2 + E3),去车站1和记录的数量站和客户站点数量收费。(2)确定路线序列是可行的旅行期间根据当前的电量。当当前的剩余电池容量车辆无法到达车站最近的当前点,也就是说,当SOC < E1,也是衡量一个公司作为一个不可行的解决方案。
3.3.4。决定的时间窗口
我们更新当前时间每次当车辆到达客户网站通过时间推进机制。比较当前时间和客户的时间窗口,如果超过时间窗的范围,它是作为一个不可行的顺序决定的。
3.4。一种改进的手脚让组件
Mladenovic和汉森30.)首次提出可变邻域搜索(VNS)算法,随后成为运筹学领域的一个研究热点,并具有良好的性能应用到的np困难问题。迷走神经刺激法的基本思想是通过一系列获得近似最优解邻域操作可行的解决方案。满足终止条件后,认为目前的近似最优解是全局近似最优解。
传统的迷走神经刺激法对TSP算法具有相当大的适应性和其他单车问题,但无法解决multivehicle问题。因此,通过生成虚拟配送中心,我们提出一个解决方案适合multivehicle分布,已详细描述部分3.2。接下来,我们将详细介绍了迷走神经刺激法算法结构的基础上,这个解决方案的形式。
3.4.1。社区结构
迷走神经刺激法算法的社区结构是至关重要的。社区结构是不断变换的目的当前可行的解决方案,这样大量的其他解决方案可以从附近的可行的解决方案。在附近结构,算法将可行的解决方案的核心是社区运营。因此,在我们的算法结构,两个互补筛选后选择和有效的社区业务,这样操作可以在附近完全遍历。
(1)社区操作1。最重要的是,两个位置必须确定可行解序列年代(两端除外),然后顺序是相反的两端获得一个新的序列 ,如图10。
(2)社区操作2。首先,两个位置在可行解序列应该确定(两端除外),然后整体序列中间的两个位置移动到开始整个序列的一部分。应该注意的是,最初的点代表了配送中心,因此初始点的位置保持不变。序列的可动部分实际上是插入第一点后,如图11。
下面描述了社区结构算法的程序通过社区结构1为例:第一步:输入一个可行的解决方案S0,附近的近似最优解年代=S0。步骤2:在序列中的位置的初始操作执行更改我= 2,j=我+ 1。步骤3:设置最大数量米社区行动。最初的记录是米= 0。步骤4:米+ +;如果米≥米,停止。第五步:(1)的位置我在倒数第二的序列,我= 2,j=我+ 1,返回到步骤4。(2)如果的位置j末端的序列,我+ +,j=我+ 1。(3)执行社区操作在两个位置1我和j在可行解序列生成年代′。步骤6:确定S′是可行的。如果不是这样,j+ +,返回到步骤5。第七步:确定S′更好的;如果更好,年代=年代′。第八步:j+ +;返回到步骤5。
3.4.2。盾组件
迷走神经刺激法算法的盾是一个主要组成部分。它的主要功能是执行社区操作可行解决方案的输入,生成近似最优解的范围内多个轮流社区当前的解决方案,并选择通过比较新的近似最优解。两种类型的社区结构,介绍了相应的操作3.4.1在这里,它将不会重复。
越南盾的具体操作步骤如下:第一步:输入一个可行解,并将其分配给当前的解决方案。步骤2:生成社区进行社区结构1对当前解决方案,和屏幕的当地社区1中近似最优解。步骤3:比较当地的近似最优解附近的1和当前的目标函数值的解决方案。如果当地的近似最优解的目标函数更好,替换当前的解决方案与当地的近似最优解的附近1,回到步骤2;否则,继续步骤4。第四步:生成社区进行社区结构2对当前解决方案,和屏幕的当地社区2中近似最优解。第五步:比较当地的近似最优解附近的2和当前的目标函数值的解决方案。如果当地的近似最优解的目标函数值是更好,替换当前的解决方案与当地的近似最优解的附近,并返回步骤2;否则,执行步骤6。第六步:电流近似最优解=当前解决方案。输出当前的解决方案。
3.4.3。震动过程
盾后操作上执行当前的近似最优解,盾的输出需要与全局近似最优解。如果当前的近似最优解的目标函数的多次迭代大于全局近似最优解,我们可能会在当地的近似最优解的情况。跳过局部优化,大转换所需的电流近似最优解,即振动过程的主要意义。
一个简单的例子,如图12,删除“0”的两端序列0-5-2-4-0-6-7-9-0-8-10-3-1-0。因此,它变成了5-2-4-0-6-7-9-0-8-10-3-1。随后,我们把它分成四个部分:第一部分是5-2-4,第二个是0-6-7,第三是9-0-8,第四个是10-3-1。原来的第三,第四,第二,和第一段排列形成一个新的当前解决方案0-9-0-8-10-3-1-0-6-7-5-2-4-0。
3.4.4。一种改进的TDEVRPTW-PF迷走神经刺激法算法
迷走神经刺激法算法的组件上面已经介绍了。图8迷走神经刺激法描述了整个过程,左边的一部分已经介绍了部分3.3,而正确的部分说明了其余的迷走神经刺激法算法的一部分。迷走神经刺激法算法的步骤介绍如下:第1步:生成初始路线序列根据原则。步骤2:检查车辆的总和;如果条件不匹配,返回步骤1。步骤3:检查车辆的最大负载和体积是否满足要求。如果没有,回到步骤1。第四步:生成历史和检查电量收费。如果条件不满足,回到步骤1。第五步:查看时间窗口。如果条件不满足,回到步骤1;如果遇见了,把它作为一个可行的解决方案。第六步:设置一个迭代计数器米= 0;越南盾的最大迭代次数M。第七步:米+ +;执行盾操作上可行解在多个社区找到近似最优解。第八步:确定新的可行的解决方案是比当前可行的解决方案。如果更好,目前可行解=新的可行的解决方案。第九步:执行摇晃来避免在当地的近似最优解。第十步:如果米>米,停止;如果没有,回到步骤7。
3.5。Double-Optimization方法
为了提高全局近似最优解的优化程度和稳定通过迷走神经刺激法算法,我们生成多个初始序列根据上述原则和迷走神经刺激法同时运作。通过比较每组所产生的全局近似最优解,是最好的一个作为最终的最优解。提高时间效率为目的的整个过程,我们使用多线程的主要框架double-optimization编程,取得一个好的结果在随后的实验和数据分析。
4所示。数值实验
在本节中,进行了大量的数值实验来评估我们的修改VNS算法的性能。在第一部分中,我们目前的开发工具,实验环境和参数设置的数值实验。在第二部分中,一组初始条件下生成的解决方案。然后,我们评估的性能解决方案和详细解释旅游路线。此外,我们还分析了改进算法的效率和解决方案优化的程度。最后,电池容量的敏感性分析,加载,体积,和第三部分中演示了电动汽车的数量。
4.1。实验环境和参数设置
我们修改的手脚被实现为一个Microsoft Visual Studio 2017中的代码在c++软件在Windows 10.0平台上的个人电脑与英特尔(R) (TM)核心i7 - 6500 u @ 2.50 GHz CPU和4 gb的内存。
我们的数据是随机生成的模拟真实的分布情况。我们随机选择30个客户,12个充电站,5电动汽车作为我们的实验实例。表3显示了基本参数对TDEVRPTW-PF实例。根据实际情况,参数设置电动汽车的能源消耗表4。参数对电动汽车本身和客户所示,分别在表5和6。
的地理分布的客户,收取站,配送中心是如图13和表6给客户的参数。
4.2。实验TDEVRPTW-PF实例
4.2.1。准备代TDEVRPTW-PF实例
的基本条件进行数值实验给出了在前面的部分。在本部分中,波动的速度是由时间和路径,这是有限的范围从50公里/小时60 km / h。之后,迷走神经刺激法算法程序运行的最大迭代数集,300次,在表获得的近似最优解7。在近似最优解,30个客户服务的总旅行距离5 EVs是1512.4公里。具体的旅游路线和收费记录如下。
4.2.2。迷走神经刺激法在TDEVRPTW-PF的性能
我们使用生成的TDEVRPTW-PF测试实例来分析我们的迷走神经刺激法算法的性能。图14显示了特定的旅游路线,可以看出,电动汽车的旅行路线是闭环路线与水滴的形状。它显示了明显的区域分布情况。这是一致的分布安排物流企业在现实中,这证明了我们的解决方案的正确性。
然而,我们也发现一些看似不合理的路线同时,如电动汽车5选择出客户13至客户9而不是客户14。相反,电动车2是需要从客户返回2,然后前往客户14。通过探索原因,我们安排客户14背后客户13。检查新序列之后,发现电动车2到达客户16在54所以不在其服务时间窗口(12:00-22:00)。同样,我们尽量安排客户16背后客户18 - 26背后客户29岁,然而,所有这一切不符合其服务时间窗口当到达客户16日和底层的原因是,所有车辆在同一时间将开始交付规定的先决条件。
一系列的实验的基础上,我们得出一个结论,解决方案的性能影响因素主要分为两类。一个是约束条件,包括客户的硬时间窗、车辆载荷约束和车辆容量约束。另一种是迷走神经刺激法算法本身,基于迭代的最大数量的算法和在附近的最大迭代数。解决方案的部分非理性因素的影响第一类型是不可变的,但是受到第二种类型可以更改,这将在下一部分中详细解释。
4.2.3。分析迷走神经刺激法的效率
从实验中可以看出TDEVRPTW-PF实例,我们改进VNS算法能够生成我们想要的解决方案来解决TDEVRPTW-PF。然而,我们需要解决的问题是使过程更高效和优化分配方案。通过调整的重要参数,改进算法,进一步实验如表所示8。
从实验结果的分析表8,它可以发现多线程的设置可以显著提高近似最优解的优化程度和鲁棒性的某些其他常数条件下时间效率。同样,在附近的最大迭代数无显著影响的近似最优解。最后,当线程的最大数量的迭代和社区是恒定的,迭代的最大数量的算法可以在一定程度上提高解决方案的优化。在给定的实验环境和接受的情况下,我们最终采用可变邻域搜索算法,在附近的最大迭代数等于30,在算法迭代的最大数量等于300,和线程的数量等于10,提高时间效率和优化程度的解决TDEVRPTW-PF。
4.3。敏感性分析
4.3.1。灵敏度分析的电力
的实验环境和参数设置上面的例子,进行敏感性分析是通过改变电池容量(电电动车充满电时)的电动汽车。表9显示相应的十组实验结果不同的电池容量。
实验结果绘制在一个二维坐标系统表明,解决方案的目标函数值降低电动汽车的电池容量增加260千瓦时的范围从120千瓦时。目标函数值之间有很强的相关性和电动汽车的电池容量的解决方案,和相关系数是0.9683。原因是,当车辆的数量越少,平均每辆车需要服务的客户数量会增加,这将增加充电时间和总计划的旅行距离。当电动车的电池容量大于或等于260千瓦时,解决方案的目标函数值稳定在一定的范围内波动,和一个电动汽车甚至可以没有充电完成分配的任务。的下降趋势近似最优解的目标函数值也就消失了。在解决方案的鲁棒性方面,每一个近似最优解的波动大约是5%,这是在可以接受的范围之内,当电池容量是恒定的。
通过灵敏度分析电动汽车的电池容量,我们得到一个建议,根据实际的分配需求,物流企业应该选择电动汽车的电池容量的拐点汉英曲线在图15,可以有效地降低成本,提高经济效益。
4.3.2。灵敏度分析的体积
除了电力,电动汽车的最大负荷和最大体积也影响性能的解决方案。因为类似的属性,我们选择最大体积进行灵敏度分析。实验结果表10表明,当最大体积大于或等于20 ,与最大体积的增加,目标函数值的解决方案提出了一种下行趋势与波动。当最大体积达到29 ,解决方案的目标函数值不再减少。原因是客户数量的电动车可以直接与车辆的最大体积成正比,当汽车的数量是固定的,车辆的最大体积越大,越可行的驱动序列是可用的。
这是汽车采购的实际意义,我们可以得到最好的车辆音量级别通过分析C-V曲线在图的拐点16。因此,可以选择电动汽车的类型和模型的基础上,以进一步提高经济效率的分布。
4.3.3。灵敏度分析的电动汽车的数量
给出的实例4.2.1展示如何交付和电荷分布的过程中在给定数量的电动汽车。然而,事实上,过多或过少的电动汽车为某些客户会影响成本或服务的服务质量。因此,我们进行灵敏度分析电动汽车的数量。表11展示了我们的实验结果。在图17,趋势线氮是拟合结果显示。在30个客户的情况下,增加车辆的数量从3的过程,首先解决方案的目标函数值降低,然后增加,达到最小值时,车辆的数量等于5。这表明,在电流分布条件下,5车辆的成本可以减少到最低水平。此外,目标函数值的解决方案的健壮性是最好的,和平均绝对偏差的所有近似最优解的目标函数值约为1.27%。因此,我们应该选择最好的电动汽车数量和做一个权衡根据所需的鲁棒性在实践中当安排分配计划。
5。结论
在本文中,我们目前TDEVRPTW-PF考虑时间窗,充电时,能源消耗,和路径的灵活性。为了确定任意两个地点之间的最优路径,建立了0 - 1整数规划模型,减少能源消耗和距离。最优路径选择模型的基础上,建立了其他模型来解决多个电动车辆路由问题的时间窗口。
然后,我们选择在VNS算法具有良好的影响的np困难问题的启发式算法作为我们的算法框架。我们修改和优化的基础上TDEVRPTW-PF。之后,编程和调试程序的完成基于改进的手脚。
最后,大量的数值实验是由运行程序。我们解释了实验实例和分析算法的效率。此外,还进行了敏感性分析。通过调整一些参数如电池容量、最大载荷、最大体积,和电动汽车计划的数量,我们得出一些结论,现实意义为物流企业采购操作和车辆安排。
然而,车辆路径问题,优化TDEVRPTW-PF是没有止境的。在未来,进一步的研究可能会专注于能源消耗分析和剩余的电力EVs估计。此外,不同类型的车辆需要考虑。进一步的研究对这个话题也可能地址等详细的工作需要执行不同的起飞时间EVs和插入随机分布的任务。所有的研究旨在使建立的模型更接近现实,和科学研究的结果更能服务于社会。
数据可用性
使用的数据来支持本研究的结果包括在纸上。更多细节可以从相应的作者向读者。
的利益冲突
作者宣称他们没有利益冲突有关的出版。
确认
本研究工作得到了国家自然科学基金(没有。71801018)和基础研究基金为中央大学(没有。2018 rc39)。