It is well known that decision support systems (DSSs) usually only solve models that simplify and approximate the real problem. The planners might therefore be more interested in a set of diverse high quality solutions to 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 assigned 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.