We propose solution strategies for hard Mixed Integer Programming (MIP) problems, with a focus on distributed parallel MIP optimization. Although our proposals are inspired by the Less-than-truckload (LTL) freight routing problem, they are more generally applicable to hard MIPs from other domains. We start by developing an Integer Programming model for the Less-than-truckload (LTL) freight routing problem, and present a novel heuristic for solving the model in a reasonable amount of time on large LTL networks. Next, we identify some adaptations to MIP branching strategies that are useful for achieving improved scaling upon distribution when the LTL routing problem (or other hard MIPs) are solved using parallel MIP optimization. Recognizing that our model represents a pseudo-Boolean optimization problem (PBO), we leverage solution techniques used by PBO solvers to develop a CPLEX based look-ahead solver for LTL routing and other PBO problems. Our focus once again is on achieving improved scaling upon distribution. We also analyze a technique for implementing subtree parallelism during distributed MIP optimization. We believe that our proposals represent a significant step towards solving big-data driven optimization problems (such as the LTL routing problem) in a more efficient manner. / Thesis / Doctor of Philosophy (PhD) / Less-than-truckload (LTL) freight transportation is a vital part of Canada's economy, with revenues running into billions of dollars and a cascading impact on many other industries. LTL operators often have to deal with large volumes of shipments, unexpected changes in traffic conditions, and uncertainty in demand patterns. In an industry that already has low profit margins, it is therefore vitally important to make good routing decisions without expending a lot of time. The optimization of such LTL freight networks often results in complex big-data driven optimization problems. In addition to the challenge of finding optimal solutions for these problems, analysts often have to deal with the complexities of big-data driven inputs. In this thesis we develop several solution strategies for solving the LTL freight routing problem including an exact model, novel heuristics, and techniques for solving the problem efficiently on a cluster of computers. Although the techniques we develop are inspired by LTL routing, they are more generally applicable for solving big-data driven optimization problems from other domains. Experiments conducted over the years in consultation with industry experts indicate that our proposals can significantly improve solution quality and reduce time to solution. Furthermore, our proposals open up interesting avenues for future research.

The less-than-truckload (LTL) transportation industry is highly competitive with low profit margins. Carriers in this industry strive to reduce costs and improve customer service to remain profitable. LTL carriers rely on a network of hubs and service centers to transfer freight. A hub is typically a cross docking terminal in which shipments from inbound trailers are unloaded and reassigned and consolidated onto outbound trailers going to the correct destinations. Freight handling in a hub is labor intensive, and workers must quickly transfer freight during a short time period to support customer service levels. Reducing shipment transfer time in hubs offers the opportunity to reduce labor costs, improve customer service, and increase competitive advantages for carriers. This research focuses on improving the efficiency of hub operations in order to decrease the handling costs and increase service levels for LTL carriers. Specifically, the following two decision problems are investigated: (1) assigning trailers to dock doors to minimize the total time required to transfer shipments from inbound trailers to destination trailers and (2) sequencing unloading and loading of freight to minimize the time required by dock employees. The trailer-to-door assignment problem is modeled as a Quadratic Assignment Problem (QAP). Both semi-permanent and dynamic layouts for the trailer-to-door assignment problem are evaluated. Improvement based heuristics, including pair-wise exchange, simulated annealing, and genetic algorithms, are explored to solve the trailer-to-door assignment problem. The freight sequencing problem is modeled as a Rural Postman Problem (RPP). A Balance and Connect Algorithm (BCA) and an Assign First and Route Second Algorithm (AFRSA) are investigated and compared to Balanced Trailer-at-a-Time (BTAAT), Balanced Trailer-at-a-Time with Offloading (BTAATWO), and Nearest Neighbor (NN). The heuristics are evaluated using data from two LTL carriers. For these data sets, both the total travel distance and the transfer time of hub operations are reduced using a dynamic layout with efficient freight sequencing approaches, such as the Balance and Connect Algorithm (BCA), the Balanced Trailer-at-a-Time with Offloading (BTAATWO), and the Nearest Neighbor (NN). Specifically, with a dynamic layout, the BCA reduces travel distance by 10% to 27% over BTAAT and reduces the transfer time by 17% to 68% over BTAAT. A simulation study is also conducted for hub operations in a dynamic and stochastic environment. The solutions from the door assignment and freight sequencing approaches are evaluated in a simulation model to determine their effectiveness in this environment. The simulation results further demonstrate that the performance measures of hub operations are improved using a dynamic layout and efficient freight sequencing approaches. The main contributions of this research are the integer programming models developed for the freight sequencing problem (FSP), based on the Rural Postman Problem (RPP). This is the first known application of the RPP for the FSP. Efficient heuristics are developed for the FSP for a single worker and for multiple workers. These heuristics are analyzed and compared to previous research using industry data. / Ph. D.

The less-than-truckload (LTL) industry is highly competitive, with recent average profit margins less than 3%. LTL shipments are routed through a network of service centers and hubs. The performance of the entire LTL distribution network is highly dependent on the speed and accuracy of the hub operations. The focus of this research effort is to improve hub operations in order to reduce costs and increase service performance levels. Specifically, new approaches are investigated for assigning trailers to dock doors and sequencing the unloading of shipments at hubs. This thesis reviews current industry practices and available research literature on hub operations. Solution approaches for the trailer-to-door assignment and freight sequencing problems are presented along with case study results. The main performance measures are bottleneck time, total labor time, and total travel distance. For the trailer-to-door assignment problem, also referred to as the hub layout problem, the three approaches investigated are the original approach, a semi-permanent approach, and a dynamic approach. For the freight sequencing problem, the five approaches evaluated are trailer-at-a-time, trailer-at-a-time with offloading, nearest neighbor within a group, nearest neighbor within a shared group, and nearest neighbor. The approaches are implemented in C++ and analyzed using data from a regional LTL carrier. The case study results indicate that the dynamic layout performs significantly better than the original and semi-permanent layout for total distance, total labor time, and bottleneck time. For total distance and total labor time, the dynamic layout with nearest neighbor sequencing is the preferred approach. For bottleneck time, the dynamic layout with trailer-at-a-time with offloading performs best, while the nearest neighbor sequencing approach performs almost as well. In general, the case study results indicate that a dynamic layout with either a trailer-at-a-time with offloading approach or a nearest neighbor approach offers the largest potential for improvement. The assumptions and results of the hub layout and freight sequencing approaches are further evaluated using a simulation model. The simulation model indicates that a dynamic layout with nearest neighbor sequencing offers the largest potential for improvement in a more realistic environment with probabilistic and dynamic events. The simulation results also indicate that the trailer-at-a-time with offloading approach may need to be modified to account for more realistic dock conditions. In summary, the approaches explored in this research offer significant opportunity to improve hub operations through reducing bottleneck time, total labor time, and total travel distance. / Master of Science

Esta pesquisa trata do projeto de redes de distribuição de carga parcelada. Mais especificamente são tratados dois tipos de problemas que são comuns no planejamento desse tipo de sistema. O primeiro deles corresponde ao problema estratégico de configuração de redes do tipo hub-and-spoke, consistindo na definição simultânea da quantidade e localização de terminais para consolidação de carga (ou hubs), e na definição da alocação dos terminais aos hubs localizados. Uma vez determinada a configuração da rede, o segundo problema, no nível de decisão tático, corresponde na definição do caminho que cada carga parcelada deve percorrer desde sua origem até alcançar seu terminal de destino, a um mínimo custo, tendo a rede hub-and-spoke como um dado de entrada do problema. Um novo modelo matemático é proposto para representar o problema estratégico de configuração de uma rede hub-and-spoke, possuindo uma menor quantidade de variáveis e restrições, ao se comparar com outros modelos matemáticos comumente utilizados para representar o problema. Esse novo modelo matemático permitiu a obtenção de soluções ótimas para problemas em redes com até 100 terminais, sendo apresentada pela primeira vez a solução ótima para problemas utilizados como benchmark na literatura. Dado que problemas de grande porte ainda continuam muito difíceis de serem resolvidos, são propostas três variantes de uma heurística simples e eficiente utilizando técnicas de multi-início e busca tabu, bem como uma heurística integrada em dois estágios baseada em busca tabu para solução. Experimentos computacionais utilizando dados tradicionalmente utilizados na literatura para solução de problemas de configuração de redes hub-and-spoke (conjuntos de dados CAB e AP), bem como instâncias novas e modificadas, mostraram que a abordagem utilizada para solução do problema possibilitou a obtenção da solução ótima, ou a melhor solução conhecida, para esses problemas em um tempo de processamento muito curto, permitindo assim resolver de forma eficiente problemas de grande porte, nunca antes resolvidos em pesquisas anteriores. O segundo problema foi motivado por uma aplicação prática de uma empresa de transporte rodoviário de cargas parceladas no Brasil. O problema diz respeito ao planejamento de carregamentos a serem realizados em cada terminal, levando-se em consideração cada carga parcelada que precisa ser transportada, definindo o percurso que cada carga deve percorrer até chegar ao seu destino. É proposto um modelo matemático e, dada a dificuldade para se resolver problemas de tamanho como o encontrado na prática, é proposto também um método de solução utilizando metaheurística busca tabu. Experimentos computacionais realizados mostraram que a heurística proposta pôde efetivamente resolver problemas de tamanho como o encontrado na prática. / This research deals with problems related to distribution networks for less-than-truckload (LTL) freight transportation. More specifically, we deal with two relevant problems that arise. The first corresponds to the strategic problem of designing and configuring hub-and-spoke networks in terms of simultaneously determining the optimal number of consolidation terminals (hub) nodes, their locations and the allocation of the other terminals (spokes) to the hubs. . Once the network configuration is determined, the second problem, in the tactical level of decision, corresponds to defining the path that each LTL individual freight needs to follow from its origin to reach its destination terminal, at a minimum cost, having a hub-and-spoke network topology as a data entry to the problem. A new mathematical model is proposed to represent the strategic problem of designing a hub-and-spoke network, with fewer variables and constraints than previous formulations found in the literature This model allowed us to obtain optimal solutions for problems in transportation networks with up to 100 terminals, reporting for the first time the optimal solutions of benchmark problems in the literature. Since this problems still remains too hard to solve for larger instances, we propose we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve it. Computational experiments using typical benchmark problems (CAB and AP data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. The second problem is motivated by a practical application of a LTL transportation company in Brazil. It deals with the planning of loads to be done at each terminal, taking into account each LTL freight that needs to be transported, defining the path that each good needs to follow to reach its destination. A new mathematical model is proposed, and, since real world problems are very hard to solve, a heuristic based on tabu search is also developed. Computational experiments show that our heuristic can effectively solve real-world instances from a trucking company in Brazil.

A less-than-truckload (LTL) carrier typically delivers shipments less than 10,000 pounds (classified as LTL shipment). The size of the shipment in LTL networks provides ample opportunities for consolidation. LTL carriers have focused on hub-and-spoke based consolidation to realize economies of scale. Generally, hub-and-spoke systems work as follows: the shipment is picked up from the shipper and brought to an origin terminal, which is the entry point into the hub-and-spoke system. From the terminal, the freight is sent to the first hub, where it is sorted and consolidated with other shipments, and then sent on to a second hub. It is finally sent from the second hub to the destination terminal, which is the exit point of the hub-and-spoke system. However, the flow of shipments is often more complicated in practice. In an attempt to reduce sorting costs, load planners sometimes take this hub-and-spoke infrastructure and modify it considerably to maximize their truck utilization while satisfying service constraints. Decisions made by a load planner may have a cascading effect on load building throughout the network. As a result, decentralized load planning may result in expensive global solutions. Academic as well as industrial researchers have adapted a hierarchical approach to design the hub-and-spoke networks: generate the hub-and-spoke network, route shipments within this hub-and-spoke network (generate a load plan) and finally, balance the empty trailers. We present mathematical models and heuristics for each of the steps involved in the design of the hub-and-spoke network. The heuristics are implemented in a user-friendly graphical tool that can help understand patterns of freight flow and provide insights into the design of the hub-and-spoke network. We also solved the load planning sub-problem in a parallel computation environment to achieve significant speed-ups. Because of the quick solution times, the tool lays the foundation to address pressing further research questions such as deciding location and number of hubs. We have used data provided by Roadway Parcel Services, Inc. (RPS), now FedEx Ground, as a case-study for the heuristics. Our solutions rival the existing industry solutions which have been a product of expensive commercial software and knowledge acquired by the network designers in the industry.

The trucking industry is vitally important to the economy, providing an essential service by transporting goods between businesses and consumers. The less-than-truckload (LTL) industry is an important segment, serving businesses that ship quantities between 150 lbs and 10,000 lbs. Large LTL carriers use thousands of drivers to move loads between terminals in their network, and each driver may be used for multiple dispatches between rest periods. Driver wages are a major component of transportation costs. Consequently, cost-effective driver management is of crucial importance for the profitability of LTL carriers. This thesis investigates a variety of issues related to driver management. In this thesis, we describe a dynamic driver scheduling scheme developed for a large U.S. LTL carrier. Dynamic driver scheduling is challenging because drivers must abide by a complex set of rules, including government and union regulations, and trucking moves are not pre-scheduled. The technology developed combines greedy search with enumeration of time-feasible driver duties, and is capable of generating cost-effective schedules covering 15,000 20,000 loads in minutes. One of the key tactical questions faced by an LTL carrier is how many drivers to locate at each terminal. Unionized carriers have bid drivers that can only move loads between their domicile and a designated region. The developed allocation technology determines the number of drivers to allocate to each terminal as well as the designated region for bid drivers. Computational experiments based on real-life dispatch data demonstrate the effectiveness of our domiciling methodology, and show that union rules may result in substantially larger driver fleets, in some cases up to 50% larger. Finally, we investigate a fundamental question related to driver management in order to obtain some fundamental insights: determining the minimum number of drivers required to cover a set of loaded moves. The problem is shown to be polynomially solvable without any restrictions on driver schedules. For variants with restrictions, several easily computable lower bounds are derived, integer programming formulations are presented, and fast heuristics are designed and analyzed. A computational study provides insights into the quality of the lower bounds and heuristic solutions.

Esta pesquisa trata do projeto de redes de distribuição de carga parcelada. Mais especificamente são tratados dois tipos de problemas que são comuns no planejamento desse tipo de sistema. O primeiro deles corresponde ao problema estratégico de configuração de redes do tipo hub-and-spoke, consistindo na definição simultânea da quantidade e localização de terminais para consolidação de carga (ou hubs), e na definição da alocação dos terminais aos hubs localizados. Uma vez determinada a configuração da rede, o segundo problema, no nível de decisão tático, corresponde na definição do caminho que cada carga parcelada deve percorrer desde sua origem até alcançar seu terminal de destino, a um mínimo custo, tendo a rede hub-and-spoke como um dado de entrada do problema. Um novo modelo matemático é proposto para representar o problema estratégico de configuração de uma rede hub-and-spoke, possuindo uma menor quantidade de variáveis e restrições, ao se comparar com outros modelos matemáticos comumente utilizados para representar o problema. Esse novo modelo matemático permitiu a obtenção de soluções ótimas para problemas em redes com até 100 terminais, sendo apresentada pela primeira vez a solução ótima para problemas utilizados como benchmark na literatura. Dado que problemas de grande porte ainda continuam muito difíceis de serem resolvidos, são propostas três variantes de uma heurística simples e eficiente utilizando técnicas de multi-início e busca tabu, bem como uma heurística integrada em dois estágios baseada em busca tabu para solução. Experimentos computacionais utilizando dados tradicionalmente utilizados na literatura para solução de problemas de configuração de redes hub-and-spoke (conjuntos de dados CAB e AP), bem como instâncias novas e modificadas, mostraram que a abordagem utilizada para solução do problema possibilitou a obtenção da solução ótima, ou a melhor solução conhecida, para esses problemas em um tempo de processamento muito curto, permitindo assim resolver de forma eficiente problemas de grande porte, nunca antes resolvidos em pesquisas anteriores. O segundo problema foi motivado por uma aplicação prática de uma empresa de transporte rodoviário de cargas parceladas no Brasil. O problema diz respeito ao planejamento de carregamentos a serem realizados em cada terminal, levando-se em consideração cada carga parcelada que precisa ser transportada, definindo o percurso que cada carga deve percorrer até chegar ao seu destino. É proposto um modelo matemático e, dada a dificuldade para se resolver problemas de tamanho como o encontrado na prática, é proposto também um método de solução utilizando metaheurística busca tabu. Experimentos computacionais realizados mostraram que a heurística proposta pôde efetivamente resolver problemas de tamanho como o encontrado na prática. / This research deals with problems related to distribution networks for less-than-truckload (LTL) freight transportation. More specifically, we deal with two relevant problems that arise. The first corresponds to the strategic problem of designing and configuring hub-and-spoke networks in terms of simultaneously determining the optimal number of consolidation terminals (hub) nodes, their locations and the allocation of the other terminals (spokes) to the hubs. . Once the network configuration is determined, the second problem, in the tactical level of decision, corresponds to defining the path that each LTL individual freight needs to follow from its origin to reach its destination terminal, at a minimum cost, having a hub-and-spoke network topology as a data entry to the problem. A new mathematical model is proposed to represent the strategic problem of designing a hub-and-spoke network, with fewer variables and constraints than previous formulations found in the literature This model allowed us to obtain optimal solutions for problems in transportation networks with up to 100 terminals, reporting for the first time the optimal solutions of benchmark problems in the literature. Since this problems still remains too hard to solve for larger instances, we propose we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve it. Computational experiments using typical benchmark problems (CAB and AP data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. The second problem is motivated by a practical application of a LTL transportation company in Brazil. It deals with the planning of loads to be done at each terminal, taking into account each LTL freight that needs to be transported, defining the path that each good needs to follow to reach its destination. A new mathematical model is proposed, and, since real world problems are very hard to solve, a heuristic based on tabu search is also developed. Computational experiments show that our heuristic can effectively solve real-world instances from a trucking company in Brazil.

O presente estudo trata da configuração de uma rede de distribuição capacitada com restrição de cobertura. O objetivo é determinar quais cidades, dentre um conjunto de candidatas, devem atuar como centrais de desconsolidação de carga, de forma a minimizar o custo total de transporte (transferência e distribuição) para uma determinada demanda, atendendo às restrições operacionais e de distância de cobertura. A partir da pesquisa na literatura sobre o assunto, foi preparado um modelo de programação linear inteira para encontrar a solução ótima para o problema. Esse modelo é baseado nos clássicos problemas de localização, com modificação na função objetivo para retratar melhor a estrutura de custos de transporte, além da inclusão de restrições de cobertura e restrições de atendimento mínimas e máximas em cada central. O modelo foi implementado utilizando o suplemento Solver da planilha eletrônica Excel. Um outro enfoque de solução baseado na metaheurística Busca Tabu (Tabu Search) foi elaborado, com dois objetivos: permitir a análise de problemas quando não se tem disponível uma ferramenta para solução de modelos de programação linear; e analisar o comportamento da metaheurística quando utilizada na solução desse tipo de problema. O procedimento foi implementado a partir da construção de macros em linguagem Visual Basic for Application (VBA), também em Excel. O modelo de programação linear e a metaheurística Busca Tabu foram aplicados a alguns cenários de um problema real. Resultados, comparações e conclusões dessas aplicações são apresentados neste trabalho. / The present study deals with configuring a capacitated distribution network with coverage constraint. The objective consists of determining which cities, among a set of candidates, should act as load deconsolidation centers, aiming to minimize transportation total costs to attend a given demand, and obeying all operational constraints and coverage distances. Based on a literature review, an integer linear programming model was formulated to find the problem optimal solution. The model is based on classical location problems, but includes changes in the objective function to incorporate the transportation costs structure, besides coverage constraints and minimum and maximum central capacity constraints. The model was implemented using Excel’s Solver add-in. Another solution approach based on the Tabu Search metaheuristic was proposed, with two objectives: to permit problem analysis when linear programming tools are not available; and to learn on metaheuristic behavior when used to solve this type of problem. The Tabu Search procedure was implemented using Excel macro language in Visual Basic for Applications (VBA). Both integer linear programming and metaheuristic models were applied to some scenarios of a real-world problem. Applications results, comparisons and conclusions are presented in this work.

No presente trabalho, é abordada a operação de transporte de cargas fracionadas, especificamente a determinação de quais linhas de transporte deverão ser ofertadas dentro de uma rede de terminais, de maneira a atender toda a demanda no nível de serviço desejado ao menor custo possível. Para tanto, é feita inicialmente uma descrição do problema de transporte de carga fracionada, seguido de uma revisão bibliográfica de trabalhos anteriores que já tenham abordado o tema. É então realizada a delimitação do escopo do estudo e a proposição de um modelo matemático em programação linear inteira-mista. Em seguida, é apresentado um algoritmo de resolução, consistindo na aplicação de uma heurística construtiva e uma heurística de melhoria, ambas embasadas na aplicação de caminhos mínimos com janelas de tempo a partir de custos marginais. O método é delineado para três versões do problema, estipuladas a partir de diferentes tratamentos à restrição de caminhos em formato de árvore dentro do sistema. Primeiramente, o algoritmo é aplicado a pequenas instâncias fictícias, realizando a comparação com a modelagem em programação linear inteira-mista proposta. Na maioria dos casos, não houve diferença nos valores de função objetivo encontrados, embora tenham sido identificados gaps grandes no processamento. Posteriormente, é realizada a aplicação a dados reais de uma transportadora brasileira. Para as três versões do problema, a redução de custos potencial identificada é significativa, com tempos de processamento similares ou menores do que o encontrado na literatura. Por fim, os resultados obtidos são discutidos sendo apresentadas considerações finais acerca do trabalho realizado e possíveis melhorias para pesquisas futuras. / At the present work, the operation of less-than-truckload (LTL) will be studied, more specifically the determination of which lines will be offered in a network of terminals. The service network design must attend all demands, respecting their deadlines while aiming cost reductions. The objective of this work is to propose algorithms to solve the service network design problem of LTL operations, reducing operation costs while respecting specified service levels. First, a brief introduction to the problem is made, and similar research is reviewed. Then the scope of the research is determined and a mathematical model of the problem in mixed-integer programming is presented. Next, an algorithm is proposed, consisting in a constructive heuristic followed by a local search. Both phases are based on finding minimum paths with time windows using marginal costs along the network. Three different versions of the problem are analyzed, shifting the approach given to the constraint of in-tree structure that shipments should follow in the network. The algorithm is firstly tested to small fictional instances, allowing comparison to the mixed programming model proposed earlier. No relevant differences between objective functions were found, even though substantial gaps values were identified during processing. A second test used a real dataset of a Brazilian LTL carrier. In all versions of the problem the operation cost reduction was promising, with processing times similar to the ones found in literature. The conclusion provides a discussion of the obtained results and recommendations for future research.

This dissertation addresses problems arising in freight routing and scheduling where full truckload (FTL) and less-than-truckload (LTL) carriers are used to serve transportation needs. Each of the problems investigated in this dissertation tries to optimize/maximize consolidation to decrease system transportation costs by (1) carefully choosing the timing and path of freight and/or (2) introducing consolidation points. Approaches are proposed that enable effective planning and operation of freight routing and scheduling for large-scale transportation networks. Chapter 2 presents solution approaches for a shipper pickup and delivery planning problem faced by many large retailers to move freight from suppliers to distribution centers. Each shipment is moved either direct via a LTL carrier or possibly consolidated with other shipments and moved by one or two FTL routes. When using a FTL carrier, the shipper takes advantage of contracted lane rates that establish prices per mile for a truck operated between two locations that are significantly less than the comparable LTL price for shipping a full truckload. Consolidated FTL routes may each visit multiple shipment origins (supplier locations) and/or destinations (distribution center locations). Additionally, FTL routes may move shipments through a single crossdock facility en route. The challenge in this planning problem is to exploit as much as possible negotiated truckload lane rates and to judiciously make use of routes through crossdock facilities to consolidate shipments. The primary contributions of this section are that (1) an interesting new problem variant is introduced to the field of transportation and logistics that is important in practice and (2) the solution approach demonstrates that exploiting knowledge of the problem and solution structure to cleverly select subsets of path variables for evaluation during each iteration of an integer programming based local search heuristic is effective on path-based routing models. Chapter 3 evaluates how to route each customer shipment through a sequence of transfer terminals in a LTL carrier network. At each terminal stop, a shipment is unloaded from an inbound trailer and reloaded onto an outbound trailer. A load plan determines the specific sequence of terminal transfers to be used for freight moving between each origin and destination. The design of the load plan determines the linehaul transportation and handling costs required to serve customers. We develop an improved very large-scale neighborhood search heuristic for solving an integer programming model for load plan design. The main contributions of this section include (1) the investigation of the pros and cons of optimizing system-wide into a single destination versus optimizing freight for all destinations in a small region, and (2) a solution approach that can find load plans with costs 6 to 7\% lower than those used in practice, and can find 2.5 to 5\% additional cost savings using the same time budget when compared to an approach optimizing system-wide into a single destination. Chapter 4 addresses a strategic planning problem that extends the load plan design problem to consider terminal roles. We investigate two-stage approaches that first identify the set of transfer terminals and then develop the corresponding load plan. Computational results compare the terminals chosen as transfer facilities from the proposed integer programming based local search method with a traditional hub location formulation and a simple facility location formulation to depict the benefits gained from modeling additional information. The key contributions of this section are (1) the introduction of a new hub location problem variant incorporating freight dispatch timing and trailer transportation cost characteristics found in the LTL trucking industry and (2) a solution approach utilizing IP-based local search that demonstrates the importance of incorporating freight dispatch timing. Finally, Chapter 5 summarizes the main conclusions from this dissertation and discusses directions for further research.