Prescriptive analytics for a maritime routing problem

Abstract

Port state control (PSC) serves as the final defense against substandard ships in maritime transportation. The port state control officer (PSCO) routing problem involves selecting ships for inspection and determining the inspection sequence for available PSCOs, aiming to identify the highest number of deficiencies. Port authorities face this problem daily, making decisions without prior knowledge of ship conditions. Traditionally, a predict-then-optimize framework is employed, but its machine learning (ML) models' loss function fails to account for the impact of predictions on the downstream optimization problem, potentially resulting in suboptimal decisions. We adopt a decision-focused learning framework, integrating the PSCO routing problem into the ML models' training process. However, as the PSCO routing problem is NP-hard and plugging it into the training process of ML models requires that it be solved numerous times, computational complexity and scalability present significant challenges. To address these issues, we first convert the PSCO routing problem into a compact model using undominated inspection templates, enhancing the model's solution efficiency. Next, we employ a family of surrogate loss functions based on noise-contrastive estimation (NCE) for the ML model, requiring a solution pool treating suboptimal solutions as noise samples. This pool represents a convex hull of feasible solutions, avoiding frequent reoptimizations during the ML model's training process. Through computational experiments, we compare the predictive and prescriptive qualities of both the two-stage framework and the decision-focused learning framework under varying instance sizes. Our findings suggest that accurate predictions do not guarantee good decisions; the decision-focused learning framework's performance may depend on the optimization problem size and the training dataset size; and using a solution pool containing noise samples strikes a balance between training efficiency and decision performance.