Watermarking is one of the techniques for improving the authenticity, integrity, and safety of data. A frequency domain approach is more robust against different attacks compared to a spatial domain approach. However, watermarking approaches are characterized by imperceptibility, robustness, and capacity. The problem of finding the optimal location for embedding the watermark can be challenging and affect the performance of the techniques, but it can also be seen as a path planning problem. Our main aim is to determine the optimal region for embedding the watermark in the Discrete Cosine Transform (DCT) based watermarking approach. We employ a modified Pigeon algorithm to determine the optimal embedding path, in which two objectives are considered to determine the optimal embedding place, as well as the behavior of the algorithm is enhanced to handle the nature of the problem. Our analysis indicates that our approach is highly resistant to different attacks, highly imperceptible after embedding the watermark, and consumes less complexity in embedding and extracting.