The objective of this paper is to present an effective new methodology to optimize the maintenance costs of bridges stock. Optimization takes place at the network level and not in a project level (bridge by bridge). The dynamics of passage between bridges condition state (from 1 to 5) is achieved by the Markov chains probabilistic method. The Markov transition matrix is determined either by ratios of total areas and areas degraded annually, or by the resolution of an optimization problem. In the latter case, the nonlinear optimization algorithm SQP (Sequanciel Quadratic Programming) is developed. A bridge maintenance matrix is introduced in the calculation of the repair cost. The originality of our approach is to parameterize this matrix by introducing the different optimization variables of the problem. Finally, the cost function to be optimized annually is calculated and optimized by a genetic algorithm. This cost function represents the cost of maintaining the entire asset.