文摘
本文地址一个特殊的露天矿卡车调度问题不同的运输收入的考虑。混合整数规划模型制定清晰地定义问题和一些有效不等式推导出加强模型。一些属性和两个上界问题的提出。基于这些不平等、属性和上界,提出了一种启发式解决方案方法的两种改进策略解决问题,数值实验表明该方法是有效和高效的解决方案。
1。介绍
在一个露天矿山,卡车是一种至关重要的设备进行几乎所有的矿石和废石运输(1]。通常情况下,材料的卡车装载满载(也许矿石、煤矸石、或其他覆盖矿石和废石需要搬走了)在电动挖掘机,传输倾销仓库,将其加载材料,然后返回到铲进行下一轮。图1举例说明了一个露天的照片和一个简化的地图在露天矿道路网络。所有材料的加载点,每个配备电动挖掘机,和倾销仓库是相对稳定而卡车运输材料从不同的加载和卸载在不同仓库(2]。有效的卡车调度不仅可以减少卡车运输成本也增加我铲利用率和生产率(1]。
(一)一个露天矿山
(b)一个露天道路网络的示意图代表了加载点和,,代表了倾销仓库
有很多研究发布在运筹学在露天矿山,但大多数集中在矿井设计和生产计划(3坑),如战略极限设计问题(4- - - - - -7]和战术block-sequencing问题[8- - - - - -11]。在研究战术和操作在露天矿山装备配置,设备一直强调的随机特性。排队论和模拟都作为随机方法模型和分析露天生产调度问题,特别是在早期的文献发表。例如,枢纽和Ramani12)模拟卡车运输过程中初始化卡车调度研究。Kappas和Yegulalp13]利用排队理论,结合扩展马尔可夫链的原理,分析典型的truck-shovel系统的稳态性能和估计其操作参数。Oraee和Asi (14模拟生产过程的卡车和铲子在军铜矿在伊朗,考虑模糊参数对每一铲。Najor和哈根15)关注truck-shovel系统随机行为和提供了一个基于排队论模型和分析。他们的分析表明,生产力可以因为俯瞰排队高估了8%。
在一些露天设备路由和选择模型,优化方法,也就是说,整数规划和动态规划,用于确定机队规模和分配3]。例如,白色和奥尔森(16)应用网络模型、线性规划和动态规划方法,卡车调度问题,提出了一个可行的卡车调度系统。他们把问题分为三个阶段。第一个是决定矿井中的所有位置之间的最短路径,这实际上是一个最短路径的问题。在下一阶段,线性规划是用来确定材料流沿着这些路径。最后,动态程序分配卡车铁锹和转储之间的优化路径。他们的卡车调度系统不仅会产生巨大的(10 - 20个百分比,在大多数情况下)生产率的提高也产生影响卡车调度理论的三阶段过程(17]。和阳et al。18采用三级过程解决卡车调度问题。
在本文中,我们考虑各种运输收入不同材料装载点和解决路径规划和塔克调度问题。
本文的概述如下。部分2描述了考虑露天卡车调度问题不同的卡车运输收入详细并提供它的整数规划模型。节3,一些有效的不平等,两个最优解的性质,提出了两个上界问题。节4提出了两种改进策略的启发式方法来解决这个问题。部分5测试该上界和解决方案的方法。部分6总结了纸。
2。问题描述和数学模型
2.1。问题描述
在露天,通常有几个加载点和倾销仓库(后来被称为转储),如图1。在每个装载点,总有一堆松散矿石,煤矸石、或废石(称为集体材料),自装载点需要一个松动爆破开挖前操作开始。每个加载点被认为是配备一个且只有一个电动挖掘机(不失一般性,它将被视为两个不同的加载点装备如果两个铲子)。电动挖掘机挖掘和装载松散材料到卡车在每个装载点和与其自卸卡车卸载本身设备在一个垃圾场。类似于装载点,我们假设一个转储只能容纳一个卡车同时和多个装车的卸货区位置将被视为不同的转储。
值得注意的是,电动挖掘机(或装载点)在同一时间只能加载一个卡车和一个转储同时只允许一个卡车。通常会有公园附近等待卡车操作电动挖掘机或转储。它实际上是关键任务减少卡车等待时间在传统的卡车调度问题。
在我们的考虑问题的场景中,一辆卡车的材料从不同的装载点给出不同的运输收入和我们的优化目标就等于总运输收入完成调度地平线。收入/装车(材料的运输卡车)不同的装载点总是由管理和决策决定的基础包括两个方面的考虑:可能的传输距离和传输优先级。前者是容易理解由于更长的距离总是引起更多的运输时间,因此应该得到更多的收入。传输优先级来自开采顺序,从未被建模为一种约束在传统研究[1,3)和/或不同的市场需求。每装车运输收入可以被视为产品可能的传输距离和传输优先级。
从的角度调度器负责卡车调度决策的转变(8小时),我们的目标是最大化运输收入根据给定的收入总额/装车。决策包括转储以及卡车的路由选择。转储选择是几乎一样的第一阶段决策在文献[16,18),决定我的所有位置之间的最短路径。
约束被认为包括以下:(1)承载能力约束:每个铲(加载点)只能加载一个卡车同时,(2)卸货能力约束:每个转储可以卸载卡车在同一时间,只有一个(3)转储选择约束:一组候选转储给出每个加载点和装载点的材料必须被转储的候选人。
2.2。混合整数规划模型
定义和制定明确的问题,以下符号需要引入代表所有装载点,转储,材料要加载的加载点,卡车,路径参数,等等: :设置可用的电动铲子(加载点),, :,0表示虚拟的铲子, :设置可用的卡车, 每卡车的材料:收入电动挖掘机,, :组候选人转储相应材料(矸石或煤)在电动加载铲,, :包括所有转储, :地平线上考虑问题, :最大数量的卡车载荷电动挖掘机最多可以完成在地平线,, :可能的卡车,设置电动挖掘机的岩(煤)负载,, 材料:一辆卡车装载铲,,,以下简称装车, :,表示虚拟装车, 装货时间:每车电动挖掘机,, :每卡车在仓库卸货时间,, :时间一个空卡车从仓库去铲,,, :时间一辆满载的卡车将形成铲到仓库,,, :时间的卡车从其铲的初始位置,,, :非常大的+号。
代表转储选择和卡车调度决策,我们引入以下决策变量: 完成装货时间材料吗,因为,; 完成卸货的时间材料吗,因为,。
基于上面的符号,可以制定以下问题整数规划模型(类似于唐模型等。19)涉及一辆卡车调度问题在集装箱码头):
目标函数(2)模型的总运输价值最大化,也就是说,运输收入的总和所有卡车载荷卸载的地平线。约束(3)可以提供每个卡车之间有足够的加载时间及其相邻的卡车在同一个铲下。同样,约束(4)确保足够的时间来卸载材料之间的两个相邻卡车不断倾倒在同一仓库。约束(5)保证每个车都有足够的旅行时间运输材料从参与铲得宝而约束(6)为卡车提供足够的空旅行时间返回下一个推土机。约束(7)保证每个卡车从它的初始位置和储备足够的空旅行时间达到第一个加载点相关铲开始前卡车装载作业。约束(8)定义的变量;也就是说,设置如果装车可以完成在地平线上吗。约束(9)和(10)保证每个有效的装车()被分配给一个且只有一个卡车和卡车可以连续操作。约束(11)防止卡车装载自身环。约束(12)状态,有且只有一个装车作为头(去年)为每个可用的卡车装车。类似于约束(9)和(10),约束(13),每个有效装车分配给一个且只有一个仓库运作不断得宝,每个倒垃圾。约束(14)执行相同的约束(11),禁止在卸载自身环序列。类似于约束(12),约束(15)状态,有且只有一个装车作为每个倾销的头(去年)卡车仓库。约束(16)定义变量之间的关系和;也就是说,每个有效装车都有且只有一个倾销仓库。
3所示。有效的不平等、财产和上界的问题
3.1。有效的不平等
在本节中,介绍了一些有效的不平等。问题的定义,模型部分2.2已经足够和有效的不平等都是多余的,但他们可以直接减少计算时间,如果我们试图解决模型通过商业优化软件,如最大化策略。此外,有效的不平等也有利于构建启发式方法。
3.1.1。电动挖掘机产能不平等
考虑
不平等(17)给出了最大数量的卡车每个电动挖掘机可以完成在地平线上。的不平等,实际期限铲吗,在那里最近的时间是空的卡车从它的初始位置移动到铲吗,最不可能的次铲开始第一次装车,允许至少保留时间运输和卸载最后卡车装载铲吗。
3.1.2。卸货能力不平等
考虑
不平等(18)给出了最大数量的卡车每个卸货仓库可以卸载在地平线上。的不平等,是仓库的实际时间限制吗,在那里是最早可能在仓库卸货时第一个卡车开始吗。
3.1.3。变量之间的关系不平等
考虑
不平等(19)来自于材料运输序列所保证的公式(3),卡车装载注定要运输吗当站。
3.2。最优解的性质
上述定义露天卡车调度问题;我们观察两个属性最优解决方案。需要引入一些新的概念来描述属性。
定义1。空卡车,从一个仓库,,一把铁锹,,加载材料(铲),运输到仓库和卸载的材料(例如,从转储加载点和在图2)。整个运动过程被称为卡车往返,用旅行。
值得注意的是最后得宝参与卡车往返可以开始得宝一样。
定义2。对于任何一辆卡车往返,,,,被称为旅行交通价值。
粗略地说,这次旅行交通价值可以看作是卡车运输收入单位时间对于一些卡车往返。有一个直观的建议从卡车的定义应该被派往更高的旅行旅行交通工具价值。
定义3。卡车操作时间,不包括以下三类宝贵的时间,被称为有价值的时间:(1)时候,卡车等在电子铲加载由于另一个卡车占据相同的铲,(2)时候卡车在仓库等待卸货卡车由于另一个占据了仓库,(3)时间未完成往返如果一辆卡车不能卸载它最后装车在地平线上。
值得注意的是卡车被假定不旅行时间超过给定的旅行时间(和通过路径)。
属性1。如果每个卡车的初始位置是一个仓库,一个可行的解决方案的客观价值等于联合问题 在哪里卡车表示总宝贵的倍有花在旅行上解决方案和表示所有卡车往返的集合。
问题目标函数的属性提供了另一种配方,将发挥重要的作用在构建的上界。
属性2。在共同问题的可行解,总宝贵的时间花在卡车往返,,,不是比,在那里和表示电子铲的最大承载能力和最大的卸货能力转储,分别。
3.3。上界
因为每个电子铲载荷的卡车数量可以完成在地平线上是有限的,是很明显的低于上限的问题。
3.3.1。上限1
的客观价值不能超过最优解。
针对卡车运输能力和铲装载能力,另一个可以获得更多收紧上限。让表示可用卡车的数量;然后表示总的可用卡车次参与问题。让表示的最优卡车往返涉及铲,;也就是说,旅行需要最短的有价值的卡车次旅行,运输材料从铲一个可用的转储,和表示所需的宝贵的卡车运输值对应的旅行时间和旅行,分别。
假设铲降序的顺序吗;也就是说,和。
上限2可以清楚的描述和制定,根据上面的符号和假设。
3.3.2。上限2
最优解决方案的客观价值不得超过以下分段函数值:
上界的基本想法是,应该派车电子铲和往返运输价值尽可能高总收益最大化。
4所示。启发式解决问题的方法
4.1。一个建设性的启发式方法生成初始解
在实际调度过程中,卡车等待时间往往是不可避免的,因此期望实时传输值的概念介绍。
定义4。在实际卡车调度,,,,,,称为实时传输值(ERTV)可能卡车往返选择,是预期的卡车等待时间(宝贵的卡车次)在整个旅行。
基于上述定义,一个建设性的启发式方法可以介绍给生成初始解。它包括以下步骤。
一步A1。构建一套卡车,包括所有卡车不分配给一个往返或刚完成往返的调度,并设置包括所有的卡车在初始状态。
构建一套卡车,让在最初的状态。
建立一个卡车调度信息表,一把铁锹调度信息表和调度信息表。初始化三个信息表,,。
A2步。如果,对于每个卡车构造相应的往返,计算预期实时传输值的当前状态(指,,),并记录最高的旅行ERTV及其ERTV;否则,去一步。
一步A3。选择ERTV最高的卡车,将其分配给记录最优旅行一次,并决定加载操作的起始时间尽可能早地根据预期卡车到达时间和涉及铲可用时间。计算的完整的卡车和铲在分配的往返。
删除的卡车。如果获得旅行完成时间是在给定的地平线,附加卡车的分配和时间信息,铲,转储,,分别和附加的卡车。
去一步。
一步A4。如果最早的旅行完成时间,选择一辆卡车、删除的卡车,并将它附加到;否则,输出电流,,和停止。
上述几乎启发式模拟设备运行过程中,尤其是卡车操作,因此可以被称为基于仿真的解决方案建设的方法。也适当的在线调度场景通过取代上述仿真过程与实际生产过程。
4.2。两种改进策略
通过观察在属性和上界以及分析上面的启发式方法,提出了两种改进策略改善初始解。
策略1(铲能力再平衡战略)。策略1参考序列定义铲吗降序排列的(见部分3所示。3)。因为最初的卡车的位置可以远离高的铲这些铲子,策略应该分配更多的卡车为目标的追求。
战略的步骤1列出如下。
一步B1。让和当前铲。
B2步。检查铲调度信息表在当前的解决方案,并计算出总空闲的时候铲毕业后第一次装车。让表示计算空闲时间和让表示的集合分配给铲的卡车。
B3步。如果一开始,重新分配卡车铲从通过重复,重新安排计划总卡车常规步骤在最初的解决方案方法,删除这些重新分配卡车从卡车组。注意,较低的卡车ERTV应调离为主。
B4步。如果,设置,,去一步;否则,终止。
策略2(邻居交换策略)。策略2是一个简单的邻居交换策略。它包括以下步骤。
步骤c₁。集卡车集。让表示任何卡车和删除从。
一步C2。让表示集卡车往返执行的卡车。
集。
C3步。尝试重新分配卡车往返其他铲子和修改涉及卡车调度。如果有重新分配,能带来一个改进,接受改变。
C4步。如果,设置然后转到步骤。
一步C5。如果,以一个新的卡车从并返回到步骤;否则,终止。
5。计算实验
测试性能的数学模型和提出的启发式方法制定改进策略,我们补充了所有相关程序vc++开发环境下的2010年,部分中的整数规划模型来解决2最大化策略,一种优化软件。实验都是在电脑上执行2赢得7操作系统和2.8 GHz Intel核心CPU和4 GB RAM。
数值试验中的数据来自于一个实际露天矿。数据包括8问题实例但我只涉及两种不同的路径配置由于相对恒定的露天道路网络。表1实例显示的细节问题,包括路径配置(路径),问题实例ID(问题)的卡车数量(卡车)、铲子(铲),和数量的转储(转储)。调度地平线是一个转变,8小时,所有实例。
材料产品的每卡车运输收入预期的最短的距离和加载点的优先考虑的因素。优先级因子范围在生产调度。truck-shovel系统,卡车容量通常是稀缺的铲子的承载能力。所有这些特性也反映在收集问题实例。
小尺寸的问题首先解决使用制定数学模型(最大化策略)和提出的启发式方法。小尺寸的问题实例的削减从实例路径配置在表1和21和调度地平线下降到2小时。每一个小尺寸的问题实例涉及2铲子,2转储,不同数量的可用的卡车。表2展示了实验结果与不同大小的问题(可用的卡车数量)。在表中,列路径和大小显示路径配置的数量和可用的卡车,分别。模型Model_Ineq Heu_Imp代表的数学模型,模型与不平等(17)- (19),分别与改进策略和启发式。
实际问题实例的实验结果列在表中3有问题的ID(问题)、客观价值的初始解(启发式)和改进的解决方案(改善),由发达两种改进策略,提高相对好转(相对imp),最好的上界(乌兰巴托),采用最大两个上界的部分3所示。3,获得优化解的相对偏差和上界。所有实例的计算时间不超过5 CPU秒,因此表中被忽视。
从表2,我们可以看到的数学模型是有效的但不是实际问题的大小。从表3我们可以观察到,平均相对偏差为4.46%,两种改进策略执行平均增加3.02%。实验表明,该上界是好的,发达的启发式方法与改进策略是有效的和有效的解决方案。对不同的问题和解决方案性能相对稳定构型。
6。结论
在本文中,一个特殊的露天卡车调度问题进行了研究。首先制定一个混合整数规划模型,考虑运输收入随不同的加载点。和一些有效的不平等,两个属性,并推导出两个问题的上界。基础上,提出了一种启发式解决方案方法的两种改进策略来解决这个问题。最后的数值试验表明,提出的方法是有效的和有效的解决方案。
利益冲突
作者宣称他们没有利益冲突有关的出版。
确认
本研究在一定程度上是由中国国家自然科学基金(71201105)和中国博士后科学基金会(2013 m530947)。