露天矿生产的车辆安排B

1、露天矿生产的车辆安排露天矿生产的车辆安排 2002年年A（C）题）题露天矿生产的车辆安排露天矿生产的车辆安排-问题陈述问题陈述装卸点平面分布图露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石: 平均铁含量不低平均铁含量不低于于25%的为矿石，否则为岩石。每个铲位的矿石、的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均是已知的。每个铲位至多安置一台电铲，电铲平均装车时间装车时间5分钟分钟矿石卸点需要的铁含量要求都为矿石卸点需要的铁含量要求都为29.5%1%(品位品位限

2、制），搭配量在一个班次（限制），搭配量在一个班次（8小时）内满足品位小时）内满足品位限制即可。卸点在一个班次内不变。平均卸车时间限制即可。卸点在一个班次内不变。平均卸车时间为为3分钟。分钟。主要因素与已知条件主要因素与已知条件:电铲和卸点都不能同时为两辆及两辆以上卡车服务。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。卡车每次都是满载运输。 卡车载重量为卡车载重量为154吨，平均时速吨，平均时速28km,卡车在等待卡车在等待时所耗费的能量也是相当可观的，原则上在安排时所耗费的能量也是相当可观的，原则上在安排时时不应发生卡车等待不应发生卡车等待的情况。的情况。 铲位铲位1

3、1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿石量矿石量0.951.051.001.051.101.251.051.301.351.25岩石量岩石量1.251.101.351.051.151.351.051.151.351.25铁含量铁含量30%28%29%32%31%33%32%31%33%31%实例数据实例数据: : 距离距离铲位铲位1 1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿石漏矿石漏5.265.194.214.

4、002.952.742.461.900.641.27倒装倒装1.900.991.901.131.272.251.482.043.093.51岩场岩场5.895.615.614.563.513.652.462.461.060.57岩石漏岩石漏0.641.761.271.832.742.604.213.725.056.10倒装倒装4.423.863.723.162.252.810.781.621.270.50有铲位有铲位10个，卸点个，卸点5个，铲车个，铲车7台，卡车台，卡车20辆。各卸辆。各卸点一个班次的产量要求：矿石漏点一个班次的产量要求：矿石漏1.2万吨、倒装场万吨、倒装场1.3万吨、倒装场

5、万吨、倒装场1.3万吨、岩石漏万吨、岩石漏1.9万吨、岩万吨、岩场场1.3万吨。万吨。 问题：问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次分别在哪些路线上各运输多少次 ? ?考虑下面两条原则之一：考虑下面两条原则之一： 1.1.总运量（吨公里）最小，同时出动最少的卡车，从总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；而运输成本最小；2.2.利用现有车辆运输，获得最大的产量（岩石产量优利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）先；在产量相同的情况下，取总运量

6、最小的解）就两条原则分别建立数学模型，并给出一个班次生产就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。计划、相应的总运量及岩石和矿石产量。 问题分析问题分析 与典型的运输问题明显有以下不同：与典型的运输问题明显有以下不同：这是运输矿石与岩石两种物资的问题；这是运输矿石与岩石两种物资的问题；属于产量大于销量的不平衡运输问题；属于产量大于销量的不平衡运输问题；为了完成品位约束，矿石要搭配运输；为了完成品位约束，矿石要搭配运输；产地、销地均有单位时间的流量限制；产地、销地均

7、有单位时间的流量限制；运输车辆只有一种，每次满载运输，运输车辆只有一种，每次满载运输，154吨吨/车次；车次；铲位数多于铲车数意味着要最优的选择不多于铲位数多于铲车数意味着要最优的选择不多于7个个产地作为最后结果中的产地；产地作为最后结果中的产地；1. 最后求出各条路线上的派出车辆数及安排。最后求出各条路线上的派出车辆数及安排。运输问题对应着线性规划，以上第运输问题对应着线性规划，以上第1、2、3、4条可条可通过变量设计、调整约束条件实现；第通过变量设计、调整约束条件实现；第5条使其变条使其变为整数线性规划；第为整数线性规划；第6条用线性模型实现的一种办条用线性模型实现的一种办法，是从法，是从

8、 个整数规划中取最优的即得到最个整数规划中取最优的即得到最佳物流；对第佳物流；对第7条由最佳物流算出各条路线上的最条由最佳物流算出各条路线上的最少派出车辆数（整数），再给出具体安排即完成全少派出车辆数（整数），再给出具体安排即完成全部计算。部计算。对于这个实际问题，要求快速算法，计算含对于这个实际问题，要求快速算法，计算含50个变个变量的整数规划比较困难。另外，这是一个二层规划量的整数规划比较困难。另外，这是一个二层规划，第二层是组合优化，如果求最优解计算量较大，第二层是组合优化，如果求最优解计算量较大，现成的各种算法都无能为力。于是问题变为找一个现成的各种算法都无能为力。于是问题变为找一个寻

9、求近优解的近似解法，寻求近优解的近似解法，例如可用启发式方法求解例如可用启发式方法求解 120710C近似处理：近似处理：先求出产位、卸点每条线路上的运输量先求出产位、卸点每条线路上的运输量(MIP模型模型)然后求出各条路线上的派出车辆数及安排然后求出各条路线上的派出车辆数及安排这是一个多目标规划，第一问的目标有两层：第一这是一个多目标规划，第一问的目标有两层：第一层是总运量（吨公里）最小，第二层是出动卡车数层是总运量（吨公里）最小，第二层是出动卡车数最少，从而实现运输成本最小。第二问的目标有：最少，从而实现运输成本最小。第二问的目标有：岩石产量最大；矿石产量最大；运量最小，三者的岩石产量最大

10、；矿石产量最大；运量最小，三者的重要性应按此序。重要性应按此序。调用调用120次整数规划可用三种方法避免：（次整数规划可用三种方法避免：（1）先不）先不考虑电铲数量约束运行整数线性规划，再对解中运考虑电铲数量约束运行整数线性规划，再对解中运量最少的几个铲位进行筛选；（量最少的几个铲位进行筛选；（2）在整数线性规划）在整数线性规划的铲车约束中调用函数来实现；（的铲车约束中调用函数来实现；（3）增加）增加10个个01变量来标志各个铲位是否有产量。变量来标志各个铲位是否有产量。模型假设模型假设 卡车在一个班次中不应发生等待或熄火后再启动卡车在一个班次中不应发生等待或熄火后再启动的情况；的情况； 在铲

11、位或卸点处由两条路线以上造成的冲突问题在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；为不冲突。我们不排时地进行讨论； 空载与重载的速度都是空载与重载的速度都是28km/h，耗油相差很大；，耗油相差很大；因此总运量只考虑重载运量因此总运量只考虑重载运量 卡车可提前退出系统，等等。卡车可提前退出系统，等等。符号符号 xij ：从：从i号铲位到号铲位到j号卸点的石料运量号卸点的石料运量 (车车) 单位：吨单位：吨 cij ：从：从i号铲位到号铲位到j号卸点的距离号卸点的距离 公里公里 Ti

12、j : 从从i号铲位到号铲位到j号卸点路线上运行一个周期平均时间号卸点路线上运行一个周期平均时间 分分 Aij ：从号铲位到号卸点最多能同时运行的卡车数：从号铲位到号卸点最多能同时运行的卡车数 辆辆 Bij ：从号铲位到号卸点路线上一辆车最多可运行的次数：从号铲位到号卸点路线上一辆车最多可运行的次数 次次 pi： i号铲位的矿石铁含量号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) % qj : j号卸点任务需求，号卸点任务需求， q=(1.2,1.3,1.3,1.9,1.3)*10000 吨吨 cki ：i号铲位的铁矿石储量号铲位的铁矿石储量 万吨万吨

13、cyi ：i号铲位的岩石储量号铲位的岩石储量 万吨万吨 fi : 描述第描述第i号铲位是否使用的号铲位是否使用的0-1变量，变量， 取取1为使用；为使用；0为关闭。为关闭。模型建立、算法设计与模型求解：模型建立、算法设计与模型求解： 问题一、求运输成本最小的生产计划问题一、求运输成本最小的生产计划一以总运量最小为目标函数求解最佳物流一以总运量最小为目标函数求解最佳物流-第第一层规划一层规划 一个电铲（卸点）不能同时为两辆卡车服务，一条一个电铲（卸点）不能同时为两辆卡车服务，一条路线上最多能同时运行的卡车数是有限制的。卡路线上最多能同时运行的卡车数是有限制的。卡车从车从i号铲位到号铲位到j号卸点

14、运行一个周期平均所需时号卸点运行一个周期平均所需时间为间为: 532平均速度距离到jiTij 道路能力约束：道路能力约束：5ijijTAijijijTAB5) 1(608(近似近似)最多能同时运行的卡车数为：最多能同时运行的卡车数为： 最后一辆卡车一个班次中在这条路线上最多可以运最后一辆卡车一个班次中在这条路线上最多可以运行的次数为行的次数为 :一个班次中这条固定路线上最多可能运行的总车次一个班次中这条固定路线上最多可能运行的总车次大约为：大约为： ijijijBAL总吨数总吨数 为为:ijL154一台电铲不能同时为两辆卡车服务，所以一台电铲一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班

15、次中的最大可能产量为在一个班次中的最大可能产量为:860/5154（吨）。（吨）。 电铲能力约束：电铲能力约束： 卸点能力约束：卸点能力约束： 卸点的最大吞吐量为每小时卸点的最大吞吐量为每小时60/3=20车次，于是一车次，于是一个卸点在一个班次中的最大可能产量为个卸点在一个班次中的最大可能产量为:820154（吨）（吨） 铲位储量约束：铲位储量约束：铲位的矿石和岩石产量都不能超过相应的储藏量。铲位的矿石和岩石产量都不能超过相应的储藏量。 产量任务约束：产量任务约束：各卸点的产量不小于该卸点的任务要求。各卸点的产量不小于该卸点的任务要求。 铁含量约束：铁含量约束：各矿石卸点的平均品位要求都在指

16、定的范围内。各矿石卸点的平均品位要求都在指定的范围内。 整数约束：整数约束：当把问题作为整数规划模型时，流量当把问题作为整数规划模型时，流量xij除以除以154为为非负整数非负整数 卡车数量约束：卡车数量约束：不超过不超过20辆。辆。 电铲数量约束：电铲数量约束：电铲数量约束无法用普通不等式表达，可以引入电铲数量约束无法用普通不等式表达，可以引入10个个01变量来标志各个铲位是否有产量。变量来标志各个铲位是否有产量。优化模型优化模型cxijijij10151min5 , 1,10, 1,jiBAxijijij10, 1, 5/60851ifxijij5 , 1,208101jiijx10, 1

17、,154/10000154/1000043521icyxxckxxxiiiiiii（1）道路能力）道路能力(卡车数卡车数)约束约束（2）电铲能力约束）电铲能力约束（3）卸点能力约束）卸点能力约束（4）铲位储量约束）铲位储量约束（5）产量任务约束）产量任务约束（6）铁含量约束）铁含量约束（7）电铲数量约束）电铲数量约束（8）整数约束）整数约束（9）车辆）车辆约束约束5 , 1,154/101jqxjiij5 , 2 , 1,0)5 .28(0)5 .30(101101jpxpxiiijiiij.7101iifxij为非负整数为非负整数fi 为为0-1整数整数20154,jiijijBx计算结果（

18、计算结果（LINGO软件）软件）车次车次铲位铲位1 1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿漏矿漏131354541111倒倒42424343岩场岩场70701515岩漏岩漏81814343倒倒13132 27070车辆数车辆数铲位铲位1 1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿石漏矿石漏0.8671.8620.314倒场倒场1.0771.162岩场岩场1.8920.326岩石漏岩石漏1.8411.229倒场倒场

19、0.6840.11.489计算结果（派车）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏1 (29)倒场1 (39)1 (37)岩场1 (37)岩石漏1(44)1 (35)倒场1 (47)此外：此外：6辆联合派车方案为：辆联合派车方案为： 第第1辆：从铲位辆：从铲位1、3到岩石漏，铲位到岩石漏，铲位1到岩石漏运到岩石漏运37车，铲位车，铲位3到岩石漏运到岩石漏运5车。车。 第第2辆：从铲位辆：从铲位9、10到岩场，铲位到岩场，铲位9到岩场运到岩场运33车，车，铲位铲位10到岩场运到岩场运5车。车。 第第3辆：从铲位辆：从铲位8、10到矿石漏，铲位到矿石漏，铲位8到矿石漏运

20、到矿石漏运22车，车，铲位铲位10到矿石漏运到矿石漏运6车。车。 第第4辆：从铲位辆：从铲位2、8到矿石漏，铲位到矿石漏，铲位2到矿石漏运到矿石漏运13车，铲车，铲位位8到矿石漏运到矿石漏运3车。车。 第第5辆：从铲位辆：从铲位2、4到倒装场到倒装场和从铲位和从铲位2、3到倒装场到倒装场，铲位铲位2到倒装场到倒装场运运3车，铲位车，铲位4到倒装场到倒装场运运6车，铲位车，铲位2到到倒装场倒装场运运13车，铲位车，铲位3到倒装场到倒装场运运1车。车。 第第6辆：从铲位辆：从铲位3到倒装场到倒装场、岩石漏和从铲位、岩石漏和从铲位10到矿石漏、到矿石漏、岩场、倒装场岩场、倒装场，铲位，铲位3到岩石漏

21、运到岩石漏运3车，铲位车，铲位3到倒装场到倒装场运运1车，铲位车，铲位10到倒装场到倒装场运运23车，铲位车，铲位10到岩场运到岩场运10车，铲车，铲位位10到矿石漏运到矿石漏运5车。车。结论：结论：铲位铲位1、2、3、4、8、9、10处各放置一台电铲。处各放置一台电铲。一共使用了一共使用了13辆卡车；总运量为辆卡车；总运量为85628.62吨公里；吨公里；岩石产量为岩石产量为32186吨；矿石产量为吨；矿石产量为38192吨。吨。问题二、利用现有车辆运输而获得最大的产量问题二、利用现有车辆运输而获得最大的产量第二问的解法和第一问类似，也采用多目标二层规第二问的解法和第一问类似，也采用多目标二

22、层规划算法，第一层用整数线性规划，第二层用求派出划算法，第一层用整数线性规划，第二层用求派出车辆数最小的启发式方法。下面是第二问解法与第车辆数最小的启发式方法。下面是第二问解法与第一问的不同之处。一问的不同之处。 如果是，把岩石的总产量取最大值如果是，把岩石的总产量取最大值,即加入到约束即加入到约束条件中，以矿石产量最大为目标；如果否，把岩条件中，以矿石产量最大为目标；如果否，把岩石产量最大做为目标，求解最佳物流。石产量最大做为目标，求解最佳物流。 由于岩石产量优先，第一层规划计算前先做目标由于岩石产量优先，第一层规划计算前先做目标函数取岩石产量最大（函数取岩石产量最大（ ）的试算，）的试算，

23、来判断岩石产量是否能达到上限来判断岩石产量是否能达到上限: 10143maxijijx492802154208 为了求岩石（或矿石）产量最大的同时，保证总为了求岩石（或矿石）产量最大的同时，保证总运量运量(吨公里吨公里)较小，还不影响轻重顺序，运量的加较小，还不影响轻重顺序，运量的加权系数很小。如权系数很小。如 可设目标函数为。可设目标函数为。cxxxxijijijiiii 101511015210001. 0)(maxcxxxijijijiii 10151101430001. 0)(max或或 约束条件（约束条件（1）至（）至（9）不变）不变 在现有条件下岩石产量能否达到上限在现有条件下岩石

24、产量能否达到上限 由于这个整数规划的复杂性，所以必须考虑快速由于这个整数规划的复杂性，所以必须考虑快速算法算法: 先求解去掉整数约束的相应的线性规划先求解去掉整数约束的相应的线性规划; 目标值为目标值为341.2807车次车次逐个减一地依次求逐个减一地依次求“矿石产量等于比矿石产量等于比342小的整数小的整数”加到约束条件中，目标为总运量最小的整数规划。加到约束条件中，目标为总运量最小的整数规划。第一个出现可行解的规划的最优解必为原整数规第一个出现可行解的规划的最优解必为原整数规划的最优解划的最优解 把矿石卸点的最大产量为把矿石卸点的最大产量为341车次作为约束条件加车次作为约束条件加入到整数

25、线性规划中，没有可行解。入到整数线性规划中，没有可行解。 把矿石卸点的最大产量为把矿石卸点的最大产量为340车次作为约束条件加车次作为约束条件加入到整数线性规划中，得出的结果如下，即为所求入到整数线性规划中，得出的结果如下，即为所求 最佳物流相对应的各个路线上的最佳运输车次为：最佳物流相对应的各个路线上的最佳运输车次为：车次数车次数铲位铲位1 1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿石漏矿石漏382418倒装场倒装场16542268岩场岩场127474岩石漏岩石漏80283220倒装场倒装场144602

26、2卡车数卡车数铲位铲位1 1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿石漏矿石漏2.11112.11110.82760.82760.40910.4091倒装场倒装场0 0555517171.38461.38460.75860.75861.83781.8378岩场岩场0.46150.46152 21.64441.6444岩石漏岩石漏1 1818182820.93330.93330.91430.91430.66670.6667倒装场倒装场0.73680.73680.20.21.93551.93550.46810

27、.4681 根据最佳物流计算各路线上需要的卡车数根据最佳物流计算各路线上需要的卡车数 所有路线所需卡车数（实数）的和，为所有路线所需卡车数（实数）的和，为19.66。 各路线上需要的整数卡车数为各路线上需要的整数卡车数为9（这些卡车在一（这些卡车在一个班次内一直在固定路线上运输）个班次内一直在固定路线上运输） 铲位铲位1 1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿石漏矿石漏2 2倒装场倒装场1 11 1岩场岩场2 21 1岩石漏岩石漏1 1倒装场倒装场1 1 各个路线上的联合派车的卡车数为各个路线上的联合派车的卡车数为11， 各个路线上的联合派车的卡车数为各个路线上的联合派车的卡车数为11，方案为：，方案为： 第第1辆：从铲位辆：从铲位1到倒装场到倒装场、岩石漏，铲位、岩石漏，铲位1到倒装到倒装场场运运5车，到岩石漏运车，到岩石漏运36车。车。 第第2辆：从铲位辆：从铲位2到倒装场到倒装场、岩石漏，铲位、岩石漏，铲位2到倒装到倒装场场运运2车，到岩石漏运车，到岩石漏运2