Scenario-based approaches provide an effective and practical approach to capturing the probabilistic nature of travel time in a traffic network. Scenarios that represent daily roadway conditions are generated by identifying various demand- and supply-side factors that affect travel time variability and by sampling a set of mutually consistent combinations of the associated events. The sampled scenarios are then evaluated with traffic simulation models to obtain travel time distributions to provide a basis for extracting a wide range of reliability performance metrics. A key question under this framework pertains to the number of input scenarios needed to achieve the best estimators of reliability measures of interest, given a limited computation budget. Given a stratification of the entire domain of daily scenarios into distinct scenario categories (or strata), the study addressed the optimal sample size allocation problem in connection with stratified sampling. Existing sample allocation schemes (e.g., Neyman's) were optimized for estimating the mean. However, dispersion measures such as variance and standard deviation were of greater interest in travel time reliability studies. Thus, this study explicitly specified the optimal allocation scheme for estimation of variance. With a specific characteristic observed in travel time data, namely, a strong positive correlation between standard deviation and mean, an analytical formula that approximated the variance of the sample was developed, and an analytical approximate solution for the optimal allocation for estimating the variance was derived. The proposed method was validated with a simulation study and was compared with other allocation methods in regard to estimation of various reliability measures.