Second-Order Cone Relaxation Algorithms for Maritime Packing and Scheduling Problems

Integrated packing and scheduling problems arising in maritime container terminal operations lead naturally to Mixed-Integer Nonlinear Programs (MINLPs) in which discrete spatial assignments interact with continuous temporal variables and nonlinear physical constraints. These interactions often produce bilinear queueing relationships and quadratic vessel stability constraints, making the resulting optimization problems computationally challenging. In particular, standard polyhedral relaxations frequently yield weak lower bounds, limiting the effectiveness of classical spatial branch-and-bound methods. This paper proposes a lifted second-order cone (SOC) relaxation for a class of maritime packing and scheduling models. The formulation isolates the nonlinear queueing and stability structures and embeds them within a convex conic representation that preserves the geometry of the underlying quadratic constraints. We show that the resulting SOC relaxation strictly dominates the corresponding linear relaxation and provides significantly tighter lower bounds. Building on this relaxation, we develop a Conic Spatial Branch-and-Bound (Conic-sBB) algorithm that integrates the strengthened conic bounds with a hierarchical branching strategy and a deterministic primal heuristic. Computational experiments on a comprehensive benchmark set demonstrate that the proposed framework substantially improves root-node bounds and reduces search tree sizes compared with linear-relaxation-based approaches. In particular, the algorithm consistently solves medium- and large-scale instances more efficiently and proves optimality for problem sizes that remain challenging for baseline methods. The results highlight the potential of conic relaxation techniques for strengthening global optimization algorithms in integrated packing–scheduling problems.