This paper presents a realistic model that can be used to minimize fuel consumption in surface mining operations. The developed model dispatches trucks to destinations by optimally determine the paths that can lead to the minimum fuel consumption per truck and shovel cycle while the handling demands of each dumping site are met. This model is applicable to all types of open-pit mines, including over and under-trucked mines. The formulation takes into account the waiting time of trucks at dumping and loading sites and the idle times of shovels. The effectiveness of the proposed model in the determination of the best shovel allocation in the case of a heterogeneous fleet of shovels is also demonstrated in this study.