车辆配载优化.ppt.ppt

1、五、车辆配载优化,多品种混装,多品种混装问题就是：把货物按品种、形状、颜色和规格分为若干类，分别称为1类、2类m类。设共有N件（捆）待运货物，其中1类货物有N1件（捆），它们的重量分别为G11，G12，G1N1，2类货物有N2件（捆），它们的重量分别为G21、G22G2N2，依此类推，要求装入同一货车内，货车最大载重为G0，每类货物至多装入一件（捆），最大载重多少？,2类货物，共N2件,m类货物，共Nm件,1类货物,共N1件,.,G11,G12,G13,G1N1,G21,G22,G23,G2N2,Gm1,Gm2,Gm3,GmNm,共N件，N= N1+ N2+ Nm,考虑：要是你，怎么解决？,混

2、装问题的网络表示,G11,G12,G21,G33,G32,G31,G42,G41,第一类货物,第二类货物,混装问题就是在网络中自右向左找一条路线，使路线所经过的方框中的质量之和达到极大，但不超过货车的载重量的上限G0。,有的同学会说，用穷举法，太麻烦，可以化为动态规划问题求解，m类货物看成m个阶段。我们看一个例子：,例1：假设共有8件4类货物，货车载重量G0=50t，第一类货物2件，G11=20t，G12=11t；第二类货物1件，G21=13t；第三类货物3件，G31=6t，G32=11t，G33=8t；第四类货物2件，G41=19t，G42=17t。同类货物至多装1件，计算最大装载量及装载方

3、法。,此题可运用动态规划方法，按四类货物分为四个阶段。本例从第四类货物开始，计算过程见后：,第四阶段计算表,目前可用载重量,第四类货的可能的几种装载量,第四类货装完后的可能剩余载重量,50,0,19,17,50,31,33,注：W4-G4是第四类货物装完后的可能剩余载重量，可用于第三类货物的目前可用载重量：即W3= W4-G4,第三阶段计算表,装完第四类货后可用载重量W3=W4-G4,第三类货的可能的几种装载量,第三类货装完后的剩余载重量,0,6,6,11,11,8,8,0,0,6,11,8,50,44,39,42,31,25,20,23,33,27,22,25,第二阶段计算表,0,13,0,

4、13,0,13,0,13,0,13,0,13,0,13,0,13,0,13,0,13,0,13,0,13,50,37,44,31,39,26,42,31,18,25,12,20,7,23,10,33,20,27,14,22,9,25,12,29,20重复,31重复,因此，装完第二类货物共有22种可能剩余载重量,装完第三类货后可用载重量W2=W3-G3,第二类货装完后的剩余载重量,第一阶段计算表,50,37,44,31,39,26,42,18,25,12,29,20,7,23,10,33,27,14,22,9,25,12,30,39,50,37,17,26,44,24,33,31,11,20,3

5、9,19,27,26,6,15,22,31,42,29,9,18,25,5,14,18,7,12,1,20,0,9,7,23,3,12,10,1,33,13,22,27,7,16,14,3,2,11,22,9,25,5,14,12,1,从W1-G1=0处开始往前推,W1=20 G1=20,W2-G2=20,反向寻求最优解,找W1-G1=0处,第二阶段计算表,0,13,0,13,0,13,0,13,0,13,0,13,0,13,0,13,0,13,0,13,0,13,0,13,50,37,44,31,39,26,42,31,18,25,12,20,7,23,10,33,20,27,14,22,9

6、,25,12,29,从W1-G1=0处开始往前推,W1=20 G1=20,W2-G2=20,W2=20,G2=0或W2=33G2=13,W3-G3=20或33,第三阶段计算表,0,6,6,11,11,8,8,0,0,6,11,8,50,44,39,42,31,25,20,23,33,27,22,25,从W1-G1=0处开始往前推,W1=20 G1=20,W2-G2=20,W2=20或33;G2=0或13,W3-G3=20或33,W3=31 G3=11或W3=33或G3=0 ；,W4-G4=31或33,第四阶段计算表,50,0,19,17,50,31,33,综上，可以得出最优解：1、装载第一类货

7、物的20t，装载第二类货物的0t，第三类货物11t，第四类货物19t; 2、装载第一类货物20t，装载第二类货物13t，装载第三类货物0，装载第四类货物17t 。,从W1-G1=0处开始往前推,W1=20 G1=20,W2-G2=20,W2=20或33;G2=0或13,W3-G3=20或33,W3=31或33； G3=11或0,W4-G4=31或33,货区分区,大型仓库里,一般都有几十个货区,每个货区有几百个或几千个货位,存放着不同货物,通常要把这些不同货位的货物配装成整车运往目的地。 有的货物可以配装，有的货物不可以配装 货区位置不同，有的相互离得近，有的离得远，因此配装成本不同，邻近的尽量装在一辆车上。,货区组合方案就是指只在该组合方案中的各货区货物才能配装在一辆车上。 不同的组合方案装货费用不同。 把方案按装货费用从低到高顺序排列，安排货车配装计划时，首先按第一种方案D1进行货物配装，再按第二种方案D2对货物进行配装，依此类推。（货区分级组合法）,例：下表是某储运仓库选用的10种有代表性的序列，它由10种组合方案构成。,有这样一张待运表，需要运送到同一地点，货车载重为50：,首先考虑第一种组合方案，各货区分别单独进行组合：第1区货物总量为35，第4区货物总量为25，第5区货物总量为50，第6区货物总量为25，第7区货物总量为5。