*********************************
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
*********************************
Title: Exact Algorithms for Routing Problems
Advisors:
Dr. Natashia Boland
Dr. Martin Savelsbergh
Committee Members:
Dr. Alejandro Toriello
Dr. Alan Erera
Dr. Michael Hewitt (Loyola University Chicago)
Date and Time: Wednesday, August 14th, 11:00 am
Location: Groseclose 226A
Abstract:
The study of routing problems has given rise to major developments in the fields of Operations Research (OR). In particular, the Vehicle Routing Problem (VRP) has motivated the development of many exact algorithms and heuristics. In the VRP, a planner designs minimum-cost-delivery routes from a depot to a set of geographically distributed customers, subject to capacity and business constraints. This problem is an important component of distribution systems and, in practice, several variants of the problem that exist are motivated by the diversity of operations rules and constraints in real-life applications. The VRP generalizes the Traveling Salesman Problem (TSP), so any of its variants present a computational challenge. We study a stochastic variant of the VPR and the Inventory Routing Problem (IRP), a problem that was initially studied as a variant of the VPR.
In Chapter 2, we study the Vehicle Routing Problem with Probabilistic Customers (VRP-PC), a two-stage stochastic optimization problem that is a fundamental building block within the broad family of stochastic routing models. In the first stage, a dispatcher determines a set of vehicle routes serving all potential customer locations, before actual requests for service realize. In the second stage, vehicles are dispatched after the subset of customers requiring service is observed; a customer not requiring service is skipped from its planned route at execution. The objective is to minimize the expected vehicle travel cost by assuming known customer realization probabilities. We propose a column generation framework to solve the VRP-PC to a given optimality tolerance. Specifically, we present two novel algorithms, one that under-approximates a solution's expected cost, and another that uses its exact expected cost. Each algorithm is equipped with a route pricing mechanism that iteratively improves the approximation precision of a route's reduced cost; this produces fast route insertions at the start of the algorithm and reaches termination conditions at the end of the execution. Compared to branch-and-cut algorithms for the VRP-PC using arc-based formulations, our framework can more readily incorporate sequence-dependent constraints such as customer time windows. We provide a priori and a posteriori performance guarantees for these algorithms, and demonstrate their effectiveness via a computational study on instances with realization probabilities for customers ranging from 0.5 to 0.9.
In Chapter 3, we consider a variant of the Inventory Routing Problem (IRP), the Continuous Time IRP (CIRP). In time dependent models, such as the CIRP, the objective is to find the optimal times (continuous) at which activities occur and resources are utilized. These models arise whenever a schedule of activities needs to be constructed. A common approach consists of discretizing the planning time and then restricting the decisions to those time points. However, this approach leads to very large formulations that are intractable in practice. In the CIRP, a company manages the inventory of its customers, resupplying a single product from a single facility during a finite time horizon. The product is consumed at a constant rate (product per unit of time) by each customer. The customers have local storage capacity. The goal is to find the minimum cost delivery plan that ensures that none of the customers run out of product during the planning period. We investigate time-expanded network formulations that can form the basis of a Dynamic Discretization Discovery (DDD) algorithm and demonstrate in an extensive computational study that they, by themselves, produces provably high-quality, often optimal, solutions.
In Chapter 4, we study the Continuous Time IRP with Out-and-Back Routes (CIRP-OB): a vehicle route starts at the depot, visits a single customer, and returns to the depot. We develop the full DDD algorithm to solve the CIRP-OB by using partially constructed time-expanded networks. This method iteratively discovers the time points needed in the network to find optimal solutions. We test this method on randomly generated instances with up to 30 customers, where provable optimal solutions are found in most cases.
