The Trajectory Based Operations (TBO) concept creates an environment for information sharing and collaborative decision making between the Air Traffic Management (ATM) stakeholders. This means that airspace users (AUs) share information about the intended 4D-trajectories of their flights, which are then negotiated with other stakeholders for a better use of air traffic system capacity resources. In this paper the authors develop a mathematical model that will contribute to the optimization of 4D-trajectories. They introduce a multi-objective binary integer programming (IP) model whose aim is to assign a 4D-trajectory to each flight based on the preferences and priorities of the airlines. The model considers the preferred 4D-trajectory of all the flights in the pre-tactical planning phase and outputs an optimal pre-departure 4D-trajectory for each flight to be shared or negotiated with other stakeholders and subsequently managed throughout the flight. These output trajectories are obtained by minimising the deviation (delay and re-routing) from the original preferred 4D-trajectories as well as minimizing the air navigation service (ANS) charges subject to the constraints of the system. Some preliminary computational results for the model are presented, which show that the proposed model can provide the basis for the implementation of the TBO concept and pave the way to a fully integrated performance based air traffic management system.