露天矿生产的车辆安排 、问题重述 露天矿里有若干个铲位,每个铲位已预先根据铁含量将石料分成矿石和岩 石。每个铲位的矿石、岩石数量,以及矿石的平均铁含量(称为品位)都是已知 的。每个铲位至多能安置一台电铲,电铲的平均装车时间为5分钟 卸点有卸矿石的矿石漏、2个铁路倒装场(以下简称倒装场)和卸岩石的岩 石漏、岩场等,每个卸点都有各自的产量要求。要求矿石卸点需要的铁含量在 个班次(8小时)内满足品位限制(假设要求都为29.5%±1%)即可。从长远看, 卸点可以移动,但一个班次内不变。卡车的平均卸车时间为3分钟。 所用卡车载重量为154吨,平均时速28km/h,每个班次每台车消耗近1吨 柴油,一个班次中只在开始工作时点火一次,原则上在安排时不应发生卡车等待 的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载 运输。每个铲位到每个卸点的道路不会出现堵车现象,每段道路的里程都是已知 的 个合格的计划要在卡车不等待条件下满足产量和质量(品位)要求,而 个好的计划还应该考虑下面两条原则之 1)总运量(吨公里)最小,同时出动最少的卡车,从而运输成本最小; 2)利用现有车辆运输,获得最大的产量(岩石产量优先;在产量相同的情况下 取总运量最小的解)。 要求就两条原则分别建立数学模型,并给出一个班次生产计划的快速算法, 包含以下内容:出动几台电铲,分别在哪些铲位上:出动几辆卡车,分别在哪些 路线上各运输多少次。请针对给出的实例(略),给出具体的生产计划、相应的 总运量及岩石和矿石产量。 模型假设: 1、每辆卡车满载石料154吨,平均时速28km/h,装载石料需要5分钟,卸石料 需要3分钟 、在一个班次内所有铲点和卸点的位置均是不变的,一个班次时间定为8小时。 3、其中矿石卸点需要有品位限制,即矿石卸点的含铁量要求为29.5%±1% 4、铲点和卸点均不能同时为两辆及两辆以上的卡车服务,如果多辆卡车同时出 第1页共20页
第 1 页 共 20 页 露天矿生产的车辆安排 一、问题重述 露天矿里有若干个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩 石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知 的。每个铲位至多能安置一台电铲，电铲的平均装车时间为 5 分钟。 卸点有卸矿石的矿石漏、2 个铁路倒装场（以下简称倒装场）和卸岩石的岩 石漏、岩场等，每个卸点都有各自的产量要求。要求矿石卸点需要的铁含量在一 个班次（8 小时）内满足品位限制（假设要求都为 29.5%± 1%）即可。从长远看， 卸点可以移动，但一个班次内不变。卡车的平均卸车时间为 3 分钟。 所用卡车载重量为 154 吨，平均时速 28km h ，每个班次每台车消耗近 1 吨 柴油，一个班次中只在开始工作时点火一次，原则上在安排时不应发生卡车等待 的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载 运输。每个铲位到每个卸点的道路不会出现堵车现象，每段道路的里程都是已知 的。 一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一 个好的计划还应该考虑下面两条原则之一： 1) 总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小； 2) 利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下， 取总运量最小的解）。 要求就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法， 包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些 路线上各运输多少次。请针对给出的实例（略），给出具体的生产计划、相应的 总运量及岩石和矿石产量。 二、模型假设： 1、每辆卡车满载石料 154 吨，平均时速 28km/h，装载石料需要 5 分钟，卸石料 需要 3 分钟。 2、在一个班次内所有铲点和卸点的位置均是不变的，一个班次时间定为 8 小时。 3、其中矿石卸点需要有品位限制，即矿石卸点的含铁量要求为 29.5%± 1%。 4、铲点和卸点均不能同时为两辆及两辆以上的卡车服务，如果多辆卡车同时出
现在同一点上,则需要等待。 5、应尽量避免卡车等待的情况出现,并作为一个基本原则予以考虑。 6、运输路线上不发生堵车,并且卡车在路上不停车 7、一个班次内不发生任何重大意外因素(如熄火、撞车、抛锚等)。 8、一个车辆安排计划应当在尽量避免等待的情况下,完成给定的产量和质量要 求 三、符号说明: 提供的铲点数量(实例中=10) J:提供的卸点数量(实例中J=5) K:提供的卡车数量(实例中K=20) 表示第i个铲点,i=1..I j:表示第j个卸点,j=1.J(实例中5个卸点分别表示:1.矿石漏;2.倒 装场I;3.岩场;4.岩石漏;5.倒装场II) k:表示第k辆卡车,k=1..K dn:从铲点i→卸点间的距离 n:在铲位→卸点间的运输时间 a:在一个班次中,在铲位i→卸点间可运输石料的卡车的数量 Pg:在一个班次中,一辆卡车在铲位i→卸点间可运输石料的次数。 need,:表示卸点j在一个班次中需要的产量 reality,:表示卡车在一个班次中真正运到卸点j的产量 provide_rock:表示铲点i在一个班次中可以提供的岩石产量 provide_iron:表示铲点i在一个班次中可以提供的矿石产量 quality:表示铲位i矿石的平均铁含量。 四、模型分析: 该问题主要是对一个多铲位和卸点的石料配送运输系统提供一动态即时车 辆指派与路径规划的控制方案,使其目标为在尽量避免等待的前提下,降低总的 运输成本和提髙产量。为有效的处理系统的目标,我们发现露天铁矿的铲位可以 看作服务提供商,卸点可以看作是用户,而我们现在需要解决的就是提出一个物 第2页共20页
第 2 页 共 20 页 现在同一点上，则需要等待。 5、应尽量避免卡车等待的情况出现，并作为一个基本原则予以考虑。 6、运输路线上不发生堵车，并且卡车在路上不停车。 7、一个班次内不发生任何重大意外因素（如熄火、撞车、抛锚等）。 8、一个车辆安排计划应当在尽量避免等待的情况下，完成给定的产量和质量要 求。 三、符号说明： I ： 提供的铲点数量 （实例中 I =10） J ： 提供的卸点数量 （实例中 J = 5 ） K ： 提供的卡车数量 （实例中 K = 20） i ： 表示第i 个铲点,i I =1K j ： 表示第 j 个卸点, j J =1K （实例中 5 个卸点分别表示：1.矿石漏；2.倒 装场 I；3. 岩场；4. 岩石漏；5. 倒装场 II） k ： 表示第k 辆卡车, k K =1K ij d ： 从铲点i j ®卸点 间的距离 ij t ： 在铲位i j ®卸点 间的运输时间 ij a ： 在一个班次中，在铲位i j ®卸点 间可运输石料的卡车的数量 ij p ： 在一个班次中，一辆卡车在铲位i j ®卸点 间可运输石料的次数。 j need ：表示卸点 j 在一个班次中需要的产量 j reality ：表示卡车在一个班次中真正运到卸点 j 的产量 provid _ i e rock ：表示铲点i 在一个班次中可以提供的岩石产量 provid _ i e iron ：表示铲点i 在一个班次中可以提供的矿石产量 qualityi：表示铲位i 矿石的平均铁含量。 四、模型分析： 该问题主要是对一个多铲位和卸点的石料配送运输系统提供一动态即时车 辆指派与路径规划的控制方案，使其目标为在尽量避免等待的前提下，降低总的 运输成本和提高产量。为有效的处理系统的目标，我们发现露天铁矿的铲位可以 看作服务提供商，卸点可以看作是用户，而我们现在需要解决的就是提出一个物
资(矿石或岩石)的配送运输措施。这样,我们可以近似的将这个问题看作是 个定位一运输问题,也就是说,每一个卸点可以根据自己的需求向不同的铲位提 出运输的请求,同时每个铲位也可以根据自己所能提供的服务能力(在本题中, 可以看作是每个铲位的石料是有限)向不同的卸点派出不同车次的运输车辆 根据所给的实例条件,我们得知,有10个服务商(其中最多只有7个可同 时提供服务),5个用户(如下图所示) 图一:本题可以看作是10(7)5的定位运输问题 个车辆安排计划应当以自己可以提供的能力来满足卸点产量要求,于是我 们分析出方案的限制条件是 1、应该尽量避免发生卡车等待情况的发生 2、卸货点所卸货的总产量大于等于所要求的供应量。 3、每个铲点的矿石总运输量不超过该铲点的实际矿石产量。 4、每个铲点的岩石总运输量不超过该铲点的实际岩石产量 5、每个矿石卸点品位限制为29.5%1% 6、设计方案的总卡车数不超过提供的卡车数量。 7、设计方案的总铲位数不超过提供的铲位数量。 五、模型的建立与求解 模型建立: 通过上面的模型分析,我们初步建立两种模型分别讨论 1、车辆模型(可归结为整数非线性规划) 2、车次模型(可归结为整数线性规划) 因为考虑到上述算法的的时间复杂度比较高,不适用于大网络的方案构造 我们基于上面两个模型的基础上建立了内外圈模型。在这种算法的指导下,我们 给出了一种较好的快速算法。 当然评价一个好的方案的重要原则是尽量保证不等待,为了衡量一个方案满 足这个原则的程度,我们引入了冲突率的概念: 冲突率=所有卡车等待的总时间/所有卡车工作的总时间 车辆模型: 车辆模型是一个以车辆为基础来考虑的模型,这个模型基于下面的假设: 假设一辆卡车在一个班次里只能在固定的两点之间完成运输任务,即一个确 第3页共20页
第 3 页 共 20 页 资（矿石或岩石）的配送运输措施。这样，我们可以近似的将这个问题看作是一 个定位—运输问题，也就是说，每一个卸点可以根据自己的需求向不同的铲位提 出运输的请求，同时每个铲位也可以根据自己所能提供的服务能力（在本题中， 可以看作是每个铲位的石料是有限）向不同的卸点派出不同车次的运输车辆。 根据所给的实例条件，我们得知，有 10 个服务商（其中最多只有 7 个可同 时提供服务），5 个用户（如下图所示）： 图一：本题可以看作是 10(7)— 5 的定位运输问题 一个车辆安排计划应当以自己可以提供的能力来满足卸点产量要求，于是我 们分析出方案的限制条件是： 1、应该尽量避免发生卡车等待情况的发生。 2、卸货点所卸货的总产量大于等于所要求的供应量。 3、每个铲点的矿石总运输量不超过该铲点的实际矿石产量。 4、每个铲点的岩石总运输量不超过该铲点的实际岩石产量。 5、每个矿石卸点品位限制为 29.5% 1%。 6、设计方案的总卡车数不超过提供的卡车数量。 7、设计方案的总铲位数不超过提供的铲位数量。 五、模型的建立与求解： 模型建立： 通过上面的模型分析，我们初步建立两种模型分别讨论： 1、车辆模型（可归结为整数非线性规划） 2、车次模型（可归结为整数线性规划） 因为考虑到上述算法的的时间复杂度比较高，不适用于大网络的方案构造， 我们基于上面两个模型的基础上建立了内外圈模型。在这种算法的指导下，我们 给出了一种较好的快速算法。 当然评价一个好的方案的重要原则是尽量保证不等待，为了衡量一个方案满 足这个原则的程度，我们引入了冲突率的概念： 冲突率=所有卡车等待的总时间/所有卡车工作的总时间 车辆模型： 车辆模型是一个以车辆为基础来考虑的模型，这个模型基于下面的假设： 假设一辆卡车在一个班次里只能在固定的两点之间完成运输任务，即一个确
定的铲位和一个确定的卸点。 问题 于是根据上面的分析,我们可以将模型描述成一个整数非线性规划问题 模型分析中的限制条件可以用一些不等式来表示,这里要使不冲突,其中 个必要但不充分的条件是在铲点总车辆次数不超过480/5=96次;在卸点总车辆 次数不超过480/3=160次,故而加上上面的6个限制条件可以描述成一个整数非 线性规划问题 ∑∑aP reay=154×∑a1Pn2med 154×∑ a,p s provide rock j为岩石点 154×∑anP1≤powl_mon,/为矿石点 480 P li 28.5%≤ ≤30.5% 4×P ∑sgn∑a)≤7sgn(x)为符号函数 480 Pi 480 a. x P 160 0 Z 上面的规划还并没有完全考虑到冲突问题,为了考虑冲突问题,我们引入了 以下的优化方案: 单路线避免冲突方案: 在固定一个装车点和卸车点的情况下,车辆行驶两点之间的时间为x。 如图所示,假设在这单条路线上可以允许n辆车工作,那么他们不冲突的条件是: 5smin(d)≤∑d1=(5+x+3+x)=-(8+2x) 第4页共20页
第 4 页 共 20 页 定的铲位和一个确定的卸点。 问题一： 于是根据上面的分析，我们可以将模型描述成一个整数非线性规划问题： 模型分析中的限制条件可以用一些不等式来表示，这里要使不冲突，其中一 个必要但不充分的条件是在铲点总车辆次数不超过 480/5=96 次；在卸点总车辆 次数不超过 480/3=160 次，故而加上上面的 6 个限制条件可以描述成一个整数非 线性规划问题： : 154 154 _ 154 _ 480 8 . . ij ij ij i j j ij ij j i ij ij i j ij ij i j ij ij Min apd reality a p need a p provide rock j a p provide iron j p d s t 154´ = ´ ³ ´ £ ´ £ £ + åå å å å 为岩石点 为矿石点 2 60 28 ( ) 28.5% 30.5% sgn( ) 7 sgn( ) 20 480 96 5 480 160 3 0 ij ij i i ij ij i ij i j ij i j ij ij j ij ij j ij a p quality a p a x a a p a p c ´ ´ ´ ´ ££ ´ £ £ ´ £ = ´ £ = ³ å å å å åå å å 为符号函数 ij c ì ï ï ï ï ï ï ï ï ï ï ï ï ïï í ï ï ï ï ï ï ï ï ï ï ï ï ï ï ÎZ î 上面的规划还并没有完全考虑到冲突问题，为了考虑冲突问题，我们引入了 以下的优化方案： 单路线避免冲突方案： 在固定一个装车点和卸车点的情况下，车辆行驶两点之间的时间为 x 。 如图所示，假设在这单条路线上可以允许n辆车工作，那么他们不冲突的条件是： ( ) ( ) 1 1 1 1 5 min( ) 5 3 8 2 n i i i d d x x x n = n n £ £ å = + + + = +
这里d表示相邻两辆车的行驶时间。(=1.n) 8+2x 即 故取:n y=[x]为取整函数 利用这个公式我们可以得到下面的一张表: 固定采矿点和卸矿点所对应的最大可放置卡车数: 5678910 矿石漏665 倒装场1323 岩场666544 「岩石漏 2352 252 「倒装场2 行:卸点,列:铲位 我们以上面的最大卡车数作为一个约束准则,限制了卡车的单线数量,这对方案 的求解有帮助 多路线避免冲突方案: 通过上面单路线方案的启发,我们试图扩展到多路线的避免策略,但是我们通过 模拟发现当考虑两条路线冲突状况时,等待则是无法避免的。而且当时间长度足 够大时,无论两个时间周期如何交错并不会影响冲突率的大小,故我们打算以一 个评价函数∫(xym,n)来进行计算两条路线的冲突率。 ∫(x,ym,n)表示m辆卡车在1路线和n辆卡车在2路线开时交汇点的冲突率。 这里x表示1路线上的行驶时间,y表示2路线上的行驶时间 我们可以采用的是蒲丰投针实验模拟计算冲突率 算法步骤如下 1、计数器清零 2、设定时间从0-480分钟,进行随机投针以考察某一个时刻是否冲突。 3、周期性地安排时间表,并加一个随机变量来影响时间表的排布,如果在抽样 时刻中,时间表位于等待的状态,计数器累加一,否则不加。 4、转到3,安排下一辆卡车的实验,直到对m辆1路线车和n辆1路线车全部做 完为止。 5、如果计数器大于等于2,则说明有冲突现象出现,冲突次数累加器加一,否 则就不冲突。 上面的算法执行多次就可以得到冲突率 通过评价函数的计算,我们可以用定阈值的方法限制冲突率,在阈值以上的冲突 率可以考虑不接受,否则就接受。 第5页共20页
第 5 页 共 20 页 这里di表示相邻两辆车的行驶时间。(i n =1... ) 即： 8 2 5 x n + £ 故取： 8 2 5 x n é ù + = ê ú ë û y=[x]为取整函数 利用这个公式我们可以得到下面的一张表： 固定采矿点和卸矿点所对应的最大可放置卡车数： 1 2 3 4 5 6 7 8 9 10 矿石漏 6 6 5 5 4 3 3 3 2 2 倒装场 1 3 2 3 2 2 3 2 3 4 4 岩场 6 6 6 5 4 4 3 3 2 2 岩石漏 2 3 2 3 3 3 5 4 5 6 倒装场 2 5 4 4 4 3 4 2 2 2 2 行:卸点，列:铲位 我们以上面的最大卡车数作为一个约束准则，限制了卡车的单线数量，这对方案 的求解有帮助。 多路线避免冲突方案： 通过上面单路线方案的启发，我们试图扩展到多路线的避免策略，但是我们通过 模拟发现当考虑两条路线冲突状况时，等待则是无法避免的。而且当时间长度足 够大时，无论两个时间周期如何交错并不会影响冲突率的大小，故我们打算以一 个评价函数 f ( xymn ,,, ) 来进行计算两条路线的冲突率。 f ( xymn ,,, ) 表示m辆卡车在 1 路线和n辆卡车在 2 路线开时交汇点的冲突率。 这里 x表示 1 路线上的行驶时间， y 表示 2 路线上的行驶时间 我们可以采用的是蒲丰投针实验模拟计算冲突率。 算法步骤如下： 1、计数器清零 2、设定时间从 0~480 分钟，进行随机投针以考察某一个时刻是否冲突。 3、周期性地安排时间表，并加一个随机变量来影响时间表的排布，如果在抽样 时刻中，时间表位于等待的状态，计数器累加一，否则不加。 4、转到 3，安排下一辆卡车的实验，直到对m辆 1 路线车和n辆 1 路线车全部做 完为止。 5、如果计数器大于等于 2，则说明有冲突现象出现，冲突次数累加器加一，否 则就不冲突。 上面的算法执行多次就可以得到冲突率。 通过评价函数的计算，我们可以用定阈值的方法限制冲突率，在阈值以上的冲突 率可以考虑不接受，否则就接受