露天矿生产的车辆安排-2003全国一等奖(第一组)

1露天矿生产的车辆安排赵航（010513）陈哲（010712）李辉（010731）（全国一等奖）摘要本文讨论露天矿生产的车辆安排问题，即在满足一个班次合格生产计划的前提下，分别考虑给出的两条原则，建立数学模型。首先，我们采用线性规划的方法，将合格生产计划作为约束条件，分别以两个原则为目标建立模型，采用一个快速算法，求出一可行解集，确定了铲位的位置与数量，然后再利用约束条件找出所用卡车数量和运输路线，经过我们的计算得出：以原则一为目标，则需要出动7个电铲，13辆卡车，使总运量为88991.04吨公里，矿石产量为：38192吨，岩石产量为：32186吨，以原则二为目标，则需要出动7个电铲，20辆卡车，使总运量为153410.18吨公里，矿石产量为：49280吨，岩石产量为：53284吨具体路线安排见正文。其次，我们考虑了问题中的各种随机因素，如装车时间、卸车时间和等待时间等随机波动对结果的影响。我们通过随机模拟获得了一个班次的总装车时间和总卸车时间的样本值。我们发现这个样本值和用5分钟和3分钟的确定值算出来的一个班次的总等待时间和总卸车时间基本吻合。从而证实了线性规划模型的合理性。我们又从随机性的角度重新考虑了总运量问题获得了一个修正的置信区间。同时我们也顾及了班次之间的相互影响。最后我们建立了计算机仿真模型。在论文的最后，我们还对模型进行了改进和推广，说明了我们的模型的实际操作和适用的范围。关键词：线性规划整数规划快速算法随机模拟计算机仿真2一、问题重述露天矿的生产主要由电铲装车、卡车运输来完成。为提高经济效益，我们研究露天矿生产的车辆安排问题，要求出一个班次生产计划的快速算法，计划需要考虑以下两条原则之一：Ⅰ.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；Ⅱ.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。条件：1．每个铲位至多能安排一台电铲，每个卸位至多由一辆卡车在卸车。2．每个卸点都有各自的产量要求，矿石卸点的品位限制为29.5%±1%；3．卡车不等待，每次都是满载运输；我们所要做的就是根据上述两条原则，分别建立满足条件约束的数学模型，并给出一个班次生产计划的快速算法。而且针对题目给的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。二、问题的假设4．电铲和卡车在一个班次的时间内都要正常工作，不需要维修。5．题中所给的数据都是准确无误的。6．卡车载重与空载时的平均时速都是28km/h。7．只考虑一个班次的生产计划。8．卸点在一个班次内不变。9．每个铲为到每个卸点的道路都是专用的宽60m的双向车道，不会出现堵车现象。10．电铲和卸点都不能同时为两辆及两辆以上的卡车服务。11．卡车的调头时间可以忽略不计。三、符号的说明n………………………………该露天矿所用电铲的个数；m………………………………该露天矿卸位的总数；xij……………………………卡车从第i个铲位到第j个卸位重载的总趟数；ci………………………………第i个铲位矿石的铁含量；ai………………………………第i个铲位矿石的产量（t）；ai’……………………………第i个铲位岩石的产量（t）；bj………………………………第j个卸位所需的矿（岩）石量；P………………………………卡车的载重量（154t）；v………………………………卡车的平均时速（28km/h）；dij……………………………第i个铲位到第j个卸位点的距离（km）;Nij………………………………铲位i到卸位j路线上卡车的数目;rij………………………………铲位i到卸位j路线名称;3四、问题的分析和模型的建立4.14.14.14.1分析：露天矿生产系统中一些参数的估计：（1）卡车从铲点i到卸点j必须满载运行，到j点全部卸完。总车次==457⎥⎥⎤⎢⎢⎡+⎥⎥⎤⎢⎢⎡+⎥⎥⎤⎢⎢⎡+⎥⎥⎤⎢⎢⎡+⎥⎥⎤⎢⎢⎡1541300015419000154130001541300015412000（2）系统中电铲n的变化范围：若电铲在一个班次内不停的工作的理想状态，不考虑其他任何的时间浪费，要满足卸点的产量要求，n的最小值==5⎥⎥⎥⎥⎤⎢⎢⎢⎢⎡×++++15454801300019000130001300012000系统中对电铲没有最小的限制，现有铲车7台，因此，5≤n≤7（3）系统中卡车数量N的范围：同理，考虑卡车不停的工作，这些运输路径中的最短距离就是0.50公里，那么系统中卡车运输一次最少需要5+260+3=10.14分××285.0钟那么至少需要卡车=10辆，系统中卡车的数量为20台，因此，10≤N⎥⎥⎤⎢⎢⎡××86014.10457≤20。4.24.24.24.2模型的建立：（一）线性规划模型：基于以上分析，我们首先给出一些初始解，然后提出了一些启发式算法，按照一定的规则对初始解进行优化。由于模型的约束条件很多，相互制约，需要满足的条件和考虑的问题很多，属于NP完全问题。因此，我们将问题简化、分解，以缩小搜索范围，给出满意的求解方法。我们首先假定卡车重载时行驶的路线和空载时行驶的路线时一致的，即卡车从第i个铲点重载到第j个卸点，然后原路返回。当然，这种假设的合理程度我们将在下文进行阐述。我们用线形规划的理论建立了本矿车流的调配方案，车流规则用线性规划或多目标规划建模。首先考虑原则一：总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；目标函数：min.min.min.min.++++Cmin.Cmin.Cmin.Cmin.∑∑==×vijijijdx151154∑∑==nijijn151约束条件：s.t.:s.t.:s.t.:s.t.:≤i=1,2i=1,2i=1,2i=1,2……，nnnn∑=31154jijxai≤,,,,i=1,2i=1,2i=1,2i=1,2……，nnnn∑=54154jijxai'4≥,,,,j=1,2j=1,2j=1,2j=1,2……5555∑=niijx1154bj0.0.0.0.285285285285≤≤0.305,0.305,0.305,0.305,jjjj====1,2,31,2,31,2,31,2,3∑∑==niijijniijxcx11154154=N=N=N=N≤20202020∑∑==nijijn151≤480480480480∑=515jijx≤480480480480∑=niijx13====xijvdnijij×+××28608经过计算机搜索，我们发现即使可行解也很难搜索到，因为露天矿生产的车辆安排，车辆从铲位运岩石或者矿石到卸位的运输请求具有多次往返的特点，若采用往返的单程运输方式，车辆行驶的里程利用率只有50%，调用的资源比较少，里程的利用率比较低，在8小时的时间限制内很难完成任务，要想在有限的资源下一个班次内完成任务，那么就要提高里程利用率，减少空载里程，这样就可以保证构成的环形运输路线有较高的里程利用率，进而更大的满足约束条件下求得可行解。但是，对于这个线性规划问题而言，这种复杂性的组合计算采用穷举法，从中选择最优解时几乎是不可能的。我们再将问题简化，分解，先去掉一些约束条件，将问题转化为多变量的整数线性规划的求解问题,找到可行解集,接着逐步加入原约束条件,得到满足所有约束条件的近似最优解。（二）多变量的整数线性规划::::2.12.12.12.1分析：由题意知，卡车必须满载出驶，因此，卡车只能在铲位与卸点之间运输，而不能在两个铲位与两个卸点之间运输，这样，此运输网络就可以抽象为二部图G（V，R），其中，铲位为顶点集V1，卸点为顶点集V2，V=V1V2，V1V2=，卡车的运输∪∩φ路线抽象为二部图中的边集合R。由于等待时间对问题的约束过强，是导致问题复杂的主要因素，为简化计算，所以暂不考虑，。我们不妨以原则1为目标，以产量和质量（品位）作为约束条件，分步骤建立模型，并求解，然后根据解确定铲位的数量与位置，以及卡车的数目和运输路线。分析如下：5（1111）铲位的确定：设Xi=，i=1，2，……n，其中Xi代表一个班次内第i个电铲装的车次数∑=mjijx1那么，对n个电铲按照Xi值的大小进行排序，根据矿场的实际拥有铲车情况，选择Xi的值大的铲位设置铲车。（2222）运输系统路线的确定：当铲位的数目和位置都已经确定，在原二部图G（V，R），去掉不设置铲车的铲位所代表的点以及与这些点相关联的边，这样得到简化的二部图G’(V’,R’).再对目标函数进行规划，求解出Xij的解集：若Xij=0，说明在rij这条线路上没有卡车通过，这条边是闲置的，舍弃。若Xij0，说明在rij这条线路上有卡车通过，保留这条边。由此，确定了该运输系统中卡车运行路线。（3333）卡车最小数量：本题目要求卡车无论在铲位还是在卸位都不等待，因此，卡车周转一次所需时间Tz可用下列公式计算：Tz=tz+ty+tetz…………..装车时间min；ty…………..卡车运行时间min；te…………..卸载时间min；从整体角度看，若调度合理，那么系统中无等待卡车，于是，可以初步计算运输系统中，一共要用多少个小时才能完成运输任务：总时间=总车次装卸总时间+×卡车的平均速度系统总行程×2那么有：最小卡车的数量=一个班次工作时间总时间（4444）卡车对线路的分配问题：1）若规模大，采用计算机模拟。2）若规模小，则运用自适应原则，人为排车。排车原则：61．先排和关系网最差的卸点相关联的路线车次；2．保证每条路线上最多只有3辆车；3．尽可能使从卸点回来的路线最短；4．使一辆车走的路线尽可能的少。2.22.22.22.2快速算法：根据以上分析，我们可以很方便的写出快速算法：step1:建模求解：只将质量和产量作为约束条件，建立整数规划模型并求解；step2:确定铲点：设Xi=，i=1，2，……n，对n个电铲按照Xi值的大小进行排序，∑=mjijx1根据矿场的实际拥有铲车情况，剔除掉Xi值相对比较小的铲点,保留Xi值比较大的铲点；step3:调整模型：由于铲点的剔除，导致变量的减少，所以将模型重新调整，去掉无关变量，建立新的整数规划模型并求解；step4:确定运输路线：根据step3的结果进行判断，若Xij=0，说明在rij这条线路上没有卡车通过，这条边是闲置的，舍弃。若Xij0，说明在rij这条线路上有卡车通过，保留这条边。Step5:计算卡车需要的辆数：运输系统完成任务需要的总时间为：总时间=总车次装卸总时间+,由此确定卡车数量为：×卡车的平均速度系统总行程×2最小卡车的数量=一个班次工作时间总时间Step6:车流分配：若规模大，采用计算机模拟。若规模小，则运用自适应原则，人为排车。五、模型的求解（1）按原则一建立模型::::minminminmin∑∑105154ijijijdxS.TS.TS.TS.Taxijij≤∑=311547axijij'54154≤∑=bxjiij≥∑=101154305.0154154101101≤∑∑==iijiiijxcx285.0154154101101≥∑∑==iijiiijxcx480551≤∑=jijx4803101≤∑=iijx首先，将50个变量按照模型的方法全部输入，在Lindo软件中求解，得：从表格中的结果很明显可以看出，5和6的铲位是根本不需要的，而简单计算一下各个铲位的输出量，我们就可以将8舍弃，因为需要8号铲位的产品的数量和其他相比，实在是太少了，所以，通过如上线性规划，我们很容易的判断出需要选取哪些铲位，而X110X430X1050X120X440X510X130X450X520X140X710X530X1581X720X540X210X7332X550X2237X740X616X2331X750X620X240X9172X630X250X920X640X310X930X650X320X9412X810X330X950X820X340X1010X8311X3543X1020X840X410X10311X850X4248X104738铲位的确立，为我们求解问题带来了极大的方便