By Chi Zhang
R&D Division, Hitachi America, Ltd.
In mining operations, huge quantities of ore and waste material at mine sites are transported using extremely large equipment 24 hours a day. Material transportation represents up to 50% of operating costs in open pit mining *1. In order for mining companies to have sustainable and economical mining operations, they must do two things: (i) Constantly improve what is known as overall equipment effectiveness (OEE) for their field equipment (ii) Reduce operating costs. In the last decade, the focus has been on operating cost reduction, and it has been mainly achieved by increasing the capacities of the equipment. Nowadays, with limited budgets the focus is on improving OEE, where due to huge equipment operational costs, even small gain in operational efficiency can result in savings of 10s-100s million dollars depending on the mine size. Improvement in OEE can be primarily achieved by two means: (i) increase availability of equipment (ii) increase utilization of available equipment. We focus on the latter problem, i.e., increasing equipment utilization by better planning and optimal management of the equipment.
Major components of material handling are trucks, shovels and loaders. Shovels and loaders are responsible for loading the trucks. Shovels are extremely large and slow-moving equipment usually located at digging site, while loaders are more mobile and located at stockpiles. Trucks usually haul material from loading areas to one of three types of destinations determined by material type and quality: (i) waste - from digging site to dump area (ii) ore - from digging site to stockpile or crusher (processing plant) (iii) ore - from stockpile to crusher. One complete hauling cycle consists of productive as well as non-productive truck activities (see Figure 1). Productive truck activities during the haul cycle are done in following order: driving empty from dump to shovel/loader; spotting (positioning) at shovel/loader; loading by shovel/loader; hauling to dump area; dumping. In terms of utilization, queuing is a major non-productive activity for trucks. Queues can be formed in front of both shovels/loaders and dump areas. For shovels, the major non-productive activity is starvation, i.e., waiting for trucks to arrive. Therefore, in order to reduce non-productive activities, truck queuing and shovel starvation should be reduced. Our approach to increase utilization is to reduce time spent in non-productive activities by combining machine learning with optimization and simulation.
Figure 1: Truck activities in a haul cycle during mining operations
All equipment activities involved in material transportation are monitored and controlled by dispatchers where goal is to meet daily targets at the lowest cost. Unfortunately, complex environments such as open pit mines and their stochastic nature are not amenable to optimal human decision making. Hence, many companies use fleet management software which includes optimizations for truck allocation(assignment) *2, *3 and dynamic (real-time) dispatch *4, *5. Truck allocation approaches usually determine optimal number of trucks and their assignment to logical routes with the objective of reaching shift targets. A logical route is a pair of loading location (shovel, loader) and dumping area. In some cases, once trucks are assigned to the routes, dynamic dispatch algorithm dynamically changes truck allocation while shift progresses in order to further reduce non-productive time. There are several practical and technical shortcomings with current allocation approaches such as simply using historical average of equipment activity duration, ignoring queuing effects during optimization, or lacking tools to validate the decisions, which all lead to sub-optimal solutions.
To resolve the above issues, we proposed a new approach with the following advantages:
- Using a multi-run simulation, it is possible to estimate confidence with which production targets will be met given a truck allocation.
- Our optimization algorithm and simulation are general and not limited to the choice of non-negative probability distributions for predictors of activity times, neither to the type of the predictors.
- Simulator can be used as standalone application for other purposes such as off-line dispatcher training.
First let us denote S as total number of shovels, D as total number of dumps, and F as total number of truck fleets (or hauling sizes). The overall goal is to minimize number of trucks such that utilization of shovels is above the given threshold. If we let x (s, d, f) be number of trucks from the fleet (hauling size) f traveling between shovels and dump area d, the optimization problem is mathematically expressed as
where U (s) is utilization of shovel s, cs is a pre-specified positive constant between 0 and 1 which controls minimum accepted utilization of shovels, N (f) is the number of trucks from the fleet(hauling size) f , and R is a specified set of nonviable triplets (s, f ,d) that addresses the above-mentioned shovel matching problem and road constraint.
Specifically, we solve the problem in the following manner:
• Activity durations: We developed new predictors of activity times, which are modeled using generalized linear models. Generalized linear models (GLMs) enable us to restrict output distributions of activity duration to be positive (time is always positive), and allow useful predictors to be incorporated. Also, GLMs are easy to interpret. Doing this, better truck allocation solutions are achieved because more accurate predictions are involved in the optimization, instead of simple historical averages which is a common practice. In addition, GLM and other machine learning models are suitable for testing what-if scenarios during planning. It is worth noting that, our solution is not restricted to the use of GLMs.
Our truck allocation algorithm uses optimization along with simulator outputs to find solution which satisfies production targets with certain confidence. Simulation outputs are used as a part of the truck allocation algorithm to incorporate impact of queuing, which none of the previous approaches have taken into account.
• Initial guess: In order to avoid searching over all possible number of trucks that can be used in the mine as well as all possible truck assignment we start from the initial guess for minimum number of trucks based on optimization using expected values and neglecting queuing effect. To reduce computation complexity, we applied linear programming to solve this problem and obtain minimum number of trucks and their assignment by rounding.
• Re-assignment of trucks: For the case that current truck assignment solution does not meet confidence requirements additional trucks and new optimization problem are introduced. New optimization is constrained such that only one new truck can be added to a shovel. The objective of new optimization is to maximize shovel utilization for a given number of trucks. Integer programming is used to obtain assignment which can be passed to the simulator.
• Mine simulator for dispatcher validation: Dispatcher can compare his/her own intuition against proposed truck assignment by running simulations and comparing the simulator outputs. These are the what-if scenarios provided by our system, which represent different truck assignments. In order to use simulation outcomes for planning or dispatcher training purposes simulator outcomes should be as close as possible to reality. To build realistic simulator we support many features such as: dynamic dispatch, material transportation, equipment breakdowns, lunch breaks, etc.
An overview of the truck assignment system is showed in Figure 2.
Figure 2: Truck assignment system
Experiments are performed on real data generated by fleet management system in open pit mines. We obtained two years of data to demonstrate the improvements and benefits of our system compared to the current practices. We first evaluate the performance of generalized linear models as predictors of future activity times versus baselines which are used in practice today. Mean and random walk predictors are commonly used in practice and we use them as baselines. Results in Table 1 show that our GLM predictor can significantly outperform the baseline methods.
Table 1: Accuracy and coverage of predictors
Then we compare assignment approaches provided by dispatching software versus initial guess outcome. Initial guess optimization was for 90% utilization for all shovels. We simulated assignments calculated by our algorithm and actual assignments obtained from the fleet management database on 100 different randomly picked shifts. Simulation outputs are averaged across multiple runs as well as shift. Results are shown in Figure 3.
Figure 3: (a) average shovel utilization, (b) average truck waiting time, and (c) average number of trucks
used in actual assignment and initial guess optimization for shovel utilization 90%.
We also studied connection between truck waiting time and utilization by changing target utilization in initial guess optimization from 0.2 to 0.9 in steps of 0.1. When the utilization level increases, the effect of queuing is becoming dominant as number of trucks increases to achieve the target utilization level. For targeted utilization of 50% initial guess achieved average utilization of 54% with 0.47 hour of queuing per truck. This is about 10% better in terms of both shovel utilization and truck waiting compared to values reported for the assignments done by current dispatching software.
Lastly, we changed shovel target utilization from 0.5 to 0.9 in steps of 0.1, and set the required confidence to 90%. We calculate number of additional trucks needed to meet the confidence level. We also measured execution time of our algorithm to reach that confidence. Results are reported in Figure 4. Again, as utilization requirement increases more trucks are needed compared to initial guess. For utilizations of 80% and 90% utilization re-assignment optimization was invoked two times while for the rest cases only one time. Our algorithm took the longest time of about 30 seconds which is tolerable from operational perspective.
Figure 4: Number of additional trucks that is added by reassignment optimization step to achieve target utilization with 90% confidence.
We demonstrated novel approach for truck allocation in open pit mines which integrates machine learning, optimization and simulation. Our approach addresses stochasticity in travel times and queuing effect that were not previously addressed. Experimental results have shown benefit of using machine learning techniques to improve prediction accuracy of activity times in mining operation. Also experiments indicate that our approach can improve OEE by 10% when compared to the current dispatching software. The proposed solution is applicable to mines which use large numbers of shovels and dumps. This was achieved by using linear programming to approximate initial solution. Then initial solution was tuned to meet objective shovel utilization with a given confidence by using integer programming and simulation. We believe that integration of machine learning with operational research can make mines smarter and bring significant values to the mining industry.
In a previous blog post, dynamic dispatching with Reinforcement Learning in a manufacturing use case was discussed. In this post we showed how to solve scheduling problem using optimization and simulation for a mining use case. These two presents a comprehensive solution to optimizing stochastic operations. For more details, we encourage you to read our paper, Dispatch with Confidence: Integration of Machine Learning, Optimization and Simulation for Open Pit Mines
at SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2017.
References
*1 Meredith Augusta May. 2013. Applications of Queuing Theory for Open-Pit Truck/Shovel Haulage Systems, Master Thesis. Virginia Tech.
*2 Erkan Topal and Salih Ramazan. 2012. Mining truck scheduling with stochastic maintenance cost. Journal of Coal Science and Engineering (China) 18, 3 (2012), 313-319.
https://doi.org/10.1007/s12404-012-0316-4
*3 Shuxing Li and Peter Knights. 2009. Integration of real options into short-term mine planning and production scheduling. Mining Science and Technology (China) 19, 5 (2009), 674-678.
*4 St. ľphane Alarie and Michel Gamache. 2002. Overview of Solution Strategies Used in Truck Dispatching Systems for Open Pit Mines. International Journal of Surface Mining, Reclamation and Environment 16, 1 (2002), 59-76.
*5 Robert F. Subtil, Diego M. Silva, and Julio Cesar Alves. 2011. A Practical Approach to Truck Dispatch for Open Pit Mines. In 35th APCOM Symposium.
