Abstract
The purpose of this paper is to solve a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies are committed to carrying some contract cargoes and will try to derive additional revenue from optional spot cargoes. An efficient tabu search algorithm has been developed to ensure quick decision support for the planners. The solutions generated by the tabu search heuristic are compared with those produced by a previously published multi-start local search heuristic. Computational results show that the tabu search heuristic yields optimal or near-optimal solutions to real-life instances within reasonable time. For large and tigthly constrained cases, the tabu search heuristic provides much better solutions than the multi-start local search heuristic. A version of the tabu search heuristic will be integrated as an improved solver in a prototype decision support system used by several shipping companies.
Acknowledgements
This research was carried out with financial support from the INSUMAR, OPTIMAR and DESIMAL projects, funded by the Research Council of Norway and from the Canadian Natural Engineering Research Council under Grant 39682-05. This support is gratefully acknowledged. We are also grateful to the shipping companies that provided real data for the test cases used in the computational study. Thanks are due to two referees for their valuable comments.