王汉湘-露天矿生产的车辆安排(全国二等奖)

1露天矿生产的车辆安排摘要本文解决了一个露天矿生产的车辆安排问题。对于原文中的两个问题，我们通过分析，分别建立了两个多目标整数规划模型。由于原问题的约束条件很繁杂，经过适当的简化，我们把模型的求解分为两个步骤，先不考虑卡车不能等待这一原则，我们提出搜索算法和逐步迭代逼近算法，利用数学工具软件Lindo，分别得到模型一和模型二的解；然后考虑卡车不能等待的原则，针对本题的特殊情况，我们提出了卡车编队运输和卡车转移运输的理念，很好地解决了这一问题，再通过计算，得到满足基本产量的最小运量为86361.66吨公里，出动电铲数为7台，卡车数为13辆；利用现有条件运输获得的最大产量为103642吨，出动电铲数为7台，卡车数为17辆。随后，我们针对两问题，分别给出了生产计划和车辆安排。最后，我们针对本文这一特定问题，给出了适于现场计算的快速算法，用此算法得到的结果和精确解非常贴合，说明此算法可行。本文的最大特色是我们提出了卡车编队运输和卡车转移运输的理念，使本文中最复杂的约束条件变为简单，这使本来极为难解的整数规划问题大大简化，降低了求解难度，但并未降低求解精度。我们给出的快速算法精度很高，非常适合现场计算。2一、问题的提出某露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石(平均铁含量不低于25%的为矿石，否则为岩石)。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。所用卡车载重量为154吨，平均时速28hkm。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量相当可观，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽60m的双向车道，不会出现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。在卡车不等待条件下满足产量和质量（品位）要求，并就以下两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。原则1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；原则2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。有关数据见附录1。试给出具体的生产计划、相应的总运量及岩石和矿石产量。3二、问题的假设1、露天矿里有m堆石料堆，每堆称一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石(平均铁含量不低于25%的为矿石，否则为岩石)；2、每个铲位的矿石数量，岩石数量，矿石的平均铁含量都已确定；3、每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟，电铲数有限，为简化问题计，电铲在一个班次内不能移动；4、卸点有n个，其中矿石卸点为k个，每个卸点的产量要求为Q；5、矿石卸点的铁含量要求为29.5%+1%，送到卸点的矿石搭配的量在一个班次内（8小时）满足要求即可；6、卸点在一个班次内不能移动；7、卡车载重量均为154吨，记为G，平均时速为28km/h，记为v，卡车的平均卸车时间为3分钟；8、卡车在一个班次中只在开始工作时点火一次，且原则上在安排时不发生卡车等待的情况；9、铲位和卸点都不能同时为两辆及两辆以上卡车服务；10、运输过程中不会出现堵车现象，卡车每次都是满载运输，卡车运输路线可以转移。三、符号说明iP1------------------------i号铲位的矿石数量；i=1,2,3,…,miP2------------------------i号铲位的岩石数量；i=1,2,3,…,mjQ------------------------j号卸点一个班次内对产量的要求；j=1,2,…,niF------------------------一个控制参数，若N=1，则i号铲位安排铲车，若N=0，则i号铲位不安排铲车；i=1,2,3,…,mijx------------------------i号铲点到j号卸点卡车运输的次数；i=1,2,3,…,m；j=1,2,…,nG-----------------------卡车载重量；ijs------------------------i号铲点到j号卸点之间的路程；i=1,2,…,m；j=1,2,…,nic------------------------i号铲点的矿石的平均含铁量；i=1,2,…,mbacc,------------------卸点对铁含量限制的最小值和最大值；N-----------------------安排的车数；E------------------------一个无穷大的数；四、问题的分析原问题要求考虑的两条原则皆有多个目标，且在考虑这两条原则的同时不能发生卡车等待的情况。为使我们求解的问题不致太复杂，我们分两步来考虑原问题：先不考虑卡车会不会发生等待，先分别满足原问题提出的两条原则，得到在彼种情况下的最优解。然后，在此基础上，我们再来满足卡车不能等待的原则，并以此原则制订出车辆的安排情况，这可能会使先已解出的最优解发生变化，我们再增加约束条件从可能发生的变化中求出最优解。由于排时计划无效，我们不具体安排车辆的运输情况，只考虑一车辆从一运输线路转移到另一运输线路后会不会和另一运输线路上已有的车辆发生等待的情况，如不发生等待，则认为方案可行；如发生等待，则此车辆或转移到其它线路上运输或停止运输。4通过以上的分析，我们将原本很复杂的问题简化为一个多目标规划并逐步逼近最优的数学问题。五、模型一的建立根据以上符号的约定和对问题的假设，得到求总运量（吨公里）最小，同时出动卡车最少，从而使运输成本最小的数学模型：目标：MinminjijijsxGz111MinNz2s.t.107);,,2,1;,,2,1(0),,2,1(960),,2,1(),,2,1(),,2,1(1211121111imiiijiijmiiijjnjijinkjijikjijjmiijFFxnjmiEFxnjccGxcQxmiPGxmiPGxnjQGx为整数约束条件六、模型一的求解我们现将模型的求解分为如下几个部分：a）准备工作；b）求1z的最优值；c）安排各线路上的运输车辆，并综合考虑1z的优化得出最终解；a）准备工作；1、求各采点分别到各卸站的运输时间。由于我们问题的特殊性，我们把此运输时间定义为卡车从采点装货（需5分钟）后出发到达卸点卸货（需3分钟）并返回采点所需要的时间。结果见下表：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏30.5430.2426.0425.1420.6419.7418.5416.1410.7413.44倒装场I16.1412.2416.1412.8413.4417.6414.3416.7421.2423.04岩场33.2432.0432.0427.5423.0423.6418.5418.5412.5410.44岩石漏10.7415.5413.4415.8419.7419.1426.0423.9429.6434.145倒装场II26.9424.5423.9421.5417.6420.0411.3414.9413.4410.142、各铲位到卸点间各条运输线路上能容纳的最大车辆数。此最大车辆数为各单线路上能容纳的最大车辆数，即不考虑彼线路上的铲位和其它卸点之间的线路上的车辆对它的影响。结果见下表：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏6655433322倒装场I3232232344岩场6665443322岩石漏2323335456倒装场II54443422223、7台电铲在10个采点中的所有可能的分布（程序见附录程序1）。由集合U表示，每一个横向量u代表一种分布。由于数据量太大，计算结果略，示例如下：例：01100010111表示该号采点安排有电铲，0表示该号采点未安排电铲示例表示2、3、7、9、10号采点安排有电铲。1、4、5、6、7、8号采点未安排电铲。b）求1z的最优值；由于原题目的变量太多，约束条件繁杂，故我们采用搜索算法和逐步迭代逼近法来求解。具体算法如下：STEP1：在集合U中选取向量0u作为电铲分布初始值，解得模型一中1z的结果01z；STEP2：在集合U中，搜索0u周围的点得1u，并解得1z的值11z，；STEP3：判断11z和01z的大小，如果，11z＞01z，转STEP2；否则，令0u＝1u，转STEP1；STEP4：集合U搜索完毕，跳出，并输出结果；我们先给出1、2、3、4、8、9、10号采点为初始铲点，运用数学工具软件（程序见附录程序2）lindo，解得模型一中的目标1z的解：最小总运量为：80982.44吨公里。以以上结果为初始值，通过以上算法，最终我们得到1z的最优解：出动7台电铲，电铲分布在1、2、3、4、8、9、10号铲位上；最小运量为：80982.44吨公里；c）安排各线路上的运输车辆，并综合考虑1z的优化得出最终解由于受到电铲装卸时间的限制，每个铲位能够提供的运量也就有限。应不能发生卡车等待的情况，故每个铲位能够容纳的卡车数也就有限。针对卡车不能等待这一情况，我们提出卡车排队运输和卡车转移运输的理念。具体思路即是让卡车排队在同一条线路上运输（卡车数满足最大容车量的限制），这样能保证前一辆车和后一辆车始终间隔5分钟，这样便不会发生卡车等待的情况。要使安排的卡车数最少，我们又提出卡车转移运输的概念，即一队卡车在保证运完自己线路上的运量还有富裕时间，可以转移到其它线路上运输，我们只需考虑转移到另一条线路上后会不会和那条线路上已有的卡车发生等待（详细分析见问题的分析）。6算法：STEP1：计算每条线路上卡车的工作时（运输次数和每次运输所需时间之积）；STEP2：计算每个铲位所对应的线路上卡车工作时的总和，并计算每个铲位所需的最少卡车数，可以是小数；STEP3：判断：如果每个铲位所需的最少卡车数和该铲位能容纳的最大卡车数不冲突，则顺序执行STEP4；如果每个铲位所需的最少卡车数和该铲位能容纳的最大卡车数相冲突，则应以能容纳的最大卡车数为原则增加模型一的约束条件，重新按b到c的步骤进行求解；STEP4：运用卡车排队运输和卡车转移运输的理念，先给每个铲位排整数辆车，剩余的工作时应综合考虑，运用卡车排队运输和卡车转移运输的理念，先给每个铲位排整数辆车，剩余的工作时综合考虑，尽量让每辆卡车运满整个班次。通过以上算法，我们发现安排的卡车数和已求出的模型一的1z的解有冲突，主要是因为10号铲位最多能容纳2辆卡车，而已求出的模型一解中10号铲位对卡车的需求量超过了2辆，故应对模型一增加一个约束条件：960*14.10*44.13*44.10102103104xxx然后再重复b到c的求解步骤，得到模型一的最终解答（卡车安排服从卡车排队运输和卡车转移运输的理念）：出动7台电铲，电铲分布在1、2、3、4、