露天矿生产运输车辆安排

1、露天矿生产车辆运输安排摘 要对于本文所涉及的问题，首先根据题意，分析出其不同于常见的运输问题，按照原题对两个原则的划分，分别建立模型，再在此基础上，将每个原则分为两步解决：第一步：找到最佳物流结果；第二步：对各条线路车辆进行合理安排。针对原则一，首先将其划分为两步，明确其第一步为运输规划问题，建立总运量最小的目标函数，列写约束条件，求解出卡车运输次数（见表2）、总运量以及岩石量和矿石量。第二步为组合优化问题，设计出贪心算法，得到最终对卡车的运输安排表（见表3）。遵循原则一的情况下需要至少出动13辆卡车，其中7辆固定在线路上运输，最小总运量是80820.74吨公里。岩石量38192吨，矿石量32

2、186吨。针对原则二，同样按照问题分析中所述，分为与原则一相同的两步解决，根据第一步的模型计算得到遵循原则二的卡车运输次数（见表4）以及总运量、岩石量、矿石量等。再通过第二步得到最终遵循原则二的卡车运输安排表（见表5）。遵循原则二的情况下需要出动20辆卡车，其中14辆固定在线路上运输，最小总运量是134181.7吨公里，岩石量61292吨，矿石量42504吨。关键字：多目标规划，组合优化，NPC问题，贪心算法，非线性规划一. 问题重述钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车

3、）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限

4、制即可。一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一： 1. 总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；2. 利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及

5、岩石和矿石产量。某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场1.3万吨、倒装场1.3万吨、岩石漏1.9万吨、岩场1.3万吨。二. 模型假设1. 假设铲位同时开工；2. 每个班次为8小时；3. 每个班次内机器全部能够正常工作，不出现故障；4. 卡车在点火前的等待不算等待；5. 卡车空载和满载速度相同，但是耗油量不同；6. 卡车在运输途中流畅行驶，不出现停车等待等现象；7. 在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就算作不冲突；8. 卡车不允许从一个卸点到另一个卸点。三. 符号说明符号说明第个铲

6、位是否安置电铲第个铲位到第个卸点的卡车运输矿石的次数第个铲位到第个卸点的卡车运输岩石的次数第个卸点的产量要求从第个铲位到第个卸点的距离第个铲位的矿石量第个铲位的岩石量第个铲位的矿石的平均含铁量从第个铲位到第个卸点往返一次的时间（包括装车时间和卸车时间）第个卸点的总量第个卸点的铁含量从第个铲位到第个卸点的路线上最多允许的卡车数从第个铲位到第个卸点的一个班次所允许的最大运输次数第一类卡车从第个铲位到第个卸点的数量四. 问题分析钢铁工业是一个国家工业的基础，因而铁矿开采所涉及的问题自然成为其核心问题。在铁矿开采过程中，我们考虑使得在尽量多地开采铁矿石的前提下，也要使得成本相对较少。为使开采矿石多，需

7、要考虑安排比较多的电铲装车、比较多的卡车运输、设备比较高的利用率以及方便捷径的运输路线。为使成本较少，需要考虑减少电铲和卡车、提高设备利用率、安排捷径的运输线路。综上所述，我们需要安排合理数量的电铲和卡车以及合理捷径的运输路线，在原则一和原则二的要求下，分别做出相应的合理安排。本题属于运输问题，但是它又区别于典型的运输问题，其不同点表现在如下几个方面：1. 本题属于运输岩石和矿石两种原料的运输问题；2. 属于产量与销量不等的不平衡运输问题；3. 产销地都有单位流量的限制；4. 为了满足品位约束，矿石需要搭配运输；5. 铲位数多于电铲数，也即是说，需要在所有10个铲位选择最优的7个作为产地；6.

8、 运输车辆只有一种，而且必须满载运输，如果不能满载运输就不运输；7. 运输车辆可以往返于多个铲位和多个卸点之间；8. 本题不仅需要找出最佳运输方案，还需要对各条运输线路上的车辆进行统筹安排。每一个运输问题其本质属于规划问题。虽然对于找到最佳物流方案并不难，但是本题需要对各条线路上的车辆进行统筹安排，而这是一个组合优化问题，对于这样的问题不能使用规划问题的方法解决。为了便于表述和计算，我们将原题中铲位用表示(，卸点用表示(分别表示矿石漏、倒装场、倒装场，分别表示岩场、岩石漏。所以我们对本题原则一和原则二都分为两步规划。其中第一步，建立规划模型，找到最佳物流结果；第二步，设计优化算法，对各条线路车

9、辆进行合理安排。五. 原则一的模型5.1 模型分析针对按照原则一寻找的最终方案，我们发现按照问题分析中所述，可以将其分为两步，首先建立类似于常规运输问题的规划模型，对于原则一，需要遵循总运量最小并且出动最少的卡车，这看起来似乎是一个多目标问题，但是实际上对于需要出动多少卡车这一问题，并不能将其作为目标值求解出来，因为只能算出在每条线路上有多少卡车在运输，但是根据之前的分析，这些卡车可以在多条线路上运输。所以最终出动的卡车数是根据找到的最小总运量来决定的。那么，这一问题就转化为单目标规划问题，其目标是使得总运量最小。然后再设计优化算法安排合理线路，对于组合优化问题，不能使用规划问题的方法解决，原

10、题中要求设计快速算法，而对于按原则一解决的非线性规划而言，我们自己设计了一种相对较为快速的优化算法。5.2 模型建立第一步：规划模型在知道目标最小总运量的情况下，需要列写如下规划问题中相应的约束条件：(1 卡车最少总运次：因为各个卸点一个班次的产量是已知的，而卡车每次每车运量是一定的,所以一定存在卡车最少运送次数，即卡车至少要运送这么多次才能满足卸点的全部产量，我们称之为卡车最少运次。其值为： (1其中表示高斯取整。(2 每条线路一辆卡车最多运次：因为每一班次的卡车从铲位到卸点往返一次需要时间，那么每一班次一辆卡车允许的最大运输次数即每条线路一辆卡车最多运次： (2其中。(3 每条线路卡车最大

11、数量：因为运输过程中不存在等待现象，所以其最大卡车数量满足： (3其中表示高斯取整。(4 电铲能力约束：因为电铲每次只能为一辆卡车装车，若电铲不停歇地工作，则一个班次最多装车数，称之为电铲能力约束。其值为： (4(5 电铲数量约束：因为电铲能力约束为96次，于是一个铲位的最大运输量为96154=14784吨/车，又由于卡车最少总运次为457次，所以至少需要安置的电铲个数 (5其中表示高斯取整。又根据题意最多有7个铲车。那么综上电铲数量满足： (6将这一范围称之为电铲数量约束。(6 卡车数量约束：根据式(1(2，显然知道如下关系成立： (7所以可以计算其值为： (8其中表示高斯取整，表示中的最小

12、值。又由于题意中已知，卡车最多20辆，所以卡车数量介于1020之间，称之为卡车数量约束。(7 矿石量约束：各卸点总矿石量不能大于所有铲位总矿石量，即 (9(8 岩石量约束：各卸点总岩石量不能大于所有铲位总岩石量，也即 (10(9 卸点产量约束：运输的产量不能小于各卸点的产量要求，即卸点用来卸矿石时： (11卸点用来卸岩石时： (12(10 品位限制约束：各个卸点运输的铁含量满足题目给定的品位限制，也即由于品位满足 (13根据原题中已知，有不等式 (14将这一约束条件称之为品位限制约束。于是，综上目标函数和所有约束条件，得到规划模型如下： (15第二步：组合优化模型针对需要安排各条线路的车辆搭配

13、运输情况，通过分析可以发现，这是一个组合优化问题，也是一个NPC问题，对于问题中要求的快速算法，如果将其作为整数规划解决，势必其运算复杂程度是难于让人接受的。所以我们采用贪心算法这种较为简便的算法来解决这一组合优化模型1。算法分析将求得的和相加得到总的运次矩阵，将该矩阵与相对应的一个班次内的最大运输次数矩阵比较，我们发现可以将每一条线路上的卡车分为两类，一类只在该条线路上运输，另一类也在其它的线路上运输。我们将其作如下定义：第一类卡车：只在一条线路上运输的卡车。第二类卡车：在多条线路上运输的卡车。下面对这两类卡车分别进行安排。通过计算 (16根据其最终的值来判定这条线路上有多少第一类卡车。并由

14、此容易得到第二类卡车需要满足的运次矩阵 (17为了计算方便，我们将中的元素与对应的运输时间相乘再除以一个班次内总的时间，即得到该条线路上需要耗费的时间占一个工作班次的比例。以下是考虑第二类卡车的算法思想：先满足最耗时的线路的运输需求，再满足耗时量次之的线路，当一辆卡车的工作时间不能再满足运输要求时考虑再派出另一辆卡车，直到所有的运输要求都被满足。算法设计*具体算法如下：Step1：初始化第二种卡车数量；Step2：找到该矩阵中的最大元素，=该元素值，该元素值=0；Step3：找到次大元素，=次大元素值，Step4：若，转到Step5；若，转到Step3；Step5：重新从Step2开始，直至所

15、有元素都为零；Step6：得到第二种卡车的数量，同时得到每辆车所走的路线。5.4 模型求解为了便于计算，我们进一步分析题意，可以先考虑卸点，找出与每个卸点距离最近的铲位，再考虑铲位，找出与每个铲位距离最近的卸点，结果见表1：表 1 铲位与卸点的距离铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏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岩场5.895.615.614.

16、563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10从表1中数据可以而发现，,在行列上都是最小值，则铲位1，2，9，10是比较优越的铲位，所以首先确定在铲位1，2，9，10放置电铲。根据对上述规划模型运用lingo求解得到以下结果。计算得到最小总运量是80820.74吨公里。岩石量38192吨，矿石量32186吨pspan铲车放置在铲位 1 、 2 、 3 、 4 、 8 、 9 、 10 ，卡车运输次数结果如下表：p 表 2 原则一的 卡车运输次数 铲位1铲位2铲位3铲位4铲位8铲位9铲位10矿石漏0130

17、054011倒装场042043000倒装场013200070岩场00000580岩石漏800440000第二步结果于是通过计算可以得到固定在一条线路上的卡车有7辆。运用matlab对组合优化模型编程求解可得卡车运输安排表：表 3 原则一的卡车运输安排表铲位1铲位2铲位3铲位4铲位8铲位9铲位10矿石漏8(2 10(5 12(61(29 8(2512(11倒装场2(39 13(33(37 12(2 13(4倒装场10(1313(24(47 11(20 13(3岩场13(55(45 9(9 11(26岩石漏6(44 9(367(35 12(9表中括号外的数字表示车号，括号中的数字表示运输次数。所以

18、对于按照原则一安排，出动13辆卡车，最小总运量是80820.74吨公里，岩石量38192吨，矿石量32186吨。六. 原则二的模型6.1 模型分析每一个运输问题其本质属于规划问题2。对于按照原则二寻找最终方案而言，其实质是一个多目标规划问题。解决多目标规划问题常常采用配权值、图解法、分层规划等方法。对于本题由于数据量不大，所以难于找到权值，自然如果本题使用配权值、图解等方法，会使得最终结果误差比较大，所以我们使用分层规划的方法。对于满足原则二的规划模型时，其约束条件与满足原则一时的一样，不同的是目标函数。与满足原则一时一样，满足原则二时也是多目标规划，但不同的是满足原则一时其实质只是一个单目标

19、问题，但是满足原则二时其实质是一个主次分明的多目标问题。我们同时需要在优先考虑岩石产量的情况下兼顾考虑主要目标总产量，在产量相同时选取总运量最小的方案。由于运用分层规划的方法，所以我们采用层层推进的思路：1. 约束条件与按原则一求解的约束条件一样，只考虑岩石产量，将岩石产量作为唯一目标函数，求最大值,记为max1。2. 之前的约束条件不变，将总产量作为目标函数，并将最大岩石产量max1作为约束条件，求目标函数的最大值，记为max。3. 将max1和max同时做为约束条件，求次要目标总运量并使之最小。而在之后的组合优化过程同样可一采用原则一中的贪心算法的思路减小搜索范围，加快运行速度，得到最优运

20、输方案。6.2 模型建立第一步：多目标规划按照原则二的要求所建立的规划模型，其约束条件与原则一时一样，只是目标函数发生了变化，其模型如下（约束条件同原则一时省略）目标1：最大岩石产量，其模型为： (18目标2：最大总产量，其模型为： (19目标3：最小总运量，其模型为： (20第二步：组合优化对于原则二的第二步，其思想和具体算法与原则一完全一致，不同点仅仅是此时的一些数据发生了相应的变化。所以可以根据原则一第二步对解决组合优化问题的算法建立相应的模型。6.3 模型求解通过与原则一类似的方法，计算得到最小总运量是134181.7吨公里。岩石量61292吨，矿石量42504吨。铲车放置在铲位1、2

21、、3、4、8、9、10，卡车运输次数结果如下表：表 4 原则二的卡车运输次数铲位1铲位2铲位3铲位4铲位8铲位9铲位10矿石漏0140029035倒装场2938037000倒装场0160032046岩场000007681岩石漏81607030000计算可以得到第一类卡车有14辆，得卡车运输安排表：表 5 原则二的卡车运输安排表铲位1铲位2铲位3铲位4铲位8铲位9铲位10矿石漏17(219(121(292(35倒装场3(2915(116(374(37倒装场18(165(3215(46岩场6(387(388(4518(819(1120(17岩石漏9(4417(3710(3011(3012(3513(3514(30表中括号外的数字表示车号，括号中的数字表示运输次数。所以对于按照原则一安排，出动20辆卡车，最小总运量是134181.7吨公里，岩石量61292吨，矿石量42504吨。七. 模型改进考虑运输线路在一定时期内是相对固定的，那么可以在本问求解基础上，对运输卡车进行更加详细而固定的安排，作出类似于火车站时刻表之类的卡车运输时刻表，以使安排的结果对于完成运输任务而言更加高效。本文在安排