The reduction of fuel consumption as well as the rising demands of customers regarding a vehicle’s driving dynamic and the legislator’s continually rising demands are a current issue in vehicle development. Hybrid vehicles offer a possibility to rise to this challenge. Realistic driving cycles are of utmost importance for the calibration of a hybrid vehicle’s operational strategy. Deriving replacement speed cycles from extensive customer data sets seems to be an approach for solving these problems. The contribution at hand describes the derivation of replacement cycles by using stochastic models, probabilistic (weighted) drawings and a combinatorial optimisation. The novelty value is that the characteristic influences of all drivers are being considered in the generation due to the stochastic modelling. The newly developed algorithm extracts frequently reoccurring patterns from the stochastic model and then assembles several generated velocity progressions to one replacement cycle which combines characteristics which are important for consumption and are also customer-oriented. The contained combinatorial optimisation is based on an optimisation algorithm called "threshold accepting" and is an innovation for this usage scenario. Studies show positive properties for the combination of different driving patterns with the result that realistic replacement cycles can be extracted in a short time from extensive customer data. The ensuing replacement cycles provide the opportunity to attune a hybrid vehicle’s operational strategy to the market and to perform sensitivity examinations and consumption forecasts.