Data-Driven Scalable E-commerce Transportation Network Design with Unknown Flow Response

Motivated by our experience with a large online marketplace, we study an e-commerce middle-mile transportation network design problem. A salient feature in this problem is decentralized decision making. While the middle-mile manager decides the network configuration on a weekly or monthly basis, the real-time flows of millions of packages on any given network configuration 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 using observed shipment data. Apart from the most natural network-level predictive model, we find that the more parsimonious origin-level and arc-level flow response predictive models are more effective. We then embed the predictive model to the original network design model to obtain a transformed problem. We characterize this new problem as a c-super-modular minimization problem and develop two linear time approximation algorithms with performance guarantees. We demonstrate that these two algorithms are scalable and effective in a numerical study. Our approach is also applicable to omni-channel retailers which may have thousands of brick-and-mortar stores as the destinations for customers to pick up online orders.