Thesis Title: Advances in Tactical & Operational Planning for Less-than-Truckload Carriers

Advisors:

Dr. Natashia Boland (ISyE, Georgia Tech)

Dr. Martin Savelsbergh (ISyE, Georgia Tech)

Committee Members:
Dr. Alan Erera (ISyE, Georgia Tech)

Dr. Chelsea C. White III (ISyE, Georgia Tech)

Dr. Barrett Thomas (Tippie College of Business, The University of Iowa)

Date and Time: Thursday, November 19, 2020 at 9:00 AM (EST)

BlueJeans Meeting URL:  https://bluejeans.com/703054575

BlueJeans Meeting ID: 703 054 575

Abstract:

This thesis explores tactical and operational planning problems in the context of the Less-than-Truckload (LTL) industry. LTL carriers transport shipments that occupy a small fraction of trailer capacity,  and, thus, rely on​ the consolidation of freight from multiple shippers to achieve economies of scale.

The first part of this thesis focuses on tactical planning operations of LTL carriers. In particular,  in Chapter 2,  we study the service network design problem confronted by LTL carriers ahead of an operating season.   This problem includes determining:  (1) the number of services (trailers)  to  operate between each pair of terminals, and  (2) a load plan which specifies the sequence of transfer terminals that freight with a given origin and destination will visit. Traditionally, for every terminal and every ultimate destination, a load plan specifies a unique next terminal. We introduce the p-alt model, which generalizes traditional load plans by allowing decision-makers to specify a desired number of next terminal options for terminal-destination pairs using a vector p.  We compare a number of exact and heuristic approaches for solving a two-stage stochastic variant of the p-alt model.  Using this model, we show that by explicitly considering demand uncertainty and by merely allowing up to two next terminal options for terminal-destination pairs in the load plans, carriers can generate substantial cost savings; cost savings that are comparable to those yielded by adopting load plans that allow for any next terminal to be a routing option for terminal-destination pairs.  Moreover, by using these more flexible load plans, carriers can generate cost savings in the order of 10% over traditional load plan designs obtained by deterministic models.

The second part of the thesis shifts to an operational setting relating to how freight is routed through the carrier’s service network.  As the daily freight quantities handled by a carrier are uncertain, freight routes are dynamically adjusted on the day of operations.  In Chapter 3, we introduce the Dynamic Freight Routing Problem (DFRP) which models the problem of routing freight dynamically (in the presence of demand uncertainty) throughout the service network.  We formally model this problem as a Markov Decision Process (MDP). To overcome the curses of dimensionality of the MDP model, we introduce an Approximate Dynamic Programming (ADP) solution approach for the DFRP. Subsequently, in Chapter 4, we describe a lookup table value function approximation (LT-VFA) mechanism for this ADP algorithm,  and introduce and compare a number of aggregation approaches which use features of the post-decision states to aggregate the post-decision state space.  Furthermore, since the decision subproblems encountered by the ADP algorithm are integer programs (IPs), we present a framework for integrating lookup tables into the decision subproblem IPs.   This framework consists of:  (1) a modeling approach for the integration of lookup table value function approximations into subproblem IPs to form extended subproblem IPs, (2) a solution approach, PDS-IP-Bounding, which decomposes the extended subproblem IPs into many smaller IPs and uses dynamic bounds to reduce the number of small IPs that have to be solved, and  (3) an adaptation of the epsilon-greedy exploration-exploitation algorithm for the IP setting. Our computational experiments show that despite the post-decision state of the DFRP being high-dimensional, a two-dimensional aggregation of the post-decision space is able to produce policies that outperform standard myopic policies. Moreover, our experiments demonstrate that the PDS-IP-Bounding algorithm provides computational advantages over solving the extended subproblem IPs using a commercial solver.

Finally, in Chapter 5, we extend the work on DFRP by describing two parametric VFA variants for the DFRP ADP algorithm, namely, a linear value function approximation (L-VFA), and a neural network value function approximation (NN-VFA), both using features of the post-decision states to approximate the value function.  We conduct computational experiments to compare the performance of all three VFA variants of the ADP solution approach on instances of the DFRP, and show that the L-VFA method outperforms its two counterparts in solution quality and the required computational effort.