In the mining industry, methods to reduce the fuel consumed in the haulage operations are largely sought as a result of the growing energy demand, fuel cost increases and adverse environmental impacts due to the emission of greenhouse gases. Fuel consumption reduction in the open-pit mine operations can be achieved by improving the performance efficiency, technology efficiency, equipment efficiency and operation efficiency of trucks, shovels and the truck-shovel dispatching system. The study conducted in this work lies within the operational strategies that seek to improve the operational efficiency of the truck-shovel dispatching system. A mixed integer linear programming model (MILP) for the truck-shovel dispatching system is developed. This optimization model minimizes the fuel consumption of dump trucks and shovels, meets the handling demand of dump sites and determines the optimal number of trips that each truck should realize on each route of the mine. The developed model is built using an m-truck-for-n shovels strategy so that a truck could be allocated to different shovels during a shift. A case study of an under-trucked mine is considered for optimization and simulation of the developed model. To illustrate the effectiveness of the MILP model, its performance is compared to a fixed dispatch method. The results show that the MILP model decreases the average fuel consumption per ton for the fleet of trucks, shovels and for the truck-shovel system. Therefore, a saving of fuel is achieved by the MILP model. Two other possible applications of the MILP model are also illustrated in this study. The first application shows how this model can be used in the case of a heterogeneous fleet of shovels to determine the best allocation of shovels that can lead to minimum fuel consumption in the haulage operations. The second application shows how the MILP model can be used to identify the best fleet in terms of fuel consumption and litres per ton between different fleets having different match factors.