基于.遗传算法求解作业车间调度问题-生产运作实践

1、生产运作实践大作业学习资料WORD格式可编辑专业知识分享目录TOC o 1-5 h z HYPERLINK l bookmark28 o Current Document 目录1 HYPERLINK l bookmark30 o Current Document 问题一：基于遗传算法求解作业车间调度问题2 HYPERLINK l bookmark32 o Current Document 1问题介绍2 HYPERLINK l bookmark34 o Current Document 作业车间调度问题表述2 HYPERLINK l bookmark36 o Current Document 作

2、业车间调度问题研究的假设条件2 HYPERLINK l bookmark38 o Current Document 车间作业调度问题的数学模型2 HYPERLINK l bookmark44 o Current Document 2.基本遗传算法4 HYPERLINK l bookmark46 o Current Document 遗传算法的基本思路4 HYPERLINK l bookmark48 o Current Document 基本遗传算法参数说明4 HYPERLINK l bookmark50 o Current Document 3.用遗传算法对具体问题的解决5参数编码5 HYPE

3、RLINK l bookmark52 o Current Document 初始种群的生成6 HYPERLINK l bookmark54 o Current Document 个体的适应度函数6 HYPERLINK l bookmark56 o Current Document 遗传算子的设计7 HYPERLINK l bookmark58 o Current Document 遗传算法终止条件8 HYPERLINK l bookmark60 o Current Document 4模型的求解8 HYPERLINK l bookmark68 o Current Document 5结论总结1

4、0 HYPERLINK l bookmark70 o Current Document 6.附录10 HYPERLINK l bookmark72 o Current Document 问题二：邮政运输网络中的邮路规划和邮车调度19 HYPERLINK l bookmark74 o Current Document 问题描述19 HYPERLINK l bookmark76 o Current Document 模型建立19 HYPERLINK l bookmark78 o Current Document 2.1模型的基本假设19 HYPERLINK l bookmark80 o Curre

5、nt Document 2.2符号说明20 HYPERLINK l bookmark82 o Current Document 2.3模型分析20 HYPERLINK l bookmark84 o Current Document 2.4模型的建立21 HYPERLINK l bookmark88 o Current Document 模型的求解22 HYPERLINK l bookmark90 o Current Document 3.1求解思路22 HYPERLINK l bookmark94 o Current Document 3.2求解算法23问题一：基于遗传算法求解作业车间调度问题

6、1问题介绍作业车间调度问题表述作业车间是指利用车间资源完成的某项任务，在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上可对作业车间调度问题进行一般性的描述:假定有N个工件，要经过M台机器加工，一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”,用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程，用“加工顺序”表示各台机器上各个工件加工的先后顺序。在车间作业调度问题中，每个工件都有独特的加工路线，我们要解决的问题就是如何分配N个零件在M个机器上的加工顺序以使得

7、总的加工时间最短。作业车间调度问题研究的假设条件在研究一般的作业车间调度问题中往往需要明确两类重要假设条件:工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系;资源独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。根据上面以及求解方便，我们做出以下具体假设：每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。不同工件的加工工序可以不同；所有工件的工序数不大于设备数；每道工序必须在指定的某种设备上加工，所有机器处理的加工类型均不同；在作业优化过程中

8、既没有新的工件加入也没有取消的工件；不考虑工件加工的优先权，即工件之间没有优先约束关系限制的；工序允许等待，即前一个工序未完成，则后面工序需要等待；工件的加工时间事先给定，且在整个加工过程中保持不变。车间作业调度问题的数学模型建立车间作业调度问题的数学模型，是我们研究该问题的出发点，同时也为其后的研究奠定了基础。假设有n个工件，要在m台机器上加工，每个工件有Pi道工序，每台机器上总共要加工Lj道工序。我们定义以下基本数学符号6：J：所有工件的集合，JJ1,J2,J；12nM:所有机器的集合，MMMM；12mP.：工件J的工序集合，P.P.；，PjP.；jiijiji1ji2jipiP：所有工序

9、的集合，此为nmaxP；,P,.P矩阵。p(i,j)表示i工件的第j道工序。12P(i)P,表示i工件的所有工序按优先顺序的排列。不足maxP,P,P,那么其空余的位ji12n置用0填满。P1PPPj11j12j1P1PiP1000Pi卜.PPPPjn1jn2jnp1jn(PiPi1J:机器顺序阵，此为nmaxP,P,P矩阵。JM12nM器号，J(i)表示i工件的所有工序按优先顺序加工的各机器号的排列。注意:M如果某工件的工序数不足maxP,PP,那么其空余的位置用0填满。1.1)1)00PiP11(i,j)表示i工件的第j道工序的机P1MMMPPPjPj11j12j1P1PiP10001.2

10、)MMMPPPPjn1jn2jnp1jn(Pi1)00PiP11.p.1.iT:加工时间阵，此为nmaxPPP矩阵。T(i,j)表示工件i的第j道工序在J(i,MP，P，P,那么其空余的位置用012n12nj)上的加工时间。同样地，如果某工件的工序数不足maX填满。P1TTTPPPj11j12j1P1PiP10001.3)TTTPPPjnp1jn(Pi1)jn1jn2.P.1iM:工件排列阵，此为maxP,P,Pn矩阵。Mj12n00PiP11(ij)表示在i机器上排在第j位加工j的工件号，M（i,）表示i机器上依次加工的各工件的排列。同上，如果某工件的工序数不足jmaxP,P,P，那么其空余

11、的位置用0填满。事实上，工件排列阵就是调度的一种表示形式。12n由此，我们可以给出一般性的车间作业调度数学模型的定义：如果对应于一个确定的M,满足f（M*）minf（Mi）,f（M2）,f（Mn）或jjjjjf（M*）maxf（Mi）,f（M2）,f（Mn）o即M使得目标函数f（M）取值最小（或最大），且与jjjjjjJm相容，则称M为车间作业调度问题在此目标函数下的最优解。Mj2.基本遗传算法遗传算法是一种基于自然群体遗传演化机制的高效探索算法，由美国学者Holland于1975年首先提出来的，通过模拟达尔文的遗传选择和自然淘汰的生物进化过程来求解。它将问题域中的可能解看作是群体的一个个体或

12、染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。遗传算法的基本思路首先确定问题的求解空间；将求解空间中的每一个点进行编码，并从求解空间中任选N个点组成初始群体；计算当前群体中每个个体的适应度函数值，然后运用选择、交叉、变异算子产生新一代群体4对新一代群体中的每个个体进行评价，若找到满足问题的最优解则结束；否则，转步骤3。基本遗传算法参数说明对遗传算法性能有影响的参数主要有:种群数目N、

13、交换概率匕、变异概率Pm、代沟G、尺度窗W、和选择策略S等。种群数目种群数目N的多少直接影响到遗传算法的优化性能和效率。种群选择太小时，不能提供足够多的个体，致使算法性能较差，易产生早熟收敛，甚至不能得到可行解;种群选择过大时，虽然能避免早熟收敛，但是增加了计算量。交换概率交换概率Pc用于控制交换操作的频率。交换概率太大的时，易产生更新过快，从而破坏掉高适应度个体的现象;交换概率太小的时候又容易产生搜索停滞不前的现象。变异概率变异概率Pm对于增加种群多样性具有重要意义。如果变异概率太大的时，遗传算法易变成随机搜索，如果变异概率太小，则不能产生新个体，不利于种群的多样性。代沟代沟G用于控制每一代

14、群体被替换的比例，每代有NX（1-G）个父代个体选中进入下一代种群中，该参数和交换、变异概率以及选择策略有很大关系，它并不是一个初始参数，而是评价遗传算法的一个参数。尺度窗口该参数用于作出由目标值到适应度函数值的调整。选择策略一般来说有两种选择策略，一种为纯选择，种群中每个个体根据其适应度值进行比例选择，即个体被选择的概率与其适应度值成正比。另一种为保优策略，首先进行纯选择，把目前最优个体直接加入下一代种群中，该策略是为了防止最优解的丢失，但在实际应用中往往采取这两种选择策略结合的方法，并做适当的变型。3.用遗传算法对具体问题的解决遗传算法在解决作业车间调度问题上比经典的启发式算法好，同时遗传

15、算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式。3.1参数编码遗传编码技术是实施遗传算法的核心。遗传算法的工作基础是选择适当的方法表示个体和问题的解，对于同一问题可以有不同的编码表示方法。由于遗传算法不能直接处理空间解的数据，在解决此车间调度问题上把它们转换成遗传空间的基因按一定结构组成的染色体或个体，也就是通过编码将它们表示成遗传空间的基因型串结构数据。我们采用了基于操作的编码来解此车间调度问题，其基本思想是将所有工件的操作进行编码，不同的工件用不同的编码表示，而同一工件的所有操作在染色体中则用相同的编码表示，其解码原则是将染色体上的基因按照从左

16、到右的顺序解释为相应工件的操作顺序，具有相同编码的基因按照其在整个染色体中的位置解释为工件相应顺序的操作。表3.1加工时间和工艺约束项目工件1操作序列23Ji332操作时间J2153J3323J1M1M2M机器J2M1M3MJ3M2M1M3.2初始种群的生成在N个工件M台机器的排序问题中，对每个机器的加工存在加工工艺顺约束，这个工艺约束表示为工件的加工顺序矩阵：M11M(J,M)=M12M21M1MM22(3.2)其中Mn1Mn2号为零MnM相应的每个加工操作有时间矩阵：其中TN1T11T21T(J,M)=T1MT(3.3)2MTNM因为群体中的个体都是由工件的符号组成的，而且工件任意排列总能

17、产生可行调度，所以可以采用随机方法产生初始种群。个体的适应度函数在遗传算法中,适应度是描述个体性能的主要指标。根据适应度的大小,对个体进行优胜劣汰。适应度是驱动遗传算法的动力。从生物学角度讲,适应度相当于“生存竞争,适者生存”的生物生存能力,在遗传过程中具有重要意义。适应度函数就是目标函数，在用遗传算法解决车间调度问题里，定义个体的适应度函数为在M台机器上排序加工完N个工件所需的时间，根据染色体编码的思想提出的适应度算法如下：STEP1:定义ti(n)为每个工件的可加工时间，初始化向量为零向量。STEP2:chrom(i)对应相应工序的加工机器为machiner(i)。ti(chrom(1)=

18、ti(chrom(1),machine(1)STEP3:fori=2tonFork=1tonti(chrom(i)=ti(chrom(i-l)+max(ti(chrom(i-k),machine(i-k)+k)其中若当i-k=0,则ti(chrom(i-k),machine(i-k)=0,还有要判断chorm(i)所对应的工件在以前是否加工过，若加工过，则ti(chrom(i)=ti(chorm(i-l)。STEP4:求出适应度函数F=ti(chorm(n)。遗传算子的设计1.选择算子选择操作是对自然界“适者生存”的模拟。评价值(目标函数)较小的个体有较高的概率生存,即在下一代群体中再次出现。

19、我们采用一种常用的选择方法：按比例选择即若个体i适应值(目标函数)是打则个体在群体中复制(再生)的子代个数在群体中的比例将为：f/f。111其中，工fi表示指所有个体适应值之和。对群体中各个体的适应值做比较,将适应值小的个体复制,将适应值大的淘汰掉,这是因为在作业调度算法中的适应度函数为在M台机器上加工完N个工件所需的时间，时间越短，更能达到优化的目的。2.交叉算子在用遗传算法解决作业车间调度问题中,在对工序编码的排序问题中,交叉算子不能简单交换两个个体的相应位置的基因段,因为这样得到的后代个体可能不能满足每个工件号重复M次的要求。为了满足我们的工序编码的要求,本文采用下面的交叉算子:随机将工

20、件集合1,2,N分成两个互补子集,相应的将个体的基因分成两个部分，然后把父母个体中的part2部分用h代替形成两个新串，用第二个父母个体的part2部分按照原来的相对顺序逐个替换第一个父母个体的part2产生的新串中的h，同样用第一个父母个体的part2按照原来的相对顺序逐个替换第二个父母个体的pratl产生的新串中的h,得到两个后代个体。例如:对于一个4个工件4个机器问题,假如父母个体为:Parentl:l3424233l432l42lParent2:324ll234423l24l3假设随机选择工件1，2,则从parentl得到的新串为：Newl:lhh2h2hhlhh2lh2lPart1:

21、12212121Part2:34433434同样从Parent2得到的新串为New2:h2h112hhh2h12h1hPart1:21122121Part2:34344343然后用Parent2个体的part2:34344343按照原来的相对顺序逐个替换第一个父母个体Parentl产生的新串Newl:Ihh2h2hhlhh21h21中的h,得到的后代个体为：Parentl:1342324413421321同理用Parent1个体的part2：34433434按照原来的相对顺序逐个替换第二个父母个体Parent2产生的新串New2:h2h112hhh2h12h1h中的h，得到的后代个体为：Par

22、ent2,:3241124332412314变异算子在做变异时，先对解群以一定的概率进行突变操作。在此作业调度算法中，不能简单的将基因的值做改变。由于问题及其表示的特殊性，这样简单的改变可能是没有意义的。我们使用如下变异方法：随机产生一个整数，确定变异位置，然后，把该位置的基因与其前面的基因互换位置。同样，以132312312为例，假设变异位置为2，则变异前后的基因链码为：变异前：132312312变异后：312312312遗传算法终止条件从查阅的资料来看，大多是以优化时间或迭代次数或适应度的增量或其他参数作为终止条件的，我们采用以迭代次数作为是否终止的条件，从而控制优化过程。4模型的求解假设

23、交叉概率Pc=100%,变异概率Pm=25%，群体规模为6,加工顺序矩阵:T=136736;51010104;548917;555389;35431;3391041;相应的每个加工操作有时间矩阵：M=201354;24503;35014;02345;14503;135042;运行程序结果如下，最短时间为61，曲后件当前文件夹D名称巒aberrance.m智across.m智cal.m角calp.m程|caltime.m崔|M.m智PlotRec.m佝ranking.m酋rein&.m趟select.m會sus.m雪T.m酉zhuchengxu.m制信息工作区称筈田田田田田田田田田田mhrotn

24、venGAVIAXbcAgGijMM-J6540 x36double40 x1double2000.90003666x6double200|矗编揖器-C:ProgramFilesMATLABR2015bbinfilezhuchengxu.mAX|zhuchengxu.mI+mPointl=FValU,1):TO124-mPcjint2=Pal(2,i);125-xl=mPointl:126一yl=mText-0.5:127一x2=mPoiiit2;128一y2=mText-0.5;129一x3=mPoLiit2;130-y3=mText;131-x4=mPointl:132一y4=mText:

25、133一fill(xl,x2,x3,x4,yl,y2,y3,y4,1,0.5,1);134135一word=num2str(P(1,i);136%text(0.5*mPointl+0.5*mPoint2,mText-0.5,word);137-text(mPointl,mText-0.7,word);138-end139命令行窗口zhuchengxuAMinVal=61AV空圉0陽C:ProgramFilesMATLABR2O15bbinfileI叫|行139列1最后，由仿真得到66的曲线图3.3和甘特图3.4,图中显示了适应度值为6个工件在6个机器加工所需的最短时间，对应得工序即为工件的加工

26、顺序。图3.3中实线代表最优解的变化，虚线代表种群均值的变化。图3.4表示了工件666的调度。图3.3曲线图图3.4甘特图5结论总结遗传算法在解决作业车间调度问题上比经典的启发式算法好，同时遗传算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式。作业车间调度问题是计算机集成制造系统工程中的一个重要组成部分，它对企业的生产管理和控制系统有着重要的影响，在当今的竞争环境下，如何利用计算机技术实现生产调度计划优化，快速调整资源配置，统筹安排生产进度，提高设备利用率已成为许多加工企业面临的重大挑战。6.附录主程序：T=136736;85101010548917

27、;555389;935431;3391041M=20135;124503;235014;102345;214503;135042;%将机器号+1fori=1:6S=M(i,:);forj=1:6S(j)=S(j)+1;endM(i,:)=S;endPNumber=6;%零件个数6MNumber=6;%机器个数6WPNumber=666666;%将时间处理下TTemp=T;fori=1:6forj=1:6TTemp(i,j)=T(M(i,j),i);endendNIND=40;%个体数目(Numberofindividuals)MAXGEN=200;%最大遗传代数(Maximumnumberof

28、generations)GGAP=0.9;%代沟(Generationgap)XOVR=0.8;%交叉率MUTR=0.6;%变异率gen=0;%代计数器trace=zeros(2,MAXGEN);%寻优结果的初始值WNumber=0;fori=1:PNumberWNumber=WNumber+WPNumber(1,i);%工序个数end%初始化群Chrom=zeros(NIND,WNumber);fori=1:NINDChrom(i,:)=randperm(WNumber);end%计算目标函数值PValObjVP=cal(Chrom,NIND,T,M,PNumber,MNumber,WPNu

29、mber);whilegentrace(1,gen)Val1=PVal;Val2=P;MinVal=trace(1,gen);endendPVal=Val1;%工序时间P=Val2;%工序MinVal=MinVal%最小时间%计算解的变化holdon;plot(0,0,0,0);plot(trace(1,:);holdon;plot(trace(2,:),-.);grid;legendC解的变化，种群均值的变化)；%显示结果figure(2)；fori=1:WNumberval=P(1,i)；a=(mod(val,10)+1；b=(val-a+1)/10)；mText=M(b,a)；PlotR

30、ec(PVal(1,i),PVal(2,i),mText)；holdon；mPoint1=PVal(1,i)；mPoint2=PVal(2,i)；x1=mPoint1;y1=mText-0.5;x2=mPoint2;y2=mText-0.5;x3=mPoint2;y3=mText;x4=mPoint1;y4=mText;fill(x1,x2,x3,x4,y1,y2,y3,y4,1,0.5,1);word=num2str(P(1,i);%text(0.5*mPoint1+0.5*mPoint2,mText-0.5,word);text(mPoint1,mText-0.7,word);endM文件

31、如下：aberrance.mfunctionChromNew=aberrance(Chrom,NIND,MUTR,WNumber)%新群ChromNew=Chrom;fori=1:NIND%是否变异a=rand;ifMUTRa;%变异位置Pos1=unidrnd(WNumber);Pos2=unidrnd(WNumber);%变异位置不相同whilePos1=Pos2Pos2=unidrnd(WNumber);end%取数据S=Chrom(i,:);%交换temp=S(Pos1);S(Pos1)=S(Pos2);S(Pos2)=temp;ChromNew(i,:)=S;endendacross

32、.m:functionChromNew=across(Chrom,NIND,XOVR,WNumber)%新群ChromNew=Chrom;%交叉位置%Pos1=fix(1-XOVR)*WNumber);%Pos2=fix(XOVR*WNumber);%随机选择交叉个体SelNum=randperm(NIND);%fori=1:NIND%SelNum(i)=unidrnd(NIND);%end%交叉个体组个数Num=NIND/2;Num=2*fix(Num);fori=1:2:Numa=rand;ifXOVRa;%变异位置Pos1=unidrnd(WNumber);Pos2=unidrnd(WN

33、umber);Pos3=unidrnd(WNumber);Pos4=unidrnd(WNumber);%变异位置不相同whilePos1=Pos2Pos2=unidrnd(WNumber);endifPos1Pos2temp=Pos1;Pos1=Pos2;Pos2=temp;endwhilePos3=Pos4Pos3=unidrnd(WNumber);endifPos3Pos4temp=Pos3;Pos3=Pos4;Pos4=temp;end%取交换的个体S1=Chrom(SelNum(i),:);S2=Chrom(SelNum(i+1),:);%初始化新2个体S11=zeros(1,WNum

34、ber);S22=zeros(1,WNumber);%新个体中间部分的COPYforj=Pos1:Pos2S11(j)=S1(j);%S22(j)=S2(j);endforj=Pos3:Pos4S22(j)=S2(j);end%交换个体1forj=1:WNumberflag=ismember(S2(j),S11);ifflag=0k=1;whilek=WNumberifS11(k)=0S11(k)=S2(j);k=WNumber+1;endk=k+1;endendend%交换个体2forj=1:WNumberflag=ismember(S1(j),S22);ifflag=0k=1;whilek

35、ObjV(i,1)Val1=PVal;Val2=P;MinVal=ObjV(i,1);endendPVal=Val1;P=Val2;calp.mfunctionP=calp(S,PNumber,WPNumber)%初始化temp=zeros(1,PNumber);val=max(WPNumber);PS=zeros(PNumber,val);%转化成二维数组val=0;fori=1:PNumberforj=1:WPNumber(1,i)PS(i,j)=S(1,val+j);endval=val+WPNumber(1,i);end%工序个数WNumber=0;fori=1:PNumberWNum

36、ber=WNumber+WPNumber(1,i);endfori=1:WNumber%计算工序val,pos=max(PS);P(1,i)=pos(1,1)*10+temp(1,pos(1,1);temp(1,pos(1,1)=temp(1,pos(1,1)+1;%移动PS的位置forj=1:WPNumber(1,pos(1,1)-1PS(pos(1,1),j)=PS(pos(1,1),j+1);endPS(pos(1,1),WPNumber(1,pos(1,1)=0;endcaltime.m:functionPVal=caltime(P,T,M,PNumber,MNumber,WPNumb

37、er)%工序个数WNumber=0;fori=1:PNumberWNumber=WNumber+WPNumber(1,i);endTM=zeros(1,MNumber);TP=zeros(1,PNumber);PVal=zeros(2,WNumber);fori=1:WNumber%机器号val=P(1,i);a=(mod(val,10)+1;b=(val-a+1)/10);m=M(b,a);%时间t=T(b,a);%取这工序的机器的时间和先工序的时间val1=TM(1,m);val2=TP(1,b);%交换ifval1val2val=val1;elseval=val2;end%计算时间PVa

38、l(1,i)=val;PVal(2,i)=val+t;%记录机器时间和工序时间TM(1,m)=PVal(2,i);TP(1,b)=PVal(2,i);endplotRec.m:functionPlotRec(mPoint1,mPoint2,mText)vPoint=zeros(4,2);vPoint(1,:)=mPoint1,mText-0.5;vPoint(2,:)=mPoint2,mText-0.5;vPoint(3,:)=mPoint1,mText;vPoint(4,:)=mPoint2,mText;plot(vPoint(1,1),vPoint(2,1),vPoint(1,2),vPo

39、int(2,2)holdon;plot(vPoint(1,1),vPoint(3,1),vPoint(1,2),vPoint(3,2)plot(vPoint(2,1),vPoint(4,1),vPoint(2,2),vPoint(4,2)plot(vPoint(3,1),vPoint(4,1),vPoint(3,2),vPoint(4,2)end问题二：邮政运输网络中的邮路规划和邮车调度问题描述某地区的邮政局、所分为地市中心局、县级中心局和支局三级机构，该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。为使邮政企业实现低成本运营和较高的服务质量，我们需要对该地区的邮政运输网络进行重构，

40、确定合适的邮路规划方案并进行邮车的合理调度。该地区的邮政运输流程及时限规定如下：Stepl：区级第一班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi和沿途支局收寄的邮件运送回地市局D；区级第一班次邮车出发时间必须在06:00之后，返回地市局D时间必须在11:00之前。Step2:县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理，按寄达支局装上相应的县级邮车；县局Xi对邮件的集中处理时间为1小时（包括邮件的卸装、分拣封发等处理时间）。Step3:各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局Xi；Step4:区级第二班

41、次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi收寄的邮件（包括当日各县级邮车运回县局Xi的邮件）和沿途支局收寄的邮件运送回地市局D；区级第二班次邮车在县局Xi卸装完邮件后的出发时间必须在县局人的全部县级邮车返回县局并集中处理1小时以后，最终返回地市局D的时间必须在18:00之前。现在预解决以下问题：以县局X及其所辖的16个支局Z,Z2,Z16为研究对象，假设区级第一班次邮车08:00到达县局X1，区级第二班次邮车16:00从县局X1再出发返回地市局D,若每辆县级邮车最多容纳65袋邮件，试问最少需要多少辆邮车才能满足该县的邮件运输需求？同时，为提高邮政运输效益，应如何规划邮

42、路和如何安排邮车的运行？模型建立2.1模型的基本假设（1）所有车辆均在区局或县局出发；（2）区局两个班次邮车的行驶路线相同；（3）区局使用的邮车各个参数相同，县局使用的邮车各个参数也相同；（4）各点都有一定量的邮件待运；（5）邮车在各支局停留时间均为5分钟，在各县局停留时间均为10分钟；（6）邮车保持一定速度均速行驶，县级邮车平均速度为30km/h，区级邮车平均速度为65km/m,邮车行驶过程中无需考虑道路等级、信号等待、会车、路面清洁程度等因素;（7）一辆邮车只用于一条路由；每个支局有且只有一辆邮车寄送邮件，允许其他邮车经过该支局，但不负责该支局的邮件的寄送，不做停留。2.2符号说明M:从县

43、局X寄达16个支局的邮件总量m：每辆县级邮车最多容纳的邮件数x:对实数x上取整R：由于空车率而减少的收入gjr:支局j需要寄达的邮件数gjs:支局j需要运走的邮件数jscij：各个局之间的距离t:县局邮车出行时限maxq:邮车的最大承运能力S:县局到各支局的距离向量cj表示对应路段（i,j）的长度C:邻接矩阵T:支局连接标志矩阵Wijk:通过路段（i,j）时邮车k已收到的邮件数Zijk:通过路段（i,j）时邮车k上还未寄达的邮件数j:各支局邮件收发量之差v1:县局邮车的行驶速度t1:邮车在各支局停留的时间Sxy:从支局Zx到支局邮路合并后的里程节余lxy:判断支局Zx和Zy是否能合并的变量2.

44、3模型分析时限与成本是邮政运输问题的两个重要指标，时限关系到邮政通讯质量的好坏，成本影响着企业的经营。分别考虑这两方面因素，我们将问题一做了如下分析:首先，由该地区邮政运输流程及时限的规定可以得出，县级邮车每天的发车时间最早是早九点，返回时间最迟是下午三点，即邮车的出行时限最多为6小时。其次，一般认为，派出一辆车的固定费用远远高于该车辆行驶的费用，因此为了降低成本，设计模型的目标是使用的车辆数最少。由于从县局X1寄达16个支局的邮件量总M为176袋，而每辆县级邮车最多容纳邮件数m为65袋，故得出若要满足该县的邮件运输需求所需车辆的下限nM/m3辆。又由空车率=（邮车最大承运的邮件量（袋）-邮车

45、运载的邮件量（袋）/邮车最大承运的邮件量（袋）可知，要想提高运输效益，需要使空车率达最小。第三，关于邮路结构的选择。辐射形邮路和环形邮路各有优缺点：辐射形邮路可以缩短运递时间，加快邮运速度，但是其联系点较少，效率低耗费大；环形邮路联系点较多，效率高运费省，但是时效性稍差。考虑到该县邮车的出行时限最长为6小时，在不影响时限标准的前提下，应尽可能地降低成本，且该县各支局的连通网络中不存在最小割为1的点（若存在最小割为1的点，则该点与其临近点的连接只能选择辐射形邮路），故我们优先选择环形邮路。2.4模型的建立为了更好的描述问题，将其定义为网络G=（V,A,C），其中V=OUP为一点集，O表示县局乂，

46、编号为0，P表示各个支局，编号分力0为1，2，16，支局j需要寄达的邮件数为gjr，需要运走的邮件数为gjs，Aj=gjr-gjs；A为一距离集合，表示邮车可能走过的路线集合山为邻接矩阵，用以表jsjjrjs示邮路规划方案，可构造为：0n0cc00OnC:ncn0cnncij表示对应路段（i，j）的长度，即局与局之间的距离；对于所有的支局，要求邮车在时限tmijmax内遍历。为构造数学模型，定义决策变量：1支局的邮件由邮车k送达yki0否则1邮车k通过路段（i,j）xijk0否则Wijk为通过路段（i，j）时邮车k已收到的邮件数，Zijk为通过路段（i，j）时邮车k上还未寄达的邮件数。由于设计

47、模型的首要目标是使用的邮车数最少，故我们先以k=3入手，其数学模型可表示为如下形式：minR231616qj)k1i1j1XijkCij(1.1)s.t.yki1,fori1，16(1.2)kxijkya，iforj1，2，.，1k6;(1.3)xijkyki，jfori1，2，.，1k6;(1.4)(WijkZijkjxijk)q(1.5)ij，ijxijkijtykit，fork1maxi(1.6)vij，ij1xijk0or1，fori，j0，16i，j;k(1.7)yki0or1，fori1,16;k(1.8)q式(1.1)表示空车率带来的收入损失最小；式(1.2)表示一个支局由一辆邮

48、车寄送邮件；式(1.3)和式(1.4)表示每个支局被访问一次；式(1.5)保证在整个回路中运载邮件的数量不超过邮车的运载能力式(1.6)保证了满足时限的要求；式(1.7)和(1.8)为变量取值约束。模型的求解3.1求解思路问题一类似于车辆路径问题(VRP),常采用的是启发式算法中的C-W算法，该算法的基本思想是：首先将各支局点与县局点相连，构成N条初始邮路，计算各邮路里程，然后以邮路里程节余为判据，进行邮路的合并，直到没有邮路再能合并为止，形成最终的几条邮路。邮路合并的同时考虑到时限与邮车承运能力的问题。命题1.两条辐射形邮路合并为一条环形邮路可大大减少邮路里程。证明：如图1所示，两条辐射形邮路分别为X&X帀X1ZyX1,在这里我们给出里程节余的说法，关于邮路里程节余的计算参考图1，从县局X到支局Z和Z各有一条邮路，如有邮车既访问Z又访1xyx问Zy而不破坏时限和负载约束条件