.png){kind=icon}
.png){kind=icon}
Return
Clustering with two-stage stochastic programming: An application to usage behavior pattern mining in parking subscription services
.png){kind=icon}
PRE
AI
DOI：10.1016/j.trc.2026.105978.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
•
An operations research perspective on clustering via a two-stage stochastic programming framework.
•
Identification and clustering of usage behavior patterns in subscription services.
•
Model analyses, optimality-preserving enhancements, and an effective matheuristic algorithm.
•
Case studies on real-world parking subscription data and a public dataset demonstrate benefits and computational efficiency.
Abstract
Clustering has been extensively studied in statistics and machine learning. This study introduces an operations research perspective by modeling and solving clustering within a two-stage stochastic programming framework. The formulation is motivated by their structural alignment: each object to be clustered can be treated as an empirical realization in the scenario set. We therefore model each observation as a second-stage scenario, while the cluster centers are shared first-stage decisions whose performance is evaluated across all scenarios. This perspective offers a clearer structural interpretation of clustering and allows domain knowledge to be explicitly encoded through the objective and constraints, thereby improving interpretability and empirical clustering performance. To assess the effectiveness of this approach, we apply it to usage behavior pattern mining (user segmentation) in subscription services. To handle realistic problem sizes, we introduce three model enhancements and a tailored column-generation matheuristic with an early termination rule (ET-CG), which shortens the long tail of column generation and significantly reduces runtime without compromising solution quality. We validate the proposed framework using six months of real-world parking subscription data from a commercial parking facility in Shenzhen, China. The proposed two-stage stochastic programming approach achieves average clustering loss reductions of 6.35% compared to K-medians, 7.95% compared to K-medoids, 5.74% compared to K-modes, and 6.42% compared to BanditPAM++. Additional experiments show that the model enhancements accelerate computation by a factor of 20.68 on average, and the ET-CG matheuristic achieves near-optimal solutions with high computational efficiency, solving real-world instances in 30.94 to 47.53 seconds (average 38.26 seconds). Beyond usage behavior pattern mining in subscription services, the proposed two-stage stochastic programming framework generalizes to other clustering problems that minimize an aggregated loss over the empirical distribution induced by the observed objects.
Keywords:
Usage behavior pattern mining
Two-stage stochastic programming
Matheuristic algorithm
Parking management
Journal
IF:
7.9
Papers:
4.7K
Citations:
3.2W
Organization
View more organizations