露天矿生产的车辆安排模型.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的最小整数四 问题的分析及模型的建立问题1分析本问题要求建立在卡车不等待条件下满足产量和品位需求的一个班次生产计划，使总运量最小，同时出动最少的卡车的数学模型。该问题可以归结为一个带约束的组合优化问题。由于当总运量越小，卡车的工作量也越小，从而需要的卡车也越少（当不考虑卡车空驶的时间时）。因此，我们首先确定使总运力（公里吨）最小的各线路运输流量方案，再安排卡车。由于卡车都满载运输，且其载重量相等，因此将决策变量从铲位i运往卸点j 的矿石或岩石量xij的单位视为车皮，xij为非负整数。为书写方便，我们以10个铲位，5个卸点为例来分析该问题的目标函数和约束条件。实例改变，数字随之变化。目标函数：总运力 约束条件：1 卡车不等待应满足的约束（1） 各铲位的装车能力约束一辆车的平均装车时间为5分钟，则一个班次（8小时）最多能装860/5=96趟车，要车辆在铲位不等待，则（2） 各卸点的卸货能力约束一辆车的平均卸货时间为3分钟，则一个班次（8小时）最多能卸860/3=160趟车，要车辆在卸点不等待，则（3） 各运输线路的运输能力约束 当车辆在一条线路上来回不停地行驶时，由于路线的长度有限，为使车辆在装卸点不等待，则两车之间的时间间隔至少是5，因此同时在一条线上的车辆数不超过(2dij/v60+3+5)/5,因此，一个班次一条线上的车次数应满足2 供需约束（1）铲位的限矿量从铲位i运往各矿石卸点的矿石总量不能超过该点能提供的限量，即有 （2）铲点的限岩量从铲位i运往各岩石卸点的岩石总量不能超过该点能提供的限量，即有 （3）各卸点的产量需求从各铲位运往矿石或岩石卸点j的总量应满足该点的需求，即有 3 品位约束 （可化为线性约束）4 车辆数约束（1） 每辆车在一个班次能行驶的总路程为8v, 又因只能提供20辆卡车，因此（2） 只能提供7辆铲车，因此问题1的模型S.t -各铲位的装车能力约束 -各卸点的卸货能力约束 -各运输线路的运输能力约束 -铲位的限矿量 -铲点的限岩量 -各卸点的产量需求 （可化为线性约束）-品位限制 -卡车数约束- 铲车数约束问题一的求解方法一：上述模型是一个组合优化模型，且除铲车数约束外，其余约束和目标函数均为线性，可用分支定界法，割平面法等求解。但这些方法均不是有效算法，我们设计了一种快速的启发式算法来解决该问题。该算法步骤描述如下。各线路车次安排的贪婪算法：1）输入各卸点到各铲位的距离矩阵D=；2）求矩阵D各行中最小元素与次小元素的差, 以及各列中最小元素与次小元素的差, 计算罚数；3）对矩阵D每一行的最小元素，按其对应罚数由大到小顺序排列，并依次安排这些元素对应线路上的运输，安排的运输车次以产量，需求量，线路运输能力，装卸点的装卸能力为限，若品位小于品位下限，则优先安排铁含量较高的铲位，反之，若品位大于品位上限，则优先安排铁含量较低的铲位，保证满足品位要求；4）若全部卸点都达到需求，则停止，否则，转下一步；5）将达到需求量的卸点对应的行和产量运完的铲地对应的列删去，并将已饱和的线路对应的元素置为无穷大，得到矩阵D1, 用D1替换D,，返回2）我们给出该方法对模型进行求解的结果：各线路车次安排的贪婪算法的解下表给出了我们对各线路上车次的安排：表一铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏4929倒装场5332倒装场1570岩场5926岩石漏8143设前面算得的车次值为，对应路线一辆车8小时最多运输的次数为则卡车数ceil(13.0839)14辆总运量0.01548.3836(万吨公里)确定卡车具体的分配情况：利用求得的各条线路上的车次值和对应路线一辆车8小时最多运输的次数为，确定卡车在一个班次的运营计划。一笔画分配方法1） 为线路ij分配floor(xij/yij)辆车；2） 对于不能运完的线路，以它们为顶点，当且仅当两运输线路有一个端点相同时，便在它们相对应的顶点之间连一条边，得到一个线图G。对于G中同一条路径上的顶点对应的运输线路可安排同一辆车。3） 求图G的路径，从路径起点开始分配一辆卡车给对应路线，由于 ，把剩余次数转换为时间，再分配路径上相继顶点对应的运输路线为该卡车，直到该辆车时间用完（工作8小时）或所有点被分配完。例如，第1）步可得下表的结果表二铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏3,4(18)倒装场2（39）倒装场7(47)岩场6(38)岩石漏1（44）5(35)第2）步对剩余的部分进行安排，由下表箭头所示顺序（一笔画）分配：表三铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏13(18)29(44)倒装场14(39)32（37）倒装场15(19)23(47)岩场21(38)26(45)岩石漏37(44)8(35)易知，分配顺序和方案并不唯一，原则上只要尽量满足一笔画完。转角应为直角，即卡车只能以卸点和铲点为窗口转换其运输路线。 全部分配结果如下：（数字为卡车编号，括号内数字为其对应的运输次数）表四铲位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)附：对应路线运输一次所花费的时间（单位：分）表五铲位1铲位2铲位3铲位4铲位9铲位10矿石漏30.542930.242926.042925.142910.742913.4429倒装场16.142912.242916.142912.842921.242923.0429倒装场33.242932.042932.042927.542912.542910.4429岩场10.742915.542913.442915.842929.642934.1429岩石漏26.942924.542923.942921.542913.442910.1429问题一的求解方法二：转化为整数线性规划进行求解在我们建立的组合优化模型中，除铲车数约束外，其余均为或可化为线性的，因此，先去掉铲车数约束，和整数约束，用lindo6.1求解。（源程序参看附录A）得到一组非整数解：表六铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0130000054.833336010.166666倒装场040.833336044.166664000000岩场000000007015岩石漏810430000000倒装场014.166666000000070.833336对应的整数解为： 表七铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0130000052013倒装场040045000000岩场000000007015岩石漏810430000000倒装场015000020068由于没有限制铲车数，这组解并不符合要求，将铲位7预先去掉，再次计算：表八铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0130000054011倒装场042043000000岩场000000007015岩石漏810430000000倒装场013200000070得一近似解，其总运量为：0.01548.5629(万吨公里)从求解的结果可以看出，使用贪婪算法得到的结果比转化为整数规划求近似解要优，而且还更快。问题二分析相对于问题一来说, 问题二的目标函数变成产量最大, 岩石产量优先，在产量相同的情况下，使总运量最小。描述该问题可分为两步，第一步，建立产量最大, 岩石产量优先，满足与问题一相同的限制条件的组合优化模型。第二步，将第一步得到的最大产量作为已知，再来安排运输。问题二模型 S.t -各铲位的装车能力约束 -各卸点的卸货能力约束 -各运输线路的运输能力约束 -铲位的限矿量 -铲点的限岩量 -各卸点的产量需求 （可化为线性约束）-品位限制 -卡车数约束- 铲车数约束问题二求解:Lindo求解：与第一问的Lindo解类似，不考虑非线性约束，得总产量的一个上界：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏11859倒装场1424770岩场8773岩石漏812257倒装场2521472423其运输总吨数的一个上界为0.015410.7492(万吨)程序参见附录B根据第一题的结果，去掉铲位5，6，7再次计算，得：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏126447倒装场68166862岩场9128750岩石漏81283219倒装场142234046又得其运输总吨数的一个上界为0.015410.3488(万吨)程序参见附录C下面求优化解：以第一问数据为基础：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10需求矿石漏0.75460.44661.2倒装场0.81620.49281.3倒装场0.2311.0781.3矿石量0.951.051.001.051.101.251.051.301.351.25岩场0.90860.40041.3岩石漏1.24740.66221.9岩石量1.251.101.351.051.151.351.051.151.351.25在对应的矿石量，岩石量和吞吐量中扣除已安排的运量：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10吞吐量矿石漏1.2628倒装场1.155倒装场1.155矿石量0.951.050.24540.55721.101.251.051.300.90340.172岩场1.155岩石漏0.5544岩石量1.251.100.68781.051.151.351.051.150.44140.8496吞吐量0.2310.43120.06160.98561.47841.47841.47841.47840.12321.4784由于已经安排了6辆铲车，最多还能安排一辆，所以在剩下的5，6，7，8铲位里每次取一个，分别计算：(程序参见附录E)选铲位8：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10吞吐量矿石漏0040000120082倒装场15000000150075岩场00042000330075岩石漏0000000360036倒装场000000000075矿石量6101536718168845811岩石量0714468748768742855吞吐量15284649696969680总产量为：（457154）*154=94556（吨）总运量：16.8715（万吨公里）岩石产量：37730（吨）选铲位7：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10吞吐量矿石漏040400000082倒装场000000000075岩场00043032000075岩石漏0000036000036倒装场1500005000075矿石量6101536718168845811岩石量0714468748768742855吞吐量15284649696969680总产量为：（457139）*154=91784（吨）总运量：17.1522（万吨公里）岩石产量：40810（吨）选铲位6：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10吞吐量矿石漏1505000000082倒装场000000000075岩场0000075000075岩石漏0003600000036倒装场004400000075矿石量6101536718168845811岩石量0714468748768742855吞吐量15284649696969680总产量为：（457139）*154=91784（吨）总运量： 16.2823（万吨公里）岩石产量：38962（吨）选铲位5：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10吞吐量矿石漏0040120000082倒装场15000150000075岩场00042330000075岩石漏0000360000036倒装场000000000075矿石量6101536718168845811岩石量0714468748768742855吞吐量15284649696969680总产量为：（457157）*154=94556（吨） 总运量：16.8779（万吨公里）岩石产量：37730（吨）可见选铲位5和8解最优，考虑到总运量最小，则因选铲位8最终解为：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0053012000290倒装场15530321500000岩场00042330005926岩石漏8104303600000倒装场015000000070总产量为：（457154）*154=94556（吨）总运量：16.8