Title page for ETD etd-255314202974780

Type of Document

Dissertation

Author

Mohammed Al-Yakoob, Salem

Author's Email Address

smohamme@simopt04.ise.vt.edu

URN

etd-255314202974780

Title

Mixed-Integer Mathematical Programming Optimization Models and Algorithms For An Oil Tanker Routing and Scheduling Problem

Degree

PhD

Department

Mathematics

Advisory Committee

Advisor Name	Title
Burns, John A.
Herdman, Terry L.
Johnson, Lee W.
Wheeler, Robert L.
Sherali, Hanif D.	Committee Chair

Keywords

mixed-integer programming
aggregation
ship scheduling

Date of Defense

1997-02-27

Availability

unrestricted

Abstract

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

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	28.8 Modem	56K Modem	ISDN (64 Kb)	ISDN (128 Kb)	Higher-speed Access
	etd.pdf	723.84 Kb	00:03:21	00:01:43	00:01:30	00:00:45	00:00:03