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

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