Optimization of water-borne crude oil transport

A ship scheduling problem in optimization of water-borne crude oil transportation has been investigated. The classic optimization problem the most closely related to the problem at hand is the Multi-Vehicle-Pick-up-and-Delivery Problem with Time Windows (m-PDPTW). In addition to the basic characteristics of the m-PDPTW, the studied problem has an additional degree of freedom due to having pick-ups and deliveries that are not matched. This extra freedom gives new possibilities when creating effective heuristics when dealing with transportation problems. The studied problem has been presented in relation to carefully selected background literature. On this basis a proposed heuristic has been developed, and implemented using some already existing structures in the commercial decision support system TurboRouter. The studied problem is an industrial shipping problem, an operational mode where the shipper owns the cargo to be transported. No income is therefore made directly from transporting goods. Therefore the objective function chosen was net income, which in this mode is the same as minimizing the net expenses. A multi-start local search with pre-matching of pick-ups and deliveries heuristic was chosen based on an assessment of problem size, problem type, real life applicability and existing software. This heuristic consists of three main parts. First the pick-ups and deliveries are matched and merged in a pre-matching heuristic, and then a large number of initial solutions are generated by an insertion heuristic. The best initial solutions are then improved by a local search. Two strategies were developed for pre-matching and then tested. The one with the best test results was subsequently used in the heuristic. This multi-start local search with pre-matching of pick-ups and deliveries heuristic has been subject to rigorous testing and was compared to a single-start local search and multiple initial solutions heuristic. The solutions generated by the multi-start local search heuristic were superior compared to those of the other heuristics, but the computation time necessary was high and higher than those of the heuristics which it was compared to. This high computation time is partially believed to be a result of flexible data sets resulting in broad solution spaces. In addition some computationally expensive heuristics were deployed, increasing the computation time. In real life applications, finding a solution relatively quickly is of importance. Therefore the heuristic may need to be simplified and used on "tighter" data sets than some sets used in testing to be real life applicable