The combination of mathematical programming and heuristics is known as matheuristic. Constructing a matheuristic comprises two steps: First selecting its components, second parameterizing those components. The construction of a matheuristic is often done manually by experts, which leads to expensive engineering processes. To bring matheuristics into practice, their construction should be automated. In this paper a matheuristic construction approach is proposed to close this gap. The approach is based on instance space analysis for the selection and Bayesian optimization for the parametrization of the matheuristic. First computational studies show, how Bayesian optimization can be used to parameterize an original heuristic.