Temporal Optimization Planning for Fleet Repositioning

Fleet repositioning problems pose a high financial bur- den on shipping firms, but have received little attention in the literature, despite their high importance to the shipping industry. Fleet repositioning problems are characterized by chains of interacting activities, but state-of-the-art planning and scheduling techniques do not offer cost models that are rich enough to represent essential objectives of these problems. To this end, we introduce a novel framework called Temporal Optimization Planning (TOP). TOP uses partial order planning to build optimization models associated with the different possible activity scenarios and applies branch-and-bound with tight lower bounds to find optimal solutions efficiently. We show how key aspects of fleet repositioning can be modeled using TOP and demonstrate experimentally that our approach scales to the size of problems considered by our industrial collaborators.