露天矿生产的车辆安排 、问题重述 露天矿里有若干个铲位,每个铲位已预先根据铁含量将石料分成矿石和岩 石。每个铲位的矿石、岩石数量,以及矿石的平均铁含量(称为品位)都是已知 的。每个铲位至多能安置一台电铲,电铲的平均装车时间为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，则说明有冲突现象出现，冲突次数累加器加一，否 则就不冲突。 上面的算法执行多次就可以得到冲突率。 通过评价函数的计算，我们可以用定阈值的方法限制冲突率，在阈值以上的冲突 率可以考虑不接受，否则就接受
模型求解: 在上面的模型中,我们可以看到这里的决策变量为an,Pn,约束条件是线性的, 而目标函数却是非线性的,故无法用单纯型算法实现 我们利用动态规划算法编程实现,算法流程图见附录I。 计算结果如下 共需要15辆卡车,最小的总运量为92236.8(吨公里) 分布路线图如下: 1(2 4+2(81) 2(85) 3 1(14 1(15) 装场Ⅱ 倒装场 图中+表示铲位 o表示卸点 第6页共20页
第 6 页 共 20 页 模型求解： 在上面的模型中，我们可以看到这里的决策变量为 ij a , ij p ，约束条件是线性的， 而目标函数却是非线性的，故无法用单纯型算法实现。 我们利用动态规划算法编程实现，算法流程图见附录 I。 计算结果如下： 一共需要 15 辆卡车，最小的总运量为 92236.8（吨公里） 分布路线图如下： 路线上标示的括号前的数字表示在该路线上承载运输工作的车辆数，括号中 的数字表示该路线上所发卡车所需承载的总趟数。 铲点冲突率： 1 2 3 4 5 6 7 8 9 10 19.1% 9.8% 20.1% 0 26.9% 0 0 0 20.8% 13.9% 铲点平均冲突率：15.8% 卸点冲突率： 1 2 3 4 5 0.5% 14.6% 11.2% 28.5% 2.6% 一班次的含铁量 矿石漏 30.46% 倒装场 1 30.47% 倒装场 2 29.62%
卸点平均冲突率:11.5% 问题二 当利用现有车辆运输时,例如本实例,有20辆车进行运输,通过我们上面 的程序是搜索不到可行解的,故避免冲突的可行解也自然不存在。因此本模型对 于解决问题二是不可能的。同时我们用蒙特卡罗仿真寻找15~19内的可行解,进 行2×10°次仿真,仅能搜索到一个可行解(当为17辆卡车时),所以我们可以基 本认为该模型对于任意给定的卡车数是无解的。于是这就促使我们去寻找更优秀 而更有效的模型。 模型优缺点: 该模型的优点 1、计划简单易操作,一旦路线分配完,卡车就可以在确定的铲点和卸点之间不 停的来回工作,直到完成任务为止。 2、冲突率容易计算,并易于避免冲突的发生 3、方案受随机性影响较小,稳定性较强。 该模型的缺点 1、安排的卡车数较多,所走总路线较长,矿厂的经济效益不高。 2、所安排的计划执行效率不高,铲点挖空后卡车就不工作,处于闲置状态。 车次模型: 不同于车辆模型,车次模型是一个以计算车次为基础来考虑的模型,车次允 许卡车走多条路线。例如一辆卡车可以在一段时间内走A路线,另一段时间走B 路线,而这一点在车辆模型中是不会出现的 为了描述该模型,引入车次的概念,一个车次代表一辆卡车在一条路线上工 作一次。铲点到卸点的车次安排表示应当在该路线上所安排的车次总数。 定义x为所安排的车次数量,于是类似上面的车辆模型,可以得到一个线性规 划 问题 我们得到类似于车辆模型的线性规划如下: 第7页共20页
第 7 页 共 20 页 卸点平均冲突率：11.5% 问题二： 当利用现有车辆运输时，例如本实例，有 20 辆车进行运输，通过我们上面 的程序是搜索不到可行解的，故避免冲突的可行解也自然不存在。因此本模型对 于解决问题二是不可能的。同时我们用蒙特卡罗仿真寻找 15~19 内的可行解，进 行 9 2´10 次仿真，仅能搜索到一个可行解（当为 17 辆卡车时），所以我们可以基 本认为该模型对于任意给定的卡车数是无解的。于是这就促使我们去寻找更优秀 而更有效的模型。 模型优缺点： 该模型的优点： 1、计划简单易操作，一旦路线分配完，卡车就可以在确定的铲点和卸点之间不 停的来回工作，直到完成任务为止。 2、冲突率容易计算，并易于避免冲突的发生。 3、方案受随机性影响较小，稳定性较强。 该模型的缺点： 1、安排的卡车数较多，所走总路线较长，矿厂的经济效益不高。 2、所安排的计划执行效率不高，铲点挖空后卡车就不工作，处于闲置状态。 车次模型： 不同于车辆模型，车次模型是一个以计算车次为基础来考虑的模型，车次允 许卡车走多条路线。例如一辆卡车可以在一段时间内走 A 路线，另一段时间走 B 路线，而这一点在车辆模型中是不会出现的。 为了描述该模型，引入车次的概念，一个车次代表一辆卡车在一条路线上工 作一次。铲点到卸点的车次安排表示应当在该路线上所安排的车次总数。 定义 ij x 为所安排的车次数量，于是类似上面的车辆模型，可以得到一个线性规 划。 问题一： 我们得到类似于车辆模型的线性规划如下：
im:154x∑∑x 154×)xn≥need, 154×∑x≤ provide_mck为岩石点 ∑x≤proi j为矿石点 ∑[xx(qulm;-0.305)≤0 ∑[xx(quli,-0.285)≥0 ∑gn∑x)≤7sgn(x)为符号函数 ≤20 480 ∑x ∑x≤ 480 0 ∈Z 可以发现这个模型和车辆模型有所不同,因为所有的不等式都是线性的,所 以这个模型就可以归结为线性规划问题,上面的线性规划是可以通过 Matlab规 划工具箱编程解决的。 考虑到整数规划编程的复杂度以及车次数取整对结果的影响较小,我们先对 上面的规划做实数线性规划,用 Matlab可以得到下面的结果 总运量:8.4829万吨公里车辆数:127141辆 但是这个方案是不可实现的,因为车辆不可以为实数,这一结果仅仅是一个 下界,也就是说任何安排计划不会小于上面的总运量和车辆数。为了解决整数规 划,我们对结果进行上取整,然后计算出相应的总运量,并调配出车辆安排方案。 计算结果如下 总运量:86314万吨公里 车辆数:13辆 车次图表安排如下: 第8页共20页
第 8 页 共 20 页 : 154 154 _ 154 _ [ ( 0.305)] 0 . . ij ij i j ij j i ij i j ij i j ij i i Min x d x need x provide rock j x provide iron j x quality s t 154´ ´³ ´ £ ´ £ ´ - £ åå å å å å 为岩石点 为矿石点 [ ( 0.285)] 0 sgn( ) 7 sgn( ) 20 480 96 5 480 160 3 0 ij i i ij i j ij i j ij j ij j ij ij x quality x x a x x x c ì ï ï ï ï ï ï ï ï ï ï ´ - ³ ïï í £ ï ï ï £ ï ï ï £= ï ï ï £= ï ï ³ ÎZ î å å å åå å å 为符号函数 ï 可以发现这个模型和车辆模型有所不同，因为所有的不等式都是线性的，所 以这个模型就可以归结为线性规划问题，上面的线性规划是可以通过 Matlab 规 划工具箱编程解决的。 考虑到整数规划编程的复杂度以及车次数取整对结果的影响较小，我们先对 上面的规划做实数线性规划，用 Matlab 可以得到下面的结果： 总运量：8.4829 万吨公里 车辆数：12.7141 辆 但是这个方案是不可实现的，因为车辆不可以为实数，这一结果仅仅是一个 下界，也就是说任何安排计划不会小于上面的总运量和车辆数。为了解决整数规 划，我们对结果进行上取整，然后计算出相应的总运量，并调配出车辆安排方案。 计算结果如下： 总运量：8.6314 万吨公里 车辆数：13 辆 车次图表安排如下：
考石需 矿石漏 4 13 11 场 图中+表示铲位 o表示卸点 第9页共20页
第 9 页 共 20 页 13 辆卡车的情形 班次生产计划的快速算法见附录 II。 具体安排表如下： 车辆 任务 1 铲位 1—>岩石漏跑 44 次 2 铲位 3—>岩石漏跑 35 次 3 铲位 4—>倒装场 1 跑 37 次 4 铲位 2—>倒装场 1 跑 39 次 5 铲位 8—>矿石漏跑 29 次 6 铲位 9—>岩场跑 38 次 7 铲位 10—>倒装场 2 跑 47 次 8 铲位 1—>岩石漏跑 37 次，铲位 3—>岩石漏跑 7 次 9 铲位 4—>倒装场 1 跑 6 次，铲位 2—>倒装场 1 跑 2 次，铲位 2—>倒装场 2 跑 4 次 10 铲位 9—>岩场跑 32 次，铲位10—>岩场跑 7 次 11 铲位 8—>矿石漏跑 25 次，铲位 10—>矿石漏跑 5 次 12 铲位 2—>矿石漏跑 13 次，铲位 10—>矿石漏跑 6 次 13 铲位 10—>岩场跑 8 次，铲位 10—>倒装场 2 跑 33 次 考虑等待的模型： 我们在车辆模型中初步讨论了冲突率的问题，现在我们可以这样假设，如果 存在一个非常优秀的方案可以完全避免冲突，那应当首先满足上面所列的两个条 件： 1、到达铲点的总车次数£ 96 2、到达卸点的总车次数£160 考察这个方案对随机性影响下的冲突率，我们发现当相邻两辆车间隔为等间隔的 话是最能够避免冲突的，设两辆车之间的等间隔为d ，则有如下关系： n d = 5 + 480 这里n 为该铲点达到的车次数（针对考虑铲点）
即d d 5 d 5 下面假设对车次安排计划是可以以正态分布来影响车辆的变化的,那么模型就会 归结为下面几个算式 P(x1) 2丌δ x-(5+d P(x2) 则:P(x2-x1≤5)=J2v (卸点同理也能计算得到。) 可以看到,n越小,d越大,冲突率越低,所以我们可以推出这样的结论要想在 随机性影响下尽量避免冲突,应当使到达铲点的车次数量尽量小,因此在我们的 车次模型中可以通过增强上面所说的两个条件来达到避免冲突,也就是 增加一个(0,1)内的常数n来达到控制冲突的方法。 1、到达铲点的总车次数≤96×n 2、到达卸点的总车次数≤160× 480 ∑ x 480=160×1 模型求解: 我们令η=0.7,再通过 Matlab的优化工具箱进行运算,得到下面的结果: 第10页共20页
第 10 页 共 20 页 即 5 480 = - n d 下面假设对车次安排计划是可以以正态分布来影响车辆的变化的，那么模型就会 归结为下面几个算式： 2 2 2 1 2 1 ( ) d pd x P x e - = 2 2 2 [ (5 )] 2 2 1 ( ) d pd x d P x e - + - = 则： P(x2 - x1 £ 5) = · -• 5 1 2* è p *s „ - Hx-5-dL 2 4*s2 ‚x （卸点同理也能计算得到。） 可以看到，n 越小，d 越大，冲突率越低，所以我们可以推出这样的结论要想在 随机性影响下尽量避免冲突，应当使到达铲点的车次数量尽量小，因此在我们的 车次模型中可以通过增强上面所说的两个条件来达到避免冲突，也就是： 增加一个（0，1）内的常数h 来达到控制冲突的方法。 1、到达铲点的总车次数£ 96 ´h 2、到达卸点的总车次数£160 ´h 即 480 96 5 480 160 3 ij j ij j x x h h £ = ´ £ = ´ å å 模型求解： 我们令h = 0.7 ，再通过 Matlab 的优化工具箱进行运算，得到下面的结果：
