This paper studies the multi-objective outbound truck scheduling problem in a multi-door cross-docking terminal. The key characteristic of the problem is that each truck can travel multiple trips to deliver products to different sets of customers. The goal is to find the door assignment, truck sequencing, and the departure time of outbound trucks so that each outbound truck leave the dock door as close to their due time as much as possible. The problem is NP-hard in which an exact solution method consumes high computational time to obtain optimal solution especially in the large-size problems. For this reason, this paper proposes an application of a metaheuristic called Large Neighborhood Search (LNS) to deal with the problem complexity.  In LNS, three destroy and two repair strategies are proposed with an aim to improve the solution quality. The numerical results show that the proposed LNS yields solutions closed to those obtained from an exact method in small-sized problems with fast computing time.  For the larger-size problems, the proposed LNS can find solutions in relatively fast computing time while an exact method cannot find optimal solution in an acceptable time.