*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
