Article ID: | iaor20073828 |
Country: | United Kingdom |
Volume: | 34 |
Issue: | 3 |
Start Page Number: | 900 |
End Page Number: | 917 |
Publication Date: | Mar 2007 |
Journal: | Computers and Operations Research |
Authors: | Nygreen Bjrn, Christiansen Marielle, Fagerholt Kjetil, Brnmo Geir |
Keywords: | scheduling, heuristics: local search |
We present a multi-start local search heuristic for a typical ship scheduling problem. A large number of initial solutions are generated by an insertion heuristic with random elements. The best initial solutions are improved by a local search heuristic that is split into a quick and an extended version. The quick local search is used to improve a given number of the best initial solutions. The extended local search heuristic is then used to further improve some of the best solutions found. The multi-start local search heuristic is compared with an optimization-based solution approach with respect to computation time and solution quality. The computational study shows that the multi-start local search method consistently returns optimal or near-optimal solutions to real-life instances of the ship scheduling problem within a reasonable amount of computation time.