Keyword

1 Introduction

Material handling is an important process in open-pit mines since its cost can represent up to 50% of the entire operational cost in these kinds of mines [1]. In this process shovels and trucks work together to extract and to transport all the material required in the operational plan at minimum cost. If the material extracted is ore, it must be transported and unloaded into a crusher or onto a stockpile. If the extracted material is waste, it must be transported to a waste dump. Figure 1 depicts the operations that a truck must perform to transport materials from a shovel to a crusher, stockpile, or waste dump. This cycle is performed and repeated by each truck until the shift ends.

Fig. 1.
figure 1

The truck cycle. Adapted from [2, p. 2]

Full size image

The material handling process is performed in a dynamic environment that affects the performance and availability of the involved equipment. For example, changes in weather conditions or to the state of the routes as well as equipment failures are some of the reasons for delays in material handling [3].

During the material handling process, each time a truck ends an unloading operation it requires a new loading destination, i.e., it requires a new assignment to a shovel where the truck must go for a new loading. This is called truck dispatching. Determining the new destination for the truck is not easy because of the stochasticity of the material handling process and the dynamics of the environment where the equipment items perform their operations.

Different centralized systems have been implemented to support truck dispatching in open-pit mines [4]. Most of these systems use a multistage approach [1], which computes a guideline in the first stage. A later stage uses this guideline to dispatch the trucks in real-time each time that a truck ends an unloading operation.

One example of the application of the multistage approach is a system with two stages. The first stage determines, before the shift starts, the number of travels to transport the required materials by the production plan from shovels to unloading points. Then, when the trucks are working and when a truck requires a new destination, the later stage determines the destination based on a dispatching criterion (e.g., the number of trips performed) and the current information on the process.

The strengths of these centralized systems are their maturity and their well-known implementation. However, the weaknesses that can be observed are using estimated information [5,6,7,8], and not being able to provide a precise solution [9]. In addition, using dispatching criteria in this way is myopic, and it is hard to predict the performance of the entire system since decisions are made locally in real-time [10]. Due to these weaknesses, the material handling process is not performed efficiently, since queues of trucks can form in front of shovels and crushers, and there can also be shovel idle times. Therefore, the question remains as how to improve the efficiency of the material handling process.

Icarte et al. [2] developed an alternative solution that allows the equipment items to operate more efficiently. The solution is based on a Multiagent system in which intelligent agents that represent real-world equipment interact with each other to generate schedules.

In this paper, we extend the work presented in [2] by performing and evaluating extended experiments for the generation of schedules, and by the evaluation of the MAS when a major unforeseen event occurs at the mine. In order to demonstrate the validity of the MAS, the experiments were performed based on actual data from a Chilean open-pit mine.

The remainder of this paper is structured as follows: Sect. 2 presents related work, Sect. 3 presents the formulation of the problem, and Sect. 4 presents the distributed solution based on MAS. Section 5 presents the evaluation and discussion of the proposed MAS. Finally, conclusions and outlook are presented in Sect. 6.

2 Related Work

In the past years, many articles deal with the truck dispatching problem in open-pit mines. These articles show different methods that try to achieve two goals: improve productivity and reduce operating costs [1]. These methods are based on Operations Research, simulation modelling or heuristic procedures and follow a centralized approach. For instance, Bakhtavar and Mahmoudi [11] developed a two-phase scenario-based robust optimization (SBRO) model by considering the maximization of production, control of ore grade sent to the crusher, minimization of waiting times for trucks and shovels, and trucks with different capacities. Koryagin and Voronov [12] presented a heuristic algorithm to dispatch trucks after unloading. The algorithm uses priority parameters for choosing the shovel to which the truck will be allocated, and the corresponding route for material transportation is considered. In addition, the algorithm applies a minimizing truck waiting time criterion. Chaowasakoo et al. [13] illustrated the differences between the dispatching strategies by conducting a stochastic simulation study based on the data gathered from an actual big-size mine.

Most of the articles on the truck dispatching problem in open-pit mines propose a method that determines the next destination of a truck after the completion of an unloading activity. To do this, the methods use a previously calculated guideline, the current status of the mine, and some dispatching criteria. Although these methods are easy to implement, they are not able to provide a precise description of the activities of shovels and trucks. Therefore, they cannot guarantee a good synchronization between the activities of the equipment items [9]. In scheduling theory, this kind of method is called “Completely reactive scheduling” [10, 14].

In “Completely reactive scheduling” no schedule is generated. The decision on what is the next task to be performed is made locally in real-time [10] considering the available information at the moment and some dispatching criteria. This way of dynamic scheduling is quick, usually intuitive, and easy to implement. However, a schedule of the tasks to perform has the potential to significantly improve the performance of a system [10].

Few articles have proposed to generate schedules for the truck dispatching problem in open-pit mines. Chang et al. [3] and Patterson et al. [7] proposed algorithms that generate an initial schedule which is improved by using a metaheuristic method. Their results show that these algorithms generate schedules for different size instances with good results and performance in practical frame times. Icarte et al. [2] developed a distributed approach based on multiagent systems to generate schedules for the equipment item involved in the material handling process. Their results show that a MAS approach provides schedules in practical frame times for the mining industry. However, none of these articles mention how the schedules could be rescheduled when a major unforeseen event occurs in a mine.

There are several articles that use multiagent systems for scheduling and rescheduling problems. Most of them are applied in manufacturing [15,16,17,18] and for vehicles [19,20,21,22,23,24]. All these authors mention the good performance of MAS to generate schedules and, some of them, a good reaction when an event occurs [16, 19,20,21, 23, 25]. These articles demonstrate the applicability of MAS to scheduling and rescheduling problems.

3 Problem Representation

Truck dispatching in open-pit mines as a scheduling problem is represented by the following notations, constraints, and objective functions:

3.1 Notations

  • \(S = \left\{ {s_{1} , \ldots ,s_{n} } \right\}\). It is the set of shovels.

  • \(T = \left\{ {t_{1} , \ldots ,t_{m} } \right\}\). It is the set of trucks.

  • \(J = \left\{ {j_{1} , \ldots ,j_{p} } \right\}\). It is the set of the material extracted by a shovel.

  • \(C_{t}^{s}\). It is the loading time that the shovel s takes for loading the truck t.

  • \(C_{j}^{t}\). It is the unloading time that the truck t takes for unloading at destination j.

  • \(C\_loaded_{t}\). It is the cost matrix (Cs,j) of truck t that represent the cost of traveling from shovel s to destination j.

  • \(C\_empty_{t}\). It is the cost matrix (Cj,s) of truck t that represent the cost of traveling from destination j to shovel s.

  • \(TargetPlan = \left\{ {\left( {s,j,x} \right){|}s \in S, {\kern 1pt} {\kern 1pt} j \in J, {\kern 1pt} x \in {\mathbb{N}}} \right\}\). It is the material that must be extracted by shovel s and transported to destination j.

  • \(TruckOperation = \) {‘emptyTrip’,‘\(loading\)’,‘\(loadedTrip\)’,‘\(unloading\)’}. The operation that a truck can perform.

  • \(TruckSchedule = \left\{ {\left( {t,operation,startTime, endTime, from, to} \right){|}t \in T, operation \in TruckOperation,startTime \in {\mathbb{N}},\rm{ }endTime \in {\mathbb{N}},\rm{ }from \in \left( {S \cup J} \right), to \in \left( {S \cup J} \right) } \right\}\). It is the schedule of the trucks.

  • \(ShovelSchedule = \left\{ {\left( {s,startTime, endTime, quantityLoaded} \right){|}s \in S, startTime \in {\mathbb{N}},\rm{ }endTime \in {\mathbb{N}}} \right\}\). It is the schedule of the shovels.

The following constraints set the sequence and times of the operations scheduled and avoiding overlapping them.

$$ \begin{array}{*{20}l} {startTime + C\_empty_{t} \left( {j,s} \right)} \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = endTime{ }\forall { }x_{{\left( {t,emptyTrip,starTime,{ }endTime,{ }s,j} \right)}} } \hfill \\ {\begin{array}{*{20}l} {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \in TruckSchedule} \hfill \\ \end{array} } \hfill \\ \end{array} $$
(1)
$$ \begin{array}{*{20}l} {startTime + C\_loaded_{t} \left( {s,j} \right)} \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = endTime{ }\forall { }x_{{\left( {t,loadedTrip,starTime,{ }endTime,{ }j,s} \right)}} } \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \in TruckSchedule} \hfill \\ \end{array} $$
(2)
$$ \begin{array}{*{20}l} {startTime + C_{t}^{s} = endTime{ }\forall { }x_{{\left( {t,loading,starTime,{ }endTime,{ }s,s} \right)}} } \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \in TruckSchedule} \hfill \\ \end{array} $$
(3)
$$ \begin{array}{*{20}l} {startTime + C_{j}^{t} = endTime{ }\forall { }x_{{\left( {t,{\text{un}}loading,starTime,{ }endTime,{ }j,j} \right)}} } \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \in TruckSchedule} \hfill \\ \end{array} $$
(4)
$$ \begin{array}{*{20}l} {x_{{\left( {t,emptyTrip, startTime,endTime,s,j} \right)}} } \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \le y_{{\left( {t,loading,startTime^{\prime},endTime^{\prime},s,s} \right)}} iff\, endTime} \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \le startTime^{\prime} \forall x, y \in TruckSchedule} \hfill \\ \end{array} $$
(5)
$$ \begin{array}{*{20}l} {x_{{\left( {t,loading, startTime,endTime,s,s} \right)}} } \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \le y_{{\left( {t,loadedTrip,startTime^{\prime},endTime^{\prime},s,j} \right)}} iff\,endTime} \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \le startTime^{\prime} \forall x, y \in TruckSchedule} \hfill \\ \end{array} $$
(6)
$$ \begin{array}{*{20}l} {x_{{\left( {t,loadedTrip, startTime,endTime,s,j} \right)}} } \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \le y_{{\left( {t,unloading,startTime^{\prime},endTime^{\prime},j,j} \right)}} iff\,endTime} \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \le startTime^{\prime} \forall x, y \in TruckSchedule} \hfill \\ \end{array} $$
(7)
$$ \begin{array}{*{20}l} {x_{{\left( {t,unloading, startTime,endTime,j,j} \right)}} } \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \le y_{{\left( {t,emptyTrip,startTime^{\prime},endTime^{\prime},j,s} \right)}} iff\,endTime} \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \le startTime^{\prime} \forall x, y \in TruckSchedule} \hfill \\ \end{array} $$
(8)
$$ startTime + C_{t}^{s} = endTime{ }\forall { }x_{{\left( {s,starTime,{ }endTime} \right)}} \in ShovelSchedule $$
(9)
$$ \begin{array}{*{20}l} {x_{{\left( {s, startTime,endTime} \right)}} \le y_{{\left( {s,startTime^{\prime},endTime^{\prime}} \right)}} iff\,endTime} \hfill \\ {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \le startTime^{\prime}\forall x, y \in ShovelSchedule} \hfill \\ \end{array} $$
(10)

3.2 Objective Functions

The truck dispatching problem pursues two objectives: to achieve the production targets and the minimization of the truck travel costs. These objectives can be formulated as follows:

$$ max\sum\limits_{x\, \in \,ShovelSchedule} {\left( {quantityLoaded} \right)} $$
(11)
$$ min\sum\limits_{{x\,{\kern 1pt} \in {\kern 1pt} {\kern 1pt} TruckSchedule}} {\left( {endTime - starTime} \right)} $$
(12)

4 Dynamic Scheduling Multiagent System for Truck Dispatching in Open-Pit Mines

The objective of the developed MAS is to achieve the goals of the production plan at minimum cost. In order to do this, the agents must interact with each other to generate schedules for each equipment item involved in the material handling process. Moreover, the agents must update the generated schedules when a major unforeseen event occurs at the mine. Table 1 shows the implemented agents, their objectives, and properties.

Our developed multiagent system for truck dispatching in open-pit mines has the following advantages over current centralized systems:

  • Efficient Dispatching Solution: The schedules generated by the MAS are more efficient than a “Completely reactive scheduling”, which is applied by the current systems.

  • Use of Specific Data from Equipment Items: This allows the MAS to generate more precise schedules.

  • Robustness: As there is not a central node, if any node is out of order, the system continues working without it.

  • Flexibility: An agent can change its behavior to adapt to the new conditions in its environment and, in this way, to achieve its own objectives or the objectives of the entire system.

  • Reactiveness: The agents are able to update the schedules when a major unforeseen event occurs at the mine.

Table 1. Agent description. Adapted from [2, p. 4].
Full size table

The following subsections describe the interactions among the agents and their decision-making processes.

4.1 Interactions for Scheduling

In order to generate the schedules, the agents negotiate among them by using the adapted Contract Net Protocol presented in [2]. In this protocol, a shovelAgent plays the role of the initiator and truckAgents play the role of participants. The shovelAgents in the system start this negotiation process in parallel, therefore the protocol must manage concurrent negotiations.

To manage concurrent negotiations, the original CNP is adapted by including a confirmation stage. The state transitions in the negotiation process between a shovelAgent and truckAgents are depicted in Fig. 2. The process starts when a shovelAgent sends a call-for-proposal message (CFP) to truckAgents. After sending the CFP, the process passes to the first state “Evaluating CFP”. In this state, the truckAgents evaluate the received CFP and decide on sending a proposal or a refuse message as the answer. Meanwhile the shovelAgent is waiting for the messages from the truckAgents.

When a shovelAgent receives a message from a truckAgent, the negotiation process passes to the state “Receiving proposals”. In this state, the shovelAgent receives and stores the proposals sent by the truckAgents and keeps a count of the received messages from the truckAgents. The negotiation keeps in this state until a deadline expires or when the shovelAgent has received all the messages (propose or refuse) from the truckAgents. In the “Receiving proposals” state two situations can happen: having received proposals or not. If it has not received any proposals, the negotiation process finishes without a contract. If it has received proposals, the negotiation process passes to the state “Selecting best proposal”.

In the state “Selecting best proposal”, the shovelAgent selects the best proposal and sends a message with the performative requestConfirmation to the truckAgent that sent the best proposal, and the negotiation process passes to the state “Waiting for answer”.

In the state “Waiting for answer”, three situations can happen: receiving a message with the performative acceptConfirmation, receiving a message with the performative refuseConfirmation, or a deadline expires. In the first case, the negotiation process passes to the state “Sending results”. In the “Sending results” state the shovelAgent sends a reject-proposal message to those truckAgents that were not awarded, and the negotiation process ends with a contract. In the second and third cases, the negotiation process passes to the “Removing proposal” state. In this state, the shovelAgent removes the proposal from its storage. If there are more proposals, the negotiation process passes to the state “Selecting best proposal” and repeats the cycle. If there are no more proposals, the negotiation process ends without a contract. Figure 3 depicts the interaction between the agents using the adapted Contract Net Protocol and Table 2 shows a schedule example for a truck generated by the agents by applying this protocol.

Fig. 2.
figure 2

State machine diagram of the negotiation process by applying the adapted Contract Net Protocol.

Full size image
Table 2. Example of schedule created for a truck.
Full size table
Fig. 3.
figure 3

The interaction between the agents using the CNP with the confirmation stage. Adapted from [2, p. 4].

Full size image

4.2 Interactions for Rescheduling

In the scheduling literature, two main rescheduling strategies are mentioned: schedule repair, and complete rescheduling [10]. scheduling repair refers to some local adjustment of the current schedule. complete rescheduling regenerates a new schedule from scratch.

In the context of the MAS for the truck dispatching in open-pit mines, the agents can use both strategies, depending on the type event that triggers the rescheduling. In both strategies, the agents apply the adapted CNP described previously. For the schedule repair strategy, some agents may apply changes to their schedules. For instance, in the case of a truck failure, the truckAgent that represents the broken truck informs shovelAgents and unloadingAgents that the truck will not be able to perform the assignments. The shovelAgent must cancel the affected assignment and its production will decrease. Here, the shovelAgent starts new a negotiation process cycle to try to reach its production goals again. In the case of complete rescheduling, all agents must generate a new schedule from the point in time where the failure occurred. All agents cancel their assignments and the agents interact with each other by applying the adapted CNP to generate new schedules.

4.3 Decision Making

In the MAS for truck dispatch in open-pit mines, ShovelAgents and TruckAgents make decisions at different moments in the negotiation process. The following subsections describe the decision-making process for these types of agents.

ShovelAgent.

ShovelAgents only must make one decision during a negotiation process: what is the best proposal received. to make this decision, the shovelagents use the utility function proposed in [2], which promotes those proposals that decrease the shovel's waiting time and minimize the cost to perform the truck operations. formally:

$$ offer = number \in \left\{ 0 \right\} \cup {\mathbb{N}}.\,{\text{It represents the time offered by a}}shovelAgent $$
(13)

to start a new loading.

$$ P = set {\kern 1pt} of{\kern 1pt} {\kern 1pt} received {\kern 1pt} proposals p_{1} \ldots p_{n} $$
(14)

The decision is a multicriteria problem as

$$ Decision = arg_{min} \left( {p_{i} \in P} \right)\{ U\left( {p_{1} } \right), \ldots ,U\left( {p_{n} } \right)) $$
(15)
$$ U = U\left( {arrivalTime} \right)\rm{\prime } + U\left( {cost} \right)\rm{\prime } $$
(16)
$$ \delta = \left( {arrivalTime - offer} \right) \in {\mathbb{Z}} $$
(17)
$$ U\left( {arrivalTime} \right) = \left\{ {\begin{array}{*{20}c} {\delta , \,if \delta < 0\,\,{\kern 1pt} \left( {the \, truck \, arrives \, earlier} \right) } \\ {0, \,if \delta = 0 \,\,\left( {the \, truck \, arrives \, just \, on \, time} \right)} \\ {2*\delta , \,if \delta > 0 \,\,\left( {the \, truck \, arrives \, later} \right) } \\ \end{array} } \right. $$
(18)

Where U(arrivalTime)’ is the normalized value of U(arrivalTime) and U(cost)’ is the normalized value of U(cost). The normalization applied is

$$ x^{\prime} = \frac{{x - {\text{min}}\left( x \right)}}{{\max \left( x \right) - {\text{min}}\left( x \right)}} $$
(19)

TruckAgent.

A truckagent must make two decisions. the first one is deciding whether or not to send a proposal to a shovelagent that sent a call-for-proposal message. the second one is to decide on whether or not to confirm a previously sent proposal. Figure 4 depicts both decision-making processes.

To decide whether or not to send a proposal, the truckAgent uses the call-for-proposal message's information and its current schedule. The shovelAgents send a call-for-proposal offering the next available time to load a truck. After receiving a CFP, the truckAgent checks its schedule and determines if there is a free time slot for the offered time. If not, it sends a reject message. If yes, it calculates the total time to perform all the operations and determines if it fits into its schedule. If it does not fit into the schedule, it sends a reject message. If it fits into the schedule, it sends a proposal. This decision-making process is shown in Fig. 4a.

To decide whether or not to confirm a proposal sent previously, the truckAgent must consider two aspects: the shovel idle time (informed by the requestConfirmation message sent by the shovelAgent), and the negotiations which the truckAgent is taking part in. If the shovel idle time is higher or equal than one minute, the truckAgent sends an acceptConfirmation message. If the shovel idle time is less than one minute, the truckAgent considers the negotiations which it is taking part in. If there is a negotiation with more potential benefit for the truck (i.e., with a lower cost to perform the operations), the truckAgent sends a refuseConfirmation message. Otherwise, it sends an acceptationConfirmation message. This decision process is depicted in Fig. 4b.

5 Experiments and Discussion

In order to validate the MAS, two types of experiments were performed. On the one hand, some experiments evaluated the performance and quality of the schedules generated by the MAS. On the other hand, additional experiments evaluated the ability of the MAS to reschedule when a machine failure occurs at the mine. The following subsections describe the experiments and their results.

5.1 Experimental Setup

Our experiments were based on actual data from an open-pit copper mine in Chile. The material handling process at the mine is performed using a heterogeneous fleet of trucks and shovels in twelve-hour shifts. The truck dispatching is supported by DISPATCH (TM), which is a well-known dispatch system in the mining industry. This system follows a centralized approach and Completely Reactive Scheduling. The actual data, such as velocities and capacities, is used to set the properties of the agents. Table 3 shows the property sets of the agents.

Fig. 4.
figure 4

Decision-making processes for a TruckAgent.

Full size image

The experiments were performed by simulations run in PlaSMA [29], which is an agent-based event-driven simulation platform created for the simulation and evaluation of multiagent systems. It focuses on simulating logistics processes and is based on the FIPA-compliant Java Agent DEvelopment Framework (JADE) [30]. All simulations have been run on a laptop computer with an Intel Xeon 3 GHz CPU, 32 GB of RAM, and Windows 10.

5.2 Experiment on Schedule Generation

The aim of this experiment was to determine the required time by the MAS to generate the schedules. In order to do this, we simulated several scenarios of different sizes. The scenarios had the same characteristics, i.e. the same layout of the mine and equipment items with the same properties (velocity, capacity, etc.). The differences between the scenarios were the size of the fleet and the length of the shift (column H). Table 4 shows the scenarios and the time it took the MAS to generate the schedules.

Table 3. Property values for the simulations.
Full size table
Table 4. Required time to generate the schedules by the MAS.
Full size table

The results show that the required time for the MAS to generate the schedules increases with a bigger problem. However, the required time for the last scenario, which is a common scenario of a big-size open-pit mine, is a practical timeframe to generate schedules in the context of the mining industry.

5.3 Experiment on the Quality of the Generated Schedules

In this experiment, the aim was to analyze the quality of the generated schedules by the MAS, by comparing the production and cost of simulated shifts against real shifts. We simulated five shifts based on the actual data. Table 5 shows the amount of transported material and the truck cost to transport those materials.

Table 5. Comparison of transported material and truck cost between MAS and actual data.
Full size table

The results show that if the trucks had been dispatched according to the schedules, the material handling process had been more efficient. This is because the schedules generated by the MAS allow the trucks to transport the same amount of material as the actual data (even a little bit more), decreasing the truck travel costs by 17% on average in comparison to the actual data.

The main reason for these savings is that the agents decrease their travel times by applying a shortest path algorithm, whereas the truck operators in the real world decide by themselves which path to follow. Another reason is the use of specific data to allow for calculations better adapted to the activity times of each equipment item, and in this way, the agents can create more appropriate and efficient schedules.

5.4 Experiment on Rescheduling

The objective of this experiment was to evaluate the reaction of the MAS when a machine failure occurs in the mine. In this context, we compared a simple schedule update (cancelation of the affected assignments), a schedule repair, and a complete reschedule when truck failures occur. We simulated truck failures because it is a common situation in open-pit mines.

In the simulated scenario, the fleet is compounded by 90 trucks and 10 shovels and operates in a twelve-hours shift. Two trucks have a failure at the beginning of the shift and are not available anymore. Table 6 shows the performance of the new schedules (in terms of production level and the cost) and the required time to get them by applying a simple schedule updating, schedule repair, and complete rescheduling.

Table 6. Performance of rescheduling strategies.
Full size table

These results show that the simple schedule update achieves the lowest production level in a very short time. This was predictable because the agents update only their own schedules canceling the affected assignments. It was calculated in order to contrast it with the increase in the production level by applying schedule repair and Complete rescheduling.

Schedule repair increases the production level by 5,7% and requires more time to regenerate the schedules than the simple schedule update. This happens because the affected shovelAgents, start the negotiation processes with the cancelation of some loading assignments to achieve their production goals.

Complete rescheduling achieves the highest production level, but the required time to generate all schedules is much higher in comparison to schedule repair. This happens because all shovelAgents cancel all their assignments and initiate the negotiation processes to regenerate the schedules from scratch. As it was described before, in schedule repair only a subset of shovelAgents (the affected ones) start the negotiation processes. In addition, in complete rescheduling, since the truckAgents do not have schedules, they take more time to evaluate and decide on whether to send a proposal. In schedule repair, as the truckAgents have schedules, they are more restricted to send proposals, and therefore it takes them less time to evaluate and decide on whether to send a proposal. Basically, a negotiation process takes more time in complete rescheduling than in schedule repair.

At first sight, it looks like schedule repair is the most suitable strategy to apply by the MAS when truck failures occur since in a short period of time the schedules are repaired. However, total regeneration is also a suitable alternative to be applied by the MAS in spite the longer time it requires. This is because the adapted CNP is implemented by anytime algorithms, i.e., complete rescheduling returns a valid schedule even if it is interrupted before it ends.

6 Conclusions

A major process in open-pit mines is material handling. In this process, dispatching a truck when it completes an unloading operation becomes a complex decision because of the stochasticity of the process and the dynamics of the environment where the equipment items operate. In general, a centralized system supports this process. However, most of them follow a reactive scheduling strategy to dispatch the trucks. This strategy does not guarantee a correct synchronization between the operations of the equipment items. In order to address this situation, we developed a multiagent system (MAS) with agents that represent equipment items from the real world. The agents interact with each other using an extended Contract Net Protocol with a confirmation stage to generate initial schedules for their represented equipment items. Schedules are a more precise way to organize and synchronize the equipment item activities than those proposed by a reactive scheduling strategy. In addition, the agents are able to repair their schedules when trucks have failures.

In order to evaluate the MAS, we made experiments based on simulations to determine the efficiency of the schedules generated by the MAS, and the reaction of the agents to repair the schedules when truck failures occur. Regarding the efficiency of the schedules, the simulations show that the trucks achieved the production level of the actual data by following the schedules with decreasing truck cost by 17% on average. In addition, the MAS generated the schedules in a practical frame time for the mining industry.

Regarding the reactiveness of the MAS when trucks have failures, the experiments demonstrate that both, scheduling repair and complete repair strategies, are suitable even if the second one takes more time for scheduling than the first one.

Our results demonstrate that an agent-based system for truck dispatching in open-pit mines is a suitable alternative to existing systems. Several characteristics of the agent technology such as flexibility, robustness, and autonomy allow the agents to generate a dispatch solution that is more precise and robust than the current approaches.

In our further research, we will compare our approach also against a metaheuristic algorithm for both scheduling and rescheduling. In addition, we will consider other events such as shovel and truck delays.