The contribution of air travel to climate change is significant and growing, but emissions and their effects are not yet regulated. One of the major impacts on climate from the aviation sector is the production of contrails (vapour trails) in the atmosphere and their influence on cirrus cloud formation. Potentially, reducing cruise altitude represents one option for controlling the growing climate impact of aviation. In general, this would reduce contrail and cirrus cloud formation but there are associated penalties, including an increase in the rate of fuel consumption and hence in the rate of carbon dioxide emission. Constraining cruise altitudes also raises operational issues, including increases in airspace congestion and in journey time. Atmospheric variability can change the amount of contrail and contrail-cirrus, so contrails may sometimes be more likely to form at lower altitudes. In these cases, reducing cruise altitude could increase rather than reduce the contrail amount. This paper describes an approach to optimise the balance between the benefits of contrail reduction and the penalties incurred for altitude restriction. The calculations use an air traffic sample for western Europe, with NCEP-II reanalysis data for atmospheric temperature and humidity. A maximum cruise altitude is selected for each six-hour period, according to atmospheric conditions. This altitude provides the greatest reduction in contrail for the lowest increase in carbon dioxide emission. This avoids the contrail and carbon dioxide increases associated with ineffective or counter-productive altitude restrictions. Calculated contrail reductions are presented, along with the associated increases in carbon dioxide. These values compare favourably with previous policy designs based on altitude restrictions fixed on a monthly basis. In addition, potential operational issues associated with a varying altitude restriction policy are discussed.