This paper presents an original and generic column generation-based exact method to solve bi-objective vehicle routing problems.The talk will first provide a quick overview of exact methods on bi-objective problems and in particular on vehicle routing problems. Then mathematical formulations for these problems will be introduced, either with two explicit objectives or with ε-constraint linearization. Theorems on the structure of bi-objective vehicle routing problems will be presented, and based on them, new rules to explore the solution space will be introduced. The resulting exact method takes advantages of different techniques to discard some insignificant columns and save the current state of column generation. Numerical results on the two following case-studies show the efficiency of the approach with regards to the state-of-the art: bi-objective vehicle routing with time windows and with two integer costs and on bi-objective team-orienteering problem with time windows