Abstract We introduce the integrated block relocation and fleet allocation problem with soft precedence constraints, which jointly determines the unloading sequence of items and their assignment to a heterogeneous fleet of capacity-limited vehicles. The new problem aims at maximizing the number of delivered items while minimizing violations of a given item precedence order. Items with different destinations cannot be allocated to the same vehicle. The problem finds applications in logistic operations in steel plants and container terminals, as well as in humanitarian supply operations in the context of natural or industrial disasters. We formalize the problem as a lexicographic bi-objective model, providing two compact integer linear programming formulations reflecting different modeling perspectives, two reformulations and a family of valid inequalities. The models incurring the best dual bounds are used as backbone for a Kernel Search heuristic exploiting problem-specific structural properties. Computational experiments on a benchmark derived from the block relocation literature show that the exact models solve most instances to optimality within one hour, while the heuristic provides high-quality solutions with short runtimes and near-optimal gaps, making it an effective and reproducible approach for larger instances.
Assunção et al. (Sun,) studied this question.