The Multiple Checkpoint Ordering Proble...

The multiple Checkpoint Ordering Problem (mCOP) aims to find an optimal arrangement of n one-dimensional departments with given lengths such that the total weighted sum of their distances to m given checkpoints is minimized. In this paper we suggest an integer linear programming (ILP) approach and a dynamic programming (DP) algorithm, which is only exact for onecheckpoint, for solving the mCOPN. Our computational experiments show that there is no clear winner between the two methods. While the ILP approach is hardly influenced by increasing the number of checkpoints or the length of thedepartments, the performance of our DP algorithm deteriorates inboth cases.