PhD Defense by Edward He

Event Details
  • Date/Time:
    • Wednesday June 23, 2021
      8:30 am - 10:30 am
  • Location: Atlanta, GA; REMOTE
  • Phone:
  • URL: Bluejeans
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: Scalable Approaches to Path and Routing Problems

Full Summary: No summary paragraph submitted.

Thesis Title: Scalable Approaches to Path and Routing Problems



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):

Meeting ID (BlueJeans): 168 823 053



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.

Additional Information

In Campus Calendar

Graduate Studies

Invited Audience
Faculty/Staff, Public, Graduate students, Undergraduate students
Phd Defense
  • Created By: Tatianna Richardson
  • Workflow Status: Published
  • Created On: Jun 10, 2021 - 1:11pm
  • Last Updated: Jun 15, 2021 - 2:32pm