“露天矿生产的车辆安排”的模型和评述.pdf

第 2 o 卷 第7 期 工 程 数 学 学 报。年 。月 J OURNA L OF E NGI NE ERI NG MATHEMATI C S V o l 2 0 No 7 De c 2 0 0 3 文章编号：1 0 0 5 3 0 8 5(2 0 0 3)0 7 0 0 9 1 1 0 “露天矿生产的车辆安排”的模型和评述 摘 要 关键词 分类号 方沛辰，李磊(吉林大学，长春 1 3 0 0 2 5)结合今年全国大学生数学建模竞赛 B题的评阅情况，该文叙述了一种基本解法和结果，并对审题 中的一些 问题做 出了回答。完全问题：组合优化 A MS(2 0 0 0)9 0 C 2 7 中图分类号：0 2 2 1 文献标识码：A 最近几年全国大学生数学建模竞赛的题目侧重于优化问题，多数问题来源于生产或科 研实际是一个好事情。学生在竞赛的同时对现代科技的实用方法和热点问题有一个大致的 了解，随着解决问题也检验了自己所掌握的知识与社会需求之间有多大的差距，确定今后的 努力方向。对各学校的赛前培训提出了更高的要求并指出了方向，从而使竞赛进人良性循 环。参赛队逐年增加，解题能力、所用方法、使用软件和论文撰写的水平在不断提高都说明 了这一点。“露天矿生产的车辆安排”一题就是在这样的想法下设计的。露天矿的生产调度，可以划分成许多种类型，但不论怎样最后都要牵涉到车辆的调度安 排这样一个组合问题，因此都是没有好算法的 NP完全(N P C)问题。各国根据一些露天矿 的实际情况开发出许多实用软件，但都没有公开它们的算法。我国仅有几个露天矿用上了 智能化软件管理，水平还需要提高，应用面也需要扩大，矿业生产迫切需要这方面的成果。总之，深入研究这方面问题是很有实际意义的。由于没有详细、确定的资料可以参考，所以 比较适合作为数学建模竞赛的题目，做题时没有框框，能留有更大的空间让学生们用聪明才 智去发挥创造，充分地锻炼学生们解决实际问题的能力。这道题是以国内某露天铁矿为背景，大幅度地简化难度和去掉许 多实际要求而编制的 一个较理想的问题。特别是由于去掉了随机性，使得此题更接近露天矿生产的根本问题，也 更适于作为竞赛的题目。题目中要求给出各条路线上的车辆数及安排，即给出当班次生产 的一个宏观的计划，方法和结果对仍使用人工调度计划的单位有启发、指导的作用。做了简 化之后，使得学生在阅读过短短的几行之后，就对露天矿生产的情况有一个比较清晰的理 解。下面我们结合阅卷的一些情况，简述这一问题的基本模型和解法。收稿 日期：2 0 0 3 一 l l 一 1 5 作者简介：方沛辰(1 9 4 9 年生)，男、副教授，研究方 向 随机过程、优化 维普资讯 http:/ 9 2 工程数学学报 第 2 O卷 1 问题分析 从题 目看，露天矿生产主要是运石料。它与典型的运输问题明显有以下不同：1)这是运输矿石与岩石两种物资的问题；2)属于产量大于销量的不平衡运输问题；3)为了完成品位约束，矿石要搭配运输；4)产地、销地均有单位时间流量的限制；5)运输车辆 只有一种，每次都是满载运输，1 5 4吨 车 次；6)铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；7)不仅要求最佳物流，最后还要求出各条路线上的派出车辆数及安排。每个运输问题对应着一个线性规划问题。以上不同点对它的影响不 同，第 1、2、3、4条 可通过变量设计、调整约束条件实现；第 5 条整数要求将使其变为整数线性规划；第 6 条不 容易用线性模型实现，一种简单的办法是从c 7 n=1 2 0 个整数规划中取最优的即得到最佳 物流；为完成第 7条由最佳物流算出各条路线上的最少派出车辆数再给出具体安排即完成 全部计算。然而这是个实际问题，为了及时指挥生产，题中要求算法是快速算法，而整数规 划的本质是 NP完全(N P C)问题，短时间内计算含至少 5 0 个变量的整数规划来说就不一 定办得到。从另一个角度看，这是两个阶段的规划问题，第一个阶段是确定各条路线上运输 石料的数量(车次)，可以用整数规划建模；第二阶段是规划各条线路上的派车方案，是一个 组合优化问题。如果求最优解计算量较大，现成的各种算法都无能为力。于是问题可能变 为找一个寻求近优解的近似解法，例如可用启发式方法求解。调用 1 2 0 次整数规划可用至少三种方法避免：(1)先不考虑电铲数量约束运行整数线性 规划，再对解中运量最少的几个铲位进行筛选；(2)在整数线性规划中设计铲车约束调用符 号函数(s i g n)来实现；(3)增加 1 0 个 0 1 变量来标志各个铲位是否有产量。从每个运输问题都有 目标函数的角度看，这又是一个多 目标问题，第一个原则的主要 目 标有：重载路程最小；总路程最小；出动卡车数最少。仔细分析可得：和在第一阶 段，在第二阶段；与基本等价，于是只用于第一阶段，对其结果在第二阶段中派最少 的卡车，实现全局目标生产成本最小。第二个原则的主要目标有：岩石产量最大，矿石 产量最大和运量最小，根据题意三者之间的关系应该理解为字典序。可分忻出问题的主要难点有：1 怎样处理在 1 0个铲位选择安排 7台电铲的问题。2 从铲位 i 到卸点 i 的流量均为 1 5 4 吨的整数倍，即取为整数车 次数。这题的核心是如何 用近似算法求解 N P C问题。整数规划的现有解法不是快速算法，无法保证在任何数据下都能在 短时间内算完，应该想办法巧妙地设计算法和使用数学软件减少运行整数规划耗费的时间。3 模型中应有道路能力约束，否则原则二的结果不可能正确。4 派车问题本质为组合优化问题，如何快速得到最优解或近优解。2 基本做法 模型假设：维普资讯 http:/ 第 7 期“露天矿生产的车辆安排”的模型和评述 9 3 1 卡车在一个班次中不应发生等待或熄火后再启动的情况；2 在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完 成任务，就认为不冲突。我们不排时地进行讨论；3 空载与重载的速度 都是 2 8 k in h，耗油相差却很大；4 卡车可提前退出系统；5 卡车加油、司机吃饭与上厕所等休息时间忽略不计；6 对所有卡车来说，一个班次的8小时是同一时刻开始的。符号：单位 z 从 i 号铲位到 号卸点的石料运量 车 次；c 从 i 号铲位到 号卸点的距离 公里；T 在 i 号铲位到 号卸点路线上运行一个周期平均所需时间 分；A 从 i 号铲位到 号卸点最多能同时运行的卡车数 辆；B 从 i 号铲位到 号卸点，一辆车一个班次中最多可以运行次数 次；P ：号铲位的矿石铁含量乘以1 0 0 P=(3 0，2 8，2 9，3 2，3 1，3 3，3 2，3 1，3 3，3 1)；q 号卸点任务需求，Q=(1 2，1 3，1 3，1 9，1 3)1 0 0 0 0 1 5 4；车 次；c k ：i 号铲位的铁矿石储量 万吨；c y ：i 号铲位的岩石储量 万吨；：描述第 i 号铲位是否使用的开关变量，取 1 为使用；取0为关闭。模型建立、算法设计与模型求解：原 则 一、求 运 输 成 本 最 小 的 生 产 计 划 一以重载路程最小为目 标函数求解最佳物流 一第一阶段规划 目标函数与约束条件的分析：(0)目 标函数取为重载运输时的运量(吨公里)最小。(1)道路能力约束：一个电铲(卸点)不能同时为两辆卡车服务，所以一条路线上最多能 同时运行的卡车数是有限制的。在 i 号铲位到 号卸点路线上运行一个周期平均所需时间 T ，=+3+5(分)。由于装车时间5 分钟大于卸车时间3 分钟，所以可分析出这条路线 上在卡车不等待条件下最多能同时运行的卡车数 A f=J。同样可分析出每辆卡车一个 班次中在这条路线上最多可以运行的次数B f：L 二 L J，其中(A u一1)5 是开始装车 最后一辆车的延时时间。则一个班次中这条固定路线上最多可能运行的总 车 次大约为：L d：Af，B 总吨数大约为 1 5 4L 注：如果假设所有卡车的上班时间可以不是同一时刻，在此处应取 B ，：L J，以下 U 的解法和结果也略有不同。维普资讯 http:/ 9 4 工程数学学报 第 2 0 卷(2)电铲能力约束：还是因为台电铲不能同时为两辆卡车服务，所以一 台电铲在一个 班次中的最大可能产量为：86 0 5=9 6(车 次)。(3)卸点能力约束：卸点的最大吞吐量为每小时6 0 3=2 0(车 次)，于是一个卸点在一 个班次中的最大可能产量为：82 0=1 6 0(车 次)。(4)铲位储量约束：各铲位的矿石和岩石产量都不能超过相应的储藏量。(5)产量任务约束：各卸点的产量大于等于该卸点的任务要求。(6)铁含量约束：各矿石卸点的平均品位要求都在指定的范围内。(7)电铲数量约束：电铲数量约束无法用普通不等式表达，可以巧妙地引入 1 0 个。一l 变 量来标志各个铲位是否有产量。这样做可以求出最优解，但算法运行时间增加了。当然也可用 其他方法解决该问题。(8)车辆数量约束：x ij 2 0，其 中 考 为 各 路 线 上 运 输 量 所 需 的 实 数 卡 车 数。(9)整数约束：问题作为整数规划模型时，为非负整数，表示运行的车 次数。这样，我们可以得到求解最佳物流 z 的各种模型之一为 ra in c o 1 5 4 t x ij AoB o，i=1，1 0，J=1，5 9 6，i=1，1 0 1 6 0，=1，5 X i l+q-2C i 2q-Xi 5 c k l 1 0 0 0c y 1 0 0 0 0 1 5 4。54，=，。3+4 J q ，=1，5 (p 一 3 0 5)o 1。，=1，2，5 (p 一 2 8 5)o j 2 0 i=1，=1 一 U 7 为整数，i=1，1 0，J=1，5 为 01 变量，i=1，1 0 二 对最佳物流进行派车一第二阶段规划 这是一个组合优化中的一维装箱模型，又是一个N P C问题，针对快速算法的要求，我们 用启发式方法求近优解。维普资讯 http:/ 第7期“露天矿生产的车辆安排”的模型和评述 9 5 先用最佳物流修正 B 即在 B ，表达式中用最佳物流 所对应的卡车数代替A ，重新 计算得到新的 B 然后在以目标为出动总卡车数最少的各路线派车中，把各路线需要的卡 下 车数“=分成整数部分L e ，J 和小数部分，一 L e ，J，进而可以分配任务让，J 辆车始终在 u t 1 i 到J路线上，每辆往返运输 B 次。为了最后实现第二阶段规划的目标，下面只需联合处理 所有的e ，一 L e ，J 时把这些小数组合成最少的整数卡车数。所需总卡车数的下界显然是 y ：r 。如果某 种派车方案恰好派出Y 辆车实现了 所有的 ，则其即为在第二阶 段目 标 l J 意义下近优解的最优方案。但由于有联合派车而总公里数不一定最小，故不一定为全局意义 下的最佳方案，还需要进一步分析确定。出动卡车数最少，意味着出动的卡车利用率要最大。容易出现的一辆卡车为两个以上路 线服务的联合派车，可分为两种情况：(1)有共同铲位(或卸点)的联合派车(V字形或更复 杂)；(2)不同铲位且不同卸点之间的联合派车(z字形或四边形或更复杂)。注意到派车方案 的空载路线应尽量安排在第一阶段规划的最佳物流路线内，即使有的超出也要保证超出的 路程总和最小，这样才能实现重载路程最小且使卡车空载路程也最小。而情况(1)的路线不 会超出第一阶段规划的最佳物流路线。只有情况(2)才会有一部分不在第一阶段规划的最佳 物流路线内。重申一下面前的问题：各路线都是小数的需车数，如何组合使总卡车数最少且如果出现 情况(2)时空载超出部分总和尽量小。如果存在情况(1)，则整体考虑情况(1)形路线需要的卡车数相加的和，先确定和的整数 部分的车数并对这些车分配任务(任务的形式为在哪条路线上运几趟，再在哪条路线上运几 趟，等等)。之后已无情况(1)了，再对各个小数进行组合相加试探，在所有动用卡车数最少的 情况中，选择超出第一阶段最佳物流路线的总和最小的，即为最后派车方案，再对这些车分 配任务。由于属于情况(1)的为多数，故后面的组合搜索比较简单，常常只有一两个任务属情 况(2)。根据最后派车方案，回代计算出各车辆在各路线的运输次数。由于整数部分已分配完运 输次数，小数乘以对应路线上的 B 取整计算出小数部分对应的具体运输次数即可。进一步计算出实际总运量与矿石和岩石的产量。三 求解过程(一)第一阶段规划 求解前面给出的整数规划模型可计算出最优值为总运量 8 5 6 2 8 6 2吨公里。最佳物流相对应的各个路线上的最佳运输车 次：铲位 l 铲 位 2 铲位 3 铲住 4 铲 位 5 铲位 6 铲位 7 铲 位 8 铲位 9 铲位 l O 矿石 漏 l 3 5 4 l l 倒装场 I 4 2 4 3 岩 场 7 0 l 5 岩石 漏 8 l 4 3 倒装场 1 3 2 7 0 (二)第二阶段规划 固定路线派车(这些卡车在一个班次内一直在固定路线上运输)方案为：维普资讯 http:/ 工程数学学报 第 2 0卷 铲位 l 铲42-2 铲 位 3 铲住 4 铲 位 8 铲 位 9 铲 位 1 0 矿 石漏(1)2 9 倒装场 I (2)3 9 (3)3 7 岩 场(4)3 7 岩石漏(5)4 4 (6)3 5 倒装场 (7)4 7 表中括号内的数是卡车车号，后面是运的车 次数，以下同。联合派车方案为：铲位 1 铲位 2 铲 位 3 铲住 4 铲 位 8 铲位 9 铲住 l 0 矿石漏(1 1)1 3 (1 0)2 2(1 1)3 (1 0)6(1 3)5 倒 装场 I (1 2)3 (1 2)6 岩 场(9)3 3 (9)5(1 3)1 0 岩 石漏(8)3 7 (8)5(1 3)3 倒装场 (1 2)l 3 (1 2)l(1 3)1 (1 3)2 3 对这道题的数据来说，只有共卸点或共铲位情况，没出现(2)型联合派车。铲位 l、2、3、4、8、9、1 0处各放置一台电铲。一共使用了l 3辆卡车；总运量为8 5 6 2 8 6 2吨公里；岩石产量为 3 2 1 8 6吨；矿石产量为 3 8 1 9 2吨。原 则 二、利 用 现 有 车 辆 运 输 而 获 得 最 大 的 产 t l-一在卡车不等待条件下利用现有车辆资源运输，获得最大的产量(岩石产 量优先；在产量相同的情况下，取总运量最小的解)的模型 这也是一个多 目标问题，目标函数为岩石产量最大、矿石产量最大和总运量最小。卡车不发生等待的条件可看作在实现了最大产量后还要使卡车数最少。由于同样都是处理石料的运输问题，所以第二个原则的解法和第一个原则类似，也采用 多目标的两个阶段算法，第一阶段用整数线性规划，第二阶段仍用前面求派出车辆数最小的 启发式方法。下面叙述两者的不同之处。由于岩石产量优先，第一阶段规划计算时首先求解约束条件与前相同，目标函数取 l 0 4 m ax：即岩 石产量 最大的 规划，来 判断岩 石产 量是否 能达到 上限3 2 0 车 次，即 i=1，=3 l 0 4 4 9 2 8 0 吨。如 果 是，把 岩 石的 总 产 量 取 最 大 值，即z =3 2 0 加入 到 约 束 条件 中，以 矿 石 i=1，=3 产量最大做为目标再第二次求解最佳物流；如果否，直接求解下一个规划。最后求解把矿石 和岩石产量分别取在前面规划中得到的各自最大值作为约束条件，目标函数取为总运量(吨 公里)最小的规划。二 实例的模型求解 由于这个整数规划的复杂性，第一阶段采用结合线性规划地求解整数规划。试算可得岩石总产量达到了上限3 2 0车 次，于是用岩石产量达到上限作为约束，矿石 产量最大为 目标函数求解最佳物流。先求解去掉整数约束的相应的线性规划，目标值为 3 4 1 2 8 0 7车 次。由于欲求的是整数线性规划，矿石的最大产量(车 次)必然应为一整数。利用线性规划的可行域 比整数规划的可行域大，故线性规划的最优解是整数规划最优解的 维普资讯 http:/ 第 7 期“露天矿生产的车辆安排”的模型和评述 9 7 上界这个原理，逐个减一地依次求“矿石产量等于比3 4 2 小的整数”加到约束条件中，目标为 总运量最小的整数规划。第一个出现可行解的规划的最优解必为原整数规划的最优解，且总 运量最小。由于等式约束造成可行域的减小，运算量已大幅度减少。采用这一技巧，运行时间 大幅度减少。把矿石卸点的最大产量为 3 4 1 车 次作为约束条件加入到整数线性规划中，没有可行解。把矿石卸点的最大产量为 3 4 0车 次作为约束条件加入到整数线性规划中，得 出的结 果如下，即为所求。最佳物流相对应的各个路线上的最佳运输车 次为：铲位 1 铲位 2 铲住 3 铲 位 4 铲位 5 铲 位 6 铲住 7 铲位 8 铲位 9 铲位 1 0 矿石 漏 3 8 2 4 1 8 倒装场 I 1 6 5 4 2 2 6 8 岩 场 1 2 7 4 7 4 岩石 漏 8 0 2 8 3 2 2 0 倒装场 1 4 4 6 0 2 2 第二阶段规划仍用前面的启发式算法：固定路线派车方案为：铲 位 1 铲住 2 铲位 3 铲位 4 铲位 8 铲位 9 铲 位 1 0 矿石漏(3)(4)3 6 倒装场 I (2)3 9 (3)3 7 岩 场 (7)(8)7 4 (9)4 5 岩石漏(1)4 4 倒装场 (6)3 1 联合派车方案为：铲位 1 铲位 2 铲位 3 铲住 4 铲位 8 铲位 9 铲住 1 0 矿石漏(1 5)l(2 0)l (1 9)1 4(2 0)1 0 (2 0)1 8 (1 2)2(1 4)8 剜装场 I (1 0)5(1 4)l 1(1 1)2(1 4)1 3 (1 3)1 2(1 5)1 9 (1 5)1 2 岩 场 (1 9)1 2 (1 8)2 7(1 9)2 岩石漏 (1 0)3 6 (1 1)2 8 f l 2)3 2 (1 3)2 0 剜装场 (1 6)1 4 (1 6)4 (1 6)1(1 7)2 8 铲位 1、2、3、4、8、9、i 0处各放置一台电铲。一共使用了2 O 辆卡车；总运量为 1 4 2 3 8 5 3吨公里；岩石产量为 4 9 2 8 0吨；矿石产量为 5 2 3 6 0吨。3 关于审题的一些问题 在评阅的过程中我们发现了同学们在审题中存在一些问题，有些是值得说明的。1 绝大多数学生对岩石不可以用于配矿的问题作了基本正确的理解。将铁矿石按品位 来进行配矿的目的是综合利用低品位的矿石。同样是爆破下来又同样要运走，成本差不多，可作为岩石还是作为矿石的差别就太大了。岩石是废料要再花成本处理掉，而矿石是我们需 维普资讯 http:/ 9 8 工程数学学报 第 2 O卷 要的，越多越好。从保护国家资源的角度看，我们的低 品位矿山较多而较高品位的矿山不是 很多，还要尽量给后代 留一些，所以应该仔细地利用资源，这一点已在题 目中简要说明了。另 外如果认为岩石可以配矿，铁含量怎么取呢?事实上生产中也不允许这样做。2 卡车不等待的条件可能是同学们作题时普遍最头疼的问题，竞赛那几天在网上几乎 随时可见这方面的讨论。实际上，卡车工作时有三种状态：装车、卸车和运行。既然路线是专 用的双向车道不会堵车，那么运行时不会等待。只有装 车和卸车时能发生等待，即到达装(卸)点时还有卡车没装(卸)完而排队等待(以下简称冲突)，这时的等待可 以分为两种情 形，就是与同路线的卡车和不同路线的卡车的冲突，下面分别对两种情形分析。同路线的冲突一旦发生，后面的卡车在此就必然连续发生冲突，也就是说这种冲突是一 种必然事件，是这条路线上安排的卡车太多了而造成的必然结果，从此应该认识到每条路线 有一个最多可以运行的卡车数的限制，即道路能力约束。比如说，卡车在一条路线上单程运 行时间为 1 分钟，加上装车时间 5 分钟和卸车时间 3分钟，那么一个周期的时间为 1 0分钟，派几辆卡车会发生冲突呢?显然 2辆车不冲突，而 3辆车就一定 冲突，并且可以分析出在铲 位处始终有一辆车在等待装车。这种浪费是不能允许的，因为派3 辆车与派2辆车的效果是 一样的。电铲在卡车运行一周期的 l 0 分钟内只能装出2 车 次，所以最适合的就是这条路线 派 2辆车。于是，从 i 号铲位到 号卸点的周期时间 T ，=x 2 x 6 0+5+3(分)，从 i 号铲 二o T 位到 号卸点的路线上最多可派 J 辆车，否则就必然发生等待。J 再分析不同路线上到达同一装(卸)点的卡车之间的冲突。由于每条路线有 自己的运行 周期 T 一般来说互不相同，所以一个班次中几乎是不可避免的要有这种冲突，但毕竟是随 机事件，发生一次冲突以后也许很长时间才发生下一次。考虑到矿山里面的道路条件很差，卡车想匀速运行是很难办到的，所以用周期去算冲突的概率也很难正确地估计。总之两种冲突的性质是截然不同的，同路线冲突为本质上的且不可避免的，而不同路线 冲突是偶尔才能发生的，显然同路线的冲突是主要矛盾，不允许等待应主要防止第一种类型 的等待发生。第二种类型的等待可以用第 2 条模型假设来忽略。有的学生在这个问题上钻牛 角尖，甚至要证明“不等待是不可能的。”等等。一方面是没有注意到题目中第一次谈到不等 待时说到的“原则上在安排时不应发生卡车等待的情况”，隐含着有的冲突是有可能发生的；另一方面是没有掌握数学建模的真谛：数学建模就是要用简单模型来描述复杂问题，特别是 在问题本身已复杂到无法精确求解时，尤其是这样。大多数答卷正确地认识了不等待的含 义，但能够完整写出道路能力约束并且建立适当假设的还不是很多。3 题目中提到需要设计一个快速算法，而问题本身又需要一个最好的安排，这本身就 是一个多目标问题。正确的理解是首先要快再尽量好。进一步分析实际问题可以得到：要求 快的原因是每个班次开始前矿山都要进行当天的生产安排，甚至一个班次中还要调整多次，要求快是自然的，但也不是越快越好，而是满足一定要求就可以了。这个要求虽不能准确描 述，但大约半个小时就应该可以了。综观建模竞赛，三天中要完成分析题 目、查找资料、建立 解题思路、写出模型与算法、寻找适用的软件、编程调试、多次计算、结果分析与验证、完成论 文等多项工作，就算不走弯路，设计出的模型与算法的执行时间也不应超过一小时，这样的 算法才差不多。学生应该知道如果所用的软件与设计的算法几个小时中还没有得出结果，就 维普资讯 http:/ 第 7 期“露天矿生产的车辆安排”的模型和评述 应该赶快改变算法了。从这个意义上说竞赛中能得到结果的算法就是快速算法了。有的队错 误的理解为设计模型并得到一个结果后，需要再设计一个手算或者图上的近似作业法供现 场使用，从而浪费了时间，并且近似作业法也无用。我们要求了“快速算法”，但在题目中并没有明确规定具体时间要求。一是因为在竞赛中 采用这个标准有些苛刻；二是由于无法准确的规定所使用的计算机和软件，其计算速度也就 没有办法衡量。我们在这里想强调的是，在具体的生产活动中，算法的运行时间，即算法的复 杂度是一个很重要的问题，其重要性甚至远远超过得到的是否是一个最优解。在实际中经常 因为算法运行时间的原因，而采用可得到近似解而运行速度较快算法。4 有的队使用的是排时或类似的方法，没有注意到题 中明确指出不能排时。下面就说 明一下原因。到过露天矿的人，都会对里面的道路有所感触：这里就是山路啊。几乎没有一段 是直的、平的，同时有拐弯和上下坡。路况也是临时路面，可能几天以后就被爆破成为新铲位 了。电动轮卡车在这样的道路上行驶，无法用匀速来描述。更不能象列车时刻表一样来计划 生产，因为那实在是没有意义。铲位装车也因为各石料堆情况的不同：堆大还是堆小，石料的 块大还是块小，而花费不同的时间，另外前一车装的是矿石还是岩石，是否要微调一下电铲 的位置与状态，也影响装车时间。因此，在这道题里装车、卸车时间和卡车速度都明确地写着 是平均的。而排时方法所用的数据必须是精确的。题目中的“求出各条路线上的卡车数及安 排”只是要求给出一个粗略的指导性的计划，所以不能用排时方法。5 绝大多数学生能正确地认识到铲车在一个班次中是不可移动的，一旦安排在哪里就 始终工作在哪里。否则既没有铲车的移动速度，又没有铲位之间的距离，怎么安排计算呢!另 外移动肯定要花费时间，卡车此时就要出现等待从而降低了设备利用率。6 在评阅过程中，发现有的同学利用题 中“每个班次每台车消耗近 1吨柴油”这个条 件，在网上查到柴油的价格后计算成本。这样做存在以下问题：由于空载和重载的耗油量是 不同的，题中没有指出两者的比例；也没有指明在一个班次中是否一直工作才耗油 1 吨。在 这样的条件下，利用“每个班次每台车消耗近 1 吨柴油”其合理性无法保证。7 大多数的队能正确理解“岩石产量优先”。由于矿山中生产是连续的，所以在完成矿 石任务的同时要及时运出一定量的岩石，如果在这个时候还有卡车可 以进行运输就要优先 考虑运岩石。这样做可以保证在下一个班次中能运出更多的矿石。同时也是由于如果岩石超 产可以处理掉，但如果矿石超产则不一定能处理。比如：矿石漏的接口为传送带，直接将矿石 运到选矿厂的球磨机粉碎，如果产量超过矿石漏吞吐量则整个环节无法处理。出题时加上这 个条件也是为了把多 目标问题变为好处理形式，岩石产量和矿石产量为字典序。关于“岩石 产量优先”有两种理解，以岩石产量 一矿石产量 一总运量为序和以总产量 一岩石产量 一总 运量为序最后的效果是一样的，原则二的岩石产量都应达最大 4 9 2 8 0吨。8 有一个问题必须指出，最后答案中要有一个可以执行的派车表。有一些队第一阶段 规划做的挺好，但是没有派车表，属于没理解题意，很可惜。4 其它 在评阅中我们发现，解第一阶段规划时除了上述的基本模型和解法外，还有一种方法用 的较多，就是求解相对应的线性规划，再调整成整数可行解后作为整数规划的近优解。但是 维普资讯 http:/ 1 0 0 工程数学学报 第 2 0 卷 有的队没有验证解的可行性只是简单的取整，从而导致得出的不是可行解。这种算法的优点 是速度较快，但算法的通用性要略差一些，调整过程不容易程序化。解第一阶段规划时比较多的是采用 L i n g o 软件，但由于采用版本的不同，算法上也不大 相同。使用的其他软件还有 L i n d o，Ma t la b，S A S，E x c e l，等等。第二阶段规划是一个装箱问题，普遍采用的是启发式方法，也有一些队采用分枝定界法、动态规划法等，效果相差不大。个别论文明确指出了这是一个装箱问题，并采用了装箱问题的 一些经典的启发式方法，如 N F算法、F F算法、B F D算法等。也有一些队采用遗传算法、模拟 退火法、层次分析法，等等。由于解题速度和结果相差都较大，这方面没有太理想的答卷。有些同学为了得到车辆严格不等待条件下的结果，通过观察题中数据的特殊性，具体数 据具体分析(局部优化)，用“八字形运输法”和“穿梭运输法”，得到了车辆严格不等待条件下 的一个结果(他们称之为“完全可行的解”)。所谓“八字形运输法”，即车辆行驶路线为：P 一 X 一P，一X 一P ；所谓“穿梭运输法”，即车辆行驶路线分别为：P X 及 P，一X 一P 。应 该说在所有参赛的论文中这种处理方法是有一定创新和特色的。不足之处在于：这种处理 方法只是依据文中数据具体进行分析，以逻辑分析为主来得到结果，有一种根据具体数据来“凑”结果的味道，缺少一般性，很难有好的一般的模型和解法。另外，得到的也只是一个可 行解，误差是否很大不得而知。最后很关键的是，这样理解与实际情况差别很大，因为题中 说明由于随机因素影响“排时无效”，实际中并不需要一个严格的排时计划。八字形运输法 严重限制生产，效率很低，只是一个纯粹理论上的讨论；并且，两个电铲向一个卸点的运量一 定要相等(满车运输条件)，对矿石运量品位难以保证。穿梭运输法属排时法的变种，无论 安排得怎样周密的计划一旦实际生产起来，就会被随机性弄得乱七八糟。所以在实际问题 面前，这种方法不能说是有效的。总的来说，今年 B题的所有参赛队整体上做的不错，获各奖项的答卷之间相差不是很 大。但是也许是时间的原因，非常好的答卷不多。参考文献：1 谢金星，邢文训网络优化 M 北京：清华大学出版社，2 0 0 3 Th e M o d e l a n d Co mme n t a r y o f Tr u c k Pl a n n i ng f o r a n Op e n c a s t I r o n Mi n e F A G P e i c h e n LI Le i (J i l i n U n i v e r s i t y，C h a n g c h u n 1 3 0 0 2 5)S u mma r y：Th i s p a p e r b a s e s o n t h e i n f o r ma t i o n f r o m t h e ma r k i n g p r o c e s s o f CUMCM 一2 0 0 3 P r o b l e m B：Tr u c k P l a n n i n g f o r a n Op e n c a s t I r o n M i n e，t O d i s c u ss s o me c r i t i c a l i ssu e s i n t h e c h e c k u p p r o c e s s o f CUMCM 一2 0 0 3 P r o b l e m B a n d t O g i v e a b a s i c s o l u t i o n mo d e l f o r t h e p r o b l e mAt t h e s a me t i me，we p r ese n t t h e b a c k g r o u n d o f t h e p r o b l e m a n d ma n y o t h e r sol u t i o n me t h o d s 维普资讯 http:/