Thesis Title: Greedy Approaches for Large-Scale Flow and Load Planning

Advisor:

Dr. Alan Erera, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Thesis Committee:

Dr. Alejandro Toriello, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Martin W.P. Savelsbergh, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Pascal Van Hentenryck, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Sushil Poudel, United Parcel Service

Date and Time: Thursday, July 7th, 2022, 8:00 am EDT

Location: Virtual

Meeting Link:  Teams

Abstract: 

The flow and load planning problem is to determine freight flows through a network and to schedule containerized dispatches to accommodate these flows. The problem is perhaps the core decision problem faced by parcel express companies, LTL carriers, and large online retailers that operate private consolidation networks. Cost minimization is achieved by consolidating goods into common trailers along their journey. The scale of the problems faced in industry can involve thousands of locations and millions of commodities; however, most approaches in the literature are exact and are only able to solve instances with hundreds of commodities. This work focuses on developing heuristic approaches that can solve industry-scale instances.

In Chapter 2 we provide a sequential marginal cost path based approach to solve the flow and load planning problem. Commodities are sequentially pathed on a partially time-expanded network with optimistically mapped arcs. Heuristic dynamic discretization discovery (DDD) is used to detect when consolidations are not possible due to mapping error and to specify which time points must be added to prevent the infeasibility. Several improvements are made to the shortest path algorithm to exploit the repeated structure of the time-expanded network. Computational experiments show that the approach has an optimality gap of 4-18% on instances which can be solved with exact methods (~300 commodities). Further experiments show that the approach outperforms a commonly used slope scaling heuristic by 16-34% on both small and realistic sized (~100k commodities) instances.

In Chapter 3, we develop a different sequential marginal cost path approach that removes the requirement for maintaining and altering a time-expanded network. The approach maintains a set of dispatches currently in the solution, and a time window associated with each dispatch representing when it can depart. At each iteration, a shortest path algorithm on an expanded state space is solved to determine for a commodity a collection of new or existing dispatches which deliver it from its origin to its destination within its delivery window. Then the set of existing dispatches is updated, and the optimal set of dispatch windows is determined. We prove that finding the optimal set of dispatch windows is equivalent to solving a minimum mean cost path on a dispatch dependency graph. We use the Bellman-Ford algorithm to solve this problem and use a creative way to maintain labels between iterations to improve the efficiency of the approach. Computational experiments were performed and demonstrate that this approach outperforms the approach from the first chapter in plan cost by up to 10% with approximately one tenth of the solution time.

Finally, in Chapter 4, we incorporate many practical constraints into the model. In the literature, most works either ignore the structure of flow plans or force them to adhere to in-tree structures where each flow class has exactly one next stop. In practice, more general structures are used where flow classes can have multiple possible next stops. We present a model for generating flow and load plans where commodities are aggregated into flow classes that may be independently directed at every building. Our model produces plans that guarantee each package will be delivered on time despite the aggregated level of control. We give a general heuristic template that we prove can preserve the flow-rule feasibility of solutions. We give four possible implementations adhering to this template. One of these heuristics was shown to produce cost savings of up to 3.4% and savings in trailer-miles of up to 8.5% on large-scale industry instances in under one hour.