The consumption of fossil fuels in order to power flights leads to undesirable pollution particles to be released to the atmosphere. Fuel also represents an important expense for airlines. For these reasons, it is of interest to reduce fuel burn for a given flight. In this article, the altitudes followed by a commercial aircraft during the cruise phase of a flight, also called vertical reference trajectory, were optimized in terms of fuel burn. The airspace was modelled under the form of a unidirectional graph. Fuel burn was computed using a numerical performance model. The weather forecast was obtained from the model delivered by Environment Canada. The selection of waypoints where to execute the changes in altitudes that provided the most economical flight cost in terms of fuel burn was determined using the particle swarm optimisation (PSO) algorithm. The trajectories provided by the algorithm developed in this paper were compared against simple geodesic trajectories to validate its optimization potential, and against as flown trajectories. Results have showed that up to 6.5% of fuel burn can be saved comparing against simple trajectories, and up to 3.1% was optimized comparing against as flown trajectories.