Stochastic optimization model for ship inspection planning under uncertainty in maritime transportation

1.   Introduction

Maritime transportation is the backbone of globalized trade and the manufacturing supply chain ^[1,2,3,4], as more than 80% of world merchandise trade by volume is carried by sea, as reported by the United Nations Conference on Trade and Development ^[5]. Large shipping volumes also render substantial and diverse navigation, safety and marine environmental protection concerns to the high seas, territorial water, and ports and terminals ^[6,7,8]. According to the International Maritime Organization (IMO), the best way of improving safety at sea is developing international regulations that should be followed by all shipping nations ^[9,10]. In recent years, environmental sustainability issues in shipping and port activities have become a major policy concern all over the world ^[11,12,13]. Several mandatory and voluntary regulations are imposed by the IMO ^[14] as well as local governments ^[8,15,16]. If a ship's conditions, crew or operations are substantially below the standards required by these regulations, the ship is deemed a substandard ship ^[17]. A ship's flag state is the nationality or tribe a ship belongs to and under whose laws the ship is plying in international waters ^[18,19]. Therefore, the ship's flag state is considered the first line of defense against substandard shipping. However, the nature of international shipping leads to the fact that ships may not frequently visit ports that belong to their flag states thus heavily weakening the power of ship flag states in catching substandard ships. As a complement of flag state control, port state control (PSC) is implemented on a regional level, where the port authorities in a certain region are rendered the ability to inspect foreign ships visiting their ports to ensure that they will not cause danger and pollution to their waters.

Before carrying out one day's PSC inspections at a port, the first thing for the port authority to do is to select those ships with the highest risks for inspection among all the foreign visiting ships. For example, at the Hong Kong port, within the Tokyo Memorandum of Understanding (MoU), a ship risk profile (SRP) under the new inspection regime (NIR) is adopted for high-risk ship selection ^[20]. Then, each of the selected ships will be inspected by one available ship inspector at the port state, who is also called a PSC officer (PSCO). A selected ship will only be inspected once during this port visit, and one PSCO can inspect several ships per working day. During the onboard inspection, a condition found that does not comply with relevant conventions or regulations is recorded as a deficiency. If one or more very severe deficiencies are found, an intervention action called detention can be taken by the port state to prevent the ship from sailing and causing potential danger and pollution to their waters. As port inspection resources (mainly refering to the available PSCOs) are quite limited, not all visiting ships can be inspected during the normal working period per working day (which is usually 8 hours) of PSCOs ^[21]. Overtime pay should be made to a PSCO if he/she cannot finish the workload assigned within the normal working period. Meanwhile, ship noncompliance found in inspections can reduce risks and pollution, and thus can be seen as a reward for PSC inspection, where such noncompliance can be represented by ship deficiencies detected. Therefore, the port state needs to make a trade-off between whether to inspect foreign visiting ships and the workload assigned to available PSCOs, so as to maximize the total inspection benefits (i.e., the total number of deficiencies identified) while minimizing the PSCOs' overtime pay.

There have been some studies on the ship risk prediction problem by adopting empirical analyses ^[22] and machine learning methods ^[23,24], which treat this problem as a classification task about whether a ship should be inspected. Recently, some pioneer studies consider combining the ship risk prediction results with PSCO assignment optimization models so as to rationalize the decision of PSC inspection ^[25]. However, these studies cannot meet the real world ship inspection decision requirements described above for two main reasons: First, they try to optimize ship selection and PSCO assignment decisions with fixed inspection resources without considering the flexible workload assignment and the corresponding inspection cost. Second, most studies follow a predict-then-optimize framework, where the predicted parameters in the following optimization model are treated in a deterministic manner, and the optimization results largely depend on the quality of the prediction models. This study tries to bridge these gaps by integrating prediction with optimization to address the above decision-making problem while considering the trade-off between more detected deficiencies and less overtime pay.

A $k$ nearest neighbor (kNN) model using real PSC inspection records at the Hong Kong port is first adopted to predict the number of ship deficiencies. Then, three optimization models are established to maximize the total reward from deficiencies identified while minimizing PSCOs' total overtime pay. To be more specific, in the first model, we develop a deterministic optimization model based on the predicted mean of each unknown parameter (i.e., ship deficiency). In the other two models, unknown parameters in the optimization models are modeled as random variables, where the predictive prescription method and the global prescriptive analysis method are adopted to estimate the distributions of the unknown parameters, respectively. We use the Hong Kong port as a case study to construct the kNN model and evaluate the three optimization models. The results show that a kNN model with $k = 3$ can well predict the number of ship deficiencies. Moreover, the optimization model with the predictive prescription method performs best among the three models, and it is suitable for problems where the objective function has a nonlinear term of the unknown parameters.

2.   Literature review

According to a review of academic literature conducted by ^[26], existing studies on PSC can be roughly divided into four categories: factors influencing PSC inspection results, ship selection scheme for inspection, effects of PSC inspection, and suggestions to improve PSC inspection. This research lies in the area of ship selection scheme for inspection, and thus we first review the existing literature within this category.

Historical inspection records are the main data source used to predict ship risk in the near future or ship inspection performance with the current PSC inspection practice. Based on such historical inspection records as well as external data sources on ship specifications (e.g., ship characteristics and information on ship management parties), empirical analysis is conducted for ship condition prediction. For example, ship risk dimensions are quantified by considering the combination of past incidents and detention information to target high-risk ships. Five combined methods were proposed to realize the combined ship classification methods, which are expected to have predictive power for incidents ^[22]. Furthermore, the authors quantified risk areas, including collisions, drift groundings, powered grounding, engine-related failures, fire and explosion, hull-related failures, pollution and loss of life, on different ship types such as oil tanker, dry bulk, chemical tanker, general cargo and container ships. The risk areas can be used to guide the assignment of ship inspection priority in PSC inspections ^[27]. In addition to empirical analyses, machine learning models are also popular for ship risk prediction. Widely used machine learning models include support vector machine, which can be found in ^[24], ^[23] and ^[28] for ship detention prediction; Bayesian network, which can be found in ^[29] for ship detention probability prediction of bulk carriers and ^[30] for ship deficiency number prediction; and tree-based model. Multi-target regression random forests were developed to predict ship deficiency conditions in ^[25]. An XGBoost model incorporating shipping domain knowledge was proposed in ^[31] for ship deficiency number prediction. A balanced random forest model was used in ^[32] for ship detention prediction, considering the fact that the un-detained ships highly outnumber detained ships in PSC.

In more recent years, an emerging research stream in PSC is to rationally allocate inspection resources at a port state for ship inspection, and the inspection resources here mainly refer to PSCOs. One typical example is ^[25], which aimed to match the expertise of PSCOs with the ships assigned to them, so as to maximize the inspection benefits represented by the total number of deficiencies that can be identified. To achieve the objective, three ship condition prediction models were developed, and the prediction results were combined with PSCO assignment models. Prediction targets in the first prediction model were natural, the numbers of deficiencies under each deficiency category, and the training target was to minimize the prediction error. Prediction targets of the second prediction model were parameters of the decision variables in the following PSCO assignment model. Prediction targets of the third prediction model were also the number of deficiencies under each deficiency category, but the training target was motivated by the structure of the PSCO assignment model to optimize the decision performance. ^[31] developed an XGBoost model for ship deficiency prediction by considering shipping domain knowledge regarding ship flag performance, recognized organization performance and company performance along with several PSCO scheduling models considering inspection templates and un-dominated inspection templates to maximize the inspection benefit evaluated by the total number of deficiencies. Both studies mentioned above aimed to allocate limited inspection resources at a port authority to maximize inspection benefits. There is another working paper aiming to design inspection resource allocation schemes for ship maintenance for ship operators while considering three types of costs: inspection cost, repair cost and risk cost. A smart predict-then-optimize (SPO) method using an ensemble of SPO trees was developed to incorporate ship maintenance decisions into the prediction of ship detention probability ^[33].

The above review shows that when evaluating inspection benefits for port authorities, the benefits only consider ship deficiency number detected, while the costs of conducting an inspection, e.g., the total payment or overtime pay to PSCOs, have not been considered yet. In practice, there is a trade-off between inspecting more ships and reducing inspection costs, and thus taking both factors into account can no doubt increase model applicability. To bridge this gap, optimization models considering more realistic factors, including the practical inspection period onboard, PSCOs' overtime pay, and reward for identifying a ship deficiency, are proposed in this study. Furthermore, in all the ship inspection resource allocation models discussed so far, the optimization models are treated in a deterministic manner where the unknown parameters are the predicted means conditional on the auxiliary data, i.e., historical inspection records and ship specifications. However, due to the fact that the data volume is limited, there might be some missing features, and there are inevitable errors in the data collected. Machine learning models developed for ship condition prediction are not perfect, indicating that the predicted conditional mean is not equal to the actual conditional mean value. To address this issue, this study adopts a kNN model for ship deficiency number prediction and considers data uncertainties by turning the original optimization model into a predictive prescription model based on kNN and a global prescriptive analysis model considering training error based on kNN.

3.   Problem description

According to the working process of the PSC authorities, on the morning of each working day, there is a set of foreign visiting ships (denoted by $S$) coming to the port state that are candidates to be inspected. There is a set of PSCOs (denoted by $P$) who will be assigned to inspect ships with higher risk. Every detected deficiency on a ship will yield a reward (denoted by $c$). Practically, the inspection time for a ship $s \in S$ is considered to be strongly related to its deficiency number $n_s$, because whenever a deficiency, especially a detainable deficiency, is discovered, the PSCO has to take a certain amount of time to provide convincing evidence, as otherwise, it may be appealed by the ship captain or shipping company ^[34]. Furthermore, the PSCO needs to communicate with the ship captain and crew after detecting a deficiency. Moreover, other categories of deficiencies related to the detected one might also be checked. Therefore, we assume the ship inspection time is linear in its number of deficiencies and can be written as $a+ b\cdot n_s$, where $a$ and $b$ are empirical values gained from historical data. Notably, we can also adopt a more complex function of ship inspection time and deficiency number by taking factors such as ship type and size into account. However, since these factors are known characters and are the same for one ship in all optimization models, they would have similar influences on our models and would not affect the relative performances of the models. So, we do not consider them to quantify ship inspection time in this study for simplicity. The total time initially assigned to each PSCO $p \in P$ for ship inspection on each working day is $t_p$. We note that if a PSCO spends more time than $t_p$ on ship inspection work, there will be overtime pay. Moreover, we assume that the overtime pay is a piecewise linear function of overtime working hours, i.e., 300 HKD/h is required for overtime within 1 hour, 400 HKD/h is for 1–2 hours, and 600 HKD/h is for more than 2 hours. Our model can also accommodate other forms of overtime payment function by modifying the corresponding constraints. The main purpose of the PSC authorities is to maximize the inspection benefits, which consist of the reward for detected deficiencies and the negative inspection costs. Since these two objectives can be converted to the same measurement, i.e., cost, we adopt a parameter $\lambda$ to transform them into a single objective which aims to minimize the total costs by the weighting method. To summarize, our decision problem is to rationally assign the available PSCOs to the selected ships so as to achieve a trade-off between the total reward for identified deficiencies and the total payment for overtime work of PSCOs.

The detailed mathematical notations used in our problem are provided below.

$\bullet$ Known parameters:

$S$: the set of candidate ships for inspection, indexed by $s$.

$P$: the set of PSCOs to be assigned for ship inspection, indexed by $p$.

$t_p$: the total time initially assigned to PSCO $p$ for ship inspection time on each working day.

$a$: the basic inspection time of a ship.

$b$: the inspection time increment with each deficiency of a ship.

$c$: the reward for each detected deficiency.

$\lambda$: a known parameter used to normalize the objective, which lies in $(0, 1)$.

$\bullet$ Unknown parameters:

$n_s$: the number of deficiencies of ship $s$.

$\bullet$ Decision variables:

$z_{ps}$: a binary variable that equals 1 if PSCO $p$ is assigned to inspect ship $s$, or 0 otherwise.

$x_p$: a continuous variable that indicates the total working time of PSCO $p$.

$y_p$: a continuous variable that indicates the overtime pay of PSCO $p$.

The model can be written as follows:

Objective (3.1a) maximizes the inspection benefit, which consists of the reward for identifying the (estimated) deficiencies of the ships inspected and the negative overtime pay to PSCOs. Constraint (3.1b) guarantees that each ship is inspected by no more than one PSCO. Constraint (3.1c) presents the total working time of each PSCO. Constraints (3.1d)–(3.1f) specify the overtime pay of each PSCO. Constraints (3.1g)–(3.1h) define the domains of variables.

4.   Prediction and optimization approaches

In our prediction and optimization approaches, a prediction model is first developed to predict the key unknown parameters (i.e., the number of deficiencies of each ship) in the optimization model by leveraging auxiliary data (i.e., PSC inspection records published by MoUs). Based on the prediction model, three optimization models are then constructed to generate decisions. We note that the overtime pay in the objective is nonlinear with the ship deficiency numbers, which are the unknown parameters predicted by the prediction model.

4.1.   Ship deficiency number prediction by kNN

A couple of machine learning approaches, such as kNN, decision trees, and random forests, can be used in this context to estimate the distribution of the deficiency numbers of ships ^[25,31,32]. In this study, we adopt a kNN model for ship deficiency number prediction because it is one of the most intuitive and easy-to-implement machine learning methods for prediction tasks, and it can be easily understood and applied to practical operations management planning in the maritime industry. Moreover, kNN is suitable to generate neighborhood points and to predict the distribution of deficiency numbers in the predictive prescriptive methods ^[35,36], which will be discussed later. Therefore, we develop a kNN model to predict the number of deficiencies for each ship based on historical records and ship-related features. The data used to predict the deficiency number are introduced in Section 4.1.1. Then, the detailed kNN model construction process is presented in Section 4.1.2.

4.1.1.   Data

The data set used in this study is derived from the Asia Pacific Computerized Information System (APCIS)^* supported by the Tokyo MoU and the World Register of Ships (WRS) database^†. Specifically, APCIS provides detailed inspection records at the Hong Kong port and PSC-related information of the inspected ships within the Tokyo MoU, while WRS provides comprehensive ship-related features: ship construction, engine, dimensions, registration, ownership, fixtures, class, etc. We searched the most frequently used features in current literature from WRS and combined it with the APCIS using ship IMO number to form a unified data set, which contains a total of 4,404 inspection records at the Hong Kong port from 2015 to 2019 with the corresponding ship specification of each record. Based on this data set, 14 features (denoted by $\mathit{\boldsymbol{w}}$), which are considered to have high correlations with ship deficiency numbers in current literature ^{[25,26,31,32]}, were used as the input of the kNN model, and the output is the deficiency number of each ship denoted by $n$. The selected 14 features include ship-related features (e.g., ship age, gross tonnage (GT), length, depth, beam, and type), PSC-related features (e.g., flag performance, recognized organization (RO) performance and company performance over the past three years reported by the Tokyo MoU) and ship historical inspection features (e.g., period since the last inspection, deficiency number of the last inspection, total detentions in all previous inspections, flag change times and casualties in last five years). Then, we randomize the whole data set and divide it into the training set, validation set and test set, containing 60%, 20% and 20% of all records i.e., (2643,881, and 881 records), respectively. Since there are situations where ship deficiencies are extremely large (e.g., 63, 77 and 87), 0.5% records in the training data with the largest ship deficiencies were filtered in order to avoid the influence of outliers on the model.

^*https://apcis.tmou.org/

^†http://www.tokyo-mou.org/inspections_detentions/psc_database.php

To be specific, we list the detailed interpretation and statistical information of the 14 features on the whole data set in Table 1. Since there are a few incomplete records, such as ships with undefined flag performance, RO performance or company performance, empty ship length or depth values, and no last inspection record, we fill the missing values by using the statistical value (e.g., mean, median, and mode) of the corresponding feature in the training set, as is shown in the column Fill-in value for missing values. Moreover, as required by the Tokyo MoU, from the best to the worst, the states of ship flag performance are "White, Grey" and "Black, " and the states of ship RO and company performances are "High, " "Medium, " "Low, " and "Very low, " respectively.

4.1.2.   Introduction and construction of kNN

kNN is a powerful non-parametric supervised learning method which was first proposed by ^[40]. The only hyperparameter in kNN is $k$, which is the cardinality of the neighborhood considered by the algorithm. As one of the most commonly used machine learning methods, it is widely applied to classification and regression tasks. In this article, we adopt kNN to predict the deficiency number of a ship, which is calculated by the average values of its $k$ nearest neighbors. Moreover, Euclidean distance is used as the distance metric to find the $k$ nearest neighbors.

Specifically, the training data set contains $N$ inspection records and is denoted by $(\mathit{\boldsymbol{w}}_1, n_1), (\mathit{\boldsymbol{w}}_2$$, n_2), \ldots, (\mathit{\boldsymbol{w}}_N, n_N)$, where $\mathit{\boldsymbol{w}}_i$, $i \in 1, \ldots, N$, is the input feature vector of a ship, and $n_i$ is the output value, which is its deficiency number recorded in data record $i$. The working process of kNN is relatively simple, because the training phase is just to memorize the training set. Then, given a new test sample with feature vector $\mathit{\boldsymbol{w}}_0$, its predicted deficiency number $\hat{n}_0$ is obtained by looking for the $k$ training samples $\mathit{\boldsymbol{w}}_i$ that are the closest to $\mathit{\boldsymbol{w}}_0$ under the defined distance metric (i.e., Euclidean distance) and then averaging their associated targets $n_i$. Mathematically, the prediction function of the target of a new sample $\mathit{\boldsymbol{w}}_0$ using kNN can be presented as follows:

where $\mathcal{N}_{k}(\mathit{\boldsymbol{w}}_0) = \{i = 1, \ldots, N:\sum_{j = 1}^{N} \mathbb{I}\left[\left\|\mathit{\boldsymbol{w}}_0-\mathit{\boldsymbol{w}}_{i}\right\| \geq\left\|\mathit{\boldsymbol{w}}_0-\mathit{\boldsymbol{w}}_{j}\right\|\right] \leq k\}$ is the neighborhood set of $k$ data points that are the closest to $\mathit{\boldsymbol{w}}_0$, and $N$ is the number of inspection records in the training set. In addition to being used for ship deficiency number prediction, kNN is also used in prescriptive methods to derive weights in the objective function, which will be discussed later.

The prediction model is validated using two common metrics for regression problems in machine learning: mean squared error (MSE) and mean absolute error (MAE). Given a total of $J$ samples in the data set, the real output $n_j$ and the predicted output $\hat{n}_j$ for a sample $j \in 1, \ldots, J$, the definitions of MSE and MAE are as follows:

4.2.   Optimization models

4.2.1.   Deterministic model (M1)

In M1, we treat each unknown parameter $n_s$ in the optimization model as a deterministic value (i.e., the predicted value $\hat{n}_s$). To be specific, we assume that the distribution of $n_s$ can be written as

Therefore, the optimization model can be reformulated as

4.2.2.   Predictive prescription model (M2)

In M2, the unknown parameters are modeled as random variables. We adopt the predictive prescription method proposed by ^[35] to capture the uncertainty, where weight functions of unknown parameters are generated in a data-driven manner based on kNN. First, the distribution of deficiency number $n_s$ for ship $s$ with feature vector $\mathit{\boldsymbol{w}}_s$ can be written as

Then, the vector of ship deficiency number for all ships denoted by $\boldsymbol{n}$ would have $k^{|S|}$ possible values, which is an exponential function of $S$. Thus, we adopt the sample average approximation (SAA) approach and randomly select a set of scenarios $U$ from the Cartesian product of the neighborhood set of every ship $\{\mathcal{N}_{k}(\mathit{\boldsymbol{w}}_0)\times\cdots \times \mathcal{N}_{k}(\mathit{\boldsymbol{w}}_s) \}$ to approximate the distribution of $\mathit{\boldsymbol{n}}$. Mathematically, the distribution of $\mathit{\boldsymbol{n}}$ can be written as follows:

where the value of $\mathit{\boldsymbol{n}}$ under scenario $u\in U$ is $\mathit{\boldsymbol{n}}^u$. The decision problem of interest can be reformulated as the following stochastic optimization problem with the above distribution (4.9) of its parameters:

Note that we employ the predicted deficiency number of each ship $\hat{n}_s$ in the first term in the objective function since it provides an exact approximation, as is proved below.

$\mathit{\boldsymbol{Proof:}}$

Since the first term of the objective is linear, we have

If the number of selected scenarios is large enough, and set $U$ is the Cartesian product of the neighborhood set of every ship, then

Therefore, $\sum_{p\in P}\sum_{s\in S} \hat{n}_s z_{ps}$ is an exact approximation of the first term in the objective.

4.2.3.   Global prescriptive analysis model (M3)

A global method to estimate the distributions of the unknown parameters relies on the prediction error of each record in the training set. To be specific, the deficiency number of each ship can be first predicted by kNN and then revised by the prediction error in the training set. Therefore, given the auxiliary data $\mathit{\boldsymbol{w}}_s$ and its predicted output $\hat{n}_s$, the distribution of $n_s$ taking a total of $N$ possible values can be approximated by

Then, the total number of scenarios for $\mathit{\boldsymbol{n}}$ would be $N^{|S|}$. Similar to (4.4), we randomly select a small subset $U$ of all possible scenarios. We denote $\mathit{\boldsymbol{e}}^u$ as the error between the predicted and actual parameter values under scenario $u\in U$. Thus, the distribution function of $\boldsymbol{n}$ can be written as follows:

Based on this distribution function, the stochastic optimization model can be written as

subject to constraints (4.10b)–(4.10h).

5.   Numerical experiment

In this section, we use the Hong Kong port as a case study to construct the kNN model and evaluate the three optimization models.

5.1.   Experiment settings

For the kNN model, the only hyperparameter used to control the learning process is $k$. Theoretically, when the value of $k$ is smaller, the training error will decrease, but the model is more complex, and the generalization ability might be weakened. Thus, $k$ is empirically set in the range $[1, 8]$ with an interval of 1, from which the optimal $k$ is chosen by considering the two metrics (i.e., MSE and MAE) on the validation set.

The values of other parameters in the optimization models are set according to the real situation at the Hong Kong port and are presented in Table 2. We assume that 20 foreign ships come to the port in one day, and 4 PSCOs are available for inspection. The 20 ships that are candidates for inspection are randomly selected from the test set, and the number of deficiencies of them is first predicted by the kNN model. The basic inspection time for a ship is set as 1 hour, and the inspection time will increase by 0.25 hours whenever there is one more deficiency detected. Moreover, each PSCO is assumed to be the same, and the initially assigned time to PSCO $p$ for inspecting the ships $t_p$ is equally set to 8 hours. In addition, in order to get the reward for each detected deficiency, we first calculate a PSCO's hourly wage by dividing the average monthly salary of a PSCO (i.e., 85,870 HKD^‡) by the working hours in a month (i.e., 176 hours under the assumption that a PSCO works 22 days a month except weekends and works 8 hours a day), and the result is 488 HKD/h. Then, we can get the average time spent for inspecting one deficiency as $(1+0.25\times4.8)/4.8 = 0.46$ h, which is calculated by the average deficiency number of one inspection and the linear function of the inspection time. Thus, the cost of inspecting each deficiency is $488\times 0.46 =$ 225 HKD, and the reward for each detected deficiency (i.e., $c$) is set to twice of it as 450 HKD. Furthermore, we set the values of $|U|$ as 300,500, and 1000, respectively, so as to explore the impacts of the selected scenarios in M2 and M3. To balance the reward for deficiency detection and PSCOs' overtime pay, parameter $\lambda$ is set to 0.3, 0.5 and 0.8, respectively.

^‡https://www.mardep.gov.hk/theme/maritime_industry/en/marine_officer.html

The experiments are performed on a computer with an Intel Core i5 CPU and 8 GB memory under the Mac operating system. The models are implemented in the Python programming language using Gurobi 9.1.2 as the solver.

5.2.   Performance of kNN

Following the procedure introduced in Section 4.1.2, we developed kNN models with $k$ varying from 1 to 8 and recorded the MSE and MAE on the validation set. The results are shown in Table 3. We can find the optimal $k$ is 3, as it leads to the minimal MSE (34.65) and MAE (3.35). The computation times of different $k$ values are similar and are below 0.4 seconds.

For comparison, we also develop a support vector regression (SVR) model, which is suitable for nonlinear regression problems and is extended from a support vector machine for classification problems ^[41]. The kernel function is the most significant factor that affects the performance of the SVR. Therefore, we tune the kernel functions by choosing one from radial basis function ('rbf'), polynomial ('poly') and sigmoid, respectively, which are popular kernel functions in SVM ^[42]. The other hyperparameters are set as the default values in sklearn for consistency. The SVR models are tested on the same data sets as kNN, and the prediction performances on the training and validation set are shown in Table 4. We can observe that 'rbf' performs best among the three kernel functions, with lower MSE and MAE on both training and validation sets. Therefore, we choose 'rbf' as the kernel function of SVR. Moreover, we can also observe that the MSE and MAE of the SVR model with kernel function 'rbf' on the validation set are still larger than those of the kNN model with $k = 3$. In addition, the computation times of both the kNN and SVR models are small.

Given the chosen $k = 3$ of kNN and kernel function 'rbf' of SVR, we divided the whole test set into 10 groups and ran each group to record its MSE and MAE. The minimum, maximum, mean and variance of MSE and MAE on the 10 groups of test sets are shown in Table 5. It can be seen that the mean values of MSE and MAE of kNN on the test sets are 30.42 and 3.32, respectively, which are slightly less than those on the validation set. By comparing the results of the two models, we can find that all measurements of kNN are better than SVR with respect to MSE. For MAE, the mean and minimal values of kNN are slightly larger than those of SVR, while the maximal value and standard derivation of kNN are smaller than those of SVR, which indicates that kNN is more stable for all test sets. To summarize, the kNN model with $k = 3$ is effective and stable in predicting the deficiency number of a ship. We note that more complex models such as tree-based models can be built to predict the ship deficiency number and may perform better on the data sets by carefully adjusting model hyperparameters. However, these models with various intricate hyperparameters are not as straightforward as the kNN model and cannot be easily understood by the port officials. Consequently, they may be reluctant to use these models.

5.3.   Performance of the three optimization models

Based on the kNN prediction model, we compared the performances of the three optimization models introduced in Section 4.2. We first randomly selected 10 groups of instances, each of which consists of 20 records from the test set. Then, we tested the three optimization models on these instances in turn and set the maximal computation time limit for each instance as 600 seconds. In addition, to avoid an unreasonable number (i.e., negative or too large of a number) of ship deficiencies, we set a range $[0, \bar{n}_s+3\times \sigma(n_s)]$ for the possible value of $n_s$ in M3, where $\bar{n}_s$ and $\sigma(n_s)$ are the mean and standard deviation values of the ship deficiency number in the training set, respectively. Specifically, if the calculated number of ship deficiencies is larger than the upper bound, which is a statistical measurement commonly used when the data set is large enough, we set it as the upper bound; similarly, if it is smaller than zero, we set it as zero, as ship deficiency number cannot be negative. The comparison results are shown in Table 6. Notably, the optimal decisions can be made if the deficiency number of each ship is predicted accurately in advance (denoted by "perfect-forecast policy"). However, this is an ideal situation that cannot be achieved in practice. We use the objective of the perfect-forecast policy as a lower bound in theory to compare the performances of the three proposed optimization models.

From Table 6, we can observe that much less time is required to solve M1 compared to that of M2 and M3 in all cases. The computation time of M2 is also much smaller than M3 under the same parameter settings. Moreover, the average computation times of both M2 and M3 would increase greatly as expected as the number of selected scenarios $|U|$ increases. Most instances in M2 and M3 would reach the time limit (i.e., 600 seconds), when $|U|$ increased to 200 and 300, respectively. The standard deviation of computation time for different models also vary a lot. While the standard deviation of computation time in M1 is quite small, it is much larger in M2 and M3. This is because more time is required to solve M2 and M3, and small changes in parameters can greatly affect the computation time. When the number of selected scenarios $|U|$ increases, there is also a rapid upward trend in the standard deviation of computation time in M2 and M3. Particularly, in M2 and M3, when the value of $|U|$ increases to a certain level that the solution times of all instances reach the time limit, the standard deviation of computation time is about zero. In addition, there is no obvious relationship between the value of $\lambda$ and the computation time.

Taking the perfect-forecast policy as a benchmark, we can further compare the performances of the three models under different parameter settings as shown in the last row of Table 6. When the value of $|U|$ is fixed, and the value of $\lambda$ increases, the performances of the three models improve, as the gaps between the objectives and the optimal policies drop from nearly 20% to about 1%. This verifies our intuition that the larger the coefficient of the linear term of deficiency number is, the better the results the models can provide. However, there is no distinct downtrend of the gaps with the increasing value of $|U|$ as expected. Two factors may contribute to this result: First, although the value of $|U|$ increases, the sampling scenarios are still very small compared to the possible values of ship deficiency numbers, which would reach $k^{|S|}$ or $N^{|S|}$; second, too many sampling scenarios would increase the computational difficulty of the model and may lead to a sub-optimal solution within the limited time. In addition, M2 outperforms M1 in most cases (except when $\lambda = 0.5$ and $|U| = 300$) and is also much better than M3 (except when $\lambda = 0.8$ and $|U| = 200$). Especially, when the value of $\lambda$ is 0.8, the average gap between the perfect-forecast policy and M2 is slightly smaller than that of M1. However, the average gap between the perfect-forecast policy and M2 is much smaller than that of M1 when the value of $\lambda$ decreases to 0.3, as the proportion of the nonlinear term of uncertain parameters is larger. Meanwhile, M3 always fails to provide a satisfactory result compared to M1 and M2, which may be because of the limited sampling number compared to the extremely large number of possible scenarios in M3.

Moreover, $\lambda$ is a parameter used to achieve a trade-off between the reward for detected deficiency number and the cost of overtime pay. When $\lambda$ increases from 0.3 to 0.8, the total number of detected deficiencies shows an increasing trend, as suggested by the optimal solution, since the weight of reward for each detected deficiency becomes larger. Then, a longer time is also needed to detect such deficiencies, and thus the overtime pay of PSCOs for ship inspection is also increased. Overall, there is a downward trend of the objective value, i.e., the total ship inspection cost, as $\lambda$ increases, because the weight of reward for detecting the ship deficiencies increases.

To summarize, the average model computation times and their standard deviation increase in the order of M1, M2 and M3. In addition, the model computation times of M2 and M3 are sensitive to the value of $|U|$, because it increases the number of constraints in the optimization model. In almost all cases, M2 outperforms M1 and M3 and has smaller gaps between the objective achieved and the perfect-forecast policy. Moreover, the gaps between M2/M3 and the perfect-forecast policy could decrease if there is a larger number of selected scenarios and no computation time limitation. We can therefore conclude that M2 is the most effective, stable and flexible among the three models. This reveals the benefits of a predictive prescription approach toward a model where the objective has a nonlinear term of the unknown parameters (the deficiency numbers of ships).

6.   Conclusions

Maritime safety and marine environment protection are two main topics in maritime study that have been gaining wide attention over the world for many years, which can be seen from the increasing number of and more and more stringent regulations and conventions implemented. PSC inspection is an effective safety net to catch substandard ships that do not comply with the requirements in the regulations and conventions. To improve the efficiency of PSC inspection, higher-risk ship selection and PSCO resources assignment are addressed as essential problems. Whereas previous studies model this problem in a deterministic manner to maximize the reward for detected ship deficiencies based on the prediction model of ship deficiency number, this study adopts a more comprehensive objective, which considers not only the benefits of identified deficiencies, but also the cost of ship inspection. Based on this target, a deterministic model (M1), and two stochastic models (i.e., M2, based on the predictive prescription method, and M3, based on the global prescriptive analysis method) were established using a kNN prediction model as the predictor of ship deficiency number. Extensive numerical experiments were conducted using inspection data at the Hong Kong port to evaluate the performances of the three models and study the impacts of significant parameters.

To be specific, we tested the performance of the kNN model with different values of $k$, from which the optimal $k = 3$ was chosen by minimizing two metrics for regression (i.e., MSE and MAE) on the validation set. Based on this kNN model, we compared the average performances of the three optimization models with ten groups of randomly generated instances from the test sets. The results show that M2 stands out by the minimal average gap from the perfect-forecast policy and the relatively small average total computation time. Meanwhile, the results also show that M2 is particularly suitable for the problem, where the objective is nonlinear with the predicted uncertain parameters. By contrast, M1, which is widely used in current studies, bears larger optimality gaps than M2 in almost all cases, although it has the least average total computation time among the three models. In addition, M3 cannot perform well in those cases, which may be due to the use of all training data errors in estimating the distribution of the number of ship deficiencies, the issue of over-fitting to the predictions and the limit of computation time. However, there is still an improvement possibility for M3 if we design more suitable filter methods for the errors used to estimate the distribution of unknown parameters. Moreover, by conducting sensitivity analysis on important parameters, we can observe that there is a falling trend in the average gap between the perfect-forecast policy as the value of $\lambda$ increases in all of the three models, and there is an increase in the average total computation time for M2 and M3 when the value of $|U|$ becomes larger.

The main contributions of this paper lie in the following aspects:

$1)$ Taking an important policy in the maritime industry into account, we propose prediction and optimization approaches which consider the trade-off between detecting more deficiencies and reducing overtime workload. This helps port states to identify high-risk ships effectively and assign the PSCOs more flexibly. Therefore, the main objectives of PSC to eliminate substandard shipping and safeguard the sea can be enhanced.

$2)$ Theoretically, we implement both a predictive prescription model and a global prescriptive analysis model based on kNN for ship deficiency number prediction and inspection resource assignment. To the best of our knowledge, this study is the pioneer in integrating prediction with optimization in the ship inspection application and can be easily understood and adopted by port authorities for practical ship inspection planning.

$3)$ In the numerical tests, we conduct extensive numerical experiments using inspection data at the Hong Kong port to compare M1, based on the traditional deterministic model, with M2, based on the predictive prescription method, and M3, based on the global prescriptive analysis method. The experiment reveals the effectiveness of a predictive prescription approach towards ship inspection planning where the reward for ship deficiencies detected and cost of PSCOs' overtime pay are taken into account.

However, there are also some limitations of our work. First, to achieve a trade-off between detecting more deficiencies and reducing inspection cost, we only use a weighting method to unify these two objectives without developing other models. Second, the performance of the global prescriptive analysis model M3 cannot perform well as expected, since the predicted distribution function of ship deficiency number is revised by the prediction errors on the whole training set. For example, if the prediction error of one training sample is too large, revising the prediction result with this error may result in an unreasonable predicted ship deficiency number. Therefore, future research could be conducted from the following aspects: From the modeling perspective, we could adopt a dual-objective optimization model or a two-stage optimization model to achieve a trade-off between the total reward for deficiencies identified and the total overtime pay; from the methodological point of view, more scenario selection strategies could be adopted to predict the distribution function of M3 and thus improve the effectiveness of the model.

Conflict of interest

The authors declare there are no conflicts of interest.