Thesis Title: Advances in Tactical Planning Decision Problems in Trucking Service Networks
Advisor:
Dr. Alan Erera, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech
Thesis Committee:
Dr. Pascal Van Hentenryck, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech
Dr. Santanu Dey, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech
Dr. Alejandro Toriello, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech
Dr. Vikrant Vaze, Mechanical, Operations & Systems Engineering, Dartmouth Engineering
Date and Time: Thursday, September 5th , 12 pm EDT
Location: Virtual
Meeting Link: Teams: Join The Meeting
teams.microsoft.com
Meeting ID: 215 541 751 247
Passcode: NLTfAx
Abstract:
The growth in e-commerce has spurred demand for parcel and less-than-truckload (LTL) freight services, and carriers providing these services compete by improving shipment delivery speed and reliability. Much of e-commerce relies on home delivery of small packages or parcels and other boxed freight. Key parcel carriers like UPS and FedEx continually seek to redesign and operate profitable logistic networks that meet e-commerce customer service expectations. Beyond physical network design, including the location and sizing of various freight processing terminals, these companies need help with challenging service network design problems. This thesis addresses load (capacity) planning and trailer scheduling problems faced by planners at terminals in a parcel delivery service network. The research described in this thesis is conducted directly with a leading global parcel carrier that operates a massive network moving large volumes of packages each day.
In Chapter 2, we address the Outbound Load Planning Problem (OLPP) to determine (1) how many loads or trailers to operate from a terminal to different destinations and (2) how to allocate the package volume processed at the terminal to outbound loads such that capacity constraints are satisfied, and packages are loaded into their compatible outbound destinations which are known apriori. We build a hierarchical optimization model to generate load plans with high utilization that are consistent in practice; this approach is beneficial as the planners are more amenable to consistent and easy-to-evaluate recommendations. We develop an optimization-based learning methodology that blends machine learning (ML) and feasibility restoration frameworks. The ML model imitates the hierarchical optimization model to learn consistent solution patterns, and the feasibility restoration framework recovers a feasible solution from the ML predictions. An extensive computational study on industrial instances shows that the optimization-based learning approach is 10× faster than a commercial solver in obtaining the same quality solutions.
In Chapter 3, we address the Robust Outbound Load Planning Problem (ROLPP). We formulate ROLPP as a two-stage robust optimization model with relatively complete recourse. In stage 1, a planner determines the number of trailers to operate on each outbound arc. Once an adversary chooses a demand scenario from a given polyhedral uncertainty set, the planner minimizes the total cost of adding fractional trailer capacity in the second stage. We use a column-and-constraint generation algorithm that iterates between solving a master problem and a MILP reformulation of the bilinear subproblem to solve the ROLPP. We exploit the problem structure to carefully choose demand scenarios that can warm start the subproblem, as it is very difficult to get feasible solutions to the subproblem using a commercial solver. Furthermore, we start the master problem with a small set of carefully chosen demand scenarios to produce tight lower bounds to the ROLPP objective. We highlight that simple scenario-generation heuristics can often be used to produce tight bounds for the optimal ROLPP objective.
In Chapter 4, we address the Integrated Inbound-Outbound Load Planning Problem (IOLPP) for a cluster of terminals in a parcel delivery service network. Each terminal in the cluster has a set of inbound trailers, a planned package processing capacity, and a set of planned outbound trailers. The planner aims to determine a cost-effective outbound load (capacity) plan for the cluster of terminals while ensuring that the package processing capacity is respected. The planner has the flexibility to shift an inbound trailer, planned to arrive at a terminal, to a nearby terminal in the same cluster to ensure that the package processing capacity is satisfied and to achieve a better outbound trailer consolidation. We formulate IOLPP as a MILP and solve it using a commercial solver. Through an extensive computational study on real-life instances, we show that it is often necessary to shift inbound trailers to ensure that the processing capacity at individual terminals is respected. Furthermore, shifting inbound trailers reduces outbound trailer capacity by 0.8 - 2.1% due to better package consolidation.
In Chapter 5, we address the Crossdock Trailer Scheduling Problem with Workforce constraints (XDTS-W). Given an arrival plan of inbound trailers and a fixed number of workers, planners need to determine an unloading schedule for the trailers that minimizes the total delay in loading the outbound trailers; the unloading schedule includes trailer-to-door assignments, trailer unloading sequence at each door, and worker-to-trailer assignment. We formulate XDTS-W as a MILP over a complete time-expanded network. We prove that if XDTS-W is formulated over a partial time-expanded network satisfying some properties, then the corresponding MILP is guaranteed to yield a lower bound to the optimal objective value of XDTS-W. We propose an exact dynamic discretization discovery (DDD) algorithm to solve XDTS-W. DDD iterates between a lower-bound and an upper-bound model and refines the partial network in each iteration until it converges to a provably optimal solution. Through computational experiments, we highlight the instances where the DDD algorithm outperforms existing state-of-the-art interval scheduling approaches in the literature and the instances where it is better to use a commercial solver to solve practical instances of XDTS-W.