Exact algorithm for autonomous dump truck routing in open-pit mines considering coal production

Abstract

This study investigates a truck scheduling problem in open-pit mines, which focuses on optimizing truck transportation and commercial coal production. Autonomous dump trucks are essential transportation tools in the mines; they transport the raw coals and rocks excavated by electric shovels to the unloading stations. Raw coals with different calorific values are processed to produce commercial coals for sale. This process requires maintaining a calorific balance between the excavated raw coals and the blended commercial coals. We formulate a mixed-integer linear programming model for the truck scheduling problem in open-pit mines. The objective of this decision model is to minimize the total working time of all trucks. To solve the proposed model efficiently in large-scale instances, a branch-and-price based exact algorithm is devised. Based on real data of an open-pit mine in Holingol, Inner Mongolia, China, numerical experiments are performed to validate the efficiency of the proposed algorithm. The experiment results show that the optimality gap of the proposed algorithm by comparing with CPLEX is zero; and the solution time of CPLEX is 2.46 times that of the proposed algorithm. Moreover, sensitivity analyses are conducted to derive some managerial insights. For example, open-pit mine managers should carefully consider the truck fleet deployment, including the number of trucks and the capacity of trucks. Additionally, the spatial distribution of unloading stations and electric shovels is crucial for enhancing transportation efficiency in open-pit mines.

Graphical abstract

Keywords

open-pit mines / truck transportation / mixed-integer linear programming / branch-and-price

1 Introduction

With the development of intelligent technology, autonomous vehicles have been used widely across various industries to enhance work efficiency. In the coal mining sector, autonomous dump trucks (hereafter referred to as “trucks”) are becoming increasingly popular, driven by the need to navigate complex production environments and meet strict safety requirements. These trucks rely on wireless communication systems, positioning and navigation systems, and data acquisition systems to achieve autonomous intelligent driving. This technology enables them to efficiently and safely complete material transportation tasks in mining environments (Li and Zhan, 2018). Trucks travel along transportation routes optimized by scheduling systems, which can significantly reduce safety risks caused by human error and improve the efficiency of mineral transportation. An open-pit mine is a type of surface mining where mineral resources are extracted directly from the earth’s surface rather than through underground tunnels, as shown in Fig. 1(a). This method involves removing layers of rock that cover the mineral deposit and exposing the ore for extraction. By working at the surface, open-pit mining allows large machinery to efficiently extract resources like coal, metal ores, and construction materials. In open-pit mining operations, trucks are important for transporting materials, while electric shovels are commonly used for the extraction of materials, as shown in Fig. 1(b). This study focuses on real requirements from an open-pit mine located in Holingol, Inner Mongolia, China, where electric shovels are mainly used for extracting raw coals and rocks. According to the type of extracted materials, there are two types of unloading stations (as shown in Figs. 1(c) and 1(d)): waste dumps and coal crushing stations. The waste dumps are used to store excavated rocks, while the coal crushing stations are used to crush raw coals and process them into commercial coals for sale.

In mining operations, electric shovels are utilized to extract rocks and raw coals. The extracted rocks are transported to the waste dumps to reduce safety risks in the mine, while the extracted raw coals are transported to the coal crushing stations to produce commercial coal. The open-pit mines produce various types of commercial coals with specific calorific values based on customer orders. However, the varying characteristics of coal seams across different locations lead to differences in the calorific values of raw coals excavated by electric shovels. Therefore, the coal crushing stations need to blend raw coals from different electric shovels to meet the calorific value requirements for commercial coals. Typically, coal crushing stations need trucks to accurately transport raw coals with varying calorific values to produce commercial coals. For example, if a customer orders 400 tons of commercial coals with a calorific value of 3400 cal/g, the trucks need to transport 200 tons of raw coals with a calorific value of 3200 cal/g and 200 tons with a calorific value of 3600 cal/g to meet the calorific requirements. This requirement influences the transportation quantity of different types of raw coals and creates challenges for truck scheduling.

Many studies examine transportation scheduling in production systems, offering valuable references to models, methodologies, and managerial insights. In open-pit mines, the truck transportation scheduling problem differs from those in other production systems due to the specific calorific value requirements for commercial coal production. In this study, we develop a truck scheduling problem in open-pit mines, which focuses on both truck transportation and commercial coal production. We formulate a mixed-integer linear programming (MILP) model for the truck scheduling problem, to minimize the total working time of all trucks and optimize their routes and commercial coal production. To efficiently solve the model, we design a branch-and-price (BP) based exact algorithm. Based on the real data of an open-pit mine in Holingol City, China, experimental results demonstrate that the BP-based algorithm effectively and accurately addresses the problem. Additionally, we conduct a sensitivity analysis focused on the relationship between the distribution of electric shovels and unloading stations, the number of trucks in the fleet, and the combinations of truck loading capacity. This analysis provides valuable management insights.

The structure of this study is as follows: Section 2 provides a review of related literature and outlines the current research landscape. Section 3 describes the truck scheduling problem specific to open-pit mining. Section 4 presents the formulation of the MILP model designed to address this scheduling issue. Section 5 details the BP-based algorithm. Section 6 discusses the numerical experiments, including the experimental setup, results, and sensitivity analysis, along with managerial insights. Finally, Section 7 summarizes the conclusions of the study.

2 Related works

As mining technology advances, researchers increasingly focus on the field of mine planning, which employs operations research methods to optimize various issues within mines. Interested readers may refer to the excellent reviews provided by Newman et al. (2010). The authors summarize the applications in operations research for mine planning problems from 1960 to 2010, including mine design, long-and short-term production scheduling, equipment selection, and dispatching. Jélvez et al. (2020) focus on the precedence-constrained production scheduling problem, which involves selecting the blocks (tasks) to extract to maximize total profit. They propose a heuristic algorithm that combines a rolling horizon decomposition with a block preselection procedure to solve the problem efficiently. Brickey et al. (2021) developed a three-dimensional mining plan for ore extraction to satisfy spatial precedence constraints. Souza et al. (2010) proposed an optimization problem for open-pit mines that considers dynamic truck allocation, to minimize the number of used trucks. This paper presents a hybrid algorithm that combines two metaheuristic approaches to solve the problem efficiently. Bakhtavar and Mahmoudi (2020) developed a MILP model to solve a truck-shovel allocation problem in open-pit mining, which employs a scenario-based robust optimization approach to address the issue. However, our study differs from the aforementioned research but is instead a truck scheduling problem.

In open-pit mining operations, the truck scheduling problem is also an important problem of research in mine planning. Patterson et al. (2017) proposed a MILP model to schedule truck transportation to minimize the energy consumption of trucks and shovels with production target constraints. They demonstrate the efficiency of the proposed heuristic algorithm using a case of an operating mine in South-east Queensland. Tian et al. (2021) developed a trajectory planning framework for autonomous mining trucks with engine power and time window constraints. Li et al. (2023) focused on a heavy-duty mining truck trajectory planning problem and formulate an efficient mixed-integer nonlinear program model with conditional constraints. Additionally, some researchers consider factors such as truck travel speed, traffic congestion, and uncertainty in mining operations. Zhang et al. (2022) concentrated on the ability of autonomous trucks to precisely control their speed and develop a MILP model to optimize both truck routes and travel speed. To solve the model efficiently, they propose a two-part tabu search algorithm and demonstrate the effectiveness of the algorithm using a case of a coal mine in Inner Mongolia, China. Zhang et al. (2023) addressed the traffic congestion issue in mine road networks during truck transportation and develop a MILP model by using a time-space network method, to optimize truck routes. Noriega et al. (2025) focused on uncertainties in open-pit mining production and develop a discrete event simulation model. The aforementioned literature primarily uses single-objective, single-stage modeling approaches, some researchers adopt multi-stage, multi-objective models for mine optimization. Shishvan and Benndorf (2019) proposed a multi-stage simulation-based optimization algorithm for material transportation scheduling, integrating mathematical optimization models with stochastic simulation models for solutions. Afrapoli et al. (2019) adopted a multi-objective transportation model for real-time truck dispatching, to minimize shovel idle time, truck waiting time, and deviations from the path production requirements. Our study also addresses the truck transportation problem and constructs a MILP model to minimize the total travel time of all trucks.

In the truck transportation problem, our study also focuses on commercial coal production through the blending of raw coal in mining operations. This topic has been widely explored by many researchers. Ta et al. (2013) formulated a MILP model with ore grade constraints to minimize the number of trucks. Matamoros and Dimitrakopoulos (2016) focused on a short-term mine production scheduling problem with blending restrictions, optimizing the combination of different ore types. Goycoolea et al. (2021) addressed the issue of material grades in mining and propose a time-varying “cutoff grade” policy to optimize the production scheduling of single-metal, single-processor open-pit mines. They design a Lane algorithm to efficiently solve this problem. In addition, many researchers connect open-pit mines and ports to optimize production scheduling. Blom et al. (2014) developed a short-term production scheduling problem for multiple open-pit mines and ports, which considers ore grade and quality. Blom et al. (2016) expanded the problem presented in Blom et al. (2014) to a multiple-time-period production scheduling issue involving multiple open-pit mines and ports. This study regards the combinations of mined products to meet consumers’ demands for ore grade and quality. Haonan et al. (2021) also focus on the integrated optimization problem of mines and ports, which takes into account the blending of products extracted from the mines at port terminals to achieve blending targets.

Additionally, some studies also focus on decision-making for mine optimization from other issues, such as long-term mine planning, truck types and transport environments, and extraction methods and systems. Epstein et al. (2012) considered long-term planning that involves sharing ore reserves among multiple processing plants and open-pit mines to achieve integrated optimization of mining production. Unlike many studies that focus on truck types and transport environments, Riquelme-Rodríguez et al. (2016) optimized the water truck routes and determine the locations of water reservoirs within the mine. Yang et al. (2023) focused on implementing cooperatives for trucks at unloading points in unstructured environments to enhance operational efficiency in these areas. Differing from the traditional extraction way, Nesbitt et al. (2020) designed two ore extraction methods, namely open-stope mining and bottom-up stoping with backfill, to optimize the underground mine design and scheduling problem. Samavati et al. (2020) addressed a novel extraction system by developing a new integer programming model for the open pit mine production scheduling problem.

In summary, this paper integrates decision-making problems related to truck transportation and commercial coal production, which have limited attention in previous research. Within the context of open-pit mines, we optimize truck routes to meet the extraction requirements of electric shovels. Specifically, we focus on commercial coal production and determine the optimal blending ratios of raw coals with different calorific values. Unlike most studies that employ heuristic solutions, we propose a BP-based exact algorithm for efficient problem-solving. Utilizing real-world data for an open-pit mine in Holingol, Inner Mongolia, we conduct some sensitivity analyses to provide some management insights for decision-makers.

3 Problem background

We propose a truck scheduling problem that optimally schedules trucks within a given planning horizon (one or two hours) to improve the efficiency of operations in open-pit mines. The mining process starts with removing the rock overburden to expose coal seams, followed by the extraction of raw coal, which is then crushed and blended to produce commercial coal. Commercial coal is sold in the market for energy production and other uses. Two types of equipment play a central role in the mining and production processes of open-pit mines: electric shovels and unloading stations. Electric shovels are responsible for excavating raw coals as well as excavating the layers of rocks that cover the coal seams. Let S be a set of electric shovels; let S^C and S^R be sets of coal electric shovels and rock electric shovels, respectively, S=S^C\cup S^R, indexed as i,j. The unloading stations are responsible for handling and processing the extracted materials, denoted by D and indexed as i,j. Based on the type of materials, unloading stations can be divided into two types: set D^C is a set of waste dumps that store rocks; while set D^R is a set of coal crushing stations that blend raw coals to produce commercial coals for sale, D=D^C\cup D^C. The transportation of materials within the mine relies on trucks. Let V be the set of trucks, indexed as v. Truck v departs from the starting location o_v, transports marital between elective shovels and unloading stations, and then returns to the ending location o_v. Trucks are responsible for transporting raw coals to coal crushing stations and transporting rocks to waste dumps.

Considering the capacity of each shovel, we define the electric shovels can extract T_i (indexed by t,i\in D) loads of material. The trucks can make multiple trips to the electric shovels to load the materials and transport them to the unloading stations. Therefore, we need to decide which tth (t\in T_i) load of materials excavated by electric shovel i is transported by truck v, represented by the decision variable {\alpha }_{vti}. Additionally, we need to determine which unloading station the load materials are unloaded, defined by the decision variable {\theta }_{vtij}. In addition, the mine managers preliminarily determine the planned extraction quantity for each electric shovel based on the production schedule, denoted as g_i. The maximum production capacity of the coal crushing station is represented by p_i, which is determined by the power of the machinery used at the station. In the mine operation, the quantity of material extracted by the electric shovels ({\sum }_{v\in V}{\sum }_{t\in T_i}h{\alpha }_{vti}) should exceed their planned extraction quantity g_i, while the quantity of commercial coal produced \left({\sum }_{v\in V}{\sum }_{i\in S^C}{\sum }_{t\in T_s}h{\theta }_{vtij}\right) by the coal crushing station should be less than its maximum production capacity p_i. In the transportation of materials, we focus on the truck scheduling problem, which determines truck transport routes to ensure the accurate transport of materials.

In a mining operation, electric shovels excavate materials and load them into trucks, which then unload the materials into the unloading stations. We use parameters l_i to represent the loading time of electric shovel i (or unloading time of unloading station i). The unloading time for one truck is much less than the loading time. In addition, the electric shovel can only load one truck at a time. However, the unloading station is spacious enough to allow multiple trucks to unload simultaneously. Therefore, we consider the sequential loading queue of trucks at the electric shovel. The decision variable {\delta }_{vti} is defined to represent the start time of truck v transports the t-th load of material excavated by electric shovel i, v\in V,i\in S,t\in T_i. When two trucks v,v^{\prime } are scheduled to transport consecutive loads (the t-th load and the (t+1)th load) from the same electric shovel i, the truck v^{\prime } transporting the (t+1)th load must wait until the truck v transporting the t-th load has completed loading before it can begin loading its material. The waiting behavior of the truck v^{\prime } leads to a delay in the transporting start time for the (t+1)th load ({\delta }_{v^{\prime },t+1,i}), which subsequently increases the total working time of the truck. We defined the total working time for truck v to complete the transportation as {\zeta }_v, which includes the travel time, loading and unloading time, as well as waiting time. We establish a truck scheduling plan for a planning horizon to minimize the total working time of the trucks \left({\sum }_{v\in V}{\zeta }_v\right) within that period. Moreover, we define the maximum working time for the trucks as the duration of the planning horizon, and the total working time for each truck cannot exceed the maximum working time.

The coal electric shovels are responsible for excavating raw coals, while the coal crushing stations are responsible for producing commercial coals. Due to the varying characteristics of coal seams at different locations, the calorific value of raw coals extracted by electric shovels also differs across these sites. In a planning horizon, the locations of the electric shovels are considered fixed. Therefore, the calorific values of the extracted coals are also assumed to remain constant. We define the calorific value of the raw coal extracted by the coal electric shovel i is b_i, i\in S^C. The extracted raw coals are used to produce U (indexed as u) types of commercial coals. The calorific value of each type of commercial coal is represented by {\overline{b}}_u, u\in U. We define decision variables {\rho }_{viu} and {\sigma }_{viu} to represent the quantity and the calorific value of raw coals transported by truck v to coal crushing station i for the production of type-u commercial coal, respectively. In the process of blending raw coals, the crushing stations ensure the conservation of calorific value between all mined raw coals and the final blended commercial coals, which means {\sum }_{v\in V}{\sigma }_{viu}={\sum }_{v\in V}{\overline{b}}_u{\rho }_{viu}, u\in U. By maintaining this balance, the station guarantees that the resulting commercial coals meet the required calorific specifications for sale.

Based on the preceding discussion, the truck scheduling problem in open-pit mines should address truck transportation and commercial coal production. To improve mining operational efficiency, our optimization objective is to minimize the total working time of all trucks. For truck transportation, it is crucial to determine truck routes to ensure that materials are transported accurately to designated unloading stations while fulfilling excavation quantity requirements. For commercial coal production, decisions related to maintaining the calorific value balance between mined raw coals and blended commercial coals.

4 Model formulation

4.1 Notations

Before formulating the mathematical model, the notation for both the parameters and decision variables is clearly defined.

Indices and sets:

S set of electric shovels used for mining both raw coals and rocks, indexed by i,j.

D set of unloading stations, which include coal crushing stations and waste dumps, indexed by i,j.

S^R set of electric shovels used for mining rocks, S^R\subset S.

D^R set of waste dumps, D^R\subset D.

S^C set of electric shovels used for mining raw coals, S^C\subset S.

D^C set of coal crushing stations, D^C\subset D.

V set of trucks, indexed by v.

o_v,e_v index of the starting and ending locations for the transportation route of truck v.

T_i set of transportation loads for electric shovel i, indexed by t, where each element corresponds to the t-th load of material excavated by electric shovel i, i\in D.

U set of commercial coal types, indexed by u.

Parameters:

K maximum working time of a truck.

h maximum load of a truck.

p_i maximum production capacity of coal crushing station i, i\in D^C.

g_i planned extraction quantity of electric shovel i, i\in S.

l_i loading time of electric shovel i, or unloading time at unloading station i, i\in S\cup D.

c_{ij} transportation time of location i to location j, i,j\in S\cup D\cup o_v\cup e_v.

b_i calorific value of raw coal extracted by electric shovel i, i\in S^C.

{\overline{b}}_u calorific value of type-u commercial coal, u\in U.

M a sufficiently large positive number.

Decisions variables:

{\alpha }_{vti} binary, equals one if truck v transports the tth load of material excavated by electric shovel i, otherwise zero, v\in V,i\in S,t\in T_i.

{\beta }_{vti{t}^{\prime }{i}^{{}^{\prime }}} binary, equals one if truck v transports the tth load of material excavated by electric shovel i before transporting the t^{\prime }th load of material excavated by electric shovel i^{\prime }, otherwise zero, v\in V,i\in S,t\in T_i,i^{\prime }\in S,t\in T_{i^{\prime }}.

{\gamma }_{vti}^{ST} binary, equals one if truck v transports the tth load of material excavated by electric shovel i from starting location o_v, otherwise zero, v\in V,i\in S,t\in T_i.

{\gamma }_{vti}^{ED} binary, equals one if truck v travels to ending location e_v after transporting the tth load of material excavated by electric shovel i, otherwise zero, v\in V,i\in S,t\in T_i.

{\delta }_{vti} start time of truck v transports the t-th load of material excavated by electric shovel i, v\in V,i\in S,t\in T_i.

{\theta }_{vtij} binary, equals one if truck v transports the tth load of material excavated by electric shovel i to unloading station j, otherwise zero, v\in V,i\in S,t\in T_i,j\in D.

{\rho }_{viu} quantity of raw coals transported by truck v to coal crushing station i for producing type-u commercial coals, v\in V,i\in D^C,u\in U.

{\sigma }_{viu} calorific value of raw coals transported by truck v to coal crushing station i for producing type-u commercial coals, v\in V,i\in D^C,u\in U.

{\zeta }_v total working time for truck v, v\in V.

4.2 Mathematical model

Based on the above defined notation, the MILP model is formulated as follows.

(1)[\mathbf{M}\mathbf{1}]\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}{\sum }_{v\in V}{\zeta }_v.

Objective (1) minimizes the total working time for all trucks, subject to:

(2){\sum }_{v\in V}{\alpha }_{vti}\le 1\mathrm{\forall }i\in S,t\in T_i,

(3){\sum }_{i^{\prime }\in S}{\sum }_{t^{\prime }\in T_{i^{\prime }}}{\beta }_{vti{t}^{\prime }{i}^{\prime }}+{\gamma }_{vti}^{ED}={\alpha }_{vti}\mathrm{\forall }v\in V,i\in S,t\in T_i,

(4){\sum }_{i\in S}{\sum }_{i\in T_i}{\beta }_{vti{t}^{\prime }{i}^{\prime }}+{\gamma }_{v{t}^{\prime }{i}^{\prime }}^{ST}={\alpha }_{v{t}^{\prime }{i}^{\prime }}\mathrm{\forall }v\in V,i^{\prime }\in S,t^{\prime }\in T_{i^{\prime }},

(5){\beta }_{vtiti}=0\mathrm{\forall }v\in V,i\in S,t\in T_i,

(6){\sum }_{i\in S}{\sum }_{t\in T_i}{\gamma }_{vti}^{ST}\le 1\mathrm{\forall }v\in V,

(7){\sum }_{i\in S}{\sum }_{t\in T_i}{\gamma }_{vti}^{ED}\le 1\mathrm{\forall }v\in V,

(8){\sum }_{j\in D}{\theta }_{vtij}={\alpha }_{vti}\mathrm{\forall }v\in V,i\in S,t\in T_i,

(9){\sum }_{j\in D^R}{\sum }_{i\in S^c}{\theta }_{vtij}={\sum }_{j\in D^C}{\sum }_{i\in S^R}{\theta }_{vtij}=0\mathrm{\forall }v\in V,t\in T_i.

Constraint (2) state that each load excavated by an electric shovel can be transported by at most one truck. Constraints (3) and (4) ensure that each valid load, apart from the first one, has precisely one predecessor, while each load, apart from the last one, has exactly one successor, all transported by the same truck. Constraint (5) ensure no loops occur in the truck’s travel route. Constraints (6) and (7) define the first and last loads transported by each truck. Constraint (8) require that each load excavated by the electric shovel must be transported to unloading stations. Constraint (9) restrict raw coal excavated by coal electric shovels must be transported to coal crushing stations, while rock excavated by rock electric shovels must be transported to waste dumps.

(10){\sum }_{v\in V}{\sum }_{t\in T_i}h{\alpha }_{vti}\ge g_i\mathrm{\forall }i\in S,

(11){\sum }_{v\in V}{\sum }_{i\in S^C}{\sum }_{t\in T_i}h{\theta }_{vtij}\le p_j\mathrm{\forall }j\in D^C.

For the electric shovel i\in S, Constraints (10) require that the total quantity of material extracted \left({\sum }_{v\in V}{\sum }_{t\in T_i}h{\alpha }_{vti}\right) from electric shovel i must exceed the planned extraction quantity of the shovel g_i. T_i consider a limit on the extracted material from the shovel, and the mining capacity of an electric shovel is captured by the \left|T_i\right|h. For the coal crushing station j\in D^C, Constraints (11) specify that the total quantity of raw coal \left({\sum }_{v\in V}{\sum }_{i\in S^C}{\sum }_{t\in T_s}h{\theta }_{vtij}\right) crushed at the coal crushing station i must be less than the station’s maximum production capacity p_j.

(12){\delta }_{vti}\ge c_{o_{v}i}{\gamma }_{vti}^{ST}\mathrm{\forall }v\in V,i\in S,t\in T_i,

(13)\begin{array}{c}{\delta }_{v{t}^{\prime }{i}^{\prime }}\ge {\delta }_{vti}+\left(c_{ij}+c_{j{i}^{\prime }}\right){\theta }_{vtij}+l_i+l_j-M(1-{\beta }_{vti{t}^{\prime }{i}^{\prime }})\mathrm{\forall }v\in V,\\ i\in S,t\in T_i,i^{\prime }\in S,{t^{\prime }\in T}_{i^{\prime }},j\in D,\end{array}

(14){\delta }_{v^{\prime },t+1,i}-{\delta }_{vti}\ge l_i{\alpha }_{vti}\mathrm{\forall }v,v^{\prime }\in V,i\in S,t\in T_i\mathrm{\setminus }\left\{\left|T_i\right|\right\},

(15)\begin{array}{c}{\zeta }_v\ge {\delta }_{vti}+\left(c_{ij}+c_{j{e}_v}\right){\theta }_{vtij}+l_i+l_j-M(1-{\gamma }_{vti}^{ED})\mathrm{\forall }v\in V,\\ i\in S,t\in T_i,j\in D\end{array}

(16){\zeta }_v\le K\mathrm{\forall }v\in V.

For the truck v\in V, Constraint (12) define the start time at which the truck begins to transport the first load. Constraint (13) state that the start time for transporting the next load must be after the start time of the previous load. The time interval between the two loads must exceed the sum of the transportation time, the loading time, and unloading time related to the previous load. Constraint (14) define that when trucks transport two consecutive loads (t-th load and (t+1)th load) from the same electric shovel, the time interval between the start times of the t-th load and (t+1)th load must be greater than or equal to the loading time of electric shovel. These constraints ensure that the electric shovel only loads one truck at a time. Constraint (15) define the total working time for a truck. This includes travel time, loading and unloading time, as well as waiting times. Constraints (16) ensure that the working time of a truck does not exceed its maximum working time.

(17){\sum }_{u\in U}{\rho }_{vju}={\sum }_{i\in S^c}{\sum }_{t\in T_i}h{\theta }_{vtij}\mathrm{\forall }v\in V,j\in D^C,

(18){\sum }_{u\in U}{\sigma }_{vju}={\sum }_{i\in S}{\sum }_{t\in T_i}{b}_{i}h{\theta }_{vtij}\mathrm{\forall }v\in V,j\in D^C,

(19){\sum }_{v\in V}{\sigma }_{viu}={\sum }_{v\in V}{\overline{b}}_u{\rho }_{viu}\mathrm{\forall }i\in D^C,u\in U.

For the coal crushing stations i\in D^C, Constraints (17) and (18) address both the quantity and the calorific value of the raw coal transported to the coal crushing station i for commercial coal production. Constraint (17) specify the quantity of raw coal transported by truck v to the coal crushing station i for all types of commercial coal production. Constraint (18) define the calorific value of the raw coal transported by truck v to the station i for all types of commercial coal production. Constraint (19) ensures that the total calorific value of the raw coal transported by all trucks matches the calorific value of the blended commercial coal produced.

(20){\alpha }_{vti},{\gamma }_{vti}^{ST},{\gamma }_{vti}^{ED},{\theta }_{vtij}\in \left\{0,1\right\}\mathrm{\forall }v\in V,i\in S,t\in T_i,j\in D,

(21){\beta }_{vti{t}^{\prime }{i}^{\prime }}\in \left\{0,1\right\}\mathrm{\forall }v\in V,i\in S,t\in T_i,i^{\prime }\in S,t^{\prime }\in T_{i^{\prime }},

(22){\delta }_{vti},{\zeta }_v\ge 0\mathrm{\forall }v\in V,i\in S,t\in T_i,

(23){\rho }_{viu},{\sigma }_{viu}\ge 0\mathrm{\forall }v\in V,i\in D^C,u\in U.

Constraints (20)– (23) define the decision variables.

5 Branch-and-price based algorithm

Although model M1 can be solved using commercial solvers like CPLEX, it becomes difficult to handle efficiently for large-scale problems. To address this, we develop an BP-based exact based algorithm based on the work of Costa et al. (2019). The BP-based algorithm combines column generation (CG) with branch-and-bound, which also be applied in Hernandez et al. (2016), allowing us to handle large-scale problems by optimizing over a reduced set of variables while maintaining solution feasibility.

5.1 Set partitioning reformulation

We employ Dantzig-Wolfe decomposition introduced by Dantzig and Wolfe (1960) to formulate the master problem (MP) and execute the CG procedure. Let {\mathcal{M}}_v denote the set of all possible transport routes for truck v from the starting location o_v to the ending location e_v. Each route m_v\in {\mathcal{M}}_v represents a complete route for truck v, beginning at o_v, traveling between electric shovels and unloading stations to transport raw coal or rock, and go back to ending location e_v. Let {\tau }_{m_v} be a binary variable for route m_v, where {\tau }_{m_v} equals to one if truck v selects route m_v, otherwise zero. The total time of route m_v is defined {\kappa }_{w_v}, including the total travel time, loading time and unloading time, waiting time in route m_v. For each route m_v, the parameters as follow:

r_{m_{v}ti} binary, equals one if route m_v transports the tth load of coal or rock on electric shovel s, otherwise zero, i\in S,t\in T_i.

w_{m_{v}ti} start time of route m_v transports the tth load of coal or rock on electric shovel i, i\in S,t\in T_i.

x_{m_{v}tij} binary, equals one if route m_v transports the tth load of coal or rock from electric shovel i to unloading station j, otherwise zero, i\in S,t\in T_i,j\in D.

y_{m_{v}iu} quantity of raw coal transported by route m_v to coal crushing station i for the production of type-u commercial coal, i\in D^C,u\in U.

{\mathrm{z}}_{m_{v}iu} calorific value of raw coal transported by route m_v to coal crushing station i for type-u of commercial coal production, i\in D^C,u\in U.

According to the parameters and variables above, a covering model can be set as follows:

(24)[\mathbf{M}\mathbf{P}]\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}{\sum }_{v\in V}{\sum }_{m_v\in {\mathcal{M}}_v}{\kappa }_{m_v}{\tau }_{m_v}

subject to:

(25){\sum }_{m_v\in {\mathcal{M}}_v}{\tau }_{m_v}\le 1\mathrm{\forall }v\in V,

(26){\sum }_{v\in V}{\sum }_{m_v\in {\mathcal{M}}_v}{r}_{m_{v}ti}{\tau }_{m_v}\le 1\mathrm{\forall }i\in S,t\in T_i,

(27){\sum }_{v\in V}{\sum }_{m_v\in {\mathcal{M}}_v}{\sum }_{t\in T_i}h{r}_{m_{v}ti}{\tau }_{m_v}\ge g_i\mathrm{\forall }i\in S,

(28){\sum }_{v\in V}{\sum }_{m_v\in {\mathcal{M}}_v}{\sum }_{i\in S^C}{\sum }_{t\in T_s}h{x}_{m_{v}tij}{\tau }_{m_v}\le p_j\mathrm{\forall }j\in D^C,

(29)\begin{array}{c}{\sum }_{v\in V}{\sum }_{m_v\in {\mathcal{M}}_v}{w}_{m_v,t+1,i}{\tau }_{m_v}-{\sum }_{v\in V}{\sum }_{m_v\in {\mathcal{M}}_v}{w}_{m_{v}ti}{\tau }_{m_v}\\ \ge l_i{\sum }_{v\in V}{\sum }_{m_v\in {\mathcal{M}}_v}{r}_{m_{v}ti}{\tau }_{m_v}\mathrm{\forall }i\in S,t\in T_i\mathrm{\setminus }\left\{\left|T_i\right|\right\},\end{array}

(30)\begin{array}{c}{\sum }_{v\in V}{\sum }_{m_v\in {\mathcal{M}}_v}{z}_{m_{v}iu}{\tau }_{m_v}=\\ {\sum }_{v\in V}{\sum }_{m_v\in {\mathcal{M}}_v}{\overline{b}}_u{y}_{m_{v}iu}{\tau }_{m_v}\mathrm{\forall }i\in D^C,u\in U,\end{array}

(31){\tau }_{m_v}\in \left\{0,1\right\}\mathrm{\forall }v\in V,m_v\in {\mathcal{M}}_v.

Objective (24) minimizes the total working time of all trucks. Constraint (25) restrict each truck to selecting at most one route. Constraint (26) ensure that each load excavated by an electric shovel is transported by no more than one truck. Constraint (27) stipulate that the total quantity of materials loaded by all trucks at the electric shovel i\in S must exceed the planned extraction quantity of the electric shovel. Constraint (28) ensure that the total quantity of materials unloaded by all trucks at the coal crushing station i\in D^C remains within the station’s maximum processing capacity. Constraint (29) ensure that when trucks transport two consecutive loads from the same electric shovel, the time between the transports must be at least the electric shovel’s loading time, guaranteeing that the electric shovel loads only one truck at a time. Constraint (30) state that the total calorific value of all raw coal transported to coal crushing station i\in D^C matches the calorific value of the commercial coal produced at the station. Constraint (31) define decision variable {\tau }_{m_v}.

5.2 Restricted master problem

As the size of the MP model instance increases, the complexity, solution space, and solving time rise exponentially, making it impractical to solve the entire set of schedules directly. To overcome this, the CG process typically addresses the linear programming (LP) relaxation of the model. We formulate an RMP that includes a set of possible routes for each truck within the CG algorithm, which is denoted as {\mathcal{M}}_v^{\prime }\subseteq {\mathcal{M}}_v. The RMP is formulated as follows:

(32)[\mathbf{R}\mathbf{M}\mathbf{P}]\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}{\sum }_{v\in V}{\sum }_{m_v\in {\mathcal{M}}_v^{\prime }}{\kappa }_{m_v}{\tau }_{m_v},

subject to: Constraint (25)–Constraint (30)

(33){\tau }_{m_v}\ge 0\mathrm{\forall }v\in V,m_v\in {\mathcal{M}}_v^{\prime }.

The following are the definitions for these six variables:

{\pi }_v dual variables for Constraint (25), \mathrm{\forall }v\in V.

{\varpi }_{it} dual variables for Constraint (26), \mathrm{\forall }i\in S,t\in T_i.

{\varrho }_i dual variables for Constraint (27), \mathrm{\forall }i\in S.

{\varsigma }_i dual variables for Constraint (28), \mathrm{\forall }i\in D^C.

{\phi }_{it} dual variables for Constraint (29), \mathrm{\forall }i\in S, t\in T_i\mathrm{\setminus }\left\{\left|T_i\right|\right\}.

{\psi }_{iu} dual variables for Constraint (30), \mathrm{\forall }i\in D^C,u\in U.

5.3 Pricing problem

This subsection introduces the pricing problem based on the dual variables from the RMP solution, which generates new columns for the next RMP iteration. Before modeling the pricing problem, the relevant parameters and decision variables for truck v\in V are listed.

Input parameters:

{\pi }_v,{\varpi }_{it},{\varrho }_i,{\varsigma }_i,{\varphi }_{it},{\psi }_{iu} dual variables obtained from the RMP.

o,e the starting and ending locations for transportation route.

Decisions variables:

{\alpha }_{ti} binary, equals one if the route transports the tth load of material excavated by electric shovel i, otherwise zero, i\in S,t\in T_i.

{\beta }_{ti{t}^{\prime }{i}^{\prime }} binary, equals one if the route transports the tth load of material excavated by electric shovel i before transporting the t^{\prime }th load of material excavated by electric shovel i^{\prime }, otherwise zero, i\in S,t\in T_i,i^{\prime }\in S,t\in T_{i^{\prime }}.

{\gamma }_{ti}^{ST} binary, equals one if the route transports the tth load of material excavated by electric shovel i from starting location o, otherwise zero, i\in S,t\in T_i.

{\gamma }_{ti}^{ED} binary, equals one if the route travels to ending location e after transporting the tth load of material excavated by electric shovel i, otherwise zero, i\in S,t\in T_i.

{\delta }_{ti} start time of the route transports the tth load of material excavated by electric shovel i, i\in S,t\in T_i.

{\theta }_{tij} binary, equals one if the route transports the tth load of material excavated by electric shovel i to unloading station j, otherwise zero, i\in S,t\in T_i,j\in D.

{\rho }_{iu} quantity of raw coal transported by the route to coal crushing station i for the production of type-u commercial coal, i\in D^C,u\in U.

{\sigma }_{iu} calorific value of raw coal transported by the route to coal crushing station i for type-u of commercial coal production, i\in D^C,u\in U.

{\kappa }_{m_v} total working time of the route m_v.

(34)\begin{array}{c}[\mathbf{P}\mathbf{P}]\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}{\kappa }_{m_v}-{\pi }_v-{\sum }_{i\in S}{\sum }_{t\in T_i}{\varpi }_{it}{\alpha }_{ti}\\ -{\sum }_{i\in S}{\sum }_{t\in T}h{\varrho }_i{\alpha }_{ti}-{\sum }_{j\in D^C}{\sum }_{i\in S^C}{\sum }_{t\in T_s}h{\varsigma }_i{\theta }_{tij}\\ +{\sum }_{i\in S}{\sum }_{T_i\mathrm{\setminus }\left\{\left|T_i\right|\right\}}{\varphi }_{it}\left(l_i{\alpha }_{ti}-{\delta }_{t+1,i}+{\delta }_{ti}\right)\\ +{\sum }_{i\in D^C}{\sum }_{u\in U}{\psi }_{iu}\left({\overline{b}}_u{\rho }_{iu}-{\sigma }_{iu}\right).\end{array}

Objective (34) seeks to minimize the reduced cost.

subject to:

(35){\sum }_{i^{\prime }\in S}{\sum }_{t^{\prime }\in T_{i^{\prime }}}{\beta }_{ti{t}^{\prime }{i}^{\prime }}+{\gamma }_{ti}^{ED}={\alpha }_{ti}\mathrm{\forall }i\in S,t\in T_i,

(36){\sum }_{i\in S}{\sum }_{i\in T_i}{\beta }_{ti{t}^{\prime }{i}^{\prime }}+{\gamma }_{t^{\prime }{i}^{\prime }}^{ST}={\alpha }_{t^{\prime }{i}^{\prime }}\mathrm{\forall }{i}^{\prime }\in S,t^{\prime }\in T_{i^{\prime }},

(37){\beta }_{titi}=0\mathrm{\forall }i\in S,t\in T_i,

(38){\sum }_{i\in S}{\sum }_{t\in T_i}{\gamma }_{ti}^{ST}\le 1,

(39){\sum }_{i\in S}{\sum }_{t\in T_i}{\gamma }_{ti}^{ED}\le 1,

(40){\sum }_{j\in D}{\theta }_{tij}={\alpha }_{ti}\mathrm{\forall }i\in S,t\in T_i,

(41){\sum }_{j\in D^R}{\sum }_{i\in S^c}{\theta }_{tij}={\sum }_{j\in D^C}{\sum }_{i\in S^R}{\theta }_{tij}=0\mathrm{\forall }\in T_i,

(42){\delta }_{ti}\ge c_{oi}{\gamma }_{ti}^{ST}\mathrm{\forall }i\in S,t\in T_i,

(43)\begin{array}{c}{\delta }_{t^{\prime }{i}^{\prime }}\ge {\delta }_{ti}+\left(c_{ij}+c_{j{i}^{\prime }}\right){\theta }_{tij}+l_i+l_j-M(1-{\beta }_{ti{t}^{\prime }{i}^{\prime }})\mathrm{\forall }i\in S,\\ t\in T_i,i^{\prime }\in S,{t^{\prime }\in T}_{i^{\prime }},j\in D,\end{array}

(44)\begin{array}{c}{\kappa }_{m_v}\ge {\delta }_{ti}+\left(c_{ij}+c_{je}\right){\theta }_{tij}+l_i+l_j-M(1-{\gamma }_{ti}^{ED})\\ \mathrm{\forall }i\in S,t\in T_i,j\in D,\end{array}

(45){\sum }_{u\in U}{\rho }_{ju}={\sum }_{i\in S^c}{\sum }_{t\in T_i}h{\theta }_{tij}\mathrm{\forall }j\in D^C,

(46){\sum }_{u\in U}{\sigma }_{ju}={\sum }_{i\in S}{\sum }_{t\in T_i}{b}_{i}h{\theta }_{tij}\mathrm{\forall }j\in D^C,

(47){\kappa }_{m_v}\le H,

(48){\alpha }_{ti},{\gamma }_{ti}^{ST},{\gamma }_{ti}^{ED},{\theta }_{tij}\in \left\{0,1\right\}\mathrm{\forall }i\in S,t\in T_i,j\in D,

(49){\beta }_{ti{t}^{\prime }{i}^{\prime }}\in \left\{0,1\right\}\mathrm{\forall }i\in S,t\in T_i,i^{\prime }\in S,t^{\prime }\in T_{i^{\prime }},

(50){\delta }_{ti}\ge 0\mathrm{\forall }i\in S,t\in T_i,

(51){\rho }_{iu},{\sigma }_{iu}\ge 0\mathrm{\forall }i\in D^C,u\in U,

(52){\kappa }_{m_v}\ge 0.

Constraints (35) and (36) define the loading sequence for the truck. Constraint (37) prevent loops in the truck’s travel route. Constraints (38) and (39) identify the first and last loads carried by the truck. Constraint (40) ensure that each load excavated by the electric shovel is transported to unloading stations. Constraint (41) limit raw coal only being transported to coal crushing stations and rock must to waste dumps. Constraint (42) define the start time for the truck to start its first load. Constraint (43) define that the truck must complete the transportation of the previous load before starting the next load. Constraint (44) define the total working time for the truck. Constraints (45) and (46) define the quantity and calorific value of raw coal used for commercial coal production, respectively. Constraint (47) require that the total working time of the truck does not exceed its maximum working time. Finally, Constraints (48) through (52) define the decision variables.

5.4 Branching strategy

By executing the previously outlined CG process, we obtain the optimal solution to the LP problem. However, this optimal solution is often not an integer. Therefore, we apply branch and bound to further process the LP solution to obtain a feasible integer solution. After running the CG procedure, we derive the values of each route (i.e., the values of the variables {\tau }_{m_v}, where v\in V,m_v\in {\mathcal{M}}_v). Each route includes the loading sequence of the trucks, the start time for each load, and the unloading stations for each load. In the optimal solution of the LP, a truck may choose multiple routes, with various loading sequences. Thus, we construct a binary tree for branching and establish the corresponding branching strategy.

We propose the branching strategy and define an indicator b_{vti{t}^{\prime }{i}^{\prime }}\leftarrow {\sum }_{m_v\in {\mathcal{M}}_v}{s}_{m_{v}ti{t}^{\prime }{i}^{\prime }}{\tau }_{m_v} for v\in V,i\in S,t\in T_i, i^{\prime }\in S,t\in T_{i^{\prime }}. We arrange the b_{vti{t}^{\prime }{i}^{\prime }} in increasing order based on \left|b_{vti{t}^{\prime }{i}^{\prime }}-0.5\right| and choose the first one b_{v{t}^{\ast }{i}^{\ast }{t^{\prime }}^{\ast }{i^{\prime }}^{\ast }}, it represents the b_{vti{t}^{\prime }{i}^{\prime }} value closest to 0.5. The selected two loads are the t^{\ast }th load excavated by shovel i^{\ast } and the {t^{\prime }}^{\ast }th load excavated by shovel {i^{\prime }}^{\ast }. This process creates two new child nodes in the branch tree. In the left child node, the {t^{\prime }}^{\ast }th load excavated by shovel {i^{\prime }}^{\ast } must be transported immediately after the t^{\ast }th load excavated by shovel i^{\ast }. In the right child node, it is forbidden to transport {t^{\prime }}^{\ast }th load excavated by shovel {i^{\prime }}^{\ast } after the t^{\ast }th load excavated by shovel i^{\ast }.

To effectively handle the new child nodes in the branch tree, some branching constraints are added to both the RMP and PP for each child node. In the left child node, all transport routes m_v where s_{m_v{t}^{\ast }{i}^{\ast }{t^{\prime }}^{\ast }{i^{\prime }}^{\ast }}=0 in the RMP are removed. In the PP, a constraint is added to ensure that the {t^{\prime }}^{\ast }th load excavated by shovel {i^{\prime }}^{\ast } is transported immediately after the t^{\ast }th load from shovel i^{\ast }. In the right child node, transport routes where s_{m_v{t}^{\ast }{i}^{\ast }{t^{\prime }}^{\ast }{i^{\prime }}^{\ast }}=1 in the RMP are removed, and a constraint is added in the PP to prevent the {t^{\prime }}^{\ast }th load excavated by shovel {i^{\prime }}^{\ast } from being transported after the t^{\ast }th load excavated by shovel i^{\ast }.

In the node selection strategy, we use the best-lower-bound rule and the depth-first rule. If the objective value of the current node reaches or exceeds the upper bound, we prune that node. When a node is pruned, we select the node with the lowest lower bound from the list for the next exploration. If the node is not pruned, we explore the left child of the current parent node instead.

5.5 Generation of the initial solution

To apply the CG procedure, we first generate an initial set of feasible routes for the RMP, ensuring that the RMP produces at least one feasible solution. We use a greedy algorithm (GA) to generate the driving route for each truck. In this algorithm, we aim to minimize the total working time of the trucks while ensuring that the calorific value and quantity of the transported material meet the mining and production requirements. The steps of our greedy algorithm are as follows:

Step 1: Initialize the minimum access count for each electric shovel according to the planning extraction quantity.

Step 2: Assign trucks to the nearest available location. Each time, a truck is selected and assigned to the nearest available location, which ensures the workflow is maintained and has a remaining visit count greater than zero. For example, after a truck completes a task for an excavator, it should visit the nearest coal crushing station. After the minimum access count for each electric is zero, proceed to Step 3.

Step 3: Update coal requirements and secondary visits for electric shovels. Based on the calorific value requirements of commercial coal, update the secondary visit count for the electric shovels.

Step 4: Repeat to assign truck until all electric shovels have zero secondary visits remaining.

5.6 Framework of the branch-and-price based algorithm

To provide a clearer understanding of the BP-based algorithm, the previous sections outlined its key steps. Below, we present the overall framework of the proposed algorithm.

Step 0: The initial routes are generated as outlined in Section 5.5. Define {\mathbb{x}}^{\ast } as the current best solution and UB as the objective value corresponding to this best solution. Define \mathbb{N} as the current nodes list in the branch and bound tree, initializing it to an empty set \mathbb{N}\leftarrow \varnothing. The RMP is established with the initial routes as the current parent node, and {\mathbb{x}}^{\ast }\leftarrowinitial feasible solution, UB\leftarrowinitial objective value.

Step 1: Solve the RMP of the current parent node using the CG procedure to obtain the LP relaxation. Define the LP solution as \mathbb{x} and the current objective value as {\mathbb{z}}_{LP}\left(\mathbb{x}\right).

Sub-step 1–1: If and \mathbb{x} is a non-integer infeasible solution, go to Step 2.

Sub-step 1–2: If and \mathbb{x} is an integer feasible solution, set {\mathbb{x}}^{\ast }\leftarrow \mathbb{x}, UB\leftarrow {\mathbb{z}}_{LP}\left(\mathbb{x}\right), and go to Step 3.

Sub-step 1–3: If {\mathbb{z}}_{LP}\left(\mathbb{x}\right)\ge UB, prune this node, and go to Step 3.

Step 2: Choose the branching decision variable based on the branching strategy from Section 5.4 and branch the current parent node into two child nodes (a left child node and a right child node) by adding specific constraints. The left child node is designated as the new current parent node, while the right child node is added to the current nodes list \mathbb{N}. Then, go to Step 1.

Step 3: If \mathbb{N} is empty, stop the whole BP-based algorithm; otherwise, select the node with the lowest LB value from the current node list \mathbb{N} and set it as the current parent node, go to Step 1.

6 Computational experiments

To test the correctness of the proposed model and the effectiveness of the proposed algorithm, we conduct numerous computational experiments. All experiments are performed on a workstation with an Intel(R) Xeon(R) Platinum 8360Y CPU @ 2.40GHz 3.50 GHz and 128GB RAM. The model and algorithm are implemented in C# and use CPLEX solver version 12.6.1. Each experiment has a 3,600-s time limit.

6.1 Generation of test instances

This study is motivated by the practical requirements of an open-pit mine in Holingol, Inner Mongolia, China. The open-pit coal mine operates 10 WK-10B electric shovels, including 4 shovels for excavating raw coal and 6 shovels for excavating rock. During each excavation, the loading time of shovels varies from 120 to 300 s due to the differences in the size and shape of excavated raw coals and rocks. The theoretical productivity of each electric shovel is 1170 tons/h. The mine also includes 6 unloading stations, with 2 coal crushing stations and 4 waste dumps. The maximum processing capacities of two coal crushing stations are 4000 tons/h and 4500 tons/h, respectively. The truck unloading process is straightforward and fast, with an average unloading time of 60 s. In the mine, the electric shovels excavate four types of raw coal. The calorific values of four types of raw coal are 3,000 cal/g, 3,200 cal/g, 3,300 cal/g, and 3,500 cal/g, respectively. Based on customer orders, the coal crushing stations produce two types of commercial coal: calorific values of 3,100 cal/g and 3,400 cal/g. The mine operates 30 Caterpillar 777G trucks with a load capacity of 100 tons. Trucks can operate continuously in the mine along predetermined routes. In our experiments, we develop a two-hour operational plan for the trucks.

Using real data from the mine, we conduct computational experiments to verify the efficiency of the proposed algorithm and assess the correctness of the decision model. We use six instance groups (ISGs) in the experiments, and the parameters for these instance scales are detailed in Table 1. For each instance group, we conduct five sets of experiments, labeled ID1 to ID5. The difference between each ID within the same instance group lies in the planned excavation quantity and loading time of each electric shovel.

6.2 Performance of the BP-based algorithm

We conduct experiments to evaluate the performance of solutions calculated by the BP-based algorithm. The solution performance is measured by the optimality gap, defined as the difference between the solutions generated by the proposed algorithm and the optimal solutions obtained from CPLEX. Furthermore, we also design a GA algorithm to solve the M1 model and evaluate its performance. Table 2 presents the results of the comparative analysis for small-scale instances.

The optimality gap ({Gap}_{BP}^{CP}) of the BP-based algorithm compared to CPLEX is zero, which indicates the BP-based algorithm provides high-quality solutions. Compared to the solution times of the BP-based algorithm and CPLEX, the BP-based algorithm spends more time than CPLEX to solve the problem in ISG1. However, as the problem size increases, CPLEX’s solution time grows significantly, while the BP-based algorithm continues to find optimal solutions efficiently. In ISG3, the solution time of CPLEX is 2.46 times that of the BP-based algorithm. This demonstrates that the BP-based algorithm not only delivers high-quality solutions but also solves problems faster and more efficiently. Additionally, the optimal gap ({Gap}_{GA}^{CP}) of the GA algorithm compared to CPLEX is 2.24%, which demonstrates the effectiveness of the GA algorithm. Therefore, the optimality of the solution provided by the BP-based algorithm is confirmed and the efficiency of the GA algorithm is also validated.

In large-scale instances, CPLEX cannot find an optimal solution within 3600 s. Thus, we compare the solution generated by the BP-based algorithms with those obtained from the GA algorithm to evaluate the performance of the BP-based algorithms. Table 3 presents the results of the comparative analysis for large-scale instances. The values in the “Gap” column in Table 3 show that the solutions obtained by the BP-based algorithm have an average reduction of 13.54% compared to those obtained by the GA algorithm. Notably, in ISG6, the reduction increases significantly to 20.22%. Therefore, the results show that the BP-based algorithm offers high solution quality, fast solving speed, and effectively addresses problems even at large scales.

6.3 Managerial insights derived from sensitivity analyses

In this section, we conduct some sensitivity analysis to gain management insights. The analysis focuses on three factors that impact all trucks’ total working time: the locations distribution of electric shovels and unloading stations, the number of trucks, the combination of truck loading capacity in the truck fleet. In addition, we also analyzed the impact of the calorific value of raw coal on the production of commercial coal. We aim to provide insights into the location distribution from a long-term strategic planning perspective, as well as recommendations on the number and loading capacity of trucks in the fleet from a short-term tactical perspective.

6.3.1 Determining the proper location distribution of shovel and stations

In mining operations, the location distribution of electric shovels and unloading stations is different. Therefore, we propose three location distributions of electric shovels and unloading stations to conduct experiments. These distributions are referred to as random distribution, material-specific clustered distribution, and equipment-specific clustered distribution. Each distribution has the following characteristics: (a) In the random distribution, shovels and stations are scattered throughout the mining area. The unloading stations are randomly distributed in the mining area. (b) In the material-specific clustered distribution, electric shovels and unloading stations that excavate and process the same type of material are clustered together. The materials include two types: coal and rock. For example, coal crushing stations are placed close to areas where coal electric shovels operate, while waste dumps are located near areas where rock electric shovels are excavating. (c) In the equipment-specific clustered distribution, equipment of the same type is clustered together. The equipment includes two types: electric shovels and unloading stations. The electric shovels are grouped within the mining area, while the unloading stations are clustered outside the mining area.

Figure 2 shows that in material-specific clustered distribution, the total working time for all trucks is the shortest, followed by random distribution. In contrast, equipment-specific clustered distribution shows the longest total working time. This is because both material-specific clustered distribution and random distribution place electric shovels and unloading stations in the mining area. Compared to equipment-specific clustered distribution, this results in reduced transportation distances for the trucks. Additionally, compared to random distribution, the material-specific clustered distribution enhances the material handling process efficiency where the unloading stations are situated close to the electric shovels that extract the same type of material. This distribution not only enhances immediate operational efficiency but also supports more effective resource allocation and management. The open-pit managers should position electric shovels and unloading stations within the mining area. Furthermore, they should determine the location distribution based on the material handling process to optimize operational efficiency and minimize the total working time of all trucks.

6.3.2 Determining the proper number of trucks

We examine the effect of the number of trucks on the total working time for all trucks to determine the proper number required. Based on real mining data, we analyze the proper number of trucks by using an ISG with 6 electric shovels and 4 unloading stations. The results are illustrated in Fig. 3, where we observe that the optimal number of trucks is 6. When the number of trucks is less than 6, the total working time for all trucks increases. Conversely, when the number of trucks exceeds 6, the total working time remains unchanged. At this point, adding more trucks will not further improve transportation efficiency because the key bottleneck in mine transportation is the loading and unloading time, not the number of trucks. More than six trucks would not be actively involved in transportation; they would be idle, with no additional impact on total work time. This indicates that having more trucks is not necessarily performing better. Therefore, managers should determine the proper number of trucks to reduce equipment purchase costs and enhance truck operational efficiency.

6.3.3 Determining the proper combination of trucks with different loading capacities

In the current model, we use the same loading capacity trucks to transport material. However, in real-world scenarios, a fleet may consist of trucks with varying loading capacities. Therefore, we explore different combinations of truck loading capacities in a fleet to identify the optimal combination. We design three truck types with different capacities, which are as follows: (a) the Caterpillar 773E truck with a load capacity of 50 tons, (b) the Caterpillar 777G truck with a load capacity of 100 tons, and (c) the EH3500AC-3 truck with a load capacity of 150 tons. Based on three types of truck loading capacities, we design four combinations of these capacities as follows: (i) two trucks with a load capacity of 50 tons and three trucks with a load capacity of 100 tons; (ii) four trucks with a load capacity of 100 tons; (iii) one truck with a load capacity of 50 tons, two trucks with a load capacity of 100 tons, and one truck with a load capacity of 150 tons; and (iv) one truck with a load capacity of 100 tons and two trucks with a load capacity of 150 tons. We ensure that the total load capacity of all trucks in each combination equals 400 tons to maintain fairness in the experiments.

The results in Fig. 4 indicate that combination 4 performs the best, followed by combination 3, while combinations 1 and 2 show the poorest performance. This is because combinations 3 and 4 include the largest capacity truck, the EH3500AC-3 truck with a load capacity of 150 tons. This enables the trucks to transport larger quantities of materials in a single load, which reduces the number of required loads and expedites the overall transportation process. Additionally, the proportion of large capacity trucks in combination 4 is greater than that in combination 3. This result indicates that a higher percentage of large capacity trucks can lead to shorter total working times for all trucks. However, it is important to note that although combination 2 has a higher proportion of large capacity trucks (the Caterpillar 777G truck with a load capacity of 100 tons) compared to combination 1, both combinations have the same objective value. This suggests that while increasing the proportion of large capacity trucks can improve performance, it does not always guarantee better outcomes. The mine can incorporate large capacity trucks into the fleet and set a reasonable proportion for the large capacity of trucks.

6.3.4 Determining the type of commercial coal for production

In open-pit mining production, different raw coals with varying calorific values are blended to produce commercial coal with a fixed calorific value. We propose an experiment to examine the impact of the raw coal’s calorific value on commercial coal production. We design there are four types of commercial coal, with calorific values of 3100, 3200, 3300, and 3400 cal/g, respectively. We also design five scenarios for the calorific value distribution of raw coal, where in each case, the calorific value follows a uniform distribution. The values are U(3000, 3200), U(3000, 3400), U(3100, 3400), U(3200, 3500), and U(3300, 3500), respectively. We calculate the average calorific value of the commercial coal produced under different calorific value distributions of raw coal scenarios, which is calculated by {\sum }_{v\in V}{\sum }_{i\in D^C}{\sum }_{u\in U}{\rho }_{viu}/{\sum }_{v\in V}{\sum }_{i\in D^C}{\sum }_{u\in U}{\sigma }_{viu}. The experimental results in Fig. 5 indicate a positive relationship between the calorific value of raw coal and that of the commercial coal produced.

7 Conclusions

This study investigates the truck scheduling problem in open-pit mines, which focuses on materials transportation, truck waiting time, excavation planning, and commercial coal production. To address this complex issue, we develop a MILP model and designed a BP-based exact algorithm to solve the model. The main contributions of this study are categorized into three perspectives:

From the perspective of mathematical modeling, we construct the truck scheduling problem based on the real conditions of an open-pit mine located in Inner Mongolia, China. This problem involves making decisions regarding truck transportation and commercial coal production. In decisions related to truck transportation, trucks must accurately transport excavated materials to unloading stations. In decisions related to commercial coal production, coal crushing stations should maintain a calorific balance between the excavated raw coals and the blended commercial coals. To handle the complexity of these factors, we formulate a MILP model to minimize the total working time for all trucks.

From the perspective of algorithmic design, we create and apply a BP-based exact algorithm to solve the MILP model. Based on real data of the open-pit mine, we design six ISGs and conduct some numerical experiments. Experiments show that the optimality gap of the BP-based algorithm compared to CPLEX is zero and the solution time of CPLEX is 2.46 times that of the BP-based algorithm. As the problem size increases, CPLEX is unable to find a solution within a limit of 3600s, while the BP-based algorithm continues to rapidly generate high-quality solutions. Experiments validate the efficiency and effectiveness of the BP-based algorithm.

From the perspective of managerial insights, we perform sensitivity analyses on the location distribution of shovels and stations, the number of trucks, and the combination of truck loading capacity in the truck fleet. From a long-term strategic planning perspective, to enhance mining efficiency, open-pit managers should place electric shovels and unloading stations within the mining area and establish the location distribution according to the material handling process. From a short-term tactical perspective, the open-pit managers need to set the proper number of trucks to improve operational efficiency. Additionally, while increasing the proportion of large capacity trucks can improve performance, it does not always guarantee better outcomes. The open-pit managers should determine the suitable proportion of large capacity trucks and produce commercial coals with moderate calorific values.

Despite its significant contributions, this study has some limitations. In the real world, roads in open-pit mines often intersect at multiple intersections, which causes trucks to wait at intersections and results in traffic congestion. Additionally, the travel speed of trucks varies and is not constant. Future research should focus on incorporating traffic congestion and variable truck speeds into the model.

References

[1] Afrapoli A M, Tabesh M, Askari-Nasab H, (2019). A multiple objective transportation problem approach to dynamic truck dispatching in surface mines. European Journal of Operational Research, 276( 1): 331–342

[2] Bakhtavar E, Mahmoudi H, (2020). Development of a scenario-based robust model for the optimal truck-shovel allocation in open-pit mining. Computers & Operations Research, 115: 104539

[3] Blom M L, Burt C N, Pearce A R, Stuckey P J, (2014). A decomposition-based heuristic for collaborative scheduling in a network of open-pit mines. INFORMS Journal on Computing, 26( 4): 658–676

[4] Blom M L, Pearce A R, Stuckey P J, (2016). A decomposition-based algorithm for the scheduling of open-pit networks over multiple time periods. Management Science, 62( 10): 3059–3084

[5] Brickey A, Chowdu A, Newman A, Goycoolea M, Godard R, (2021). Barrick’s turquoise ridge gold mine optimizes underground production scheduling operations. INFORMS Journal on Applied Analytics, 51( 2): 106–118

[6] Costa L, Contardo C, Desaulniers G, (2019). Exact branch-price-and-cut algorithms for vehicle routing. Transportation Science, 53( 4): 946–985

[7] Dantzig G B, Wolfe P, (1960). Decomposition principle for linear programs. Operations Research, 8( 1): 101–111

[8] Epstein R, Goic M, Weintraub A, Catalan J, Santibanez P, Urrutia R, Cancino R, Gaete S, Aguayo A, Caro F, (2012). Optimizing long-term production plans in underground and open-pit copper mines. Operations Research, 60( 1): 4–17

[9] Goycoolea M, Lamas P, Pagnoncelli B K, Piazza A, (2021). Lane’s algorithm revisited. Management Science, 67( 5): 3087–3103

[10] Haonan Z, Samavati M, Hill A J, (2021). Heuristics for integrated blending optimisation in a mining supply chain. Omega, 102: 102373

[11] Hernandez F, Feillet D, Giroudeau R, Naud O, (2016). Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows. European Journal of Operational Research, 249( 2): 551–559

[12] Jélvez E, Morales N, Nancel-Penard P, Cornillier F, (2020). A new hybrid heuristic algorithm for the precedence constrained production scheduling problem: a mining application. Omega, 94: 102046

[13] Li B, Ouyang Y, Li X, Cao D, Zhang T, Wang Y, (2023). Mixed-integer and conditional trajectory planning for an autonomous mining truck in loading/dumping scenarios: A global optimization approach. IEEE Transactions on Intelligent Vehicles, 8( 2): 1512–1522

[14] Li J G, Zhan K, (2018). Intelligent mining technology for an underground metal mine based on unmanned equipment. Engineering, 4( 3): 381–391

[15] Matamoros M E V, Dimitrakopoulos R, (2016). Stochastic short-term mine production schedule accounting for fleet allocation, operational considerations and blending restrictions. European Journal of Operational Research, 255( 3): 911–921

[16] Nesbitt P, Sipeki L, Flamand T, Newman A M, (2020). Optimizing underground mine design with method-dependent precedences. IISE Transactions, 53( 6): 643–656

[17] Newman A M, Rubio E, Caro R, Weintraub A, Eurek K, (2010). A review of operations research in mine planning. Interfaces, 40( 3): 222–245

[18] Noriega R, Pourrahimian Y, Askari-Nasab H, (2025). Deep reinforcement learning based real-time open-pit mining truck dispatching system. Computers & Operations Research, 173: 106815

[19] Patterson S R, Kozan E, Hyland P, (2017). Energy efficient scheduling of open-pit coal mine trucks. European Journal of Operational Research, 262( 2): 759–770

[20] Riquelme-Rodríguez J P, Gamache M, Langevin A, (2016). Location arc routing problem with inventory constraints. Computers & Operations Research, 76: 84–94

[21] Samavati M, Essam D, Nehring M, Sarker R, (2020). Production planning and scheduling in mining scenarios under IPCC mining systems. Computers & Operations Research, 115: 104714

[22] Shishvan M S, Benndorf J, (2019). Simulation-based optimization approach for material dispatching in continuous mining systems. European Journal of Operational Research, 275( 3): 1108–1125

[23] Souza M J F, Coelho I M, Ribas S, Santos H G, Merschmann L H C, (2010). A hybrid heuristic algorithm for the open-pit-mining operational planning problem. European Journal of Operational Research, 207( 2): 1041–1051

[24] Ta C H, Ingolfsson A, Doucette J, (2013). A linear model for surface mining haul truck allocation incorporating shovel idle probabilities. European Journal of Operational Research, 231( 3): 770–778

[25] Tian F, Zhou R, Li Z, Li L, Gao Y, Cao D, Chen L, (2021). Trajectory planning for autonomous mining trucks considering terrain constraints. IEEE Transactions on Intelligent Vehicles, 6( 4): 772–786

[26] Yang Q, Ai Y, Teng S, Gao Y, Cui C, Tian B, Chen L, (2023). Decoupled real-time trajectory planning for multiple autonomous mining trucks in unloading areas. IEEE Transactions on Intelligent Vehicles, 8( 10): 4319–4330

[27] Zhang L, Shan W, Zhou B, Yu B, (2023). A dynamic dispatching problem for autonomous mine trucks in open-pit mines considering endogenous congestion. Transportation Research Part C, Emerging Technologies, 150: 104080

[28] Zhang X, Guo A, Ai Y, Tian B, Chen L, (2022). Real-time scheduling of autonomous mining trucks via flow allocation-accelerated tabu search. IEEE Transactions on Intelligent Vehicles, 7( 3): 466–479

RIGHTS & PERMISSIONS

Higher Education Press