露天矿生产的车辆安排模型..doc

B题 露天矿生产的车辆安排 摘要: 本问题要求对露天矿的矿石和岩石的运输进行优化安排，该问题可归结为一个带约束的组合优化问题，是NP难题。首先，我们建立在卡车不等待条件下满足产量和品位需求的一个班次生产计划，使总运量最小，同时出动最少的卡车的数学模型。并设计了求各条线路优化车次的快速启发式算法，贪婪算法，并用该算法进行求解得到如下结果：分别在铲位1、2、3、4、9、10出动6辆铲车并出动14辆卡车按下表方案进行运输，其总运量为8.3836万吨公里。我们还将建立的优化模型，转化为多个整数线性规划问题，利用lindo和matlab等数学工具进行了求解，其结果没有贪婪算法优，也没有贪婪算法快。根据得到的车次来推算下表的各条路线上所需卡车数及安排的时候，我们创造性的使用了自己发明的“一笔画”方法使问题的复杂度大大的得到了降低。 （数字为卡车编号，括号内数字为其对应的运输次数） 铲位1 铲位2 铲位3 铲位4 铲位9 铲位10 矿石漏 3(18)，4(18)9(13) 9(29) 倒装场Ⅰ 2（39）,13（14） 13(23)14(9) 倒装场Ⅱ 12 (15) 7(47)，11(22)12(1) 岩场 6 (38)，9 (5)10(16) 10(19), 11(7) 岩石漏 1（44）， 8(37) 5(35)，8(7)9(1) 对于题目要求的第二个原则，我们建立了一个两步模型，第一步，产量最大, 岩石产量优先。第二步，将第一步得到的最大产量作为已知，再来安排运输，使总运量最小。 我们也设计了相应的快速算法，求得最大产量为9.4556万吨。 关键字： 混合约束 线性规划 露天矿开采 贪婪算法 一 问题的重述 许多现代化铁矿通常采用露天开采的形式，它的生产主要是由电动铲车装车、电动轮自卸卡车运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。 卸货地点有卸矿石的矿石漏、2个铁路倒装场和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。 所用卡车载重量为154吨，平均时速28。卡车的耗油量很大，故一个班次中只在开始工作时点火一次。原则上在安排时不应发生卡车等待的情况。 一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一： 1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小； 2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。 本题要求根据这两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。 二 模型的假设 1、 在一个班次内，卸点不可以移动。 2、 电铲和卸点都不能同时为两辆及两辆以上卡车服务。 3、 在一个班次中卡车只在开始工作时点火一次，在运输过程中原则上不应发生等待， 4、 在每个铲位到每个卸点的途中，不会出现堵车现象。 5、 每个铲位至多能安置一台电铲。 6、 卡车每次都是满载运输。 三 符号说明 ：决策变量，从铲位到卸点所需的运输车次， ：铲位 到卸点的距离， ： 铲位的矿石数量， ： 铲位的岩石数量 ： 卸位的产量需求。，倒装场Ⅰ，倒装场Ⅱ，即3个卸矿点；岩石漏和岩场，即两个卸岩点 : 铲位的铁含量， ：品位下限，为28.5% ：品位上限，为30.5% 卡车平均时速，为28 ： 表示的符号函数，即 floor(x): 表示x的整数部分 ceil(x)： 表示大于或等于x的最小整数 四i运往卸点j 的矿石或岩石量xij的单位视为车皮，xij为非负整数。为书写方便，我们以10个铲位，5个卸点为例来分析该问题的目标函数和约束条件。实例改变，数字随之变化。 目标函数：总运力 约束条件： 卡车不等待应满足的约束 各铲位的装车能力约束 一辆车的平均装车时间为5分钟，则一个班次（8小时）最多能装8(60/5=96趟车，要车辆在铲位不等待，则 各卸点的卸货能力约束 一辆车的平均卸货时间为3分钟，则一个班次（8小时）最多能卸8(60/3=160趟车，要车辆在卸点不等待，则 各运输线路的运输能力约