Most construction projects involve earth removal operations. Careful management of truck fleets to perform these operations is considered crucial by earthwork contractors in Taiwan. This paper presents a hybrid mechanism to optimize the management of the truck fleets of earthwork contractors. The authors use discrete event simulation models to represent earthmoving operations, and these models are used to simulate schedules for dispatching truck fleets. The authors then apply genetic algorithms to select the optimal schedules with the least amount of operational time. A theoretical example proves that the proposed mechanism can determine near-optimal solutions efficiently. Finally, the authors develop a user-friendly interface so that earthwork transportation companies can use the proposed mechanism easily and effectively.