<p>The headways or the time gaps between successive bus departures are small for high-frequency routes in a bus transportation system. Any perturbation, like variability in load and/or traffic conditions, makes such systems quickly unstable; this instability can lead to bunching, where buses start traveling together and may result in longer passenger waiting times. This paper aims to derive Pareto-optimal policies of the two performance measures, the bunching probability and the average passenger waiting times—to be precise, the aim is to design state-dependent and possibly non-stationary policies that optimize any given weighted combination of the two performance measures. In practice, operators commonly use static headway policies, scheduling buses to depart from the depot at equal intervals of time. However, in the presence of increased traffic randomness, these policies may not be sufficient, and bunching can become significantly high. We propose ‘partially-dynamic’ policies, where the current headway depends on the readily available components of the <i>state</i> information (the headways of the previous trips); it does not use elaborate information (like the number of passengers waiting at various stops, round trip delays) of the previous trips. Closed-form expressions for the Pareto-optimal headway policies are derived by solving the appropriate dynamic programming equations. Monte-Carlo simulation-based estimates of both the performance measures show significant improvement compared to the static policies. The optimal dynamic policies are derived for both the correlated and independent travel times. The two sets of optimal policies are structurally similar – they are linear in the state-components (previous trip headways at the depot). However, the coefficients of the two policies may differ.</p>