Globalization and subsequent increase in seaborne trade have necessitated efficient planning and management of world's anchorage areas. These areas serve as a temporary stay area for commercial vessels for various reasons such as waiting for passage or port, fuel services, and bad weather conditions. The research question we consider in this study is how to place these vessels inside a polygon-shaped anchorage area in a dynamic fashion as they arrive and depart, which seems to be the first of its kind in the literature. We specifically take into account the objectives of (1) anchorage area utilization, (2) risk of vessel collisions, and (3) fuel consumption performance. These three objectives define our objective function in a weighted sum scheme. We present a spatio-temporal methodology for this multi-objective anchorage planning problem where we use Monte Carlo simulations to measure the effect of any particular combination of planning metrics (measured in real time for an incoming vessel) on the objective function (measured in steady state). We resort to the Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm for identifying the linear combination of the planning metrics that optimizes the objective function. We present computational experiments on a major Istanbul Straight anchorage, which is one of the busiest in the world, as well as synthetic anchorages. Our results indicate that our methodology significantly outperforms comparable algorithms in the literature for daily anchorage planning. For the Istanbul Straight anchorage, for instance, reduction in risk was 42% whereas reduction in fuel costs was 45% when compared the best of the current state-of-the-art methods. Our methodology can be utilized within a planning expert system that intelligently places incoming vessels inside the anchorage so as to optimize multiple strategic goals. Given the flexibility of our approach in terms of the planning objectives, it can easily be adapted to more general variants of multi-objective spatio-temporal planning problems where certain objects need to be dynamically placed inside two or even-three dimensional spaces in an intelligent manner.