Ship scheduling with soft time windows: An optimisation based approach

This paper considers a real ship scheduling problem that can be considered as a multi-ship pickup and delivery problem with soft time windows (m-PDPSTW). The motivation for introducing soft time windows instead of hard is that by allowing controlled time window violations for some customers, it may be possible to obtain better schedules and significant reductions in the transportation costs. To control the time window violations, inconvenience costs for servicing customers outside their time windows are imposed. An optimisation based approach based on a set partitioning formulation is proposed to solve the problem. First, all (or a number of promising) feasible routes are enumerated. Second, the various possible schedules of each route are computed as well as the corresponding operating and inconvenience costs. Finally, the schedules are given as input to a set partitioning problem. The solution method also determines the optimal speeds for the ships on the various sailing legs. The computational results show that the proposed approach works on the real ship scheduling problem. (C) 2001 Elsevier Science B.V. All rights reserved.