| dc.description.abstract | This thesis considers a chemical tanker arriving a port with several terminals where customers are to be served. The customers have both pickup and delivery requirements, and the intention is to find a feasible route for serving the customers such that the total time used in port is minimized. Chemical tankers carry chemicals in compartments, and the routing decision is complicated when these chemicals need to be allocated to specific tanks. Draft limits at the terminals and time windows for when the cargoes can be served will also influence the terminal sequence the ship can follow.
A literature study examining problems with similar characteristics is presented. There has been done relatively little research on ship routing and scheduling compared to vehicle routing, and this thesis contributes to the literature by studying a pickup and delivery problem with time windows and draft limits. This has never previously been explicitly studied. Also including tank allocation to the problem is an additional contribution to literature, as the allocation of cargoes to tanks is an important planning problem for chemical shipping companies.
Two models are developed, one without and one with tank allocation. The models are solved with two different solution methods. The model disregarding tank allocation is solved exactly by direct implementation in a commercial mixed integer programming solver (MIP-solver), and by using a dynamic programming algorithm. The model considering tank allocation is solved exactly with a MIP-solver and by using a heuristic. The heuristic consists of a dynamic programming algorithm to find ship routes and a MIP-solver to find feasible tank allocations. The computational study in this thesis includes testing of the two models using both solution methods for instances of different sizes, and analyses of the models and solution methods.
The results from the computational study show that when the problem without tank allocation is solved using a MIP-solver, only small instances are solved in a short time.
The results from the computational study show that the MIP-solver is able to solve the problem without tank allocation in a short time only when instances of small sizes are considered. The run times increase drastically when the number of cargoes increases or tank allocation is included. The dynamic programming algorithm and the heuristic shows promising results when solving the models without and with tank allocation, respectively. Both solution methods are able to solve the problems for instances of realistic sizes.
These solution methods are therefore considered suitable to be a part of a tool used for decision support for chemical shipping companies. | |
