vrp-混合编队车辆路径问题的混合算法研究

vrp-混合编队车辆路径问题的混合算法研究

车辆路径问题（虚拟现实）是运营领域中的一个重要问题。在该领域，许多科学家研究了基于不同实际情况的虚拟现实和三维算法的模型和算法。在文献中，他们对虚拟现实的问题及其精确算法和近似计算方法进行了综合研究。在文献中，本文描述了这种特殊的三维问题：停车场里有几个不同的单元，每个单元有一定的流量。同一辆车可以组成一个包含不同数量的工作群体（以下简称团队）。每个单元的车辆数的数量受该车辆数的限制，因此有一些任务。每个任务都有不同的地理距离，如起点、终点、运输需求、货物装载时间、货物装卸时间和其他任务。每个任务都有不同的任务，比如起点、终点、，无论运行的次数和次数都不同。每个任务都可以接受相同数量的车辆，每个任务都可以接受相同数量的车辆。在执行任务时，团队可以多次往返，不同技能的团队可以不同时间重复，因此任务的使用时间也不同。这些问题广泛存在于大型公司的内部货物运输车辆规划和管理领域。本文通过引入“车队模式”定义,提出了多种车队模式下的混合车队车辆路径问题的求解框架,设计了基于遗传算法和禁忌搜索启发式的混合算法,并以实例计算验证了框架、模型和算法的有效性·1有一个可能模式一个可能模式为了方便建立问题求解框架和模型,对问题附加如下假设:(1)对于每个任务,如果按照任务最多允许同时访问车辆数组成车队,任务的需求在车辆允许最大工作时间内可以完成;(2)所有任务的最多允许同时访问车辆数相同;(3)车辆一经编组成车队,则在车辆的工作时间内保持固定,不拆散;(4)车队只有在完成一个任务后,才可以执行其他任务·下面给出车队模式定义·定义k种车按照1辆,2辆,…,P辆的车辆数组合成车队,包含1辆车的车队有mk1个,包含2辆车的车队有mk2个,…,包含P辆的车队有mkP个,mk1,mk2,…,mkP满足1×mk1+2×mk2+…+P×mkP=Mk,所有种类车辆组成的车队的一个可能组合,称为一个车队模式·这里k∈V,V为车辆种类集,V={k|k=1,…,v},P表示任务允许最多同时访问车辆数,Mk表示k种车的车辆数·例如:有3种车,每种5辆,任务最多允许同时访问车辆数P=2·用3位自然数组合编码表示车队,第1位表示车种,第2位表示车队所包含车辆数,第3位表示该车种以该车辆数组成的车队的编号·则:{111,121,122,211,221,222,311,321,322}为模式1,{111,112,113,121,211,221,222,311,321,322}为模式2,…,以此类推,共有9种可能模式·通过引入车队模式定义,将前面所述问题的求解分为如下两个阶段·第1阶段:确定一种车队模式·按照车队模式定义:对于k种车,确定决策变量mk1,mk2,…,mkP的一组值,使之满足1×mk1+2×mk2+⋯+P×mkP=Mk,0≤mkP≤[MkP],p∈{1,2,⋯,P}1×mk1+2×mk2+⋯+Ρ×mkΡ=Μk,0≤mkΡ≤[ΜkΡ],p∈{1,2,⋯,Ρ},以此类推,每种车确定一组值,所有的值构成一种车队模式·第2阶段:对于第1阶段确定的一种车队模式,求解一个车辆能力不同,以最小化费用为目标的混合车队车辆路径问题(HeterogeneousFleetVRP)·将车队聚结成能力变大了的车,每个车代表一个车队,将任务聚结成网络图上的顶点,顶点0代表停车场,车队从任务i到任务j的转移时间由连接顶点i和顶点j的弧值tij代表,(这里tij≠tji),任务对车辆能力的需求以任务被车队服务的时间表示·求解以上的HVRP问题,得到问题在一种车队模式下的解,保留此模式及对应的解,返回到第1阶段,产生一新的车队模式,进入第2阶段,求出新模式下问题的解,将其与原保留的解进行比较,保留更好的解和对应的模式,如此循环,直到没有新的模式产生为止,将保留的最好解和对应模式作为问题的最终解·2混合车联网模型问题总的求解框架如上所述·因车辆数有限,组合成的车队模式数量有限,对问题第1阶段,本文采用枚举的办法用启发式每次生成一个车队模式·这里主要介绍混合车队车辆路径问题的求解算法·混合车队车辆路径问题在车辆能力相同时,则成为一般VRP问题,由于已证明VRP问题是NP-难问题,所以混合车队车辆路径问题显然也是NP-难问题·本文提出一种遗传算法(GA)和禁忌搜索(TS)启发式相结合的混合算法,利用遗传算法进行全局搜索,利用禁忌搜索进行局部改进·2.1过程任务编码本文提出一种车队、任务分段组合编码-解码的方法·该方法分别对车队和任务编码,将两段编码组合在一起,构成一个染色体·其中车队段代表车辆序列,任务段代表任务序列,而问题的解则通过对染色体按解码规则进行解码来得到·(1)有个人所需赔偿的车道数采用车队、任务分段组合编码·染色体长度为(m+n),前一段码长为m,m为给定模式下的车队数,基因为1到m之间的自然数·第i个位置基因k1表示车队k1在车辆序列的第i个位置·后一段码长为n,n为需分派车辆的任务数,基因为1到n之间的自然数·第j个位置基因k2表示任务k2在任务序列的第j个位置·(2)基于垂直流值的方法,把任务纳入ristep1:从染色体车队段给出的车队序列按车队顺序依次取出一个车队i,建立i的一个只包含停车场的初始路径ri·step2:判断染色体任务段给出的任务序列中是否有未派车的任务·如果有,则从任务序列按任务顺序依次取出一个未派车任务,然后转step3;否则转step6·step3:如果任务不能被车队i服务,则将任务放回任务序列原来位置,转step2,取下一个任务·试将任务加入路径ri,如果加入任务后ri上所有任务所需服务时间和任务间转移时间之和(包括离开、回到停车场的时间)大于车队i的车辆最大允许工作时间,则将任务放回任务序列原来位置,转step4;否则,将任务加入ri,然后转step2·step4:如果车队序列中有未分派的车队,则转step1,取下一个车队,否则转step5·step5:引入可服务所有任务的虚拟的租车车队,其固定费用和单位时间转移费用远大于现有车辆,将未派车的任务分派给租车车队·step6:记下已分派并且除停车场外路径不为空的车队和与其对应的路径,作为此染色体对应的问题的解·Step7:利用禁忌搜索启发式对解进行改进;(详见2.2)·Step8:结束·采用上述的染色体编码和解码方法,可以尽可能多的满足HVRP问题约束,对于不满足车辆能力约束的情况,则通过引入租车车队,将租车费用作为惩罚·(3)初始群体采用随机生成的办法产生pop-size个染色体个体·(4)采用ox算子进行交叉采用按段独立交叉和按段独立变异·交叉:对染色体的每段分别进行交叉,采用应用于旅行商问题的OX算子·变异:对染色体的每段分别进行变异,对车队段,采用从右向左循环移位变异;对任务段,采用换位变异·(5)目标函数的值因目标函数求最小值,所以染色体的适值定义为F(x)=Cmax-f(x)·其中Cmax是一个比较大的数,保证F(x)>0,f(x)是目标函数值·(6)选择策略采用最优保持策略,保留上一代中μ个最优个体,其余选择下一代中pop-size-μ个最优个体·2.2反向移动t对GA中每个新产生的后代,在其进入种群之前应用禁忌搜索对其进行局部改进·这里介绍禁忌搜索中邻域的定义和禁忌表的构成·对染色体对应的解x中路径按照染色体车队段中车队序列的顺序排序·邻域定义:从解x中任取一条路径r,将最末尾的任务il(不包括停车场)从路径r中取出,按照染色体任务段的任务序列的顺序,将il插入到r后面第1条可服务该任务的车队路径r+,称为正向移动·或者,将最开始的任务if(不包括停车场)从r中取出,按照染色体任务段的任务序列的顺序,将if插入到r前面第1条可服务该任务的车队路径r-,称为一个反向移动·如路径r1后面已没有可服务任务il的车队路径或将il插入路径r+后,r+不满足时间约束,则此正向移动不可行·同样,如路径r1前面已没有可服务任务if的车队路径或将if插入路径r-后,r-不满足时间约束,则此反向移动不可行·从当前解x所有的可行移动(包括正向移动和反向移动)而产生的解的集合定义为解x的一个邻域,记为N(x)·禁忌表的构成:如果第t次迭代中,作为一个移动,任务i从路径r1取出,插入到路径r2,则直到t+θ次迭代之前,把任务i插回到r1的移动是被禁忌的,这里θ为禁忌表长度·但如果把任务i插回到r1的移动产生的解x′的目标值f(x′)小于吸收水平函数A(s,x)的值,则不禁忌·采用这种移动方式,保留了染色体中基因的顺序特性,可有效避免GA中染色体的有用模式因禁忌搜索而遭到破坏·3需要预充电机的车轮模式和最佳解的确定采用上述方法,对来自某大型企业的实际派车数据进行了计算·算法程序采用Java语言编制,程序运行在PⅡ/350微机上·程序中设定初始种群大小为40,交叉概率pc=1,变异概率pm=0.3,最大代数为100·程序用时36s·由于初始种群是随机产生的,程序运行10次,记录下的最好目标值,最差目标值,平均目标值,如表1所示·最好解对应的车队模式和最好解路径分别如表2,表3所示·由于该企业每班需派车的任务中,一些任务的运输量比较大,需要车队服务时间较长,在作者的数据中也有这种情况,所以,计算结果中有6个车队的路径上只有1个任务·计算结果的最好值、最差值、平均值非常接近的原因之一是数据中许多任务之间的转移时间相同,而车辆的固定费用和单位时间转移费用也相同·4