Arrival runways are a critical resource in the air traffic system. Arrival delays have a great impact on airline operations and cost. Therefore, tactical arrival planning is becoming increasingly important. In this paper, we consider the tactical single runway arrival problem. The current focus on collaborative decision making is reflected by giving airlines the possibility to provide cost functions related to arrival delays for their flights. A scaling method for these cost is introduced to ensure equity. Our formulation will assign landing times to the flights, while taking the costs into account. A problem-specific local search heuristic has been implemented to obtain reasonable solutions within acceptable computation times. A large number of instances, created using schedule data from a major European hub, have been tested. These experiments show large cost savings for the airlines compared to current practice. All airlines achieve improvements, which is important for the acceptance of the method. The heuristic is able to solve instances with over 100 flights in a few minutes. A simulation experiment shows the method can also be used in a dynamic setting and produces robust schedules. © 2007 Elsevier B.V. All rights reserved.