露天矿生产的车辆安排2003B.ppt

数学建模案例 露天矿生产的车辆安排 2002年A C 题 露天矿生产的车辆安排 问题陈述 装卸点平面分布图 露天矿里铲位已分成矿石和岩石 平均铁含量不低于25 的为矿石 否则为岩石 每个铲位的矿石 岩石数量 以及矿石的平均铁含量 称为品位 都是已知的 每个铲位至多安置一台电铲 电铲平均装车时间5分钟 矿石卸点需要的铁含量要求都为29 5 1 品位限制 搭配量在一个班次 8小时 内满足品位限制即可 卸点在一个班次内不变 平均卸车时间为3分钟 主要因素与已知条件 电铲和卸点都不能同时为两辆及两辆以上卡车服务 卡车每次都是满载运输 卡车载重量为154吨 平均时速28km 卡车在等待时所耗费的能量也是相当可观的 原则上在安排时不应发生卡车等待的情况 实例数据 有铲位10个 卸点5个 铲车7台 卡车20辆 各卸点一个班次的产量要求 矿石漏1 2万吨 倒装场 1 3万吨 倒装场 1 3万吨 岩石漏1 9万吨 岩场1 3万吨 问题 出动几台电铲 分别在哪些铲位上 出动几辆卡车 分别在哪些路线上各运输多少次 考虑下面两条原则之一 1 总运量 吨公里 最小 同时出动最少的卡车 从而运输成本最小 2 利用现有车辆运输 获得最大的产量 岩石产量优先 在产量相同的情况下 取总运量最小的解 就两条原则分别建立数学模型 并给出一个班次生产计划的快速算法 针对下面的实例 给出具体的生产计划 相应的总运量及岩石和矿石产量 问题分析 与典型的运输问题明显有以下不同 这是运输矿石与岩石两种物资的问题 属于产量大于销量的不平衡运输问题 为了完成品位约束 矿石要搭配运输 产地 销地均有单位时间的流量限制 运输车辆只有一种 每次满载运输 154吨 车次 铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地 最后求出各条路线上的派出车辆数及安排 运输问题对应着线性规划 以上第1 2 3 4条可通过变量设计 调整约束条件实现 第5条使其变为整数线性规划 第6条用线性模型实现的一种办法 是从个整数规划中取最优的即得到最佳物流 对第7条由最佳物流算出各条路线上的最少派出车辆数 整数 再给出具体安排即完成全部计算 对于这个实际问题 要求快速算法 计算含50个变量的整数规划比较困难 另外 这是一个二层规划 第二层是组合优化 如果求最优解计算量较大 现成的各种算法都无能为力 于是问题变为找一个寻求近优解的近似解法 例如可用启发式方法求解 近似处理 先求出产位 卸点每条线路上的运输量 MIP模型 然后求出各条路线上的派出车辆数及安排 这是一个多目标规划 第一问的目标有两层 第一层是总运量 吨公里 最小 第二层是出动卡车数最少 从而实现运输成本最小 第二问的目标有 岩石产量最大 矿石产量最大 运量最小 三者的重要性应按此序 调用120次整数规划可用三种方法避免 1 先不考虑电铲数量约束运行整数线性规划 再对解中运量最少的几个铲位进行筛选 2 在整数线性规划的铲车约束中调用函数来实现 3 增加10个0 1变量来标志各个铲位是否有产量 模型假设 卡车在一个班次中不应发生等待或熄火后再启动的情况 在铲位或卸点处由两条路线以上造成的冲突问题面前 我们认为只要平均时间能完成任务 就认为不冲突 我们不排时地进行讨论 空载与重载的速度都是28km h 耗油相差很大 因此总运量只考虑重载运量 卡车可提前退出系统 等等 符号 xij 从i号铲位到j号卸点的石料运量 车 单位 吨cij 从i号铲位到j号卸点的距离公里Tij 从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号铲位的铁矿石储量万吨cyi i号铲位的岩石储量万吨fi 描述第i号铲位是否使用的0 1变量 取1为使用 0为关闭 模型建立 算法设计与模型求解 问题一 求运输成本最小的生产计划 一 以总运量最小为目标函数求解最佳物流 第一层规划 一个电铲 卸点 不能同时为两辆卡车服务 一条路线上最多能同时运行的卡车数是有限制的 卡车从i号铲位到j号卸点运行一个周期平均所需时间为 道路能力约束 近似 最多能同时运行的卡车数为 最后一辆卡车一个班次中在这条路线上最多可以运行的次数为 一个班次中这条固定路线上最多可能运行的总车次大约为 总吨数为 一台电铲不能同时为两辆卡车服务 所以一台电铲在一个班次中的最大可能产量为 8 60 5 154 吨 电铲能力约束 卸点能力约束 卸点的最大吞吐量为每小时60 3 20车次 于是一个卸点在一个班次中的最大可能产量为 8 20 154 吨 铲位储量约束 铲位的矿石和岩石产量都不能超过相应的储藏量 产量任务约束 各卸点的产量不小于该卸点的任务要求 铁含量约束 各矿石卸点的平均品位要求都在指定的范围内 整数约束 当把问题作为整数规划模型时 流量xij除以154为非负整数 卡车数量约束 不超过20辆 电铲数量约束 电铲数量约束无法用普通不等式表达 可以引入10个0 1变量来标志各个铲位是否有产量 优化模型 1 道路能力 卡车数 约束 2 电铲能力约束 3 卸点能力约束 4 铲位储量约束 5 产量任务约束 6 铁含量约束 7 电铲数量约束 8 整数约束 9 车辆约束 xij为非负整数fi为0 1整数 计算结果 LINGO软件 计算结果 派车 此外 6辆联合派车方案为 第1辆 从铲位1 3到岩石漏 铲位1到岩石漏运37车 铲位3到岩石漏运5车 第2辆 从铲位9 10到岩场 铲位9到岩场运33车 铲位10到岩场运5车 第3辆 从铲位8 10到矿石漏 铲位8到矿石漏运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到岩石漏运3车 铲位3到倒装场 运1车 铲位10到倒装场 运23车 铲位10到岩场运10车 铲位10到矿石漏运5车 结论 铲位1 2 3 4 8 9 10处各放置一台电铲 一共使用了13辆卡车 总运量为85628 62吨公里 岩石产量为32186吨 矿石产量为38192吨 问题二 利用现有车辆运输而获得最大的产量 第二问的解法和第一问类似 也采用多目标二层规划算法 第一层用整数线性规划 第二层用求派出车辆数最小的启发式方法 下面是第二问解法与第一问的不同之处 如果是 把岩石的总产量取最大值 即加入到约束条件中 以矿石产量最大为目标 如果否 把岩石产量最大做为目标 求解最佳物流 由于岩石产量优先 第一层规划计算前先做目标函数取岩石产量最大 的试算 来判断岩石产量是否能达到上限 为了求岩石 或矿石 产量最大的同时 保证总运量 吨公里 较小 还不影响轻重顺序 运量的加权系数很小 如可设目标函数为 或 约束条件 1 至 9 不变 在现有条件下岩石产量能否达到上限 由于这个整数规划的复杂性 所以必须考虑快速算法 先求解去掉整数约束的相应的线性规划 目标值为341 2807车次逐个减一地依次求 矿石产量等于比342小的整数 加到约束条件中 目标为总运量最小的整数规划 第一个出现可行解的规划的最优解必为原整数规划的最优解 把矿石卸点的最大产量为341车次作为约束条件加入到整数线性规划中 没有可行解 把矿石卸点的最大产量为340车次作为约束条件加入到整数线性规划中 得出的结果如下 即为所求 最佳物流相对应的各个路线上的最佳运输车次为 根据最佳物流计算各路线上需要的卡车数 所有路线所需卡车数 实数 的和 为19 66 各路线上需要的整数卡车数为9 这些卡车在一个班次内一直在固定路线上运输 各个路线上的联合派车的卡车数为11 各个路线上的联合派车的卡车数为11 方案为 第1辆 从铲位1到倒装场 岩石漏 铲位1到倒装场 运5车 到岩石漏运36车 第2辆 从铲位2到倒装场 岩石漏 铲位2到倒装场 运2车 到岩石漏运28车 第3辆 从铲位3到倒装场 岩石漏 铲位3到倒装场 运2车 到岩石漏运32车 第4辆 从铲位4到倒装场 岩石漏 铲位4到倒装场 运12车 到岩石漏运20车 第5辆 从铲位1 2 3到倒装场 铲位1到倒装场 运11车 铲位2到倒装场 运13车 铲位3到倒装场 运8车 第6辆 从铲位3 4到倒装场 和铲位3到矿石漏 铲位3到倒装场 运12车 铲位4到倒装场 运19车 铲位3到矿石漏运1车 第7辆 从铲位2 3 8到倒装场 铲位2到倒装场 运14车 铲位3到倒装场 运4车 铲位8到倒装场 运1车 第8辆 从铲位8 10到倒装场 铲位8到倒装场 运28车 铲位10到倒装场 运4车 第9辆 从铲位10到岩场 倒装场 铲位10到岩场运27车 铲位10到倒装场 运18车 第10辆 从铲位8