基于ga和sa混合算法的车辆路径问题研究

基于ga和sa混合算法的车辆路径问题研究

dantzig等人提出了车辆路径问题。旅行客问题是psp的一个特例（当psp只包含一条路径且没有能力限制时，它将成为一个旅行社问题）。由于Garey和Johnson证明了TSP是NP-难问题,因此,VRP也是NP-难问题。VRP是一个困难的组合优化问题,到目前为止,仅有一些相对较小规模的VRP能保证被求解到最优。国内外专家和学者对VRP及其求解方法进行了大量的研究,提出了许多关于不同类型VRP的不同的求解算法。其中,Fishetti用分枝定界算法求解具有能力约束的VRP(CVRP),获得较好的求解结果;Chao使用改进启发式求解了周期VRP(PVRP),并对几个Windmill形状和StarofDavid问题进行测试,取得好的结果;Vigo用启发式对不对称能力约束的VRP进行了求解;Gendreau用禁忌搜索求解VRP也是一种有效的方法;Ateahiru用3-opt和模拟退火结合求解VRP获得满意的结果,等等。其他求解VRP的方法还有遗传算法、最小化K-树算法等。从研究可知,分枝定界算法不适合求解大规模VRP问题;启发式算法始终要求保证可行解;遗传算法爬山能力差;禁忌搜索全局性差等。总之,单纯使用一种算法求解大规模VRP,一般都存在各种缺陷,难以获得更为满意的结果。因此,求解大规模VRP的方法必然向混合算法发展。另外,人们在求解VRP时,在聚类和排序之间存在矛盾,如果先排序后聚类(存在分解问题),即使排序和聚类两个阶段分别均得到最优解,其最终结果也不一定是最优解;而先聚类再排序,显然不一定得到最优解;既使使用改进搜索算法,在排序过程中也必须使用某种处理方法对已聚类的元素进行不断改进,搜索的全局性受到很大限制。目前,国内外关于VRP的研究很多,但其车辆数一般都是已经确定的。本文提出一种车辆数不确定的车辆路径问题(VehicleRoutingProblemwithUncertainVehicleNumber,UMVRP),并用遗传算法和禁忌搜索算法相结合来求解UMVRP。1uvmrp模型的构建1.1车辆数不确定考虑UMVRP可以概述如下:假设有n个城市,每个城市的位置坐标和货物需求已知,车辆的负载能力一定,但车辆数不确定。UMVRP是对车辆(每辆车一条路径,开始和终止都在起始点(depot)所要访问的城市进行排序,使所有城市都满足要求,且总旅行成本最小。假设每个城市被分配到某一辆车(除了depot被所有车辆访问),访问一个城市的一辆车也必须离开那个城市,每辆车所访问的城市的需求总和不能超过车辆的能力。1.2车辆能力模型为了叙述方便,引入下面的符号:(1)城市集合,V={i},i=0,1,…,n,且i=0指depot。(2)车辆集合,M={k},k=1,…,m,m是一个待定的决策变量。(3)城市i的需求量,i∈V(i=0时,q0=0)。(4)城市i到城市j的距离,ci0=0,c0i=0,i∈V\{0},cii=∞,i∈V‚城市间距离矩阵‚C=(cij)。(5)每辆车的能力(每辆车的载重量相同),Q≥max{qi,i∈V}。xijk={1如果车辆k在访问城市i之后立即访问城市j0其他yik={1如果车辆k访问城市i0其他由如上假设,可建立UMVRP模型如下:minm(1)min∑i,jcij∑kxijk(2)约束:m∑k=1yik={1i=1,2‚⋯,nmi=0(3)n∑i=1qiyik≤Qk=1,2‚⋯,m(4)n∑j=1xijk=n∑j=1xjik=yik(5)i=1,⋯,n;k=1,2‚⋯,m∑i∈S∑j∈Sxijk≤|S|-1(6)对于所有S⊆{1,2‚⋯,n},k=1,2‚⋯,m‚yik∈{0,1}(7a)xijk∈{0,1}(7b)i=0,⋯,n;j=0,⋯,n;k=1,⋯,m最少车辆数由下式决定:m=[JX-*3]-[JX*3]n∑i=1qi/Q[JX-*3]-[JX*3](8)其中:目标式(1)是保证车辆数最少;式(2)是最小化旅行距离。约束式(3)保证每个城市被分配到某辆车(除了depot被所有车辆访问);式(4)是车辆的能力约束;式(5)保证访问一个城市的一辆车也离开那个城市;式(6)消除子回环;式(7a)和(7b)是参数的取值范围,2uvmp的混合算法2.1限制使用的因素尽管遗传算法能够胜任任意函数和高维空间的组合优化问题,但是对于像优化大规模神经元网络的权系数,优化网络的结构等超大规模的优化问题,遗传算法的应用就受到了限制。究其原因,主要在于遗传算法在进化搜索过程中,每代总是要维持一个较大的种群规模,限制了遗传算法的使用。遗传算法的另一个不足之处是“早熟”。造成这种成熟前收敛的原因,一方面是遗传算法中最重要的遗传算子——交叉算子使群体中的染色体具有局部相似性,从而使搜索停滞不前;另一方面是变异概率又太小,爬山能力差,以至于不能使搜索转向解空间的其他区域进行搜索。2.2启发式算法获得初始解文献阐述了禁忌搜索算法的原理和应用。禁忌搜索算法的搜索速度比遗传算法的搜索速度快,但是其对于初始解具有较强的依赖性。一个较好的初始解可使禁忌搜索算法在解空间中搜索到更好的解,而一个较差的初始解则会降低禁忌搜索算法的收敛速度。为此,人们往往使用启发式算法来获得一个较好的初始解,提高禁忌搜索算法的性能。禁忌搜索算法的另一不足是在搜索过程中初始解只能有一个,在每代也只是把一个解移动到另一个解,即为点-点操作,而不像遗传算法那样每代都是对多个解进行操作,即为种群-种群的操作。2.3城市染色体的基于自然数编码的新能源检测在求解VRP时,一般使用先聚类后排序(CFRS)或先排序后聚类(RFCS)方法。CFRS最早是由G.gillettL.Miller使用两阶段启发式算法求解VRP时使用的,它是先用启发式把节点分为若干条路径,再对各条路径中的点排序。RFCS产生于CFRS之后,Besley首先给出了基本RFCS的思想,它是先对所有节点进行TSP排序,然后对此大的路径进行分割聚类,其中的聚类过程描述为分割问题,处理分割问题的典型方法是最小化分割时的附加成本(具有能力约束)。如前所述,这两种方法都存在一定的不足之处。针对上述各种方法的不足,本文提出用混合遗传算法来求解UMVRP,如图1所示。对遗传算法主要要素的构造包括:(1)染色体编码方式。本文中,令每个染色体对应一个解,采用自然数编码,设计染色体V={vi}(i=1,…,n)。其中,vi表示染色体中的基因,对应于第i个城市的城市号(用自然数编号),这种编码方式保证了式(3)、(5)和(6)的可行性。(2)适应值函数的确定。目标函数:f=∑i,jcij∑kxijk(9)定义染色体对式(4)的可行距离ID,用以表征染色体关于式(4)的非可行程度:ΙD=max{0,Q′m-Q}(10)式中:Qm为分配给车辆m的总负荷;Q为车辆的能力。设计适应值函数为fitness=Cmax-f-αmax{0,Q′m-Q}(11)式中:Cmax为足够大的常数;α为式(4)的不可行惩罚系数,这里,α为较大的正整数。适值函数对于式(4)的惩罚处理,只能使新一代染色体的非可行程度降低,而不能杜绝非可行染色体的存在,本算法并不局限在可行域中寻优,以图扩大寻优的途径。(3)选择策略。本算法采用滚轮盘的方式进行复制,复制的选择概率由下式获得:Ρg=fitnessg/G∑α=1fitnessα(12)式中,g=1,2,…,G,G为种群规模。(4)遗传算子。采用CycleCrossover(CX)算子,采用禁忌搜索作为变异算子。详细步骤如下:(1)初始化。设置最大代数max-gen、种群模型G、交叉概率pc和变异概率pm。计算所需车辆的最小值m,代数gen=0。(2)初始解。随机产生n个城市的G个排列作为初始染色体,其顺序聚类为初始解,初始解不一定可行。(3)选择。按滚轮盘方式选择出G个染色体,如果这些染色体不包括最好解best-fit,则用best-fit代替当前代最差的染色体。(4)交叉。对每个染色体,按照交叉概率pc,判断是否使它参加交叉(随机产生一概率p,如果p≤pc,则此染色体参加交叉),如果此染色体参加交叉,则采用CX方式进行交叉。(5)变异。对每个染色体,按照变异概率pm,判断是否对它进行变异(随机产生一概率p,如果p≤pm,则对此染色体进行),禁忌搜索作为变异操作算子。(6)最好解。按照顺序聚类成m条路径后,计算解的目标函数值,并识别解的可行性,然后计算解的适应值。记录至当前最好的可行解best-fit。gen加1,如果代数gen小于max-gen,则转(3)。(7)最终解。如果已获得可行解,退出;否则,gen=0,m=m+1,转(3)。2.4禁忌搜索步骤若用禁忌搜索方法求解VRP时,一个解是m条路径R1,…,Rm的集合S(对应染色体{vi}(i=1,2,…,n)),其中路径Rr={v0,vr1,vr2,…,vrn,v0},v0为VER中的depot,{vi}中每个元素属于且仅属于一条路径。这些路径可能是关于能力约束可行或不可行的。写:vi∈Rr,如果vi是Rr的一个元素;(vi,vj)∈Rr,如果vi和vj是Rr的2个连续的元素。对于任何解x,搜索决定于一个参数向量:Ρ=(x0,W,Λ,θ,Τ,nmax)其中:x0为初始解;W为允许移动的元素的集合,这里包括所有的城市;Λ为移动的构成方式,这里是W中的两元素交换;θ为禁忌表的长度;T为最大循环次数;nmax为适应值函数没有任何改进时,允许循环的最大次数。禁忌搜索步骤:(1)初始化。设置循环次数t=1,没有移动被禁忌。最好解x*=x0,最好解的目标值f(x*),适应值函数fitness(x*)=Cmax-f(x*)-αmax{0,Q′m-Q}(2)评价所有的候选移动。考虑所有城市vi和vj(i,j∈W)的两元素交换,从中找到最好的移动,产生的新解为x′,解的适应值函数为fitness(x′)。(3)禁忌判断。判断是禁忌移动否,是转(4);否则转(5)。(4)改进。判断fitness(x′)>fitness(x*),成立,则fitness(x*)=fitness(x′),x*=x′,转(5);否则,转(2)。(5)修正。若城市vi和vj(i,j∈W)已做过交换,则直到循环t+θ之前禁止元素vj和vi(i,j∈W)交换,θ是一个整数。t=t+1,修正x*,f(x*)和fitness(x*)。(6)终止检查。如果t>T或fitness(x*)在最后nmax个循环中没有增加,则终止禁忌搜索;否则,转(1)。3车辆损伤的检测为了测试算法的有效性,分别采用文献的5个典型问题进行了测试,并与目前已知的最好结果进行了比较。算法用C语言编程,在PC586兼容机上运行,由于