We developed and compared Constraint Programming (CP) and Quantum Annealing (QA) approaches for rolling stock optimisation considering necessary maintenance tasks. To deal with such problems in CP we investigated specialised pruning rules and implemented them in a global constraint. For the QA approach, we developed quadratic unconstrained binary optimisation (QUBO) models. For testing, we use data sets based on real data from Deutsche Bahn and run the QA approach on real quantum computers from D-Wave.