Clustering techniques in marine transportation

This dissertation focuses on the development of load clustering methods to support cost minimization models in the barge transportation industry. An integer-programming (I.P.) model is presented which optimizes barge grouping into the most cost efficient configurations for transit. Barges are grouped such that the total costs associated with dwell time, handling, and transit are minimized while constraints associated with pick-up and delivery requirements, physical tow sizes, travel time, and locking time are considered.; This dissertation is divided into six chapters. In Chapter One a brief overview of the current problem is addressed and the developmental and research goals are outlined. Chapter Two gives a historical overview of clustering techniques and integer programming models in the transportation industry. Chapter Three investigates an original integer-programming model that was developed for the Ohio River forecasting problem. However, due to the large size of this IP for realistic size problems, different clustering/grouping techniques are considered to achieve the goals that were indicated earlier. Clustering is the art of grouping together pattern vectors that in some sense belong together because of similar characteristics. Various grouping techniques are explored that perform clustering of a given set of raw data and take under consideration the “hard constraints” that the problem possesses. In particular hierarchical and non-hierarchical clustering algorithms are considered. Also, a specific grouping heuristic that takes under consideration some of the most important aspects of the problem is developed. Five clustering models are applied to the Ohio River forecasting model including single-linkage, complete-linkage, average, Wards clustering and Partitioning around Medoids. Chapter Four describes in detail all of the research models and the utilization levels that each method produced. In Chapter Five a cost comparison equation is developed based on the cost factors that affect these groupings. The purpose of this cost equation is to serve as a way to compare different clustering methods performed by different researchers. Lastly, Chapter Six outlines future possible research goals.; The main results from this dissertation indicated that complete linkage clustering and partitioning around medoids performed at a superior level when they were compared to any of the other grouping models. Specifically the slot utilization percentages for complete linkage and partitioning around medoids were 73.89% and 75.60% respectively. However, when the cost issues were calculated the results yield that complete linkage was the most cost efficient method for this particular set of data with {dollar}601,392 versus {dollar}610,997 for partitioning around medoids.; The primary contributions of this research are the heuristic algorithm and the clustering algorithms. The algorithm is a tool to achieve a guaranteed good solution to a marine transportation problem with multiple ports, and constraints in capacity, direction of travel, time, and type of barge. Another contribution of the heuristic algorithm is that it can serve as an initial solution to an integer programming model or a non-hierarchical clustering model in which the search of an optimum solution is crucial. The secondary contribution of this research is the hierarchical and non-hierarchical clustering models that fit the constraints of the barge transportation problems.; The research is strengthened and the practicality of results is ensured by the participation of American Commercial Barge Lines.