Theoretical and Computational Methods for Network Design and Routing

Complex decision-making is ubiquitous in contemporary supply chain management. Over the years, researchers

from related fields have developed a variety of techniques to facilitate the modeling and optimization arising in supply chain areas such as network design, inventory management and vehicle routing. Traditionally, however, techniques from these fields are developed separately with their own strengths and weaknesses. For instance, approximation algorithms, developed by theoretical computer scientists, are able to produce solutions with a provable worst-case guarantee but can be too pessimistic for practical applications. On the other hand, heuristics typically focus on the improvement of feasible solutions and neglect the

rigorous analysis of the gap with respect to the optimal value. This dissertation aims to explore connections between neighboring fields such as computer science and

operations research by bringing together ideas and techniques from approximation algorithms, complexity

theory, constraint programming, decision diagrams and mixed-integer programming. In particular, we study

the following three problems in supply chain optimization.

In Chapter 2, we study a two-level network design problem to route demand between source-sink pairs. The demand is routed in a combination of lower level routes that aggregate and disseminate demand to and from local hubs, and upper level routes that transport aggregated demands between hubs. Due to economies of scale, the unit cost of upper level arcs is significantly lower than the lower level counterpart. The objective is to cluster demand at hubs so as to optimally trade off the cost of opening and operating hubs against the discounted costs of cheaper upper level routes. We construct a mathematical model for this problem and term

it the hub network design (HND) problem. We study the computational complexity and develop approximation

algorithms for the HND and its variants. Inspired by our theoretical analysis, we develop matheuristics that combine evolutionary algorithms, very large neighborhood search and mixed integer programming. Using realistic data, we demonstrate that our approximation techniques provide very good starting solutions for further heuristic search. Our methods produce solutions with an optimality gap of less than 3% in a reasonable amount of time on instances of up to 100 nodes. In Chapter 3, we consider the deterministic inventory routing problem over a discrete finite time horizon.

Given clients on a metric, each with daily demands that must be delivered from a depot and holding costs over the planning horizon, an optimal solution selects a set of daily tours through a subset of clients to deliver all demands before they are due, with the goal of minimizing total holding and tour routing costs over the horizon. For the capacitated case, a limited number of vehicles are available, where each vehicle makes at most one trip per day. Each trip from the depot is allowed to carry a limited amount of supply.

Motivated by an approximation algorithm proposed in the literature that relies on a reduction to a related problem called the prize-collecting Steiner tree (PCST) problem, we develop fast heuristics for both cases by solving a family of PCST instances. Computational experiments show that proposed methods can find near optimal solutions for both cases and substantially reduce the computation time compared to a MIP-based approach. In Chapter 4, we study a new routing problem called the traveling salesman problem with drone (TSPD), which is a promising new model for future logistics networks that involves the collaboration between traditional trucks and modern drones. The drone can pick up packages from the truck and deliver them by air

while the truck is serving other customers. The operational challenge combines the allocation of customers to either the truck or the drone, and the coordinated routing of the truck and the drone. In this work, we consider the scenario of a single truck with one drone, with the objective to minimize the completion time (or makespan). As a partial explanation for the computational challenge of the TSP-D, we show it is

strongly NP-hard to solve a restricted version where drone deliveries need to be optimally integrated in a given truck route. Then we present a compact scheduling-based constraint programming (CP) formulation. Our computational experiments show that solving the CP model to optimality is significantly faster than the state-of-the-art exact algorithm at the time of publication. For larger instances up to 60 customers, our CP-based heuristic algorithm is competitive with a state-of-the-art heuristic method in terms of the solution quality. The increasing popularity of drone-assisted routing has met with the difficulty of solving those problems

to optimality, which has inspired a surge of research efforts in developing fast heuristics. To help develop scalable exact algorithm, as well as to evaluate the performance of heuristics, strong lower bounds on the optimal value are needed. In Chapter 5, we propose several iterative algorithms to compute lower bounds motivated by connections between decision diagrams (DDs) and dynamic programming (DP) models used for pricing in a branch-and-cut-and-price algorithm. Our approaches are general and can be applied to various vehicle routing problems where corresponding DP models are available. By adapting techniques from the DD literature, we are able to generate and strengthen novel route relaxations. We also propose alternative approaches to derive lower bounds from DD-based route relaxations that do not use column generation. All the techniques are then integrated into iterative frameworks to obtain improved lower bounds. When applied

to the TSP-D, our algorithms are able to produce lower bounds whose values are competitive to those from the state-of-the-art approach. Applied to larger problem instances where the state-of-the-art approach does

not scale, our methods are shown to outperform all other existing lower bounding techniques.