《基于遗传算法求解作业车间调度问题-生产运作实践.docx》由会员分享，可在线阅读，更多相关《基于遗传算法求解作业车间调度问题-生产运作实践.docx（22页珍藏版）》请在三一办公上搜索。
1、目录i问题一：基于遗传算法求解作业车间调度问题21 .问题介绍21.1 作业车间调度问题表述2生产运作实践大作业1.2 作业车间调度问题研究的假设条件31.3 车间作业调度问题的数学模型32 .根本遗传算法42.1 遗传算法的根本思路52.2 根本遗传算法参数说明53 .用遗传算法对具体问题的解决63.1 参数编码63.2 初始种群的生成63.3 个体的适应度函数73.4 遗传算子的设计83.5 遗传算法终止条件94 .模型的求解95 .结论总结106 .附录10问题二：邮政运输网络中的邮路规划和邮车调度171 .问题描述172 .模型建立182.1 模型的根本假设182.2 符号说明182.
2、3 模型分析192.4 模型的建立203 .模型的求解203.1 求解思路203.2 求解算法21问题一：基于遗传算法求解作业车间调度问题1 问题介绍1.1 作业车间调度问题表述作业车间是指利用车间资源完成的某项任务.在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工，为了研究方便，我们将这项任务限定为加工一批工件。在此根底上，可对作业车间调度问题进行一般性的描述:假定有N个工件，要经过M台机器加工,一个工件在一台机器上的加工程序称为一道工序，相应的加工时间称为该工序的加工时间,用事先给定的加工路线表示工件加工时技术上的约束，即工件的加工工艺过程,用加工顺序表示各台机器上各个
3、工件加工的先后顺序。在车间作业调度问题中，每个工件都有独特的加工路线，我们要解决的问题就是如何分配N个零件在M个机器上的加工顺序以使得总的加工时间最短。1.2 作业车间调度问题研究的假设条件在研究一般的作业车间调度问题中往往需要明确两类重要假设条件：1 .工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系；2 .资源独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。根据上面以及求解方便，我们做出以下具体假设：1 .每一台机器每次只能加工一个工件，每一个工件在机器上的
4、加工被成为一道工序。2 .不同工件的加工工序可以不同；3 .所有工件的工序数不大于设备数；4 .每道工序必须在指定的某种设备上加工，所有机器处理的加工类型均不同；5 .在作业优化过程中既没有新的工件参加也没有取消的工件；6 .不考虑工件加工的优先权，即工件之间没有优先约束关系限制的；7 .工序允许等待，即前一个工序未完成，那么后面工序需要等待；8 .工件的加工时间事先给定，且在整个加工过程中保持不变。1.3 车间作业调度问题的数学模型建立车间作业调度问题的数学模型，是我们研究该问题的出发点，同时也为其后的研究奠定了根底。假设有n个工件，要在m台机器上加工，每个工件有Pi道工序，每台机器上总共要
5、加工Lj道工序。我们定义以下根本数学符号囿：上所有工件的集合，J=2，J11；M:所有机器的集合，M=Ml,M2,-Mm；写：工件J的工序集合，4=%,%2，今“；P:所有工序的集合，此为xmax几g,?矩阵。Pi,j表示i工件的第j道工序。P(i,)=P.,表示i工件的所有工序按优先顺序的排列。缺乏max几鸟,2,那么其空余的位置用O填满。G得2 %oPjjPja，/“（/?+1）/“：机器顺序阵，此为XmaX%鸟,?矩阵。JM(i.D表示i工件的第j道工序的机器号,Jm(，；)表示i工件的所有工序按优先顺序加工的各机器号的排列。注意：如果某工件的工序数缺乏max,6,.己,那么其空余的位置
6、用0填满。M Mp i 2。400 0Mp Mp Mp Mp0 0片一片TT加工时间阵，此为XmaX%6，矩阵。T(i,j)表示工件i的第j道工序在/i，D上的加工时间。同样地，如果某工件的工序数缺乏max片,6,.鸟.那么其空余的位置用0填满。Oo0Mj：工件排列阵，此为maxR,R,?X矩阵。Mj(i,_/)表示在i机器上排在第j位加工的工件号，Mj(i,)表示i机器上依次加工的各工件的排列。同上，如果某工件的工序数缺乏max/6,?,那么其空余的位置用0填满。事实上，工件排列阵就是调度的一种表示形式。由此，我们可以给出一般性的车间作业调度数学模型的定义：如果对应于一个确定的M；满足/(M
7、)=min(M)/(M)fMnj)或f(Mj)=maf(Mij),f(M-),/(M；)。即M；使得目标函数/(%)取值最小(或最大)，且与JM相容，那么称M:为车间作业调度问题在此目标函数下的最优解。2 根本遗传算法遗传算法是一种基于自然群体遗传演化机制的高效探索算法，由美国学者Holland于1975年首先提出来的，通过模拟达尔文的遗传选择和自然淘汰的生物进化过程来求解。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作遗传，交叉和变异L根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规那么，不断得到更优的
8、群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。遗传算法的根本思路1.首先确定问题的求解空间；2 .将求解空间中的每一个点进行编码，并从求解空间中任选N个点组成初始群体；3 .计算当前群体中每个个体的适应度函数值，然后运用选择、交叉、变异算子产生新一代群体；4 .对新一代群体中的每个个体进行评价，假设找到满足问题的最优解那么结束；否那么，转步骤3。2.1 根本遗传算法参数说明对遗传算法性能有影响的参数主要有:种群数目N、交换概率Pc、变异概率Pm、代沟G、尺度窗口W、和选择策略S等。1 .种群数目种群数目N的多少直接影响到遗传算法的优化性能和效率。种群选择太小时，
9、不能提供足够多的个体.致使算法性能较差，易产生早熟收敛，甚至不能得到可行解;种群选择过大时，虽然能防止早熟收敛,但是增加了计算量。2 .交换概率交换概率PC用于控制交换操作的频率。交换概率太大的时，易产生更新过快，从而破坏掉高适应度个体的现象;交换概率太小的时候又容易产生搜索停滞不前的现象。3 .变异概率变异概率Pr对于增加种群多样性具有重要意义。如果变异概率太大的时，遗传算法易变成随机搜索，如果变异概率太小，那么不能产生新个体，不利于种群的多样性。4代沟代沟G用于控制每一代群体被替换的比例，每代有NX(I-G)个父代个体选中进入下一代种群中，该参数和交换、变异概率以及选择策略有很大关系，它并
10、不是一个初始参数.而是评价遗传算法的一个参数。5 .尺度窗口该参数用于作出由目标值到适应度函数值的调整。6 .选择策略一般来说有两种选择策略，一种为纯选择，种群中每个个体根据其适应度值进行比例选择，即个体被选择的概率与其适应度值成正比。另一种为保优策略，首先进行纯选择，把目前最优个体直接参加下一代种群中，该策略是为了防止最优解的丧失，但在实际应用中往往采取这两种选择策略结合的方法，并做适当的变型。3 用遗传算法对具体问题的解决遗传算法在解决作业车间调度问题上比经典的启发式算法好,同时遗传算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式。3.1 参数编
11、码遗传编码技术是实施遗传算法的核心。遗传算法的工作根底是选择适当的方法表示个体和问题的解.对于同一问题可以有不同的编码表示方法。由于遗传算法不能直接处理空间解的数据，在解决此车间调度问题上把它们转换成遗传空间的基因按一定结构组成的染色体或个体，也就是通过编码将它们表示成遗传空间的基因型串结构数据。我们采用了基于操作的编码来解此车间调度问题.其根本思想是将所有工件的操作进行编码，不同的工件用不同的编码表示，而同一工件的所有操作在染色体中那么用相同的编码表示，其解码原那么是将染色体上的基因按照从左到右的顺序解释为相应工件的操作顺序，具有相同编码的基因按照其在整个染色体中的位置解释为工件相应顺序的操
12、作。表3.1加工时间和工艺约束工程工件操作序列123J1332操作时间J2153J3323JlMiM2M3机器J2MiMaMzJ3M2MiM33.2 初始种群的生成在N个工件M台机器的排序问题中，对每个机器的加工存在加工工艺顺约束，这个工艺约束表示为工件的加工顺序矩阵MzM12M1MM(J,M)=MZlMjj-Mpm(3.2)MM2MnM其中第J行表示第J个工件的机器顺序机器号为零表示工件加工结束。相应的每个加工操作有时间矩阵：TnT12,TlMfT21T22TzmT(JfM)=：(3.3)TniTMZTnm其中第J行表示第J个工件的机器加工时间,时间为零表示工件不在机器上加工。因为群体中的个
13、体都是由工件的符号组成的，而且工件任意排列总能产生可行调度，所以可以采用随机方法产生初始种群。3.3 个体的适应度函数在遗传算法中,适应度是描述个体性能的主要指标。根据适应度的大小,对个体进行优胜劣汰。适应度是驱动遗传算法的动力。从生物学角度讲,适应度相当于生存竞争,适者生存的生物生存能力,在遗传过程中具有重要意义。适应度函数就是目标函数，在用遗传算法解决车间调度问题里，定义个体的适应度函数为在M台机器上排序加工完N个工件所需的时间，根据染色体编码的思想提出的适应度算法如下：STEPl:定义ti(n)为每个工件的可加工时间，初始化向量为零向量。STEP2hrom(i)对应相应工序的加工机器为m
14、achineri。ti(chrom(l)=ti(chron(l)1machine(l)STEP3:fori=2tonFork=ltonti(chrom(i)=ti(chrom(i-l)+ma(ti(chrom(i-k),machine(i-k)+k)其中假设当i-k=01那么ti(chrom(i-k),machine(i-k)=0,还有要判断ChOrm(i)所对应的工件在以前是否加工过，假设加工过，那么ti(chrom(i)=ti(chorm(i-l),STEP4:求出适应度函数F=ti(chorm(n)o3.4 遗传算子的设计1 .选择算子选择操作是对自然界适者生存的模拟。评价值（目标函数）
15、较小的个体有较高的概率生存,即在下一代群体中再次出现。我们采用一种常用的选择方法：按比例选择,即假设个体I适应值（目标函数）是f.,那么个体在群体中复制（再生）的子代个数在群体中的比例将为:/。其中,2f，表示指所有个体适应值之和。对群体中各个体的适应值做比拟,将适应值小的个体复制,将适应值大的淘汰掉,这是因为在作业调度算法中的适应度函数为在M台机器上加工完N个工件所需的时间,时间越短,更能到达优化的目的。2 .交叉算子在用遗传算法解决作业车间调度问题中,在对工序编码的排序问题中,交叉算子不能简单交换两个个体的相应位置的基因段,因为这样得到的后代个体可能不能满足每个工件号重复M次的要求。为了满
16、足我们的工序编码的要求,本文采用下面的交叉算子：随机将工件集合12N分成两个互补子集相应的将个体的基因分成两个局部，然后把父母个体中的part2局部用h代替形成两个新串，用第二个父母个体的part2局部按照原来的相对顺序逐个替换第一个父母个体的part2产生的新串中的h,同样用第一个父母个体的part2按照原来的相对顺序逐个替换第二个父母个体的pratl产生的新串中的h得到两个后代个体。例如:对于一个4个工件4个机器问题,假设父母个体为：Parentl:1342423314321421Parent2:3241123442312413假设随机选择工件L2,那么从Parentl得到的新串为：New
17、l:1hh2h2hhlhh21h21Partll2212121Part2:34433434同样从Paret2得到的新串为New2:h2hll2hhh2hl2hlhPartl:21122121Part2:34344343然后用Paret2个体的part234344343按照原来的相对顺序逐个替换第一个父母个体Parentl产生的新串Newl：lhh2h2hhlhh21h21中的h,得到的后代个体为：Parentl1342324413421321同理用Parentl个体的part234433434按照原来的相对顺序逐个替换第二个父母个体Parent2产生的新串New2:h2hll2hhh2hl2h
18、lh中的h,得到的后代个体为：Parent232411243324123143 .变异算子在做变异时，先对解群以一定的概率进行突变操作。在此作业调度算法中，不能简单的将基因的值做改变。由于问题及其表示的特殊性，这样简单的改变可能是没有意义的。我们使用如下变异方法：随机产生一个整数，确定变异位置，然后，把该位置的基因与其前面的基因互换位置。同样，以132312312为例，假设变异位置为2,那么变异前后的基因链码为：变异前:132312312变异后:3123123123.5遗传算法终止条件从查阅的资料来看，大多是以优化时间或迭代次数或适应度的增量或其他参数作为终止条件的，我们采用以迭代次数作为是否
19、终止的条件，从而控制优化过程。4 模型的求解假设交叉概率Pc=100%.变异概率Pm=25%,群体规模为6,加工顺序矩阵：T=136736;851010104;5 48917;555389;935431;3391041：相应的每个加工操作有时间矩阵：M=201354;124503;235014;102345;214503;135042;运行程序结果如下，最短时间为6L最后，由仿真得到6x6的曲线图3.3和甘特图3.4,图中显示了适应度值为6个工件在6个机器加工所需的最短时间，对应得工序即为工件的加工顺序.图3.3中实线代表最优解的变化，虚线代表种群均值的变化。图3.4表示了工件66的调度。图3
20、.3曲线图图3.4甘特图5.结论总结遗传算法在解决作业车间调度问题上比经典的启发式算法好，同时遗传算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式。作业车间调度问题是计算机集成制造系统工程中的一个重要组成局部，它对企业的生产管理和控制系统有着重要的影响，在当今的竞争环境下，如何利用计算机技术实现生产调度方案优化，快速调整资源配置，统筹安排生产进度,提高设备利用率已成为许多加工企业面临的重大挑战。6附录主程序：T=136736;8510 1010 4;5489 17;5553 89；9354 31;33910 4 1;M= 2O5124503；2350
21、14；1023421450135045;3;2;；%将机器号+1fori=l:6S=M(i:);forj=l:6S(j)=S(j)+l;endM(i,:)=S;PNumber=;告零件个数6MNumber=6;%机器个数6WPNumber=666666;%将时间处理下TTemp=T;fori=l:6forj=l:6TTemp(irj)=T(M(irj)ri)；endendNIND=40;彩个体数目(NlJmberofindividuals)MAXGEN=200;宅最大遗传代数(MaXimUmnumberofgenerations)GGAP=O.9;%fi(Generationgap)XOVR=
22、0.8;s交叉率MUTR=O.6;%变异率gen=0;电代计数器trace=zeros(2rMAXGEN);告寻优结果的初始值WNumber=O;fori=l:PNumberWNumber=WNumberfWPNumber(lri);%工序个数end%初始化群Chroin=Zeros(NIND,WNUmber);forI=IjNINDChrom(i,:)=randperm(WNumber);end%计尊目标函数值PValObjVP=cal(ChromrNINDrTrMrPNumberrMNumberrWPNumber);whilegentrace(lzgen)Vall=PVal;Val2=P;
23、MinVal=trace(1,gen);endendPVal=Vall;%工序时间P=Val2;%工序MinVal=MinVal告最小时间十算解的变化holdon;plot(0,0r0,0);plot(trace(1,:);holdon;plot(trace(2,:),-，);grid;Iegend(，解的变化I，种群均值的变化，)；告显小结果figure(2);fori=l:WNumberval=P(l,i);a=(mod(valr10)+1;b=(val-a+l)/10);mText=M(bfa);PlotRec(PVal(lzi),PVal(2,i),mText);holdon;mPoi
24、ntI=PVal(1,i);mPoint2=PVal(2,i);xl=mPointl;yl=mTet-0.5;x2=mPoint2;y2=mText-0.5;x3=mPoint2;y3=mText;x4=mPointl;y4=mText;fill(xl,x2,x3,x4,yl,y2,y3,v4,1,0.5,1);word=num2strP1i);%text(0.5*mPointl+0.5*mPoint2zmText-0.5,word);text(mPointl,mText-0.7,word);endM文件如下：aberrance.mfunctionChromNew=aberrance(Chro
25、m,NINDrMUTR,WNumber)普新群ChromNew=Chrom;fori=l=NIND舍是否变异a=rand;ifMUTRa;*变异位置Posl=Unidrnd(WNumber);Pos2=nidrnd(WNumber);当变异位置不相同whilePosl=Pos2Pos2=nidrnd(WNumber);end%取数据S=Chrom(i,:);%交换temp三S(Posl);S(PoSI)=S(PoS2);S(Pos2)三temp;ChromNew(i,:)=S;endendacross.m:functionChromNew=across(Chrom,N工ND,XOVR,WNum
26、ber)%新群ChromNew=Chrom;%S交叉位置%Posl=fix(I-XOVR)*WNumber);%Pos2=fix(XOVR*WNumber);%随机选择交叉个体SelNum=Tandperm(NIND);%fori=l:NIND%SelNum(I)=Unidrnd(NIND);%end%交叉个体组个数Num=NIND2;NUm=2*fi(Num);fori=l:2:Numa=rand;ifXOVRa;%:变异位置Posl=Unidrnd(WNumber);Pos2=unidrnd(WNumber);Pos3=unidrnd(WNumber);Pos4=unidrnd(WNumb
27、er);备变异位置不相同whilePosl=Pos2Pos2=unidrnd(WNumber);endifPoslPos2temp=Posl;Posl=Pos2;Pos2=terp;endwhilePos3=Pos4Pos3=nidrnd(WNumber);endifPQS3Pqs,temp=Pos3;Pos3=Pos4;Pos4=temp;end金取交换的个体Sl=Chrom(SelNum(i)r:);S2=Chrom(SelNm(i+1)r:);2初始化新2个体Sll=zeros(1FWNumber);S22=zeros(IrWNumber);金新个体中间局部的COPYforj=Posl:
28、Pos2Sll(j)=Sl(j);%S22(j)=S2(j);endforj=Pos3:Pos4S22(j)=S2(j);end自交换个体1forj=l:WNumberflag=ismember(S2(j),Sll);iffIag=Ok=l;whilek=WNumberifSll(k)=0Sll(k)=S2(j);k=WNumber+l;endk=kl;endendend名交换个体2forj=l:WNumberflag=ismerber(SI(j),S22);iffIag=Ok=l;whilekObjV(i,1)Vall=PVal;Val2=P;MinVal=ObjVdr1);endendPV
29、al=Vall;P=Val2;calp.mfunctionP=calp(S,PNumberrWPNumber)%初始化temp=zeros(1,PNumber);val=max(WPNumber);PS=zeros(PNUmber,val);金转化成二维数组val=O;fori=l:PNUmberforj=l:WPNumber(lzi)PS(iJ)=S(lrvalj);endval=valWPNumber(1i);end宅工序个数WNumber=O;fori=l:PNumberWNumber=WNumber+WPNumber(1ri);endfori=l:WNumber%计算工序val,pos
30、=max(PS);P(1,i)=pos(lrl)*10temp(1,pos(IrI);temp(1,pos(1,1)=temp(1,pos(1,1)1;舍移动PS的位置forj=l:WPNumber(1,pos(IrI)-1PS(POS(1,1)/j)=PS(pos(l)/j+l)?endPS(pos(1,1),WPNumber(1,pos(lz1)=0;endcaltime.m:functionPVal=Caltime(P,T,M,PNumber,MNumberzWPNumber)名工序个数WNumber=O;fori=l:PNumberWNumber=WNumber+WPNumber(1,
31、i);endTM=zeros(1,MNumber);TP=zeros(1,PNumber);PVal=Zeros(2,WNumber);fori=l:WNumber%机器号val=P(l,i;a=(mod(valr10)+1;b=(val-a+1/10);m=M(bra);%时间t=T(hra)；电取这工序的机器的时间和先工序的时间Vall=TM(IfHi);va!2=TP(lrb);留交换ifvallval2val=vall;elseval=val2;end电计算时间PVal(lri)三val;PVal(2fi)=val+t;电记录机器时间和工序时间TM(I,m)=PVal(2,i);TP(
32、lrb)=PVal(2ri);endplotRec.m:functionPlotRec(mPointl,mPoint2,mText)vPoit=zero$(4,2);vPoint(工，:)=mPointlrmText-0.5;vPoint(2,:)=mPoint2,mText-0.5;vPoint(3,:)=mPointl,mText;vPoint(,:)=mPoint2,mText;plot(vPoint(lr1)rvPoint(2fl)fvPoint(lr2)rvPoint(2,2)holdon;plot(vPoint31),vPoint(3,1)#vPoint32)vPoint(3-2)
33、plot(vPoint(2,1),vPoint(4,1)9vPoint(2,2),vPoint(4,2)plot(vPoint(3,1),vPoint(4,1),vPoint(3,2),vPoint(4,2)end问题二：邮政运输网络中的邮路规划和邮车调度1.问题描述某地区的邮政局、所分为地市中心局、县级中心局和支局三级机构，该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。为使邮政企业实现低本钱运营和较高的效劳质量，我们需要对该地区的邮政运输网络进行重构，确定适宜的邮路规划方案并进行邮车的合理调度。该地区的邮政运输流程及时限规定如下：SfeP2:区级第一班次邮车从地市局D出发将邮件运
34、送到各县局X,和沿途支局，并将各县局Xi和沿途支局收寄的邮件运送回地市局D；区级第一班次邮车出发时间必须在06:00之后，返回地市局D时间必须在11:00之前。S?e02县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理，按寄达支局装上相应的县级邮车；县局Xi对邮件的集中处理时间为1小时包括邮件的卸装、分拣封发等处理时间)。Sfe03各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局Xi；Step4.区级第二班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi收寄的邮件包括当日各县级邮车运回县局Xi的邮件和沿途支局收寄的邮件运
35、送回地市局D；区级第二班次邮车在县局Xi卸装完邮件后的出发时间必须在县局X,的全部县级邮车返回县局并集中处理1小时以后，最终返回地市局D的时间必须在18:00之前。现在预解决以下问题：以县局Xi及其所辖的16个支局Z,Z为研究对象.假设区级第一班次邮车08:00到达县局Xl1区级第二班次邮车16:00从县局Xl再出发返回地市局D,假设每辆县级邮车最多容纳65袋邮件，试问最少需要多少辆邮车才能满足该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行？2模型建立2.1 模型的根本假设(1) 所有车辆均在区局或县局出发；(2) 区局两个班次邮车的行驶路线相同；(3)区局使
36、用的邮车各个参数相同，县局使用的邮车各个参数也相同；(4)各点都有一定量的邮件待运；(5)邮车在各支局停留时间均为5分钟，在各县局停留时间均为10分钟；(6) 邮车保持一定速度均速行驶，县级邮车平均速度为30km/h,区级邮车平均速度为65km/m,邮车行驶过程中无需考虑道路等级、信号等待、会车、路面清洁程度等因素；(7) 一辆邮车只用于一条路由；每个支局有且只有一辆邮车寄送邮件，允许其他邮车经过该支局，但不负责该支局的邮件的寄送，不做停留。2.2符号说明M：从县局Xi寄达16个支局的邮件总量m:每辆县级邮车最多容纳的邮件数X：对实数X上取整R：由于空车率而减少的收入g1-:支局j需要寄达的邮
37、件数g,:支局I需要运走的邮件数Cij：各个局之间的距离U,：县局邮车出行时限q:邮车的最大承运能力S:县局到各支局的距离向量cu:表示对应路段SD的长度C：邻接矩阵T：支局连接标志矩阵W“k：通过路段i,j）时邮车k已收到的邮件数Zg:通过路段SD时邮车k上还未寄达的邮件数j:各支局邮件收发量之差V1：县局邮车的行驶速度t:邮车在各支局停留的时间:从支局Z.到支局乙邮路合并后的里程节余Ixv:判断支局乙和z,是否能合并的变量2.3 模型分析时限与本钱是邮政运输问题的两个重要指标，时限关系到邮政通讯质量的好坏，本钱影响着企业的经营。分别考虑这两方面因素，我们将问题一做了如下分析：首先，由该地区
38、邮政运输流程及时限的规定可以得出，县级邮车每天的发车时间最早是早九点，返回时间最迟是下午三点，即邮车的出行时限最多为6小时。其次，一般认为，派出一辆车的固定费用远远高于该车辆行驶的费用，因此为了降低本钱，设计模型的目标是使用的车辆数最少。由于从县局X:寄达16个支局的邮件量总M为176袋，而每辆县级邮车最多容纳邮件数m为65袋，故得出假设要满足该县的邮件运输需求所需车辆的下限=PW/f=3辆。又由空车率=（邮车最大承运的邮件量（袋）-邮车运载的邮件量（袋）/邮车最大承运的邮件量（袋）可知,要想提高运输效益，需要使空车率达最小。第三，关于邮路结构的选择。辐射形邮路和环形邮路各有优缺点：辐射形邮路
39、可以缩短运递时间，加快邮运速度，但是其联系点较少，效率低消耗大；环形邮路联系点较多，效率高运费省，但是时效性稍差。考虑到该县邮车的出行时限最长为6小时，在不影响时限标准的前提下，应尽可能地降低本钱，且该县各支局的连通网络中不存在最小割为1的点假设存在最小割为1的点，那么该点与其临近点的连接只能选择辐射形邮路，故我们优先选择环形邮路。2.4 模型的建立为了更好的描述问题,将其定义为网络G=(VAC),其中V=OUP为一点集。表示县局X1，编号为0,P表示各个支局，编号分别为L2,-.16,支局j需要寄达的邮件数为g，需要运走的邮件数为g“，,=g,-gl5；A为一距离集合，表示邮车可能走过的路线
40、集合；C为邻接矩阵，用以表示邮路规划方案.可构造为：c“表示对应路段i,j)的长度，即局与局之间的距离；对于所有的支局，要求邮车在时限Lw内遍历。为构造数学模型，定义决策变量：Ww为通过路段(i.j)时邮车k已收到的邮件数.乙为通过路段(i,j)时邮车k上还未寄达的邮件数,由于设计模型的首要目标是使用的邮车数最少，故我们先以k=3入手，其数学模型可表示为如下形式：式(Ll)表示空车率带来的收入损失最小；式(1.2)表示一个支局由一辆邮车寄送邮件；式(L3)和式(1.4)表示每个支局被访问一次；式(L5)保证在整个回路中运载邮件的数量不超过邮车的运载能力；式(L6)保证了满足时限的要求；式(L7
41、)和(1.8)为变量取值约束。3模型的求解3.1 求解思路问题一类似于车辆路径问题(VRP)1常采用的是启发式算法中的C-W算法，该算法的根本思想是:首先将各支局点与县局点相连，构成N条初始邮路，计算各邮路里程，然后以邮路里程节余为判据，进行邮路的合并，直到没有邮路再能合并为止，形成最终的几条邮路。邮路合并的同时考虑到时限与邮车承运能力的问题.命题1.两条辐射形邮路合并为一条环形邮路可大大减少邮路里程。证明：如图1所示，两条辐射形邮路分别为XZX和XZXL在这里我们给出里程节余的说法，关于邮路里程节余的计算参考图L从县局X1到支局乙和Zy各有一条邮路，如有邮车既访问乙又访问Zy而不破坏时限和负载约束条件的话，那么可将上述两条邮路合并为一条，此时，其所节约的里程为：图1节余计算示意图般为正值，故将两条辐射形邮路合并为一条环形邮路可咸少邮路里程.从而降低本钱。3.2求解算法为了优化邮路的设计，以节余最大的为判据，将其所对应的两条邮路优先进行合并，C
