This dissertation explores mathematical programming optimization models and algorithms for routing and scheduling ships in a maritime transportation system. Literature surveyed on seaborne transportation systems indicates that there is a scarcity of research on ship routing and scheduling problems. The complexity and the overwhelming size of a typical ship routing and scheduling problem are the primary reasons that have resulted in the scarcity of research in this area.
The principal thrust of this research effort is focused at 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. 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 dissertation. The resulting mathematical formulation is rather complex to solve due to (1) the overwhelming problem size for a typical demand contract scenario, (2) the integrality conditions, and (3) the structural diversity in the constraints. Accordingly, attempting to solve this formulation for a typical demand contract scenario without resorting to any aggregation or partitioning schemes is theoretically complex and computationally intractable.
Motivated by the complexity of the above model, an aggregate model that retains the principal features of the KPC problem is formulated. This model is computationally far more tractable than the initial model, and consequently, it is utilized to construct a good quality heuristic solution for the KPC problem.
The initial formulation is solved using CPLEX 4.0 mixed integer programming capabilities for a number of relatively small-sized test cases, and pertinent results and computational difficulties are reported. The aggregate formulation is solved using CPLEX 4.0 MIP in concert with specialized rolling horizon solution algorithms and related results are reported. The rolling horizon solution algorithms enabled us to handle practical sized problems that could not be handled by directly solving the aggregate problem.
The performance of the rolling horizon algorithms may be enhanced by increasing the physical memory, and consequently, better solutions can be extracted. The potential saving and usefulness of this model in negotiation and planning purposes strongly justifies the acquisition of more computing power to tackle practical sized test problems.
An ad-hoc scheduling procedure that is intended to simulate the current KPC scheduling practice is presented in this dissertation. It is shown that results obtained via the proposed rolling horizon algorithms are at least as good, and often substantially better than, results obtained via this ad-hoc procedure. / Ph. D.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/30368 |
| Date | 27 February 1997 |
| Creators | Mohammed Al-Yakoob, Salem |
| Contributors | Mathematics, Sherali, Hanif D., Herdman, Terry L., Wheeler, Robert L., Burns, John A., Johnson, Lee W. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Dissertation |
| Format | application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | etd.pdf |
Page generated in 0.0026 seconds