Point label placement problem is the problem of labeling points in graphical display systems such as mapbased ones in order to minimize conflicts of labels and thus to maximize legibility. Algorithmic complexity of the general problem is proven to be NP-hard. Addressing this problem is becoming more important in dynamic and real-time environments, where both display properties or point elements are subject to change, since those systems have potential use widely and in large scale. In this study, heuristic optimization methods are proposed to facilitate fast and goodquality labeling in such dynamic environments. The methods are two-phased and comprised of several combinations of greedy construction and local search methods. Performances of the methods are examined in terms of solution quality and run time. The eliminative, two-criteria method outperform other methods in this study and the methods proposed in the literature.