Ant colony optimisation with random selection for block transportation scheduling with heterogeneous transporters in a shipyard

Abstract

This paper considers a scheduling problem of heterogeneous transporters for pickup and delivery blocks in a shipyard assuming a static environment where all transportation requirements for blocks are predetermined. In the block transportation scheduling problem, the important issue is to determine which transporter delivers the block from one plant to the other plant and when, in order to minimise total logistic times. Therefore, the objective of the problem is to simultaneously determine the allocation policy of blocks and the sequence policy of transporters to minimise the weighted sum of empty transporter travel times, delay times, and tardy times. A mathematical model for the optimal solution is derived and an ant colony optimisation algorithm with random selection (ACO_RS) is proposed. To demonstrate the performance of ACO_RS, computational experiments are implemented in comparing the solution with the optimal solutions obtained by CPLEX in small-sized problems and the solutions obtained by conventional ACO in large-sized problems.

Keywords:

• block transportation scheduling
• shipyard
• ant-colony optimisation