Cross-docking is a logistics technique applied by many industrial firms to get substantial savings in two warehousing costly functions like storage and order picking. Incoming shipments are unloaded from inbound trucks on a cross-dock terminal with minimal storage space and directly transferred to outbound vehicles that carry them to their destinations. The major decisions at the operational level are the vehicle routing and scheduling, the dock door assignment and the truck scheduling at the cross-dock. Because such decisions are interdependent, all of them are simultaneously considered in the so-called vehicle routing problem with cross-docking (VRPCD). Previous contributions on VRPCD assume that pickup and delivery tasks are accomplished by a homogeneous vehicle fleet, and they mostly ignore the internal transportation of goods through the cross-dock. This work introduces a new rigorous mixed-integer linear programming (MILP) formulation for the VRPCD problem to determine the routing and scheduling of a mixed vehicle fleet, the dock door assignment, the truck docking sequence and the travel time required to move the goods to the assigned stack door all at once. To improve the computational efficiency of the branch-and-cut search, an approximate sweep-based model is developed by also considering a set of constraints mimicking the sweep algorithm for allocating nodes to vehicles. Numerous heterogeneous VRPCD examples involving up to 50 transportation requests and a heterogeneous fleet of 10 vehicles with three different capacities were successfully solved using the proposed approaches in acceptable CPU times. (C) 2015 Elsevier Ltd. All rights reserved.