Inspired by the retail industry, we introduce a fundamentally new approach towards stochastic inventory routing by replenishing retailers from a central warehouse using a time-based shipment consolidation policy. Such a time-based dispatching policy, where retailers facing stochastic demand are repetitively replenished at fixed times, is essential in practice. It allows for easy incorporation with dependent up- and downstream planning problems such as personal staffing and warehouse operations, and has become a standard part of transportation contracts. We provide a new chance-constrained model that determines an optimal clustering of retailers in groups, their associated routing and shipment interval, and each retailers’ optimal inventory level. A newly developed branch-and-price-and-cut algorithm solves our model to optimality. Its efficiency comes from a tailored labeling algorithm for solving the pricing problem that relies, among others, on an optimality pruning criterion based on the approximate solution of a 0,1-knapsack problem. Computational experiments show that our exact method can solve instances of up to 60 retailers to optimality. Besides, we accommodate practitioners by providing fast heuristics and a hybrid heuristic that provides excellent solutions with an optimality gap of less than 1%. Finally, we show that incorporating uncertainty already in the planning process is essential for stochastic inventory routing with time-based shipment consolidation, as it results in overall cost-savings of 7.7% compared to the current state-of-the-art.