Design and Performance Prediction for Supply Chain Systems with Graphical Structures

This dissertation studies the optimal design and performance evaluation of large-scale supply chain systems with graphical structures such as assemble-to-order (ATO) systems and e-commerce fulfillment networks. It consists of three essays.

The first essay studies the design of effective operational policies in the assemble-to-order (ATO) systems. We consider continuous-review ATO systems with general bills of materials (BOM) and general leadtimes. First, we characterize the asymptotically optimal policy for the M-system. The policy consists of a periodic review priority (PRP) allocation rule and a coordinated base-stock (CBS) replenishment policy. We then construct heuristic policies using insights from the asymptotically optimal policy. In particular, we adopt the PRP allocation rule and develop a decomposition approach for inventory replenishment. This approach decomposes a general system into a set of assembly subsystems and constructs a linear program to compute the optimal policy parameters. However, both the CBS and the assembly decomposition approach are limited to simple systems. We then consider a second approach, which decomposes a system into a set of distribution subsystems and each subsystem has a straightforward optimal solution, which is similar to the newsvendor problem. Finally, in a numeral test, we find that the assembly decomposition is very effective but computationally expensive and thus only good for small-scale systems; the distribution decomposition performs as effective as the optimal independent base-stock (IBS) policy, but is highly scalable than finding the optimal IBS policy for large-scale systems.

The second essay focuses on optimizing the operational decision at one layer of the supply chain network when some operational decisions at another layer are unknown to the decision-maker. More specifically, we consider the transportation network design problem for the e-commerce marketplace. A salient feature in this problem is decentralized decision-making. While the middle-mile manager decides the network configuration on a weekly or bi-weekly basis, the real-time flows of millions of packages on any given network configuration (which we call the flow response) are controlled by a fulfillment policy employed by a different decision entity. Thus, we face a fixed-cost network design problem with unknown flow response. To meet this challenge, we first develop a predictive model for the unknown response leveraging observed shipment data and machine learning techniques. Apart from the most natural network-level predictive model, we find that the more parsimonious destination-level and arc-level predictive models are more effective. We then embed the predictive model to the original network design problem and characterize this transformed problem as a c-supermodular minimization problem. We develop a linear-time algorithm with an approximation guarantee that depends on c. We demonstrate that this algorithm is scalable and effective in a numerical study.

The third essay investigates how to use the Graph Neural Network (GNN) model to predict the operational performances of supply chain networks. GNN is a newly developed machine learning tool to leverage the graphical structure information. It has demonstrated good prediction accuracy in various contexts, including social, bioinformatics and citation networks. Surprisingly, GNNs have not received much attention in supply chain systems despite the fact that many systems exhibit a graphical structure, such as assemble-to-order systems and process flexibility networks. To the best of our knowledge, we are the first to explore the application of GNN to supply chain problems. As operational performances of the entire network can often be decomposed into node-level or edge-level performances, we study both node-level and edge-level predictions. We find that while the existing GNN model can generate reasonable node-level predictions, special tailoring is needed for edge-level predictions of supply chain networks. A key contribution of our research is to develop a novel graph transformation approach, which allows an edge to learn from its neighborhood edges. Tested on different synthetic datasets from two different supply chain systems, we implement the GNN model with our proposed graph transformation and several benchmark methods, including an existing GNN model and the traditional machine learning methods, such as the convolutional neural network and random forest. The results indicate that our approach significantly outperforms the benchmarks in edge-level prediction. We also observe the importance of utilizing the graphical structure and edge directions. Our comparison reveals that it is beneficial to start with node-level or edge-level predictions and then aggregate them together for the graph-level prediction, instead of the direct graph-level prediction commonly used in other applications.