Thesis Title: Scalable Approaches to Path and Routing Problems

Advisors:

Dr. Natashia Boland, School of Industrial and Systems Engineering, Georgia Tech

Dr. George Nemhauser, School of Industrial and Systems Engineering, Georgia Tech

Dr. Martin Savelsbergh, School of Industrial and Systems Engineering, Georgia Tech

Committee Members:

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

Dr. Mike Hewitt, Information Systems and Supply Chain Management, Loyola University Chicago

Date and Time: Wednesday, June 23, 2021, @ 8:30 am (EST)

Meeting URL (BlueJeans): https://bluejeans.com/168823053/4411

Meeting ID (BlueJeans): 168 823 053

Abstract:

Many combinatorial optimization problems involve an aspect of time, whether due to changing conditions, updated information, or being under a continuous decision-making process. A popular domain for time-based decision making is logistics, where it is not only important to decide along which routes products need to be transported, but also when the transportation should occur. The timing for these problems is critical to take advantage of changing operational conditions such as traffic, capacity, and costs. Unfortunately, introducing time as an additional dimension significantly increases the size of models over their static counterparts. In fact, such models often resort to heuristics as existing solution methods are computationally intractable. This dissertation aims to provide insights into how scalable solution methodologies can be developed for such problems in path and routing problems. 

Chapter 2 shows how DDD can be applied to the minimum duration time-dependent shortest path problem to significantly improve the run-time over existing methods. It also introduces the first polynomial-time algorithm for a related problem, the minimum travel time time-dependent shortest path problem, as well as how DDD can also be used for this problem to reduce the search space.

Chapter 3 builds upon the theory of time-expanded networks from Chapter 2 to provide new computational complexity results and polynomial-time algorithms on a large class of time-dependent shortest path problems with waiting. While this chapter does not directly use DDD, the new algorithms solve time-dependent shortest path problems identical to those in Chapter 2 as a subroutine and thus can take advantage of DDD.

Chapter 4 explores how DDD can be applied to the Service Network Design Problem with Hub Loading and Unloading Capacity (SNDP-HC), an NP-hard problem where even determining feasibility is an open question. Instances of SNDP-HC motivated by real-life problems result in integer programming formulations consisting of billions of constraints and hundreds of millions of variables. Using DDD, the size of the integer programming formulations can be reduced significantly, which enables small and medium-sized instances of SNDP-HC to be solved exactly in a reasonable time. For larger instances, this approach serves as a good starting point for the development of future algorithms.