Routing shipments efficiently on less-than-truckload trucking networks represents an important subproblem of the general network design problem that arises when designing a service network. The objective of the LTL shipment routing problem is to minimize the total transportation and handling costs subject to two key constraints: (i) service between two terminals must always satisfy a given minimum frequency (measured in trailers per week) and (ii) the paths from all origins into a destination should form a tree. This second constraint reflects a practical limitation on the types of instructions that can be implemented in the field. A solution approach is developed using a shortest path based formulation with additional routing constraints imposed to refine the routing in response to minimum frequency constraints. A local improvement heuristic is presented which manipulates the routing constraints. A separate set of primal-dual algorithms are also developed which provide both upper and lower bounds. Numerical experiments are presented to evaluate the effectiveness of both the local improvement heuristic and the primal-dual algorithms.