Advances in LTL load plan design

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: refined execution cost estimation, dynamic load planning, and stochastic load plan design.;Chapter 2 focuses on accurate estimation of the operational execution costs of a load plan. Load plan design models in use or proposed today approximate transportation costs by using costs per trailer dispatched between terminals. Furthermore, empty transportation costs are determined by solving a trailer re-balancing problem. These approximations ignore two important ideas: (1) trailers are typically moved behind tractors in trains of two or three trailers, and the cost of moving a trailer train is not linear in the number of trailers; and (2) drivers must be scheduled for each dispatch, and driver rules introduce additional empty travel than that minimally required for trailer balance. We develop models that more accurately capture key operations of LTL carriers. A computational study demonstrates that our technology produces accurate operational execution costs estimates, typically within 2% of actual incurred costs.;Chapter 3 describes dynamic load planning (DLP) technology. Traditionally, load plans are revised infrequently by LTL carriers due to the difficulty of solving the associated optimization problem. Since freight volumes served vary each operating day, carriers typically operate by manually adjusting the plan at each terminal to each day's operating conditions. Technological advances have now enabled carriers to consider more thorough, system-wide 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 two approaches for adjusting an existing load plan: an integer programming based local search procedure, and a greedy randomized adaptive search heuristic. A computational study using complete network data from a national carrier demonstrates that the proposed technology can produce significant cost savings.;Chapter 4 studies the stochastic load plan design problem. Load plan design models commonly represent origin-destination freight volumes using average demands derived from historical data, the drawback of which is that they do not describe freight volume fluctuations. We investigate load plan design models that explicitly utilize information on freight volume uncertainty during planning, and design load plans that most cost-effectively deal with varying freight volumes and lead to the lowest expected cost. We present Sample Average Approximation (SAA) approaches for solving stochastic integer programming formulations of the load plan design problem with demand uncertainty. In addition to applying the standard SAA approach, we also propose a modified version which, in order to correct the bias in the branch-and-bound search that results from using a sample, frequently computes an exact evaluation of the solution expected cost and a lower bound on this cost, to more accurately guide the search process.