A Study on Truck Dispatching in Open Pit Mines

INTRODUCTION

Truck transportation in open-pit mining consists of transporting material (mineral matter) from pick-up stations (shovels) to distribution stations or dump points (crushers, waste dumps or stock piles) during a shift by haul trucks. Mineral matter is made up of ore (the most valuable mineral product), leach (small but positive) and waste (no value)[1]. A mine is often made up of various types of trucks and shovels (heterogeneous fleet) working at trucks and shovel digging rates at similar speeds and capacities. Below demands from truck drivers, the dispatcher (or fleet manager) must determine in real time the shovel the truck must move to (truck assignment) based on the current state of the mine and on a decision support system or on its own experience. Such decisions are of crucial importance in the mining operation, as material transport is the kind of most significant aspects of open-pit mine operations, accounting for up to 60% of operating costs[2]. Because of its significance, over the past few years, many decision systems have been developed for this issue, increasing efficiency and reducing operating costs. In the following sections similarities between truck dispatching and other vehicle dispatching systems are presented; the truck dispatching in open pit-mining is fully addressed and detailed.

The truck dispatching problem does not occur only in Mining, and can be found in any area that includes management of a vehicle fleet. Some examples of vehicle dispatching problems: • Dynamic vehicle assignment problem - This is a common problem in the shipping industry. Given a request, the fleet manager must decide which truck will be sent to the ship for loading and further delivering. After the delivering, if there is not more loadings, the truck must be repositioned given future loading demands [3]. • Dial-a-ride- It is a generalization of the dynamic vehicle assignment problem. During a day, a vehicle must pickup and deliver material (or people) in different locations. This problem can have some capacity restrictions and soft time-window constraints. The objective is doing all transportation with minimum costs [4].

shop floor (raw material or finished product) in an automated plant. The transportation occurs in close locations and there are predefined robot waiting places to avoid queues in the processes [5]. Alarie and Gamache (2002) argue that truck dispatch in open-pit mining is by all accounts an improvement in other vehicle dispatch issues; in any case, it shows some attributes not generally announced in writing. • Mines are closed systems, i.e. the pick-up and distribution points remain the same and remain in the same place for a long period of time (usually a change of 8 to 12 hours); • The travel lengths are short compared to the shift duration (10 to 25 minutes); • The demand frequency at each pick-up point is high (3 to 5 minutes each); and • If the fleet size is too large; Additionally, we refer to the high combinatorial part of the issue because of a few trucks regularly working in a mine (the dispatching framework must think about the situation of all trucks on its task to the scoops, which is exemplified by values in the following section considering our model mine model). In the recreated mines introduced by there are 15 trucks in a medium-scale mine (3 scoops and 2 dump focuses), and 60 trucks in an enormous scale mine (10 scoops and 3 dump focuses). In Computer Science, the truck is an agent and this problem is modeled as a multi-agent system[6]. The number of trucks (fleet size) operating in a mine in a previous decision epoch is specified by a particular optimization technique, which is not the objective of this work. Locations with more trucks than the optimal (overflown) quantity would increase the length of queues on shovels, while fewer (under-trucked) trucks will cause shovel under-usage. So our algorithm's results are robustly partial by the quantity of trucks working in a change, which has to be near enough to the optimum quantity.

Taking care of a truck dispatching issue in open-pit mining can mean expanding tonnage creation (efficiency approach), minimization of gear idleness (truck holding up time and scoop inert time), or Run of Mine (ROM) participation (quality strategy). In a mine, the ROM is the quality degree of the mineral that can be a blend (adjusted mean) of many mining fronts. [7] developed a Fuzzy Algorithm to stages [8]: (1) truck resource allocation or fleet size estimation, and (2) real-time truck dispatching. The fleet Size estimation, which is not the subject of this proposal, is a major issue to be addressed in the issue of truck shipping; overcrowded circumstances will create the length of lines at scoops, while undercrowding would cause underusing of scoops (ALARIE; GAMACHE, 2002). The investment in an overflown mine is increased due to higher truck usage, which triggers more stops in help and higher fuel consumption, whereas the production objectives will not be attained in an under-trucked mine. Due to its importance, this issue is tackled by many recent works in the mining literature. The real-time truck dispatching stage can be modeled by three strategies (ALARIE; GAMACHE, 2002): (1) 1-truck-for-n-shovels, (2) m-trucks-for-1-shovel, and (3)m-trucksfor-n-shovels.

This is the most used strategy in the mining industry. Trucks are assigned one by one to shovels (FIG.1). The fleet manager assigns the truck to the shovel that is most suitable to the current dispatching criterion, following a heuristic method, or rule [9]. Heuristics are procedures which are not mathematically proven but which are based upon practical or logical operating procedures [10]. The most used heuristic methods used in truck dispatching are [11].

• Minimizing Shovel Waiting Time (MSWT): a vacant truck in the dispatching point is doled out to the longest inactive time scoop, or to the scoop that hopes to be • Minimizing Truck Cycle Time (MTCT): the objective of this procedure is to appoint an unfilled truck to the scoop that permits the most brief truck process duration, expanding the absolute tonnage efficiency. The goal of this paradigm is to boost the quantity of truck cycles during the move. • Minimizing Truck Waiting Time (MTWT): in this paradigm, an unfilled truck in the dispatching point is doled out to a scoop wherein the stacking activity begins first. The goal of this standard is to expand the use of a scoop by limiting its holding up time. • Minimizing Shovel Saturation or Coverage (MSC): void trucks are doled out to the scoop at equivalent time interims to keep a non-inert scoop activity. The goal of this standard is to dole out the trucks to the scoops at equivalent time interims to keep a scoop working without sitting tight for trucks. This strategy is myopic (or greedy) because the system is not completely observed when a truck is being dispatched. For example, in a two shovel and two truck mine, the first truck positioned at the dispatching point is assigned to the shovel number one, because of its higher production, and the second one must have to be assigned to the shovel number two (this example system does not allow queues in the mining). In this situation, the total production, following the production policy, will not be the maximum one. Thus, the global result (sum of individual truck productions) is affected because of the greedy behavior of this strategy[12].

In this strategy (FIG. 2), the shovels are first sorted following a priority scheme (e.g., by how much they are behind schedule on their production), and then, each one ”selects”, from a list of m trucks, the one that best serves it (e.g., the truck with highest load capacity and the nearest one). According to Alarie and Gamache (2002), there is only one implemented system that uses this technique, namely the DISPATCHTMcommercial truck dispatch kit developed by Modular Mining Systems. Because DISPATCHTMis a commercial product, there is no comprehensive knowledge in the scientific literature about its algorithms and heuristic methods.

This strategy (FIG.3) take of the m open delivery trucks and the n scoops in the mine at the same time. This is a combinatorial question that can be shown as a problem with the mission or as a problem with the vehicle. [13] solves the truck dispatching as an assignment problem. Here, the system considers for the assignment optimization the truck that asks for dispatching and the next 10 to 15 trucks that will ask for dispatch in the near future (e.g. over the paths, finishing dumping or finishing material loading). Only the latest request truck assignment will be replied, all assignments will be discarded. In the next dispatch requests, the system will repeat the same steps. Due to the combinatorial explosion of this problem, that is, NP-hard, the solution is only for the near future dispatching trucks. In addition, for a real-time system, a solution considering the entire shift

The system proposed by Temeng, Otuonye and Frendewey (1997) [14] is modeled and solved as a transport problem. In this problem, each supply center is associated to a truck that will be dispatched in a near future, and each receiver center is a shovel present in the mine. The receiver center demand is expressed as the number of trucks needed to reach the production goals. The cost of sending a truck to a shovel is given by the truck waiting time (truck queues at the shovels). Another current trend in solving this kind of problem is the Evolutionary Algorithm (EA), which Use certain biologically based mechanisms: replication, mutation, recombination and selection. This is a near optimal algorithm, that is, the global optimal solution is not guaranteed to be found and the algorithm often converges to local optimal solutions (the EAs have specific search mechanisms to avoid a premature convergence to first local optimal solutions). A near optimal solution is generally found must faster by the AGs than exact searching methods (e.g. breadth-first search), and can be considered acceptable given the convergence criteria of the algorithm.

The truck dispatching in open-pit mines is an issue where choices on truck assignments and goals are taken progressively. As in numerous other true applications, the appraisal and right demonstrating of vulnerability is a critical necessity, as the eccentrics began from gear deficiencies, climate conditions and human slip-ups can regularly bring about truck lines or inert scoops. There are likewise vulnerabilities in movement and stacking times identified with the issue; the movement time of a truck between a similar explicit stacking and dumping focuses delegated a stochastic issue, wherein the vulnerabilities must be a piece of the issue display and be considered in the critical thinking process. In any case, vulnerability isn't considered in the greater part of current dispatching frameworks, conceivably giving more awful arrangements than the normal ideal one. Consider the following example: two identical trucks are parked in the same area, just waiting to be assigned to two identical shovels. Considering that queues are not allowed, Which shovel must each truck travel to? The answer is quite obvious because of truck homogeneity: each truck must travel to a different shovel (there will be no difference in total production). This simple example shows the easiness of solution in simple environments; even if the shovels were different, the solution remains the same.

We present a modified medium-scale example of a mine to have a test bed for the simulations of the proposed truck dispatching algorithms. (FIG. 4),

The mine has three stations for pick-up (shovels S1, S2, S3) and one station for delivery / departure (crusher C). This differs from the original one in Jaoua, Gamache and Riopel (2009) due to the absence of one waste dump (another delivery center) and one departure station (parking area and starting point for truck shipping). For the sake of convenience and our main purpose (i.e. introducing a new stochastic truck dispatching

In the same manner as in the original mine, We use 15 trucks for shovel-to-crusher material transport. Sadly, the requirements of trucks and shovels are not stated in Jaoua, Gamache and Riopel (2009). We suggest heterogeneous types of trucks (Table 1) and shovels (Table 2) working in the mine setting to address the deficiency of the previously implemented model.

Truck shipping follows a Truck Cycle: an action series with its corresponding time span. Fundamentally, the sequence is: (1) the truck receives a request for dispatch at the flight station (smasher in our model), (2) the truck then continues through a path to the allocated scoop, (3) stacks the material, (4) returns to the smasher by a route (which may not be exactly the similar as the first one), (5) empties the material and (6) waits for further dispatch. This grouping is replicated until the process is ended. 1. The truck process has to be modified to a state-based representation, we represent sub-state shovels and crushers to complete the representation of actions, time span and queue on the shovels (FIG. 5). The truck cycle follows the series in a state-based representation: 2. The truck begins its process when a Shovel (state S ') is allocated to Crusher (state C) and then performs the move shovel operation which Takes the time span t shovel (depending on the distance between the crusher and the shovel and the average empty truck speed); 3. At state S, the truck moves (action move queue) to the FIFO (first out) queue state, which takes the time t queue (depends on the queue size); 4. When the truck is the first in the queue, the Shovel (state S) loads it (action load truck) over time (depending on shovel loading rate and truck capacity); distance from the shovel to the crusher and the average speed of the loaded truck); 6. At the end of the cycle, the truck unloads (action unload truck) the material in the Crusher (state C) over time (based on truck capacity). For straightforwardness, we think about that there is no line at the smasher; the trucks empty the material gathered from the scoops in a simultaneous way. Additionally, in our model the lines at the scoops are restricted to 9 trucks (the dispatching framework controls thinks about this size confinement on assignments, and we think about that the truck driver pursues carefully its scoop task). So as to make the introduced framework reasonable to a TiMDP displaying, times are identified with the activities, not to the states; for example the time that the truck holds up in the line (t line) (which is identified with the activity move_queue) relies upon the present size of the line.

We acquaint two sorts of vulnerability with the mine model, approximating its conduct to a true mining: (1) stochastic path selection, and (2) Gaussian-based truck traveling times.

Path selection is identified with activity (scoop task) results (µ). To start with, at the flight station (dispatching point), the truck driver gets from the dispatcher the data of the scoop that it must head out to. As we don't think about the directing issue, the truck driver must choose the best path to the

happens in the arrival travel (from scoop to conveyance/flight station). So as to be applied in the TiMDP model, the results are grouped relying upon the scoop task. The truck driver can choose 3 paths for the voyaging; as a matter of course, we use µ1 for the most limited path, µ2 for the medium path, and µ3 for the longest path. FIG.6 shows the outcome classification for each travel between crusher and shovels (forward and return travels). In order to represent a real-world mine operation behavior, we define that the selected path for the forward travel (empty truck) is not necessarily the similar as the return travel (full truck). Considering the truck mission, the probability of an outcome occurrence (which direction the truck will take) depends on the likelihood of work throughout the movement(FIG. 4).

Therefore, the selection of the direction is base on a probability value which can differ over time, but the sum of the probabilities of the outcome is always equal to one. The probability can be calculated on the basis of historical data we used arbitrary values and likelihood functions that are valid for all truck types. In FIG, as an example of comparison. 6(a) If the truck is assigned to Shovel 1, the likelihood of the driver taking direction μ1 is 85%; μ2 is 10%; and μ3 is 5%; from 0 to 300 minutes; and from 360 minutes until the end of the shift. Those odds change only within 300 and 360 minutes, μ1 being zero, μ2 being 60%, and μ3 being 40%. Such abrupt change in probability values takes place in the preceding period due to a scheduled maintenance and subsequent blocking of the path between C and S1. Therefore, in open-pit mining problems, we introduce a novel restriction in modeling truck dispatching, namely time slots, used before in vehicle dispatching problems[15]. The implementation of this constraint in the model approximates the problem to real-world mining, where there are regular path blockages. Trucks assignment in the mine is a cyclic operation, in which they are constantly executing material transportation between shovels and crusher until the end of the shift. Each truck movement or operation, represented in FIG. 6, takes a timespan depending on distance, truck speed, truck and shovel capacities, and queues size. These times can be attributed based on historical mine database, being these representations the basis for the presented real-time dispatching methods, hence their importance in our model.

Certainly, the truck displacement timespan between two identical points will not be the same over travels. Minor variations can be explained based on different drivers that conduct trucks with similar, but not equal, speeds and throttles, and small differences on shovel and crusher positions. Major variations are based on high reduction of truck speed because of weather conditions, and distribution function (pdf). We use a Normal (or Gaussian) distribution for timespan representation, which is a convenient model to represent time processing. However, due to only positive representations of time, this distribution may not be a good choice in some cases because of its theoretical range (−∞ to +∞). In this case, we can use the Gamma Distribution, which have range from zero to +∞ and is often used to represent the time required to complete some task. The graphical representation of the Gamma Distribution is similar to the Gaussian in situations in which the values tend to zero in the negative ”time” axis. [16] also considered the involved times in their problems as Gamma Distributions. Certainly, the truck displacement timespan between two identical points will not be the same over travels. Minor variations can be explained based on different drivers that conduct trucks with similar, but not equal, speeds and throttles, and small differences on shovel and crusher positions. Major variations are based on high reduction of truck speed because of weather conditions, and changes in mine configuration. In this thesis, our solution methods consider only the minor timespan variations, which are represented by a probability distribution function (pdf). We use a Normal (or Gaussian) distribution for timespan representation, which is a convenient model to represent time processing. However, due to only positive representations of time, this distribution may not be a good choice in some cases because of its theoretical range (−∞ to +∞). In this case, we can use the Gamma Distribution, which have range from zero to +∞ and is often used to represent the time required to complete some task. The graphical representation of the Gamma Distribution is similar to the Gaussian in situations in which the values tend to zero in the negative ”time” axis. [16]also considered the involved times in their problems as Gamma Distributions methods.

The 1-truck-for-n-shovels strategy is greedy. Indeed, this strategy can be considered as such because the truck assignment is made observing only its own state; it is an egotist behavior that leads to not so good global results. However, most of the methods applied according to this strategy are fast and have some knowledge about the mine environment, leading to acceptable results considering the realtime and uncertain aspects of the problem. Thus, due to the acceptable quality of the results presented by these heuristic methods (such as the MTCT heuristic), we propose an extremely greedy heuristic that certainly will return poor results, which will be used for comparisons with other methods. In this method, the dispatcher does not have much information about the mine environment. Crucial informations for a good dispatching, like distances and truck/shovel capacities are completely unknown and not considered by the dispatching algorithm. The only observation that is allowed is the size of the queues at the shovels. Thus, in this method the truck must be assigned to the shovel that presents the smallest queue. Because of the balanced dispatching characteristic, the size of the queues tends to be near equal during the whole shift; the problem of shovel underutilization is not present in this method. Likewise, the time-window in the shift, which indicates the blocking period of the nearest path to the crusher, is not considered in this method. Since the only information for the heuristic is the size of the queues, the knowledge about the time-window does not affect the performance of the method. Another important issue that occurs in the dispatching is the instant of decision; the first decision differs from the others, because in the beginning all trucks are available and waiting for its shovel assignment. Considering that trucks cannot overtake each other in the paths, we organize a decision queue, in which the fastest trucks are placed first in order to prevent traffic slowness. As a special case for further decisions in which trucks asks for dispatching at the same time, the fastest trucks always have the preference. This decision policy used for cases with conflicting trucks will also be used for our methods based on 1-truck-for-n-shovels strategy.

This paper addresses the issue of truck dispatching in open-pit mining. In order to position the complexity and details of the truck dispatching problem, we review the general vehicle dispatching problem with some variants and applied solution methods. Following, we present the specifies of the truck dispatching problem, such as involved equipments, special goals, and dispatching strategies that are used in real-world truck dispatching problems. Dispatching strategies are presented, which are the basis for the developed solution methods. We also present additional techniques for truck dispatching that are used in further analysis, namely: greedy heuristic, MTCT (Minimizing Truck Cycle Time) heuristic, and GAs.

[1] KOLONJA, B.; KALASKY, D.; MUTMANSKY, J. (1993). Optimization of dispatching criteria for open-pit truck haulage system design using multiple comparisons with the best and common random numbers. In: ACM NEW YORK, NY, USA. Proceedings of the 25th conference on Winter simulation. [S.l.], pp. 393–401. [2] ALARIE, S.; GAMACHE, M. (2002). Overview of solution strategies used in truck dispatching systems for open pit mines. International Journal of Surface Mining, [3] POWELL, W. (1988). A comparative review of alternative algorithms for the dynamic vehicle allocation problem. Vehicle Routing: Methods and Studies, pp. 249–291. [4] GENDREAU, M.; POTVIN, J. (1998). Dynamic Vehicle Routing and Dispatching. Fleet management and logistics, Kluwer Academic Publishers, pp. 115–126. [5] CO, C.; TANCHOCO, J. (1990). A Review of Research and AGVS Vehicle Management. [S.l.]: School of Industrial Engineering, Purdue University. [6] JAOUA, A.; GAMACHE, M.; RIOPEL, D. (2009). Specification of an Intelligent Simulation–Based Real Time Control Architecture: Application to Truck Control System. Simulation `a Ev´enements Discrets pour la Commande Temps R´eel de ´ Syst`emes Dynamiques Complexes, p. 24. [7] PINTO, E. B. (2007). Despacho de caminh˜oes em minera¸c˜ao usando l´ogica nebulosa, visando ao atendimento simultˆaneo de pol´ıticas excludentes. 2007. 120 p. Disserta¸c˜ao (Masters in Production Engineering) — Engineering School, Federal University of Minas Gerais. [8] KRAUSE, A.; MUSINGWINI, C. (2007). Modelling open pit shovel-truck systems using the Machine Repair Model. Journal of the South African Institute of Mining and Metallurgy, Marshalltown, South Africa., v. 107, n. 8, pp. 469–476. [9] TA, C.; KRESTA, J.; FORBES, J.; MARQUEZ, H. (2005). A stochastic optimization approach to mine truck allocation. International Journal of Mining, Reclamation and Environment, Taylor & Francis, v. 19, n. 3, pp. 162–175. [10] RUSSELL, S.; NORVIG, P. (2009). Artificial intelligence: a modern approach. [S.l.]: Prentice hall. [11] KOLONJA, B.; KALASKY, D.; MUTMANSKY, J. (1993). Optimization of dispatching criteria for open-pit truck haulage system design using multiple comparisons with the best and common random numbers. In: ACM NEW YORK, NY, USA. Proceedings of the 25th [12] LIZOTTE, Y.; BONATES, E. (1987). Truck and shovel dispatching rules assessment using simulation. Mining Science and Technology, v. 5, pp. 45–58. [13] ELBROND, J.; SOUMIS, F. (1987). Towards integrated production planning and truck dispatching in open pit mines. International Journal of Mining, Reclamation and Environment, Taylor & Francis, v. 1, n. 1, pp. 1–6. [14] TEMENG, V.; OTUONYE, F.; FRENDEWEY, J. (1997). Real-time truck dispatching using a transportation algorithm. International Journal of Mining, Reclamation and Environment, Taylor & Francis, v. 11, n. 4, pp. 203–207. [15] SOLOMON, M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, JSTOR, pp. 254–265. [16] GIBSON, M.; BRUCK, J. (2000). Efficient exact stochastic simulation of chemical systems with many species and many channels. J. Phys. Chem. A, ACS Publications, v. 104, n. 9, pp. 1876–1889.

Research Scholar mishra200@gmail.com