王柳君等露天矿生产的车辆安排.doc

露天矿生产的车辆安排摘要：本文围绕露天矿生产铲位与车辆安排的优化问题，建立了0-1规划跟整数线性规划综合数学模型。鉴于0-1规划跟整数线性规划综合求解的复杂性，采用了穷举法与非整数线性规划，在满足卸点产量与品质、不发生等待等原则下求出最优的铲位组合。并进一步采用搜索算法、上下取整等优化算法对模型进行整数优化求解的方案。对于题目给出的实例分别按总运量最小及总产量最大的运则进行了求解，并给出了最优解及生产安排。关于第一个模型，我们的结果是派14辆卡车，铲位是1,2，3,4，8,9，10；算得的最小总运量为：85176吨公里。对第二个模型，需要出动20辆卡车，算得的最大产量为：103488吨，铲位仍是1,2，3,4，8,9，10。在模型的改进中，我们改进了搜索算法，并且给出了一个卡车在装卸点都不等待的充分条件。我们可以利用这个条件来检验我们的模型结果。保证了是在卡车不等待的情况下的解。一、 问题重述 露天矿生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。露天矿里有若干个铲位，每个铲位已经预先将石料分成矿石和岩石，而且矿石、岩石的数量以及矿石的平均铁含量（称为品位）都是已知的。每个铲位最多能安置一台电铲，电铲的平均装车时间为5分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。在运输矿石时，必须保证其含铁量为29.5%1%，称为品位限制。在一个班次（8小时）内，卸点不变，卡车的平均卸车时间为3分钟。所用卡车载重量为154吨，平均时速28km/h。为了节省能量，在一个班次内，卡车只在开始工作时点火一次，而且原则上不应该发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上的卡车服务。卡车每次都是满载。每个铲位到每个卸点的道路不会出现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：1、 总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；2、 利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。分别就两条原则建立数学模型，并给出一个班次生产计划的快速算法。针对题目所给的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。二、 符号说明 ：铲位序号从1到10。：矿石卸点序号从1到3。：岩石卸点序号从1到2。：从铲位运载到矿石的卸点的总车次。：从铲位运载到岩石的卸点的总车次。：从铲位到矿石的卸点的距离。：从铲位到岩石的卸点的距离。：铲位的矿石量（将其转换为运载车次来计量，每车次为154吨）。：铲位的岩石量（将其转换为运载车次来计量，每车次为154吨）。：矿石的卸点的产量任务（将其转换为运载车次来计量，每车次为154吨）。：岩石的卸点的产量任务（将其转换为运载车次来计量，每车次为154吨）。： 铲位的矿石铁含量。：拥有的卡车数量。：总运量。三、 模型假设1、 每个班次开始工作前，所用的车辆都已经在各个卸点安排就绪，不再需要另外花费时间调度安排卡车。2、 每辆卡车每次只能运载一种石料，不能同时运载矿石和岩石。3、 在整个生产过程中，基本上按照时间要求作业，不考虑因为随机因素造成的负面影响。4、 在车辆安排上，为了提高车辆的利用率，允许当有车辆闲置时调到别的运线上四、 模型分析和求解模型一根据“在卡车不等待的条件下满足产量和质量要求”，以及“总运量（吨公里）最小，且出动卡车最少”两条规则，建立模型一。在实际中，铲位可以向任何一个卸点提供石料，卸点也可以从任何一个铲位运载石料。这样一来，很难直接通过线性规划的方法同时满足这两个规则，于是我们考虑分两个步骤来满足规则。首先，我们求出使总运量最小的运载路线，即求出在总运量最小的情况下，从铲位运载到卸点的总车次各是多少。然后，我们在总运量最小的运载路线上，安排每条路线上的卡车数以及每辆卡车的往返数，使出动的卡车最少。为了计算方便，统一用运载车次来计量铲位的石料数，每车次为154吨。由于卸点所需的产量任务不一定能够整除单位运载量（154吨），因此将卸点的产量任务向上取整。在求总运量最小的过程中，受到以下因素的制约：l 各卸点必须满足其产量要求。l 从矿位运载到卸点的石料不能超过矿位的石料储存量。l 在一个班次内，选择的铲位数不能大于现有的铲车数。l 每个铲位、卸点都不能同时为两辆或两辆以上的卡车服务，为了避免在矿位和卸点出现等待情况，必须保证在一个班次内接受服务的卡车数不大于其最大服务能力。l 在一个班次内，矿石卸点必须满足其品位要求。建立目标函数为(i从1到10,j从1到3,k从1到2)： 满足卸点产量的约束函数为: ，满足铲点产量的约束函数为:， 满足铲车装载能力的约束函数为: 满足卸点卸货能力的约束函数为: ，满足品位的约束函数为: ， 由以上分析，列得目标函数及约束条件方程，如下： (程序见附录1) 一般来说，经过线性规划后得到的最优解往往是小数，而在本题中，结果为运载车次，不可能为小数，必须将优化结果调整为整数。调整步骤如下：（参考文献1，见78页）首先，将第一个小数变量上下取整。然后，将调整后的整数运算比较后，得到最近且最优的离散值。再次，将得到的离散值代入约束条件，判断离散值是否满足约束条件。如果满足约束条件，就算是解决了一个变量的离散化问题；如果不满足，就需要重新进行取整调整，直到满足约束条件为止。最后，用同样的方法类推，当所有的小数变量都取得最优的整数离散值后，即解决了整数问题。 求得最小总运量后，在此基础上进行卡车调度安排，基本原则是：尽可量减少出动的卡车数量。原因是：卡车点火时消耗的能量很大，只有尽可能的利用已经点了火的卡车，才能节省能量。在具体的铲点和卸点之间，能够承受的最大卡车数是确定的，是安排卡车时需要考虑的约束条件。它由以下几个因素决定：具体的铲点和卸点之间的路程、在铲点和卸点必须浪费的时间。现在假设铲点和卸点之间的路程为s，这条路线上能够承受的最大卡车数为n，一辆卡车往返一次所走的路程为(2s+3+5)。为了避免出现两辆或两辆以上的卡车在道路发生堵塞现象，必须保证满足条件：(2s+3+5)5n (n1)；否则只能安排一辆卡车。根据以上条件，求得每条路线上能够承受的最大卡车数，见下表。铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏3333222212倒装场2122222223倒装场3332221221岩石漏1222223334岩场3333332221 对于本题给出的实例，利用以上算法计算，过程如下。1、 用运载车次来计量铲位的石料数，每车次为154吨，并将转换的结果向上取整。矿石漏倒装场I倒装场II岩石漏岩场运载任务（万吨）1.21.31.31.91.3运载任务（车）788585124852、 根据题目要求，需要在10个铲位放置7或小于7台电铲。在解题过程中，我们首先选择7个铲位，然后算出这组数据的最优解，接着采用穷举法来搜索次，通过比较得出10个铲位的最优解。3、 将得到的最优值取整，求得最终整数最优解，结果如下：算得的最小总运量为：85176吨公里。各矿石卸点的铁含量为矿石漏30.50、倒装场I30.07、倒装场II30.51。各铲位到各卸点的运载总车次见下表。铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0130000055010倒装场I041044000000倒装场II014000000071岩石漏810430000000岩场0000000070154、 经检验，此最优解满足约束条件。 5、求解各条路线上安排的卡车数。算得最少需要出动14辆卡车。具体安排结果见下表。第一次安排车次如下（跟第二次安排的具体车次综合在下面的表格里）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0000000200倒装场I0202000000倒装场II0000000002岩石漏2020000000岩场0000000020第二次派车（因部分任务已完成转而运别的线路）如下铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0200000002倒装场I0000000000倒装场II0200000000岩石漏0000000000岩场0000000001运输次数如下铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏06/70000017/1805倒装场I020/21022000000倒装场II07000000035/36岩石漏40/41021/220000000岩场00000000357/8 模型二根据“在卡车不等待的条件下满足产量和质量要求”，以及“利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）”两条规则，建立模型二。要达到最大的产量，则必须达充分利用铲车的生产能力、卸点的卸货能力以及卡车的运输能力，因此从铲位到卸点及的运载车次出满足模型一的约束条件外还必须满足小于等于20辆汽车一个班次的最大运量限制条件:即总的运载车次与距离的乘积的二倍所花的时间与装车和卸车所用时间要小于一个班次20部车的总工作时间。根据上述分析可得出如下线性规划目标函数及约束条件方程： 使用模型一的方法进行穷举，获得了最优的产量和铲车数，由于经过线性规划后得到的最优解往往是小数，而在本题中，结果为运载车次，不可能为小数，必须将优化结果调整为整数。这里，使用采用局部搜索算法对上述规划所得结果进行整数规划，即可解决整数问题。1 算得的最大产量为：103488吨。铲位到各卸点的运载总车次见下表。铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0530000054450倒装场I0075660000116倒装场II311560000010岩石漏650280300000331岩场00150000016792. 求解各条路线上安排的卡车数。需要出动20辆卡车。各矿石卸点的铁含量为矿石漏30.30、倒装场I30.48、倒装场II 30.36。具体结果见下表。第一次安排车次如下（跟第二次安排的具体车次综合在下面的表格里）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0400000000倒装场I0032000000倒装场II2000000302岩石漏2000000020岩场0000000002第二次安排车次（因部分任务已完成转而运别的线路）如下铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0000000020倒装场I0002000011倒装场II0110000010岩石漏0102000101岩场0020000110两次安排车辆运输次数如下铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏013/3*1200000022/230倒装场I15/16025330000116倒装场II32/3315600002*22/2310岩石漏028015/150001161岩场007/80000131639/40五、 模型讨论1 优点 利用了计算机快捷的特点，提高了效率。将各种组合都考虑在内，具有普遍性。2 缺点(1) 根据以上模型求解出来的结果是相当令人不满意的。因为求解的结果是依据线性规划后穷举各个组合的办法求出来的。这种求解过程复杂度太大。当铲点和卸点的数量增大的时候，将导致求解复杂度的进一步增加。因此，我们可以利用直接观察的方法先把范围缩小，再进行穷举就可以大大的减少问题的复杂度。(2) 没有充分考虑到卡车较多的地方发生的等待现象，以及上班及下班所所花费的时间，导致最优值误差过大。六、 模型改进上面的模型里，我们利用一个条件：在各个铲点和卸点上所花费的总时间要少于一个班次里的总时间（即8小时），就认为在各个点上是没有等待现象出现。事实上这个条件仅仅是没有等待现象的一个必要条件，而非充分条件。依据这个条件就确定为无等待现象出现是比较粗糙的，甚至是不合理的，几乎是默认为各个铲点和卸点都没有等待现象出现。在这里我们给出一个比较直观的各个装卸点不会因为各条路线的交汇而产生等待现象的一个充分条件：当通向同一个节点的路线共有2条，而且在每条路线上都仅有一辆卡车在行使时，: 最长的路线往返距离: 最短的路线往返距离:在条路线中最短的一条路线往返距离：最长的路线的卡车数量：最短的路线的卡车数量: 较短的路线上一个班次内卡车往返的最大次数: 在装点或卸点上占用的时间内卡车行进的路程：通往某个节点的路线总数首先要有以下两个假设：1、往返距离比较长的排在后面。因为如果往返距离比较短的排在后面的话，它往返一次所用的时间比较少。在给出的已知数据里，在一个班次内必定是会发生等待现象的。根据不等待原则，我们安排往返距离比较长的排在后面。不发生等待现象必须满足条件： 即在一个班次时间内较短路线上的卡车无法赶上较长路线上的卡车。在这里，本来还应该有短程卡车赶上了长程卡车仍然不发生等待的情况，但是由于考虑到资源尽量利用时整条线路上几乎都没有空闲，不会发生以上情况(当安排的卡车比较多，车次也比较密集的时候尤其如此)。当通向同一个节点的路线共有条时，而且在每条路线上都仅有一辆卡车在行使时，不发生等待现象必须满足条件： 当通向同一个节点的路线共有2条时，而且在每条路线上分别有、辆卡车在行使时，不发生等待现象必须满足条件： 这样我们可以根据条件计算出必定会产生冲突的两条线路。我们所解得值必须经过这个条件的检验才可以通过。此外，在前面的解法当中也有可以改进的地方。因为岩石不用考虑品位限制，因此无论是最小运量还是最大产量，距离都是决定生产计划的重要因素。根据图形的直接观察，我们发现在岩石漏距离最近的是铲点1，3，6，别的铲点离得比较远，则这3个点钟必然有一到两个在作为铲位。而到岩场最近的点是9，10点，同时10点离倒装场最近，因此10点必然入选。在所有的矿点中只有1，2，3总共3个点的品位在品位限制之下，而其中以2点的最小，距离又别的矿石卸点又最近。因此，到各个矿石卸点的铲点中肯定又铲点2在。这样通过逐步缩小范围将使搜索效率大大提高。七、 参考文献1 飞思科技产品研发中心，MATLAB6.5辅助优化计算与设计，北京：电子工业出版社，2003年。2 苏金明、邧沈勇，MATLAB6.1实用指南(上、下册) ，北京：电子工业出版社，2002年。3 卢开澄，单目标和多目标与整数线性规划，北京：清华大学出版社，1999八、 附录附录1求解模型一的约束方程clearclcA1=5.265.194.214.002.952.742.461.900.641.27 1.900.991.901.131.272.251.482.043.093.51 4.423.863.723.162.252.810.781.621.270.50 0.641.761.271.832.742.604.213.725.056.10 5.895.615.614.563.513.652.462.461.060.57%按行，各行的数据 分别代表矿石漏、倒装场、倒装场、岩石漏、岩场。B=0.951.051.001.051.101.251.051.301.351.25 1.25 1.101.351.051.151.351.051.151.351.25 %第一行为矿的总量，第二行为岩石的总量C=0.300.28 0.29 0.32 0.31 0.33 0.32 0.31 0.330.31 %矿石的铁含量B1=fix(B/0.0154) %换算为一个单位即一车154吨%B21=fix(B(11:20)/0.0154)c1=1.2 1.3 1.3 1.9 1.3%卸点的产量要求c11=fix(c1/0.0154)+1n=7 %出动铲车数QQ=combntns(1:10,n) %获得各种可能的组合m=length(QQ)%组合总数D=A1D1=B1D2=CG=100000;H=0;E=;E1=;E2=;for i=1:m %对各种组合进行优化计算for j=1:n E=E;D(QQ(i,j),1:5) %取出用于计算的数据 E1=E1;D1(QQ(i,j),1:2) E2=E2;D2(QQ(i,j),1)endE=EE1=E1E2=E2a1=0.285-E2a2=E2-0.305f=E(1,1:n),E(2,1:n),E(3,1:n),E(4,1:n),E(5,1:n) % 优化目标函数A=linspace(-1,-1,n),linspace(0,0,4*n); linspace(0,0,1*n),linspace(-1,-1,n),linspace(0,0,3*n); linspace(0,0,2*n),linspace(-1,-1,n),linspace(0,0,2*n);%满足第j个卸点生产任务的约束条件 linspace(0,0,3*n),linspace(-1,-1,n),linspace(0,0,n); linspace(0,0,4*n),linspace(-1,-1,n); eye(n,n),eye(n,n),eye(n,n),zeros(n,n),zeros(n,n); %满足i个铲点的矿石数量约束 zeros(n,n),zeros(n,n),zeros(n,n),eye(n,n),eye(n,n); %满足i个铲点的岩石数量约束 eye(n,n),eye(n,n),eye(n,n),eye(n,n),eye(n,n);%满足i个铲点电动铲装车数约束 a1,linspace(0,0,4*n); linspace(0,0,1*n),a1,linspace(0,0,3*n); linspace(0,0,2*n),a1,linspace(0,0,2*n);%满足j个卸点的矿石品位的下约束 a2,linspace(0,0,4*n); linspace(0,0,1*n),a2,linspace(0,0,3*n);%满足j个卸点的矿石品位的上约束 linspace(0,0,2*n),a2,linspace(0,0,2*n) b=-c11;E1(1:n,1);E1(1:n,2);linspace(96,96,n);linspace(0,0,6)lb=zeros(5*n,1)x,fval=linprog(f,A,b,lb)%线性优化XXX=x(1:n);x(n+1:2*n);x(2*n+1:3*n);x(3*n+1:4*n);x(4*n+1:5*n)if(fvalG) G=fval H=i y=x M=QQ(i,1:n) else if fval=G G1=fval H1=i y1=x M1=QQ(i,1:n)endendE=E1=E2=endfval_MIN=G 得出最小运量MIN=Hx=y附录2求解模型二的约束方程clearclcA1=5.265.194.214.002.952.742.461.900.641.27 1.900.991.901.131.272.251.482.043.093.51 4.423.863.723.162.252.810.781.621.270.50 0.641.761.271.832.742.604.213.725.056.10 5.895.615.614.563.513.652.462.461.060.57%按行，各行的数据分别代表矿石漏、倒装场、倒装场、岩石漏、岩场。B=0.951.051.001.051.101.251.051.301.351.25 1.25 1.101.351.051.151.351.051.151.351.25 %第一行为矿的总量，第二行为岩石的总量C=0.300.28 0.29 0.32 0.31 0.33 0.32 0.31 0.330.31 %矿石的铁含量B1=fix(B/0.0154) %换算为一个单位即一车154吨%B21=fix(B(11:20)/0.0154)c1=1.2 1.3 1.3 1.9 1.3%卸点的产量要求c11=fix(c1/0.0154)+1n=7 %出动铲车数QQ=combntns(1:10,n) %获得各种可能的组合m=length(QQ)%组合总数D=A1D1=B1D2=CG=100000;H=0;E=;E1=;E2=;for i=1:m %对各种组合进行优化计算for j=1:n E=E;D(QQ(i,j),1:5) %取出用于计算的铲位到卸点的距离 E1=E1;D1(QQ(i,j),1:2) E2=E2;D2(QQ(i,j),1)endE=EE12=E1E2=E2a1=0.285-E2a2=E2-0.305f=linspace(-1,-1,5*n) % 优化目标函数A=linspace(-1,-1,n),linspace(0,0,4*n); linspace(0,0,1*n),linspace(-1,-1,n),linspace(0,0,3*n); linspace(0,0,2*n),linspace(-1,-1,n),linspace(0,0,2*n);%满足第j个卸点生产任务的约束条件 linspace(0,0,3*n),linspace(-1,-1,n),linspace(0,0,n); linspace(0,0,4*n),linspace(-1,-1,n); eye(n,n),eye