A combined ship scheduling and allocation problem

We present a bulk ship scheduling problem that is a combined multi-ship pic kup and delivery problem with time windows (m-PDPTW) and multi-allocation p roblem. In contrast to other ship scheduling problems found in the literatu re, each ship in the fleet is equipped with a flexible cargo hold that can be partitioned into several smaller holds in a given number of ways. Theref ore, multiple products can be carried simultaneously by the same ship. The scheduling of the ships constitutes the m-PBPTW, while the partition of the ships' flexible cargo holds and the allocation of cargoes to the smaller h olds make the multi-allocation problem. A set partitioning approach consist ing of two phases is proposed for the combined ship scheduling and allocati on problem. in the first phase, a number of candidate schedules (including allocation of cargoes to the ships. cargo holds) is generated for each ship . in the second phase, we minimise transportation costs by solving a set pa rtitioning problem where the columns are the candidate schedules generated in phase one. The computational results show that the proposed approach wor ks, and optimal solutions are obtained on several eases of a real ship plan ning problem.