The optimization of an enterprise supply chain requires reducing costs and inventories. One usual way to increase the efficiency of the supply chain is to outsource the movement of shipments on third-party logistics (3PL) companies. In turn, 3PL companies are required to consolidate shipments from different suppliers in the outbound vehicles at a terminal of the carrier terminals-network. Services to manufacturing enterprises are differentiated into two groups, with regard to the shipment size. Manufacturers contract full-truckload (FTL) carriers when a shipment is large enough to fill a vehicle whereas less-than-truckload (LTL) carriers are used for minor shipments. LTL carriers must convey several transportation-requests from the origin locations to their destinations while minimizing the total movements-cost by using the possibility of goods-transshipments on the carriers terminals-network. We present a methodology for finding near-optimal solutions to a problem related to LTL-shipping by using column generation combined with a customized branch-and-price procedure. The approach rapidly provides near-optimal solutions, since it solves the column generation subproblems approximately and does not necessarily consider all unexplored nodes in the search-tree. We also present computational results on numerous test problems of varied topologies and on a real case study.