On Customers’ Multiple Purchases: Model and Application

Abstract

My thesis focuses on the emerging topic of multi-purchase behavior and comprises three essays.

In the first essay, we consider its application in the order fulfillment on E-commerce platforms. Order fulfillment is a crucial task that shapes online retailers’ competitiveness and profitability. Order arrivals to a fulfillment center often fluctuate significantly over time, causing an unbalanced workload and high operational costs. In this paper, we study an emerging practice termed anticipatory packing, which is to prepare some packages in non-peak periods to be used for fulfilling orders in the subsequent peak periods. Specifically, the preparation involves the operation of picking some items and putting them in the same customer bin but may or may not involve actual packaging. Anticipatory packing promises to better utilize the idle capacity in non-peak periods and reduce the peak-period workload, resulting in a lower cost and faster delivery. Improper prepacking operations, nevertheless, can also be costly. For effective anticipatory packing, we develop a sample-average approximation (SAA) model by using the order data of recent days. We provide a comprehensive APX-hardness analysis for the model and then design an effective approximation algorithm to solve it. To enhance the practical performance of the algorithm, we have also developed a tighter integer programming formulation and a subgradient descent method to solve the associated Lagrangian dual. We investigate the effectiveness of anticipatory packing and the SAA model with extensive experiments. On a real data set, we show that anticipatory packing can yield an operational cost reduction of over 8% and a significant fixed investment cost reduction.

In the second essay, we investigate how to predict customer orders. The ability to predict future customer orders is of significant value to retailers in making many crucial operational decisions. Different from next basket prediction or temporal set prediction, which focuses on predicting a subset of items for a single user, this paper aims for the distributional information of future orders, i.e., the possible subsets of items and their frequencies (probabilities), which is required for decisions such as assortment selection for front-end warehouses and capacity evaluation for fulfillment centers. Based on key statistics of a real order dataset from Tmall supermarket, we show the challenges of order prediction. Motivated by our analysis that biased models of order distribution can still help improve the quality of order prediction, we design a generative model to capture the order distribution for customer order prediction. Our model utilizes representation learning to embed items into a Euclidean space and design a highly efficient SGD algorithm to learn the item embeddings. Future order prediction is done by calibrating orders obtained by random walks over the embedding graph. The experiments show that our model outperforms all the existing methods. The benefit of our model is also illustrated with an application to assortment selection for front-end warehouses.

In the third essay, we introduce a Markov chain-based choice model to depict consumer choice behavior involving simultaneous purchases. Specifically, at each step, consumers either purchase an additional product or leave, depending on their current selection, and their choice behavior follows the multinomial logit model (MNL). As a result, the entire behavior forms a Markov chain. We employ rank-constrained maximum likelihood estimation to estimate the transition matrix from truncated random data. Under mild conditions, we establish the sample complexity needed to recover the low-rank matrix. Furthermore, we explore the capacitated assortment problem when consumers adhere to this model. We demonstrate that the problem is generally NP-hard to approximate within any constant, and we offer a fully polynomial time approximation scheme (FPTAS) when the transition matrix has a low nonnegative rank. Finally, we showcase the effectiveness of our approach using real and synthetic data.

Date of Award	19 Sept 2023
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Yanzhi David LI (Supervisor)