This study proposes a refundable-tradable bottleneck permits (R-TBP) scheme that is a natural expansion of the TBP scheme proposed by Akamatsu (2006, 2007) as a proactive transportation demand management method. The TBP allows its permit holder to pass through a bottleneck within a pre-specified time period, which is traded in a permit market. Akamatsu (2007) proved that the TBP scheme achieved a dynamic social optimal (DSO) assignment in a decentralized manner for a general network in a deterministic framework. This article expands these analyses into a stochastic situation where users randomly cancel their trips and thus some of the distributed TBPs remain unused. We first propose a refundable TBP that is fully refunded when its holder cancels their trip. Our analyses reveal that social optimal allocation can be realized if a manager can determine the proper issue amount of the R-TBP. We then develop an algorithmic trial-and-error process that determines the appropriate R-TBP issue amount at its convergent point using only observable data, as indicated through bottleneck flow and the market price of the R-TBP.