A method for real-time dynamic fleet mission planning for autonomous mining

Considering first the problem of path planning in underground mining, the two most common approaches are planning with vehicle constraints [8] and planning on topological maps [9]. The use of vehicle constraints addresses the problem in the most complete way as it considers the generation of kinematically or dynamically feasible trajectories. On the other hand, planning on topological maps unloads computational burden leaving the problem of navigation to the low level control, resulting in fast resolution. For this reason, most of the common approaches involving multiple vehicles tackle the problem using topological maps [10, 11]. For topological maps, a method referred to as push-and-swap was introduced in [12]; see also Sect. 6.1.1 below.

Since the vehicles share the same environment, their coordination [13] and cooperation [14] is central when solving the planning problem. The methods presented in [14, 15], and [16] are examples of multi-vehicle path planning algorithms that use artificial intelligence-based approaches (primarily reinforcement learning), to solve the problem of planning in multi-vehicle systems, demonstrating strong scalability properties [16].

Based on the well known A* algorithm [17] that computes the optimal path for a single vehicle in a graph, in [18] an implementation of subdimensional expansion, called M*, is presented that adapts A* to be used efficiently for multivehicle planning. Since its introduction, many variants of M* have been proposed [19, 20] dealing efficiently with the problem of path finding in a graph; see also Sect. 6.1.2 below. An alternative approach can also be found in [21], in which the authors proposed a so called conflict-based search algorithm. This algorithm is efficient in dealing with multivehicle path planning problems using a division between a high-level algorithm and a low-level algorithm. The low level finds the optimal path for each agent, and the high level only solves conflicts step-by-step by expanding a tree of possible solutions until a feasible one is found. Some variations of this algorithm improve performance, for example by grouping agents to reduce the number of conflicts [22], or designing the optimal assignment of targets for the agents [23]. In summary, algorithms of this kind require exploration of the solution space looking for alternative solutions every time a conflict is found.

In general, the complexity of the planning problem grows very fast with the size of the map and the number of vehicles. Hence, rather than attempting an exhaustive search, it is common to approach the problem using other search methods such as, for example, random trees [24] or genetic algorithms [25].

In the approach used here, the planning procedure starts with vehicles being assigned the individual shortest path from its start node to its end node (a path that can be computed once and for all, for any node pair in a given map, see also Sect. 3.1 below). These paths are then modified as required to meet the demands of conflict-free dynamic scheduling, described next.

It is very important to remark that, while the approach proposed here does handle path planning, our paper deals primarily with dynamic scheduling, solving the conflicts (i.e. avoiding collisions) efficiently, while attempting to minimize delays and waiting times. It does so using a modified genetic algorithm, thus crucially avoiding to explore the entire solution space every time a conflict is found. The dynamic fleet mission planning algorithm presented here is designed to fulfil tight time constraints in the loading and unloading of ore in a mine, also handling the fact that the required duration for those operations may vary.

A similar, but not identical, problem is addressed in a very recent work [26], in which the authors investigate the dynamic pickup and delivery problem. In that paper, a fleet of vehicles must transport customers from any starting point to their destination [27]. The problem is addressed using the so-called contract-net protocol, in which each customer publishes its transportation problem in a public auction, and each agent offers a price for the transportation service (moving the customer from point A to point B) according to the actual distance and traversal duration in the graph. The problem is highly complicated due to the tight scheduling and the complex bidding system. To solve the planning problem the authors use the M* algorithm, but the resolution of the scheduling problem requires long training in a cluster with multiple processors in parallel. In contrast, our algorithm does not require any offline training, but the calculation of all the optimal (shortest) paths between all node pairs, stored in a path matrix, is required. This operation need only be done once and for all for a given map, and takes at most a few seconds for a typical mine map.

The topological map is defined as a bidirectional graph \(\mathcal {T} = \{ \mathcal {P}, \mathcal {E} \}\), where \( \mathcal {P} = \{p_1, p_2, \dots p_n \}\) is the set of nodes (vertices) and \( \mathcal {E} = \{e_1, e_2, \dots e_m \}\) is the set of segments (edges). Every segment \(e_{j} = (p_{s},p_{e},t_{j})\) is fully specified by a start node \(p_s\), an end node \(p_e\), and the traversal time (cost) \(t_{j}\). Note that the maps considered here do not contain loops.

Furthermore, \(\mathcal {P}\) is the union of three disjoint subsets, that is \(\mathcal {P} = T\cup S\cup Q \), where T is the set of terminal nodes, S is the set of pause (swap) nodes, and Q is the set of transit nodes. The nodes types are illustrated in Fig. 1. The set of terminal nodes (T) is further subdivided into two disjoint subsets, namely the prioritized terminals\(T^{\mathrm{P}}\) and the non-prioritized terminals\(T^{\mathrm{NP}}\). As will be described below, a fully loaded vehicle, en route to the offloading station, should generally be given higher priority than vehicles that are currently empty. Thus, offloading sites are prioritized, whereas all other terminals (i.e. the loading sites) are non-prioritized. In this paper, for the dynamic fleet mission planning (see Sect. 5) it will be assumed that there is a single prioritized terminal, but this restriction can easily be lifted (and has indeed been lifted for the static planning case described in Sect. 4). Having a single prioritized terminal is representative of the structure of many real mines, in which vehicles returning from the underground loading sites have to reach a single offloading site (where, for example, the material is crushed before being moved out of the mine), resulting in a severe bottleneck that, evidently, must be considered when planning trajectories. As indicated in Fig. 1, the severity of this bottleneck is somewhat alleviated by the presence of pause nodes near the offloading site, where incoming loaded vehicles can (and very often must) wait until the vehicle occupying the offloading site has been emptied and can then leave that site.

Given a topological map one can compute, once and for all (unless the map is changed) all possible paths within the map. An algorithm was written that, for all pairs \((p_{i},p_{j}),\,i\ne j\) of distinct nodes, generates the shortest path (i.e. the direct path without any pause node visits), denoted \(\varPi _{0}(p_{i},p_{j})\), and stores all these paths in a data structure henceforth referred to as the path matrix.

The topological map is populated with a set of L vehicles \(\mathcal {V} = \{v_1, v_2, \ldots v_L\}\). For each vehicle \(v_k\), one can define a mission\(\mathcal {M}(v_k) = \{m_1,m_2,\ldots ,m_q\}\) as a set of mission items. A mission item, in turn, consists of a segment \(e_i\) and an initial stop time\(t_{\mathrm{w}}\) (which is non-zero only in some special cases; see below) specifying an initial standstill period before movement begins over the segment in question. The start node of the first mission item, and the end node of the last mission item, belong to the set of terminals.

When missions are initialized (before optimization), the path for any vehicle is taken from the path matrix (see above). Then, during optimization, missions are modified by inserting (or removing) pairs of mission items representing pause node visits, as described in Sect. 4.3 below. Missions are illustrated graphically as shown in Fig. 2.

A fleet mission, denoted \(\mathcal {F}\), consists of a set of missions, one for each vehicle,¹ that is \(\mathcal {F} = \left\{ \mathcal {M}(v_1), \mathcal {M}(v_2),\ldots ,\mathcal {M}(v_L)\right\} \). Once a vehicle reaches an end node, it remains there until it is (possibly) given a new mission, which it then immediately starts executing.

A fleet mission specified in this way can be either infeasible, in case there are collisions (or near-collisions; see Sect. 4.2 below) between vehicles, or feasible, in case no such events occur. The primary goal of fleet mission planning is to find feasible missions. An important, but secondary, goal is to make those missions as efficient (i.e. with short duration) as possible.

As for the missions, an incoming (loaded) vehicle will always have the prioritized offloading site as its primary destination (i.e. the end node of the mission) whereas an outgoing (unloaded) vehicle will always have a loading site as its primary destination. Evidently, if the number of incoming vehicles (to the single offloading station) is larger than one, or if the number of outgoing vehicles to any given loading station is larger than one, not all vehicles can reach their primary destination. It follows from this observation that the planning procedure must allow for secondary destinations different from the desired primary destination. Here, only pause nodes are allowed as secondary destinations.

In the case of static fleet mission planning, a single fleet mission is defined, such that the vehicles simply proceed to their destinations (whether primary or secondary), and then remain there indefinitely. By contrast, in dynamic fleet mission planning, where vehicles reaching their primary destination are eventually assigned a new mission, a vehicle blocking any terminal will at some point move away, thus making the terminal accessible to other vehicles.

While considerably simpler than the dynamic case, the static case is in fact highly relevant since (as discussed in Sect. 5 below) the planning in the dynamic case can be cast as a sequence of static plans.

For the case of underground mines of the kind considered here, there are two more conditions (rather than mere feasibility and specification of destinations), that must be imposed on the various missions that form a fleet mission. These conditions will be described next.

Before optimization (described below) can begin, one must generate an initial fleet mission that can act as a starting point for the optimizer. This is done as follows: For each vehicle \(v_k\), given node pairs \((p_i,p_j)\) (start and end), where \(p_i, p_j \in T\), assign a mission \(\mathcal {M}^0(v_k)\) using the path \(\varPi _{0}(p_i,p_j)\), and with \(t_{\mathrm{w}} = 0\) for all mission items. The resulting fleet mission \(\mathcal {F}^{0} = \left\{ \mathcal {M}^{0}(v_1), \mathcal {M}^{0}(v_2),\ldots , \mathcal {M}^{0}(v_L) \right\} \) would be ideal, since all vehicles would start directly, and then move as fast as possible along the shortest possible path. However, in all but the simplest situations, this initial fleet mission is likely to be infeasible, i.e. to involve one or more conflicts, due to the properties of the map. Hence, the next step is to tune the constituent missions in the fleet mission such that any collisions are removed while, at the same time, trying to keep the total fleet mission duration as low as possible.

Note that for a vehicle executing a prioritized mission of type \(\mathcal {M}^{\mathrm{P}}\) introduced above, the only possible modification (during optimization; see below) is to change \(t_{\mathrm{w}}\) for the initial mission item. For non-prioritized missions, however, any number of pause node visits can be inserted as well. The procedure for evaluating and tuning (optimizing) static fleet missions will be described in the following two subsections.

Taking the topological nature of the map into account, the evaluation of a fleet mission can be carried out very efficiently since it is sufficient to check for collisions and other violations only at nodes. The evaluation process proceeds as follows: At any step in the evaluation, the time \(\varDelta t_k\) required for vehicle k to reach the next node (i.e. the end point of the segment in the current mission item) is determined for each vehicle. Thus, a list \(\{\varDelta t_1, \varDelta t_2 \ldots \}\) is generated. Next, the smallest element \(\varDelta t_{\mathrm{min}}\) in the list is found, and time is advanced (in a single, discrete step) by this amount. At this point the vehicle (denoted \(v_{\mathrm{move}}\)) corresponding to the smallest \(\varDelta t\) will thus be at a node, namely the end node of its current segment, here denoted \(p_{\mathrm{min}}\), whereas all other vehicles will be between nodes.³

Next, one needs the notion of a segment pair which is defined, for any two connected nodes \(p_i\) and \(p_j\), as the two segments connecting these two nodes, i.e. the segment from \(p_i\) to \(p_j\) and the reverse segment. One can then check for collisions by simply investigating the situation, at the time just defined, and for the segment pairs such that one of the nodes is the node \(p_{\mathrm{min}}\) introduced above. By construction, these are the only segment pairs where a collision might occur, namely if the number of vehicles is non-zero for both members of any such segment pair. If that is the case, a collision will occur, an event that here is referred to as a segment violation. Note that it is allowed, in principle, to have several vehicles on one of the segments in a segment pair, as long as there are no vehicles on the other (opposing) segment.

In addition, a second check must be carried out, to avoid grazing collisions: Even if no segment violations occur, there can still be cases where, for example, a vehicle passes a node just an instant before another vehicle passes the same node. Since the vehicles are not point particles, one must also avoid this type of grazing collision. However, as the topological map does not have a notion of euclidean distance, one must base the analysis on time instead. Thus, the additional check consists simply of checking, at node \(p_{\mathrm{min}}\), where vehicle \(v_{\mathrm{move}}\) is located at the time of checking, whether any vehicle passed that node, or will pass that node, in a given time range. If that is the case, a grazing collision is detected.

This stepping procedure is then repeated until all vehicles have reached (with or without collisions) their end nodes. With this procedure, the entire evaluation of a fleet mission consists of a rather small set of discrete steps, along with the two violation checks (at each such step) described above.

During evaluation, all collisions are detected and logged, but the fleet mission is allowed to run to completion nevertheless. If any collisions occurred (of any of the kinds described above), the score of the evaluation is set aswhere \(N_{\mathrm{c}}\) is the number of collisions and \(t_{\mathrm{c}}\) is the time to the first collision. \(\beta \) is a small constant, whose value should be smaller than the inverse of the longest possible mission duration (a number that can easily be computed from the topological map), ensuring that the score remains negative as long as there are collisions, while still giving a preference for collisions that occur late, meaning that earlier collisions have already been successfully avoided. If instead no collision is detected, the score is set aswhere \(t_{\mathrm{e}}\) is the time elapsed when all vehicles have completed their missions. \(\xi _{\mathrm{min}}\) is the minimum total number of mission items, obtained for the case in which all vehicles follow their respective \(\varPi _{0}\) path. As mentioned above, in such a case, collisions will in all likelihood occur. Thus, some vehicles (namely those for which the end node is not a prioritized terminal) will need to make one or more visits to pause nodes along the way, thus increasing the number of mission items by two for every such visit. \(\xi \) is the sum (over all missions) of the number of mission items in the fleet mission under consideration. Thus, this measure will attempt to reduce the total time, while also trying to use the shortest possible path, with minimum number of pause node visits, for each vehicle. While the incoming vehicles do not stop (by construction), the outgoing vehicles might make any number of pause node visits. The number of such visits should ideally be minimized, since one or a few long-duration stops would generally be preferable to making many short-duration stops, from a fuel consumption perspective.

Here, a modified genetic algorithm (GA) [28, 29], shown in Algorithm 1, has been chosen for the optimization. As can be seen in Algorithm 1, the algorithm works as follows: First, the initial fleet mission is evaluated as just described, and an initial population (i.e. a set of candidate solutions, referred to as individuals) of size \(\alpha \) is generated by making \(\alpha \) copies of that fleet mission. Given its definition (see above), it is very likely that this mission will involve some collisions and will therefore receive a negative fitness score.

Next, a new generation is formed by applying tournament selection as described in Algorithm 2, followed by mutation of the selected individuals, described in Algorithm 3. The mutations are either parametric (changing the initial waiting times \(t_{\mathrm{w}}\); see also Fig. 4, top panel) or structural (inserting or removing pause node visits; see also Fig. 4). The parametric mutation rate is set dynamically as \(p_{\mathrm{rel}}/\kappa \), where \(\kappa \) is the total number of modifiable parameters for a given fleet mission, i.e. the total number of initial stop times that are allowed values different from zero (see also Sect. 3.3 above). The structural mutation rate is set as \(p_{\mathrm{rel}}/L\), where L is the total number of vehicles. In cases where a structural mutation is to be carried out, insertion or removal occur with equal probability. Crossover (combining two individuals [28]) is not applied, as it is doubtful whether a meaningful crossover operator could be defined that would provide any benefit beyond the structural mutations just described. Elitism [30] is applied, however, by inserting, as the first individual of the new population, a single exact copy of the best individual from the population just evaluated; see Algorithm 1.

Once the new population has thus been generated, all the new individuals are evaluated and assigned fitness values as per Eqs. (1) and (2), and the procedure of selection followed by (parametric and structural) mutation is repeated again etc. The process continues until the maximum allowed optimization time has been reached.

The static fleet mission planning algorithm was implemented in C# .NET and was evaluated using the map shown in Fig. 6. In fact, two instances of this map were generated: One in which all terminals are non-prioritized (so that pause node visits are allowed for all vehicles), and one in which half of the terminals, namely those on the left side of the map, are prioritized, and the other half are non-prioritized. These two maps will be referred to as the non-prioritized map (hereafter: NPR map) and the semi-prioritized map (hereafter: SPR map), respectively. Note that, for the latter, as described in Sect. 4, half of the vehicles will be forced to move along the shortest possible path, without any stops (except before starting the motion). It should also be noted that neither case is particularly representative of a real mine. Instead, these somewhat artificial maps are used merely to investigate the performance of the static fleet mission planning algorithm and to facilitate the comparison (carried out in the NPR map) between, on the one hand, the algorithm introduced here and, on the other hand, the push-and-swap and ODM* algorithms.

In order to carry out a thorough analysis of the static fleet mission planning method, two sets of batch runs were defined, one for each of the two maps just described. In each set, five different configurations where defined, with 2, 4, 6, 8, and 10 vehicles, respectively. For each configuration, a batch of \(n = 1000\) runs were carried out, with random selection of the start and end nodes (for each vehicle) as follows: For a given run \(i, \,\,i = 1,\ldots ,n\), in a configuration with a total of L vehicles (where L is even), the first L / 2 vehicles were assigned randomly selected start nodes (different for each vehicle) from terminals on the left side of the map, whereas the remaining L / 2 vehicles were given randomly selected start nodes (also different for each vehicle) from terminals on the right side of the map. Next, the end nodes of the first L / 2 vehicles, were taken (in order) as the start nodes of the last L / 2 vehicles, and vice versa, thus ensuring that the initial fleet mission, before optimization, would involve conflicts. For both batch runs, vehicles moving from right to left moved with half the speed of the vehicles going the opposite direction, thus simulating a case where vehicles going from right to left are fully loaded, whereas vehicles going the other direction are empty.

In all, the total number of runs was thus equal to \(2 \times 5 \times 1000 = 10,000\), where the factor 5 comes from the number of configurations considered. The duration of each individual optimization run was set at \(D = L \times \tau \) (s). \(\tau \) was set to 3 s. Thus, the maximum optimization time was equal to 30 s (for the case of \(L = 10\) vehicles), which is an acceptable optimization duration for the case of a real mine, where typical mission durations are much longer than that.

Before starting these 10,000 runs, a brief parameter search was carried out in order to find suitable settings for the GA, varying the population size, the relative mutation rate, and the tournament selection parameter. It turned out that the GA was not very sensitive to the exact parameter settings. The selected parameter settings are shown in Table 1. For each individual run, the status of the optimized fleet mission (i.e. feasible or infeasible) was logged. For feasible missions, the total number of mission items (\(\xi \); see also Eq. (2)) was logged, as well as the duration of the fleet mission, defined as the time elapsed from the start until the last vehicle reaches its end node.

The results obtained for the NPR map are given in Table 2, whereas the results from the SPR map are given in Table 3. As can be seen in the tables, the success rate (denoted \(\varSigma \)) was 100% (exactly) for most batch runs, except for one run with 8 vehicles in the SPR map, and for a few runs with 10 vehicles, for both maps. In the rare case of a failed run, the number of mission items is not defined, and those runs have therefore been omitted from the computation of the averages.

The absolute (average) number of mission items \(\overline{\xi }\) grew (as expected) approximately linearly with the number of vehicles. An even more relevant measure is the (average) ratio \(\overline{r}\) between the actual number of mission items, and the minimum number of mission items \(\xi _{0} = \xi _{\mathrm{min}} + 2 \times (L/2)\), equivalent to a case in which half of the vehicles follow the shortest possible path from start to end, and half of the vehicles make a single pause node visit. Thus, this ratio can be taken as a measure of efficiency, and it is bounded from below by 1. A value of 1 can always be reached in principle, by letting the vehicles traverse the map in pairs with all other vehicles standing still. However, such a solution would obviously not be optimal regarding the fleet mission duration; It is the task of the optimizer to find fleet missions with a minimal value of this ratio, while also minimizing the duration of the fleet missions; see also Fig. 7.

The larger values of \(\overline{r}\) obtained for the NPR map (relative to the SPR map) are easily explained by the fact that, in the SPR map, half of the vehicles are required to follow the shortest possible path, whereas this is not the case for the NPR map. Another important fact is that while the average fleet mission duration (\(\overline{\varDelta }\)) grows when the number of vehicles is increased, it grows rather slowly, increasing by less than 100% when the number of vehicles is increased by 400% (from 2 to 10).

Table 4 presents an investigation into the effects of changing the optimization duration (D), for the most challenging case, involving 10 vehicles. As expected, as D is increased, both \(\overline{r}\) and \(\overline{\varDelta }\) decrease. However, the sum of the optimization duration and the (average) mission duration reaches a minimum for \(D \approx 30\) s, at which point also the success rate is near 100%. While slightly smaller average mission durations can be obtained for larger values of D, the decrease is then offset by the increase in \(\overline{\varDelta }\), making \(D = 30\) s a suitable value for practical use for the case of 10 vehicles, and motivating the empirical choice of using \(\tau = 3\) s throughout.

In order to demonstrate the extent to which the GA is able to improve a static fleet mission, a detailed analysis was carried out in which the number of mission items and the fleet mission duration (for the current best individual in the GA) was measured as a function of the number of evaluated generations, starting at the generation at which the first feasible static fleet mission was found. This analysis was carried out for the most challenging case, with 10 vehicles, by selecting a few representative start and end node configurations among the 1000 used in the runs described above, and then running the GA 100 times for each configuration. The results, which were very similar between different configurations, are exemplified for one such configuration in Fig. 7, where the top panel shows the reduction in the number of mission items (relative to the theoretical minimum \(\xi _{0}\)), and the bottom panel shows the reduction in the fleet mission duration, in both cases averaged over the 100 runs.

Since the GA is a stochastic optimization method, the exact generation at which the first feasible mission is found will vary between runs. Thus, for the purpose of this figure, the origin of the horizontal axis has been taken (for each run) as the generation at which the first feasible mission was found, something that typically occurs after around 50 generations. As can be seen in the top panel of the figure, from that point onwards, the GA is able to reduce the number of mission items by around 10 %, reaching a value close to the theoretical minimum. Meanwhile, as shown in the bottom panel, the GA is also able to reduce the fleet mission duration by more than 50%.

Note that, with the population size of 50 individuals and the typical optimization duration \(D = 30\) s (for the 10-vehicle case), the optimizer is able to complete several thousand generations.

For the dynamic case, the simulation runs are, by necessity, carried out in real time: As outlined in Sect. 5 above, in dynamic fleet mission planning, one must take into account the fact that time flows, and therefore that vehicles move, while optimization is taking place. This implies that the optimizer, triggered by an optimization request by a vehicle located at a terminal, must run for a pre-specified duration and must, at the start of the optimization process, take into account the positions at which the (moving) vehicles will be located at the instant when the optimization is completed.

In order to evaluate thoroughly the performance of the proposed method for dynamic planning, several runs were carried out using the C# .NET implementation, and with the optimization settings again taken from Table 1. The runs had a fixed total duration of 14,400 s (4 h), and were carried out in the map shown in Fig. 1, for which the speed was 30 km/h for outbound segments (away from the offloading station). For the inbound segments, a much lower speed (10 km/h) was used in the part of the map leading up to the offloading station, i.e. the steep spiralling corridor referred to in Fig. 1, whereas the speed on all other inbound segments was set to 20 km/h, in both cases accounting for the lower maximum speed attainable by a fully loaded vehicle. As in the static case, only outbound vehicles were allowed to make pause node visits. The typical traversal times for outbound missions were on the order of 500 s. The exact traversal time for an outbound vehicle also depended on the duration of its pause node visits (if any). For inbound missions, the typical traversal times were on the order of 800 s.

The number of vehicles ranged from two to five: While the map has more terminals (seven in total), one should note that there is only a single offloading station, representing a significant bottleneck as soon as there are more than two vehicles in the map. Since the time required for loading and offloading is random (in this case ranging from 2 to 5 min for loading and from 30 s to one minute for offloading), every 4-h run will be different from any other such run and will also involve a non-repeating sequence of different situations to be dealt with by the optimizer, thus providing a thorough test of the proposed method.

Unlike the static case, the dynamic case does not have an obvious benchmark with which it can be compared, to the authors’ knowledge. However, one can define several efficiency measures for evaluating the performance. Here, three such measures have been defined. The first measure is the number of traversals completed, defined as the number of traversals C either from the offloading station to a loading station, or in the opposite direction,⁵ averaged over all vehicles, and then normalized by the number of vehicles.

Two other relevant measures are the idle time fraction at terminals\(i_{\mathrm{t}}\) and the idle time fraction at pause nodes\(i_{\mathrm{p}}\). \(i_{\mathrm{t}}\) is defined as the fraction of the total elapsed time (averaged over all vehicles) spent by vehicles at terminals after completing their necessary task (offloading or loading) at the terminal. In other words, any time spent either for mission optimization or waiting for the mission to start (i.e. in the initial stop time of the first mission item) will contribute to \(i_{\mathrm{t}}\). The unattainable ideal value of this measure would be zero. In reality, it will be larger than zero, since the optimization is not instantaneous and also since vehicles often have to wait a while before starting their motion in order to avoid collisions with other vehicles (especially for inbound vehicles, for which pause node visits are not allowed). \(i_{\mathrm{p}}\) is simply defined as the fraction of the total elapsed time, again averaged over all vehicles, spent at pause nodes. Here, too, the ideal value would be zero, but the actual value will always be positive, since pause node visits are required in order to avoid collisions, at least in maps of the kind considered here.

The results for runs with two, three, four, and five vehicles are summarized in Table 6, where all entries are averages over five runs, each lasting 4 h. In all cases, the runs were all successful. An example can be seen in the accompanying video.⁶

As can be seen in the table, the most important measure of efficiency, namely the number of completed traversals per vehicle, went down (as expected) when the number of vehicles was increased. However, the decrease was rather small: A 150% increase in the number of vehicles (from 2 to 5) resulted in a decrease of only around 27% in the number of traversals per vehicle over the 4-h interval. The larger increases in the idle times, at pause nodes and at terminals, were also expected. A major contributing factor to the increase in the idle time at terminals was the fact that a vehicle at the (single) offloading site would often be kept waiting for quite a while, due to the barrage of incoming vehicles that sometimes made it theoretically impossible to find a solution, keeping in mind that incoming vehicles are not allowed to visit pause nodes. It should be noted that using four or five vehicles in the rather small mine defined in Fig. 1 really pushes the boundary of what is possible in a case with a single offloading site.