第卷第期山东科技大学学报#自然科学版∃&%∋) !年∀月∗&+,坦∀&−./01∋2&,34/5675819:−&段5;,70,2<改=/,&∋呸妙#)09+10∋段57,7;∃>77 !文章编号=∀≅一!≅?≅# !∃ 一 Α一 !Β%ΧΔ问题的一种启发式算法柏明国‘李书金“韩梅!#∀山东科技大学信息科学与工程学院山东泰安≅∀ ∀ΕΦ河北大学河北保定≅ ∀ Φ!新汉矿业职工大学山东莱芜≅∀∀ ∃摘要=推广了>75,∋77%5&3提出的解决ΓΒ%ΧΔ的方法给出一种解决Β%ΧΔ的启发式葬法并且举例说明了这种算法的有效性与优越性关键词=车辆路径问题Φ容量固定的车辆路径问题Φ穿擂过程Φ细化过程中图分类号= ∀≅文献标识码=ΓΓΗ7+1557Γ∋3&159/Ι&−1Β%ΧΔΓϑΚΛ5,33+&∋Μ∋./+Ν5,ΟΗΓ)Λ75!#−Κ,−&∀窃∋737&;.57,770,2Π,3..4<0<50,./0,&2,3≅∀ ∀ΕΒ/5,0ΦΗ7Θ5,45678181:确。253Η7Θ5 ≅∀ Β/50Φ!Ρ5,Σ7,Λ5,53Γ2∋9Β&∋737Μ05Σ+/.0,2&3≅∀∀ Β/5,0∃ΓΘ1079=Κ,9/58Τ0Τ71Σ7Τ1787,90/7+15570∋3&159/Ι&−Β%ΧΔΘ:7Υ97,25,3>7,57∋7%53&长ΑΙ79/&27ΙΤ∋&:72&−1&8∋65,3ΓΒ%ΧΔ0,27Υ7ΙΤ∋5−:5987−−779567,7880,28+Τ715&159:Ω7:Σ&128=%ΧΔΦΒ%ΧΔΦ5,87195,3Τ1&7788Φ17−5,5,3Τ1&7788车辆路径问题#%ΧΔ∃是著名的组合优化问称阵时即Β<∴Β叫对称的6ΧΔ记为Β6ΧΔ题可以看作是旅行售货员问题#<.Δ∃的推广否则为非对称的情形记为ΓΒ6ΧΔ解决Β6ΧΔ要求对停在中心车库里的一队车辆做出安排服的方法和解ΓΒ%ΧΔ的方法是不同的借鉴解决务于一群顾客所做决定最优%ΧΔ问题应用在ΓΒ%ΧΔ问题的策略得到解决Β%ΧΔ问题的方交通运输地勤分布与管理等方面%ΧΔ问题法对653。>7,5∋77Ξ]给出的Γ76ΧΤ问题的一是)Δ难的问题提出的精确算法只能有效解决种启发式方法推广到Β%ΧΔ中此算法得到的顾客数不多于Α 个的情形对于人数多于Α 的结果优于用文献〔Α」中给出的两种算法所得到的情形精确算法大多采用松弛法得到一下界〔‘〕结果当点数较多时得到的下界和最优值的误差也较Β%ΧΔ可以归结为图论问题=假定⊥∴#%点数较多的%ΧΔ问题大多采用启发式算Π∃是一完全图大对%∴∀ ∀…司是点集Π是弧法Ξ,!〕或精确算法与启发式算法相结合的方法集点∀…,与,位顾客相对应每一个点5这里研究Β%ΧΔ的启发式算法在Β%ΧΔ中每有非负需求而点_与中心车库对应假定它有需求“。一 给定客户集“3:位顾客#假定有,位顾客∃都有一定的需求车辆令“8#∃一,孙Φ表类型都相同容量都是Ψ#不妨设Ψ之Ι0ΥΖ2‘[∃示此集合的全部需求非负花费ΒΝ5#5护∃Ν与每且满足客户需求要求对车辆做出安排满足每位条弧#5Ν∃任Π相对应表示从5到Ν的费用⎯顾客的需求每位顾客只接受一辆车的服务每辆#⎯∃⎯Ι5∃其中⎯Ι5是满足顾客需求的最小车辆车服务完都必须返回车库每辆车所服务的顾客数⎯有时取⎯Ι=或者通过解装箱问题得到需求量之和不能超过Ψ使所花的费用之和最小Β%ΧΔ要求找到一个至多⎯条简单路径的集合#费用可用时间或里程表示∃当花费矩阵Β是对使得所有回路的费用之和最小并且满足=收稿日期= 一∀一∀ 作者简介=柏明国#∀Ε?Ε一∃!男山东曹县人讲师博士研究生主要从事优化方面的研究第期柏明国等=Β%ΧΔ问题的一种启发式算法#∋∃每条路径必须经过_点Φ交换以及点的移动达到组合优化的目的使总费#∃每位顾客5任%α[ [正好被服务一次Φ用值进一步下降得到最优解及次优解同一路!#∃每条路径凡#Ν∴∀一⎯∃需求之和不超径间的弧交换可参看文献【≅〕对于不同路径间的过Ψ弧的交换以及点的移动方法结合对称情形并修把文献Ξ〕求ΓΒ%ΧΤ的方法推广到Β6ΧΔ改「」的策略而给出细化过程包括两个步骤=步骤大致为=首先给出一个初始解通过插人过程第一步=每一次迭代是对上一步的可行解先得到一个可行解最后通过点的移动以及弧的交执行一点的插人再施以两点的交换最后进行两换而得到问题的最优解或次优解弧的交换如图先在同一路径内后在不同路∀算法步骤径间每一次迭代包含三种变换每种变换直到不∀∀能进行再考虑下一种变换直到每种构造初始解变换都不能进任何一个访问中心车站⎯次行为止指所有可行性交换都不能再使费用降每位顾客一次0的简单路径集都可以作为此方法的初始解低如图#∃只考虑初始砂δ 的情形选取毋中的最大者执行图解可中的其以是不可行的不可行是指某些路径可能不余情形和第二步中的!通过_点图的或可能各种情形类似某路径的全部需求之和超过Ψ通过解撰⎯∴;Νεβ;‘β;‘一7。一7、。一;决一些松弛问题而得到初始解Ξ]?对#0∃也得对#Θ∃一可用某些启发式方法得到Ξ,!Α〕初始解不同优∴蝙β价十∋Ν;十;φΝ一电一勺一;Ν蜘对#。∃#。∃概∴。。β。记一。以一。Θ到的结果不同初始解与最优解差值越小得到的结果越好计算量也越小应尽量选取较好的方法对#2∃暇∴0;。十2;一“0;一“Θ2得到初始解第二步=得到的可行解执行三弧交换进一步降低费用值∀达到理想的结果穿插过程对于替代三弧的=把不可行的解变成可行解不可行路径上的组合方式有如下几种点被挂代地穿插到可行路径的最优位置处不与#∀∃0。Θ。−2#∃0。−Θ27#!∃02Θ7−;#∃02−Θ。。#Α∃0。Θ。 点相连的路径上的点被全部移到可行路径中72#−2#?∃07Θ2;−#≅∃−0;Θγ∃−02Θ去与 点相连的不可行路径中的点被部分移到7;当三弧在同一路径中时#∃#Α∃#≅∃可行路径中最后得到一个可行解对每个不可#γ∃无效Φ当三弧在两个不同的行路径上的点5放到可行路径上的点Ν⎯之间路径中时#∃#≅∃无效Φ当三弧分布在三个不同的路径中时#∀∃一#γ∃全部有效#如图∋∃的费用毋用下式计算=对于这一步可以考虑限定迭代次数典‘∴#7。β;诀β;β7‘βΝ;,∃一0∋△、也可以推广〔≅〕中三弧交换的Ι,5情形只考虑#∃如图!所示其中是不可这一步的每次迭行路径中与相邻的两点而0∋代按#0∃#Θ∃#。∃三种情形是合适的非负权参数顺序进行当#0∃不能进行时进行#Θ∃当# Θ∃不能进行时进行#。∃反Ωχ‘Κ2、去Χ#5∃乙一复迭代直到全部都不能进行为止其中每次交换Ι艺,[>#Χ#5∃∃一Ψ2、[ 任Χ#￡∃选取Χ#∃5表最大的_∴#示0Θ点所在的路径>#2;Χ∃表示−7∃当只考虑情形#?∃时路径Χ的需 #0Θ;2β;7,一7、一;汀一70对求之和加人0∋项考虑需求更易找到可行解−7∃∴7动β7心于其他情形 #0Θ2;对不−7∃可类推可行路径上的任一点及可行路径上的任两点Ν和⎯求出所有毋找出最小值进行一次迭代举例如此反复找到一个可行解把一些相连的点一就〔Α」中第 页的例子阐述此算法的步骤=…#一∃先产生一个初始解由于只有九个点所以就近给出一个初始解=ΧΦ= 一!一一Α一 Χ== 一一∀一 Χ!= 一γ一?一 ΦΧΦ=≅一Ε一≅显然尺∀尺=尺!是可行的而尺Φ是不可行的图∀《#∀穿插过程图#∃取0∋∴ 把点≅和点Ε放在一起对ΧΟ同插入到某两点之间加快运算过程Χ!实行穿插过程经计算可知把点≅和点Ε一起∀!细化过程放人_和γ之间是最优选择得一个可行解可行解通过路径之间以及不同路径间的弧的山东科技大学学报#自然科学版∃第卷图两点交换及两弧交换的细化过程图国图!三弧交换的细化过程图#!∃细化过程先把Χ=中的点?8移到尺提到的两种方法有很好的稳定性当,较大时中得Χ∋= 一!一一Α一 ΧΟ= 一∀一一?一8ς∋Β017⎯一Σ51/39法得不到可行解且变得不稳定 Χ!= 一Ε一≅一&然后把Χ∋中的弧!尺!中用扫描启发式方法得到的结果可行但不精确的弧 ≅换成弧 !≅得尺∀=&一Α一一≅一Ες#∃弧的交换最先在解<Δ.时被采用由于 ΧΟ= 一!一 Χ!= 一∀一一?一γ一 最后Χ∋%ΧΔ与<.Δ的相似性把它推广到%ΧΔ中中的弧 Α≅换成 Α≅得Χ∋= 一一Α一≅一Ε参考文献=一 ΧΟ= 一!一_Χ!= 一∀一一?一γ一_此后无Ξ∀]<&9/Δ2653&95−&9/7%ΧΔΞΛ〕论怎样变换都不会使结果得到改善故用此法计,Γ>Π0Υ79∋_.+&,Π劝&,=Ω∋+Σ71;Γ027Ι57Δ+Θ∋58/718∀ΕΕγ算的结果总费用为Ε≅在【Α」中提供的两种方Ξ]Μ0Τ&917⊥Γ/,+75;∋03&,9,∋/1&−97/ΓΒ6ΧΔΞ∗]Π∗+℃Τ70,∗&+Ι∋0&−#∀∃Δ_70195&8,Χ/Ε=∀ γ一∀?结果与初始解有直接关系不论初始解可【Α〕富尔兹ΜΧ组合最优化ϕ∀ΕΕ?γ#中译本∃〔Λ〕上海=上海翻行与否只要满足条件经此法得到较满意的结译出版公司∀γΕγ果运算量不大Ξ〕Η0Ν257&&90,15,&+ΠΒ/15&−5287)0,2Λ5,3&κκ5ΓΓ#∃在穿插过程中最后可能得不到可行解,Σ770Υ790∋&3159/,∋8−&19/7%ΧΔΘ0872&,λ一Τ09/80,2可提高参数“Φ的1值或另外选取初始解重复此过⎯一8&/9879Τ098/17∋0Υ095&,8Ξ∗]Γ,,0∋8&−_Τ71095&,8程一直找到初始解为止Χ787017/∀ΕΕΑ?∀=∀一!Ξ≅〕ΜΚ)Α0,#!∃在2Ω715,3/0,ϑ穿插过程或细化过程中均可以实现编η,ΓΠ−9779567Η7+1557ΚΓ即159Ι−&19/7<.Τ7017/∀Ε≅!∀Εγ程运算解决点数很多的情形此算法较之【Α」中Ξ∗]&Τ71095&,8Χ87一Α∀
