A load plan specifies how freight is routed through a linehaul terminal network operated by a less-than-truckload (LTL) carrier. Determining the design of the load plan is critical to effective operations of such carriers. This dissertation makes contributions in modeling and algorithm design for three problems in LTL load plan design: (1) Refined execution cost estimation. Existing load plan design models use approximations that ignore important facts such as the nonlinearity of transportation costs with respect to the number of trailers, and empty travel beyond what is required for trailer balance that results from driver rules. We develop models that more accurately capture key operations of LTL carriers and produce accurate operational execution costs estimates; (2) Dynamic load planning. Load plans are traditionally revised infrequently by LTL carriers due to the difficulty of solving the associated optimization problem. Technological advances have now enabled carriers to consider daily load plan updates. We develop technologies that efficiently and effectively adjust a nominal load plan for a given day based on the actual freight to be served by the carrier. We present an integer programming based local search procedure, and a greedy randomized adaptive search heuristic; and (3) Stochastic load plan design. Load plan design models commonly represent origin-destination freight volumes using average demands, which do not describe freight volume fluctuations. We investigate load plan design models that explicitly utilize information on freight volume uncertainty and design load plans that most cost-effectively deal with varying freight volumes and lead to the lowest expected cost. We present a Sample Average Approximation approach and a variant of the method for solving the stochastic integer programming formulations.