Evaluating the trade-off between the level of customer service and transportation costs in a ship scheduling problem

In many ship scheduling problems, time windows are imposed at the loading and/ or discharging of the cargoes to be lifted. Up until now, all proposed solution methods to ship scheduling problems have treated the time window constraints as hard constraints. By transforming the time window constraints into soft constraints, some of the loading/discharging operations may be performed outside the time windows, penalized by an inconvenience cost for not meeting the time window. The motivation behind introducing soft time windows is that, by allowing controlled time window violations for some customers, it may be possible to obtain better routes and significant reductions in the transportation costs. The purpose of this paper is to evaluate the trade-off between transportation costs and the time window violations. Computational results based on data from a real ship scheduling problem are presented and used as a basis for the evaluation.