The ROK Navy operates multiple outposts for efficient security of the coast and the NLL that serves as the main objective of the Navy`s maritime patrol. This paper addresses the issue of determining the location of outpost and allocation of patrol ships to the outpost for efficient patrol mission in the navy. Also, presents a two-phase mathematical model which considers the characteristics of the patrol operation to determine the location of outposts, the assignment of patrol area, and the allocation of patrol ships using the integer programming. Numerical experiments are provided to illustrate the solution procedure. Finally, we present the optimal solution and analysis using the real size examples.