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 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 machine learning techniques and observed shipment data. 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. Besides the online marketplace, our approach is also applicable to the increasingly popular omni-channel retailing which also involves middle-mile network design