As road administrations keep seeking for innovative ways to improve the means to manage their road assets, the continuous progresses of Pavement Management Systems (PMSs) towards a consistent and effective utility play an important role. An optimization methodology to support decision making is a key aspect of any PMS. In this paper, two genetic algorithms based optimization approaches are addressed. One comprises a multi-objective solver which uses the non-dominated sorting genetic algorithm II (NSGA-II). The other consists in using a genetic algorithm to optimize a single-objective function that is obtained after combining together the multiple objectives through the augmented Tchebycheff method with infinite norm. Objective functions and constraints are related with the pavement quality over time and the total costs of maintenance and rehabilitation (M&R) strategies. For each algorithm, three different constraint handling methods are analysed and compared; (1) a posteriori implementation; (2) constraint function; (3) penalty function. The results showed that, regardless specific modifications to the default algorithms’ options, the multi-objective solver with a posteriori constraints or with a penalty function are the approaches more likely to provide the best approximations to the optimal solutions.