This paper explores models and algorithms for routing and scheduling ships in a maritime transportation system. The principal thrust of this research effort is focused on the Kuwait Petroleum Corporation (KPC) Problem. This problem is of great economic significance to the State of Kuwait, whose economy has been traditionally dominated to a large extent by the oil sector, and any enhancement in the existing ad-hoc scheduling procedure has the potential for significant savings. A mixed-integer programming model for the KPC problem is constructed in this paper. The resulting mathematical formulation is rather complex to solve due to the integrality conditions and the overwhelming size of the problem for a typical demand contract scenario. Consequently, an alternate aggregate model that retains the principal features of the KPC problem is formulated. The latter model is computationally far more tractable than the initial model, and a specialized rolling horizon heuristic is developed no solve it. The proposed heuristic procedure enables us to derive solutions for practical sized problems that could not be handled by directly solving even the aggregate model. The initial formulation is solved using CPLEX-4.0-MIP capabilities for a number of relatively small-sized test cases, whereas for larger problem instances, the aggregate formulation is solved using CPLEX-4.0-MIP in concert with the developed rolling horizon heuristic, and related results are reported. An ad-hoc routing procedure that is intended to simulate the current KPC scheduling practice is also described and implemented. The results demonstrate that the proposed approach substantially improves upon the results obtained using the current scheduling practice at KPC.