Ship routing and scheduling with persistence and distance objectives

It is well known that decision support systems (DSSs) only solve models that simplify and approximate the real problem, The planners might therefore be more interested on a set of diverse high quality solutions th choose from, than in only the optimal (or near-optimal) solution to the model as is usually produced by a DSS. In ship routing and scheduling plans are generated following a rolling horizon principle, where schedules are updated when new relevant information appears. However, the planners have often already made commitments to the customers for the next few voyages, for instance regarding arrival times and which ships that are asigned to service given cargoes. Therefore, the planners are interested in a set of high quality schedules that are close to the current (baseline) schedule in the near future, and diverse from each other in more distant time. We suggest a multi-start heuristic, including a persistence penalty function and distance measures, to produce such schedules. The method has been tested on a set of real-life problems and it provides valuable decision support flexibility for planners in shipping companies.