This study addresses the optimization of voyage scheduling for transporting shipbuilding blocks manufactured overseas to shipyards. Blocks, the fundamental units in ship construction, incur substantial logistical costs for transportation; therefore, optimizing these operations is critically important. This research proposes a Constraint Programming-based optimization algorithm that simultaneously aims to minimize the frequency of voyages and ensure timely delivery of blocks under various practical constraints. Each transportation vessel (barge) can only select one manufacturing facility (workshop) per voyage, and must concurrently account for spatial loading constraints, weight restrictions, and specific due date for each block. Consequently, this study involves solving a highly complex integrated problem, combining both spatial allocation for loading blocks and scheduling issues that minimize voyage frequency while adhering to delivery schedules. To effectively address this complexity, the research proposes an integrated Constraint Programming model and two separate two-phase models that solve the problem in phases. The proposed algorithms demonstrated superior performance compared to actual operational data and existing heuristic algorithms based on real block transport data. This confirms that the proposed approach not only has generalized effectiveness but also practical applicability.