This paper presents quantitative results we obtained when optimizing the setting of priorities of the AFDX traffic flows, with the objective to obtain tighter latency and queue-size deterministic bounds (those bounds are calculated by our Network Calculus tool). We first point out the fact that setting randomly the priorities gives worse bounds than using no priorities, and we then show experiments on the basis of classic optimization techniques such as a descent method and a tentative AlphaBetaassisted brute-force approach: both of them haven’t brought significantly better results. We finally present experiments based on genetic algorithms, and we show how driving these algorithms in an adequate way has allowed us to deliver a full range of priority configurations that bring tighter bounds and allow the network traffic designer to trade off average gains of 40% on all the latency bounds against focused improvement on the largest queue-size bound (up to a 30% reduction).