Deployment of Remote Sensing Technologies for Effective Traffic Monitoring

Abstract

A rising volume of vessel traffic increases navigation density, which leads to an increasing risk of vessel collisions in navigation channels. Navigation safety issues have been widely studied with the aim of reducing such collisions. Intelligent navigation channels, which involve deploying remote-sensing radars on buoys, are an effective method of tackling vessel collisions. This paper investigates the problem of radar deployment in navigation channels, aiming to expand the radar coverage area and effectively detect vessel locations. A mixed-integer linear programming model is formulated to determine the optimal deployment of radars in navigation channels under a given budget, where radars with different coverage radii and different types of buoys are introduced. Then, sensitivity analyses involving the impacts of budgets, the coverage radii of the radars, the distance between adjacent discrete locations, and the distribution of the existing buoys on the radar deployment plan are conducted. The computational results indicate that the coverage ratio of the navigation channel can be improved by reasonably deploying the different types of radars on the existing and new buoys under a given budget.

1. Introduction

With the rapid development of trade globalization, the maritime transportation system is expanding significantly, accounting for 80% of trade and transportation in the world [1,2,3,4]. According to the US Bureau of Transportation Statistics (BTS), navigation channels, as one of the most critical forms of infrastructure in the maritime transportation system, provide access to vessels transporting freights and passengers [5]. In recent years, the increasing volume of vessel traffic volume and rising navigation density have resulted in an increasing number of vessel collision accidents in navigation channels [6]. Navigation safety issues in navigation channels have attracted extensive attention from researchers and practitioners [7,8,9,10]. To strengthen safety in navigation channels, the International Maritime Organization (IMO) has established a traffic separation scheme to prevent collisions and avoid accidents [11,12]. Meanwhile, some countries, including Singapore and China, have established their own navigation and crossing rules [13,14].

In practice, vessels typically navigate in navigation channels with the guidance of buoys. However, in the vicinity of a port, it is common for vessels to cross navigation channels. Although there are rules governing such crossings, collisions between vessels continue to occur due to human factors (such as weak awareness of the rules) and a shortage of sensor equipment (such as vessel-borne radars) [8,15]. For instance, in 2018, in the areas approaching the Port of Zhangjiagang, China, the “SY” vessel (crossing the navigation channel) did not take the initiative to avoid the “XX102” vessel sailing in the navigation channel, which resulted in a collision and a loss of 850,000 Chinese yuan [16]. In 2020, in Ningde, China, there was a collision between the “Chonghai 170” vessel and a private ship due to the lack of a vessel-borne radar, resulting in one fatality [17]. In such situations, the implementation of intelligent navigation channels, which involves deploying a certain number of radars on the buoys within the navigation channel, can efficiently curb the occurrence of collisions and improve navigation safety. In the maritime field, radar is a piece of important ship-supporting equipment, as it utilizes radio waves to detect and track the locations of vessels and transmit this information to the captains to help them maneuver their vessels [18].

Ideally, it would be beneficial to deploy as many radars as possible. With an increasing number of deployed radars, vessels can be detected more accurately. However, a significant radar deployment cost will be incurred. In addition, in navigation channels, radars can only be deployed on buoys. If there are no existing buoys in locations where radars need to be deployed, it will be necessary to build new buoys. The deployment cost of radars on new buoys is much higher than that on existing buoys, considering the construction cost of new buoys. Hence, due to limited budgets in real-world applications, determining how to deploy the radars on the existing and new buoys within navigation channels is a vital issue.

In this paper, we focus on the radar deployment problem in navigation channels involving different types of radars and different types of buoys. Specifically, we consider the fact that different types of radars have different coverage radii. The radar deployment cost varies, as deploying radars in locations without existing buoys requires the construction of buoys, thus making the deployment cost higher than in locations that already have buoys. To the best of our knowledge, the radar deployment problem in navigation channels has not received any attention in the literature. To model our proposed problem, we formulate an integer programming model. To improve the performance of our model, we transform the integer programming to a mixed-integer linear programming model. Then, we conduct numerical experiments to test the performance of our model. The contributions of this paper are twofold.

First, this paper studies radar deployment in navigation channels by considering radars with different coverage radii and buoys with different deployment costs for radars. To the best of our knowledge, it is the first paper to optimize radar deployment in navigation channels.

Second, we propose a mixed-integer linear programming model to formulate the proposed problem. The objective is to maximize the total crossing frequency by optimizing the deployment of different types of radars on existing and new buoys. We conduct sensitivity analyses concerning the impacts of the budget, the coverage radius of radars, the distance between adjacent discrete locations, and the distribution of the existing buoys.

The remainder of this study is organized as follows. Section 2 presents a review of the literature related to this paper. Section 3 elaborates on the investigated problem and provides the mathematical formulation. Section 4 summarizes the computational experiments, including the fundamental analysis and the sensitivity analyses. Finally, Section 5 concludes the paper.

2. Literature Review

This paper is first related to safety in navigation channels. During the last decades, many research efforts have been devoted to navigation safety. The related research on this issue mainly focuses on two aspects: ship collision risk assessment and vessel path planning [9,11]. For the ship collision risk assessment, a comprehensive review can be found in [19]. Therefore, we briefly discuss some representative works about ship collision risk assessment in recent years. Ref. [20] tried to estimate the vessel collision frequency of Singapore Strait, which was calculated with real-time vessel movement data, including the number of vessel conflicts and the causation. Ref. [21] proposed a quantitative risk assessment model to evaluate the risk of ship collision, including human life loss and oil pollution. Ref. [22] applied a relevance vector machine (based on Bayesian theory) to present reliable probabilistic results of ship collision risks. Ref. [23] developed a risk assessment method and real-time collision risk assessment support system to evaluate the collision risk in multi-ship environments. For vessel path planning, detailed reviews can be found in [24,25]. Here, related research is reviewed. Ref. [26] developed a data-driven method to generate efficient and safe paths for autonomous ships, in which fuel consumption was considered. Based on reinforcement learning, ref. [27] applied Q-learning to generate the routes for unmanned surface vehicles to accomplish the mission.

Another related topic is radar technique, which can be traced back to the military and commercial applications during World War II [28,29]. In the remainder of this paragraph, we mainly review the research on radars from two aspects: radar technical advance and radar target detection method. For the radar technical advance, in the early years, radar began with a static system, where radars were installed on the shore [30]. This caused the coverage areas of radars to be relatively limited since radars could not move flexibly to cover the areas. Then, portable radar systems, where radars were deployed on moving vessels, aircraft and buoys, were introduced to eliminate the drawbacks of static systems [31,32,33]. Portable radar systems significantly improved the coverage area of radars due to the mobility of radars. In recent years, the Automatic Identification System (AIS) was incorporated into maritime radars, which could provide information such as ship positions and ship speeds [34]. Here, we briefly discuss some representative works related to AIS and radar. Ref. [35] integrated the AIS data and synthetic aperture radar to estimate ship velocity. Ref. [36] utilized various sensor data (including AIS, radar, and camera) as obstacle information to develop the automatic collision avoidance system for the safe navigation of unmanned surface vehicles. Ref. [37] also used data from AIS, radar, and cameras. In their study, a data association algorithm was proposed to monitor the surroundings of ships. For the radar target detection method, the traditional method of radar detection involves enhancing the signal-to-clutter ratio through continuous improvements in time-domain, frequency-domain, and transform-domain processing [38,39]. However, these three domain-processings have some drawbacks: they assume low noise resistance and weak environmental adaptability. New radar detection methods based on deep learning theory are developed to curb the drawbacks of traditional radar detection methods [40,41]. Based on the convolutional neural network, ref. [42] proposed a multiscale ship detection method to detect arbitrarily oriented ships. Similarly, ref. [43] applied the improved R-Convolutional neural network for ship detection.

The radar deployment problem is also related to the site selection problem, which focuses on finding the optimal location from the given candidate locations under the given capital budget and finite resources. The site selection problem has attracted plenty of attention from different fields, such as agriculture [44,45,46], logistics [47,48,49], and transportation [50,51,52]. The detailed review can be referred to [53] since the investigated radar deployment problem belongs to the maritime or marine field. In the remainder of this paragraph, we will mainly discuss the site selection problem in the maritime or marine field. Some research paid attention to the wind farm site selection. For example, ref. [54] developed a site selection method based on the geographic information systems to identify the sites for floating offshore wind farms, where the available wind resources and limited maritime space were considered. Ref. [55] presented a fuzzy multiple-attribute decision-making method to find the best candidate site for offshore wind farms, taking the economic feasibility and maritime safety into consideration. The attributes included wind resources, traffic environment, wind turbine, and natural environment. Ref. [56] devised a selection framework by combining geographical information systems technology and multiple criteria decision methods to determine the maritime location for floating wind farm sites. There are also some researches focusing on marine aquaculture site selection. For example, considering the dynamic maritime environment, ref. [57] proposed a Voronoi cell-based geographic information systems model to evaluate the suitability of the aquaculture sites, which braced the integration of the current data and the new data collection. Ref. [58] developed an ordered weighted averaging method to determine the suitable sites for marine aquaculture. In their study, many factors, such as water quality and socioeconomic, were considered.

To sum up, most existing literature focused separately on the safety navigation of vessels, the radar technique, or the site selection. There is no paper studying the radar deployment problem in navigation channels. Our paper investigates the radar deployment problem in navigation channels for the first time. Besides, we consider different types of radars with varied radii. Different types of buoys are also considered, which have different deployment costs for the radars. Hence, this paper aims to fill the research gap and propose a mixed-integer linear programming model to optimize the deployment of radars in navigation channels.

3. Model Formulation

3.1. Problem Description

The investigated problem can be described as follows: We consider a two-way navigation channel and its surrounding areas. The two-way navigation channel is formed by the area enclosed by the boundary lines, represented by the set $L$. The navigation channel length is denoted by $E,$ and the navigation channel width is represented by $D$. The surrounding areas consist of the areas extending $W$ meters from both sides of the navigation channel. Large vessels navigate in the navigation channel, while small ships generally navigate in the surrounding regions. Along boundary lines, there are some buoys placed to guide the navigation of large vessels. In practice, it is common for some small ships to arbitrarily cross the navigation channel from one surrounding area to the other. This will pose potential risks, such as conflicts between small ships and large vessels. For security considerations, different types of radars, denoted by set $M$, should be deployed along boundary lines. Radars can detect small ships and transmit their location information to large vessels to help them avoid small ships. In particular, the sizes of the navigation channels vary significantly in practice. For example, the Suez Canal [59] has a length of 193,300 m and a width of 345 to 280 m. The length of the Dofuchi Strait of Japan [60] is 2500 m, while the width of its narrowest part is only 9.93 m. In our paper, we use a navigation channel with a moderate width and length in our numerical example in Section 4. Figure 1 displays the layout of our investigated two-way navigation channel. The channel length, i.e., $E$, is 2000 m. The channel width, i.e., $D$, is 100 m. The extended width from each side of the two-way navigation channel to the surrounding area, i.e., $W$, is 30 m.

For the convenience of modeling, the boundary lines $l\in L$ are discretized to a set of discrete locations, denoted by set $N$. At each discrete location, the decision of whether any type of radars should be deployed will be determined. Given that radars can only be deployed on buoys, if there is no existing buoy available for radar deployment at a given discrete location, a new buoy should be built correspondingly. Let ${\xi }_i$ be an indicator denoting whether there is an existing buoy at the discrete location $i\in N$. If there is an existing buoy at the discrete location $i$, let ${\xi }_i$ equal to 1, 0 otherwise. Specifically, the costs of deploying type $m\in M$ of radars on the existing buoys and new buoys are $c_1^m$ and $c_2^m$, respectively. $c_2^m$ is larger than $c_1^m$, since $c_2^m$ includes the cost of building a new buoy. The total cost of deploying radars cannot exceed the budget $B$. To facilitate the safe crossing of small ships, the distance between adjacent deployed radars should be larger than the width of small ships. Let set $\Phi$ include the discrete location pair $(i,j)$ (where $i,j\in N$) that cannot be used to deploy radars simultaneously due to the minimum distance limitation.

In practice, some regions of the navigation channel and surrounding areas typically experience frequent crossings by small ships, while there are fewer crossings in some other regions. For description simplicity, we discretize the navigation channel and surrounding areas into a set of grids, denoted by $S$. For each grid $s\in S$, as shown in Figure 1, the crossing frequency is denoted by $p_s$, which represents the times of small ships crossing it. Detailed crossing times can be collected from historical data. When deploying radars, it is essential to prioritize covering the grids with higher $p_s$. Let ${\mu }_i^{m,s}$ be an indicator denoting whether grid $s$ is covered by the type $m$ of radars deployed at the discrete location $i$. If the grid $s$ is covered, let ${\mu }_i^{m,s}$ equal to 1, 0 otherwise. Under the given budget, the investigated problem is to deploy radars at discrete locations to maximize the total crossing frequency of the grids covered by deployed radars.

3.2. Mathematical Model

The detailed notations used to formulate the model are as follows:

Sets and indices:

$N$: Set of discrete locations along the boundary lines, $i,j\in N$.

$M$: Set of radar types, $m\in M$.

$S$: Set of grids obtained by gridding the navigation channel and surrounding areas, $s\in S$.

$\Phi$: Set of pairs of discrete locations where radars cannot be deployed simultaneously, $(i,j)\in \Phi$.

Parameters:

${\xi }_i$: Binary parameter, equal to 1 if there is an existing buoy at the location $i\in N$, 0 otherwise.

$c_1^m$: Cost of deploying the type $m\in M$ of radars on the existing buoys.

$c_2^m$: Cost of deploying the type $m\in M$ of radars on the new buoys.

$B$: Budget of deploying radars.

$p_s$: Crossing frequency of grid $s\in S$.

${\mu }_i^{m,s}$: Binary parameter, equal to 1 if grid $s\in S$ is covered by the type $m\in M$ of radars deployed at the discrete location $i\in N$, 0 otherwise.

Variables:

$x_i^m$: Binary decision variable, equal to 1 if a radar of type $m\in M$ is deployed at the discrete location $i\in N$, 0 otherwise.

$y_s$: Binary decision variable, equal to 1 if the grid $s\in S$ is covered by the deployed radars, 0 otherwise.

Mathematical model

Based on the above definition of parameters and variables, an integer programming model is formulated as follows.

$$\max {\sum }_{s\in S}{p}_s{y}_s$$

(1)

subject to

$${\sum }_{i\in N}{\sum }_{m\in M}\left[{\xi }_i\cdot c_1^m+\left(1-{\xi }_i\right)\cdot c_2^m\right]\cdot x_i^m\le B$$

(2)

$${\sum }_{m\in M}{x}_i^m+{\sum }_{m\in M}{x}_j^m\le 1\cdots \forall \left(i,j\right)\in \Phi$$

(3)

$$y_s\le {\sum }_{i\in N}{\sum }_{m\in M}{\mu }_i^{m,s}\cdot x_i^m\cdots \forall s\in S$$

(4)

$$x_i^m\in \left\{\mathrm{0,1}\right\}\cdots \forall i\in N,m\in M$$

(5)

$$y_s\in \left\{\mathrm{0,1}\right\}\cdots \forall s\in S.$$

(6)

The objective function (1) maximizes the total crossing frequency of the grids covered by deployed radars. When the total crossing frequency of grids is larger, there will be a higher probability for small ships to be detected. This will decrease the potential risks, such as collisions. Constraints (2) state that the total cost of deploying different types of radars cannot exceed the given budget. Constraints (3) ensure that radars cannot be deployed at any pair of discrete locations belonging to $\Phi$. The pairs of discrete locations in the set $\Phi$ do not satisfy the minimum distance limitation. For example, the minimum distance can be the width of the ships. If the distance between the two adjacent discrete locations is smaller than the minimum distance, the ships will collide with the buoys, thereby causing accidents. Constraints (4) indicate that the region is covered only when it is covered by any deployed radars. Constraints (5) and (6) define the domain of decision variables.

3.3. Hardness of the Problem

The decision version of the radar deployment problem is in NP; that is, given the deployment of radars, it can be determined in polynomial time whether the total crossing frequency of the grids covered by deployed radars is greater than a given constant. We show the NP-completeness of the problem by reducing a well-known NP-complete problem, a set cover problem, into a radar deployment problem. The decision version of the set cover problem is defined as follows: Given a set $S$ of elements, a set $U$ whose elements are subsets of $S$ and whose cardinality is $\left|N\right|$, and an integer $K$, $1\le K\le \left|N\right|$, whether $U$ has $K$ elements whose union is $S$.

Proposition 1.

The decision version of the radar deployment problem is NP-complete.

Proof. 

We construct the following radar deployment problem. Let the elements in $S$ correspond to the grids in the radar deployment problem, and $\left|N\right|$ correspond to the number of discrete locations along the boundary lines. We let $\left|M\right|=1$, $\Phi$ be empty, ${\xi }_i=0$ for all $i\in N$, $p_s=1$ for all $s\in S$. An element in $U$ represents the set of grids that can be covered by radar in a discrete location. The budget $B$ is equal to $K$ times the cost of deploying a radar on the new buoys. It follows easily now that the set cover problem is feasible if and only if there is a radar deployment plan such that all the grids are covered. Thus, the set cover problem can be solved by solving a radar deployment problem. This completes the proof. □

3.4. Property of the Model

Despite the NP-hardness of the radar deployment problem, it can be solved efficiently to optimality for practical-size instances. Moreover, the above model can be improved based on Proposition 2. With Proposition 2, the above integer programming model is transformed into a mixed-integer linear programming model. The detailed explanation of Proposition 2 is as follows:

Proposition 2.

Relaxing $y_s$ as continuous variables, i.e., replacing constraints (6) with constraints (7), does not change the optimal solution of the model.

$$0\le y_s\le 1\cdots \forall s\in S.$$

(7)

Proof. 

We prove Proposition 1 by contradiction. Assume that the optimal solution of the model is ${\mathit{y}}^{\mathit{*}}=\{y_1^{*},\dots ,y_l^{*},\dots ,y_{\left|S\right|}^{*}\}$, where there exists $l\in S$ such that $0<y_l^{*}<1$. According to constraints (4), we have ${\sum }_{i\in N}{\sum }_{m\in M}{\mu }_i^{m,l}\cdot x_i^m\ge y_l^{*}>0$. As ${\mu }_i^{m,s}$ and $x_i^m$ are binary parameters and binary variables for any $i\in N$, $m\in M$ and $s\in S$, respectively, the inequality ${\sum }_{i\in N}{\sum }_{m\in M}{\mu }_i^{m,s}\cdot x_i^m\ge 1$ holds. According to constraints (4), the solution ${{\mathit{y}}^{*}}^{\prime }=\{{y_1^{*}}^{\prime }=y_1^{*},\dots ,{y_l^{*}}^{\prime }=1, \dots ,{y_{\left|S\right|}^{*}}^{\prime }=y_{\left|S\right|}^{*}\}$ is also a feasible solution. Since $p_s\ge 0$ holds for any $s\in S$, we have ${\sum }_{s\in S}{p}_s{y}_s^{*}\le {\sum }_{s\in S}{p}_s{y}_s^{*}\prime$, which is contradictory to the assumption that ${\mathit{y}}^{\mathit{*}}$ is the optimal solution. This completes the proof. □

4. Computational Experiments

To demonstrate the applicability of the proposed Models (1)–(5) and (7), we test the proposed model on a set of generated instances. The model is programmed in Pycharm, compiled with Python interpreter 3.9, and an off-the-shelf solver Gurobi 10.0 is used to solve the proposed mode.

4.1. Basic Setting

In our study, the two-way navigation channel is formed by the area enclosed by three boundary lines, i.e., $\left|L\right|=3$. Specifically, the length $E$ and width $D$ of the two-way navigation channel are set as 200 m and 100 m, respectively. The two-way navigation channel has two lanes, and the width of each lane is 50 m. The distance that is extended from each side of the navigation channel is 30 m, i.e., $W=30$. The side length of the gird is set as 5 m. Then, the number of total grids is 1280, i.e., $\left|S\right|=1280$. Along each boundary line, the distance between any two adjacent discrete locations is set as 25 m. The existing buoys are assumed to be distributed equidistantly along the boundary lines, and the distance between any two adjacent existing buoys is 100 m. There are two types of radars, namely radar type 1 and radar type 2. The coverage radius of radar type 1 is 25 m, and that of radar type 2 is 50 m. The cost of deploying radars of type 1 and radars of type 2 on the existing buoys are 200 USD and 300 USD, while the costs of deploying them on the new buoys are 350 USD and 450 USD, respectively. The budget for deploying radars is 2000 USD. The crossing frequency of grids in the surrounding areas is set as 3, and that in the two-way navigation channel is set as 1.

4.2. Basic Analysis

Figure 2 illustrates the distribution of two types of radars in the navigation channel and surrounding areas. The red dot and green dot represent the existing buoy and the new buoy. The green square and blue square denote the radar of type 1 and the radar of type 2. The yellow area contains the grids covered by the deployed radars. From Figure 2, under the basic setting, it is obvious that there are four radars of type 2 deployed on the new buoys and one radar of type 1 deployed on the existing buoy. Specifically, the maximum total crossing frequency is 2044. In addition, the cost of deploying four radars of type 2 and one radar of type 1 is 2000 USD. And the total deployment cost is equal to the budget. The number of grids being covered is 1148, presented by the yellow area in Figure 2. Then, we can further calculate the coverage ratio in the navigation channel and surrounding areas, which equals dividing the number of grids being covered by the number of total grids (i.e., 0.89).

To test our model, we generated seven different instances, which have different lengths of the two-way navigation channel and budgets. The detailed parameter setting is listed in

Table 1. Parameters of seven instances.

Instance	Length (m)	$\mathit{B}$ (USD)
1	200	2000
2	500	5000
3	800	8000
4	1100	11,000
5	1400	14,000
6	1700	17,000
7	2000	20,000

. The column “Length (m)” shows the length of the two-way navigation channel, which is measured in meters. The column “B (USD)” shows the budget measured in USD.

The detailed results of these seven instances are shown in

Table 2. Detailed results under different lengths and budgets.

Instance	$\left|\mathit{S}\right|$	$\left|\mathit{S}\mathit{’}\right|$	CR	R1E	R1N	R2E	R2N	Obj	Time (s)
1	1280	1148	0.897	1	0	0	4	2044	3.23
2	3200	2912	0.910	0	1	7	5	5224	10.51
3	5120	4736	0.925	0	4	13	5	8392	22.99
4	7040	6560	0.932	0	7	19	5	11,560	41.42
5	8960	8384	0.936	0	10	25	5	14,728	64.66
6	10,880	10,208	0.938	0	13	31	5	17,896	94.95
7	12,800	12,032	0.940	0	16	37	5	21,064	118.64

. Specifically, the column “|S|” gives the number of total grids. The column “|S′|” gives the number of covered grids. The column “CR” represents the coverage ratio in the navigation channel and surrounding areas, which is calculated by dividing |S′| by |S|. The columns “R1E” and “R2E” give the number of radars of type 1 and type 2 deployed on the existing buoys, respectively. The columns “R1N” and “R2N” give the number of radars of type 1 and type 2 deployed on the new buoys, respectively. The column “Obj” reports the maximal total crossing frequency. The computational time is given in the columns “Time (s)” in seconds.

From Table 2, it is obvious that the CR is maximal in instance 7, with a length of 2000 m and a budget of 20,000 USD. This is reasonable since more grids can be covered by more radars deployed with a larger budget. Besides, with the increased budget, more radars of type 1 will be deployed on the new buoys, and more radars of type 2 will be deployed on the existing buoys. Compared with instance 1, it can be found that deploying more radars of type 1 on the new buoys and radars of type 2 on the existing buoys (instances 2 to 7) will be more economical. It can not only save on the budget but also increase the CA. Moreover, the computational time increases with the larger instance scale. When the length of the two-way navigation channel increases from 200 m (instance 1) to 2000 m (instance 7), the number of total grids increases by ten times. Then, the number of decision variables $y_s$ increases, which will reduce the computational speed of our model.

Figure 2 shows the variation trends of Obj, CR, and Time (s) under different instances, where the red line, green line, and blue line represent Obj, CR, and Time (s), respectively. From Figure 3, it is obvious that Obj and CR are improved when the instance changes from 1 to 7. Besides, the computational time (Time) is maximal under instance 7, i.e., 118.64 s. However, the computational time under instance 7 is not much longer than those under the other six instances and is still within the acceptable computational time range. Jointly considering the CR, Obj, and computational time, instance 7 is selected as a basic instance for the following sensitivity analysis.

4.3. Comparison between Our Method and Greedy Algorithm

To validate the performance of our method, we introduce a greedy algorithm for comparison. The core idea of the greedy algorithm is finding the deployment location and the type of radars with maximum increment of total crossing frequency without violating the given budget. Before giving the greedy algorithm, we will first introduce some additional parameters and variables. Let $C$ denote the remaining deployment cost after deploying the radars. Let $Obj$ represent the total crossing frequency. Let binary variable ${\beta }_i$ indicate whether the discrete location $i\in N$ is deployed with any type of radar. Let the binary decision variable $x_i^m$, equal to 1 if a radar of type $m\in M$ is deployed at the discrete location $\in N$, 0 otherwise. The increment of total crossing frequency is denoted by $\mathsf{\sigma }$. The deployment cost of the type $m\in M$ of radars at the discrete location $i\in N$ is represented by $c_i^m$. The detailed description of the greedy algorithm (i.e., Algorithm 1) is as follows:

Algorithm 1: Greedy Algorithm
1	Set $C=Budget$, $Obj=0$, ${\beta }_i=0$ for at each discrete location $i\in N$.
2	While True do
3	$i^{*}=-1$;
4	$m^{*}=-1$;
5	$\sigma =0$;
6	foreach $i\in N$ do
7	if ${\beta }_i>0$ then
8	continue
9	foreach $m\in M$ do
10	if $C>c_i^m$ and $Ob{j}^{\prime }-Obj>\sigma$ then
11	$i^{*}=i$;
12	$m^{*}=m$;
13	$\sigma =Ob{j}^{\prime }-Obj$;
14	if $i^{*}<0$ then
15	break;
16	$Obj=Obj\prime$;
17	$C-=c_{i^{*}}^{m^{*}}$;
18	${\beta }_{i^{*}}=1$;
	Output: $Obj$

Seven instances in Section 4.2 are used to compare our method and the greedy algorithm. The detailed results are shown in

Table 3. Detailed results under different lengths and budgets.

Instance	Our Method			Greedy Algorithm			Gap (%)
	CR	Obj	Time (s)	CR	Obj	Time(s)
1	0.897	2044	3.23	0.843	1729	0.31	15.41
2	0.910	5224	10.51	0.870	4969	3.52	4.88
3	0.925	8392	22.99	0.873	8017	13.82	4.47
4	0.932	11,560	41.42	0.868	10,981	33.41	5.01
5	0.936	14,728	64.66	0.872	14,029	68.98	4.75
6	0.938	17,896	94.95	0.873	17,077	120.09	4.58
7	0.940	21,064	118.64	0.870	20,041	191.37	4.86

. The column ‘Gap (%)’ shows the difference between the objective function value (Obj) obtained by our method and that obtained by the greedy algorithm. From Table 3, it is obvious that our method can always obtain better solutions with larger objective function values than the greedy algorithm. Besides, the coverage ratios obtained by our method are also superior to those obtained by the greedy algorithm.

4.4. Sensitivity Analysis

4.4.1. Impact of the Budget

We first conducted a sensitivity analysis regarding the budget, ranging from 10,000 USD to 35,000 USD. The detailed computational results are summarized in Table 3. Columns “CA1” and “CA2” represent the coverage ratio in the surrounding areas and the coverage ratio in the two-way navigation channel, respectively. Specifically, CA1 is calculated by dividing the number of total grids covered in the surrounding areas by the number of total grids in the surrounding areas. Similarly, CA2 equals the number of total grids covered in the navigation channel divided by the number of total grids in the navigation channel. The other indicators have the same meanings as those used in Table 2. According to

Table 4. Impact of the budget.

$\mathit{B}$ (USD)	CA	CA1	CA2	R1E	R1N	R2E	R2N	Obj
10,000	0.597	0.662	0.558	1	0	28	0	13,992
15,000	0.851	0.938	0.799	0	0	39	3	19,907
20,000	0.940	0.941	0.939	0	16	37	5	21,064
25,000	0.963	1.000	0.941	0	0	20	40	21,924
30,000	0.999	1.000	0.999	1	2	32	40	22,392
35,000	1.000	1.000	1.000	17	22	17	42	22,400

, when the budget increases, CA and CA2 increase quickly and reach their peak value of 1.000 with a budget of 35,000 USD. CA1 obtains its maximal value when the budget reaches 25,000 USD.

Figure 4 illustrates the relationship between the budget and the number of radars deployed on the existing buoys and new buoys. The blue bar represents the number of radars deployed on the existing buoys, which is calculated by the sum of R1E and R2E (i.e., R1E + R2E). The gray bar represents the number of radars deployed on the new buoys, which is calculated by the sum of R1N and R2N (i.e., R1N + R2N). When the budget is low, such as 10,000 USD, 15,000 USD, and 20,000 USD, more radars of type 1 and type 2 are deployed on the existing buoys since the deployment cost on the existing buoys is much lower than that on the new buoys. With the increase in budget (increasing from 10,000 USD to 35,000 USD), the number of radars of type 1 and type 2 deployed on the new buoys increases. When the budget reaches 25,000 USD, the number of radars of type 1 and type 2 deployed on the new buoys is larger than that on the existing buoys.

Figure 5 shows the number of radars of type 1 and type 2 when the budget increases from 10,000 USD to 35,000 USD. The blue and gray bars represent the number of radars of type 1 (i.e., R1E + R1N) and the number of radars of type 2 (i.e., R2E + R2N). From Figure 5, under different budgets, compared to the number of radars of type 1, more radars of type 2 are deployed. This is probably because the coverage radius of radars of type 2 is much larger than that of radars of type 1.

To further test the relationship between the budget and the coverage ratio in the navigation channel and surrounding areas, we perform a Pareto analysis. The detailed results are shown in Figure 6. From Figure 6, it is obvious that the coverage ratio is zero when the budget is less than 200 USD. This is because there is not enough funding to deploy any type of radar. When the budget reaches 20,000 USD, the increase rate of coverage ratio becomes slow. Trivial coverage ratio gains are being achieved at a high budget. Besides, the coverage ratio reaches its peak value, i.e., 1.000, when the budget is 32,000 USD. Then, a further increase in the budget will not improve the coverage ratio.

4.4.2. Impact of the Coverage Radius of Radars

To further explore the relationship between the coverage radius (radars of type 1 and radars of type 2) and the optimal solution of our model, the sensitivity analysis on the different combinations of coverage radius is performed. The relevant results are reported in

Table 5. Impact of the coverage radius of radars.

R1 (m)	R2 (m)	CA	CA1	CA2	R1E	R1N	R2E	R2N	Obj
25	50	0.940	0.941	0.940	0	16	37	5	21,064
25	55	0.994	1.000	0.991	0	14	40	4	22,328
25	60	0.999	1.000	0.999	0	14	40	4	22,390
25	65	1.000	1.000	1.000	0	1	17	30	22,400
30	50	0.950	0.941	0.956	0	16	37	5	21,192
35	50	0.960	0.941	0.972	0	16	37	5	21,320
40	50	0.963	0.943	0.975	5	23	32	2	21,370
45	50	0.989	0.989	0.990	28	41	6	0	22,160

. The columns “R1 (m)” and “R2 (m)” represent the coverage radius of radars of type 1 and that of radars of type 2, measured in meters. The other columns have the same meanings as Table 4. When R1 = 25 m, CA, CA1, CA2, and Obj increase with the increase of R2. Particularly, the grids in the surrounding areas are all covered (CA1 = 1.000) when R1 = 25 m and R2 ≥ 55 m. Moreover, when R2 = 50 m, CA, CA1, CA2, and Obj increase as R1 increases.

Figure 7 illustrates the number of radars of type 1 and type 2 under different coverage radii of radars of type 2 (i.e., R2 ranges from 50 m to 65 m), where the radius of radars of type 1 equals 25 m. The blue bar and gray represent the number of radars of type 1 (i.e., R1E + R1N) and that of type 2 (i.e., R2E + R2N), respectively. In Figure 7, it is obvious that the number of radars of type 2 is larger than that of radars of type 1. This is because radars of type 2 can cover more grids with a much larger coverage radius and little deployment cost increase.

Figure 8 shows the number of radars of type 1 and type 2 under different coverage radii of radars of type 1 (i.e., R1 ranges from 25 m to 45 m), where the radius of radars of type 2 equals 50 m. From Figure 8, with the increase in R1, the number of radars of type 1 increases gradually and reaches its peak value when R1 = 45 m. When R1 = 45 m, it is evident that the number of radars of type 1 is much larger than that of radars of type 2. This is because the difference between R1 and R2 is relatively small, but the deployment cost of radars of type 1 is much less than that of radars of type 2.

4.4.3. Impact of the Distance between Adjacent Discrete Locations

The distance between any two adjacent discrete locations may affect the optimal solution and computational time of our model. Smaller distances indicate that more discrete locations can be utilized to deploy the radars. The computational results about the distance are given in detail in

Table 6. Impact of the distance between adjacent discrete locations.

DisL (m)	CA	CA1	CA2	R1E	R1N	R2E	R2N	Obj	Time (s)
5	0.913	0.987	0.868	0	0	16	32	21,152	5079.21
10	0.913	0.987	0.868	0	0	16	32	21,152	466.58
20	0.913	0.987	0.868	0	0	16	32	21,152	149.50
25	0.940	0.941	0.939	0	16	37	5	21,064	118.64
50	0.937	0.935	0.939	0	17	40	2	20,974	59.03
100	0.923	0.933	0.918	0	0	57	0	20,780	30.38

. The column “DisL (m)” represents the distance between any two adjacent discrete locations and is measured in meters. The other columns have the same meanings as those in Table 2 and Table 4. From Table 6, it is obvious that the computational time increases with the increase of DisL. This is reasonable since more decision variables are involved.

Meanwhile, Obj shows an overall decreasing trend with the increase of DisL. In detail, when DisL ranges from 5 m to 20 m, there is no difference in their optimal solutions (Obj). However, Obj decreases when DisL is larger than 20 m (from 25 to 100 m). This is probably because fewer discrete locations can be used to deploy the radars due to the larger DisL, affecting the optimal solution. Specifically, when DisL equals 100 m, the same as the distance between any two adjacent existing buoys, all the radars will be deployed on the existing buoys.

4.4.4. Impact of the Distribution of the Existing Buoys

Considering the locations of existing buoys will affect the optimal solution, we then investigate the impact of the locations of existing buoys. Table 6 reports the relevant results under different distributions of existing buoys. The column “DisB” gives the distance between two adjacent existing buoys, which reveals the number of existing buoys in the two-way navigation channel. From

Table 7. Impact of the distribution of the existing buoys.

DisB (m)	CA	CA1	CA2	R1E	R1N	R2E	R2N	Obj
25	0.951	1.00	0.921	2	0	56	0	21,768
50	0.948	0.963	0.940	10	0	36	12	21,388
100	0.940	0.941	0.939	0	16	37	5	21,064
200	0.902	0.963	0.865	2	1	14	32	20,792
250	0.895	0.968	0.851	1	0	14	33	20,740
300	0.893	0.968	0.848	0	0	12	35	20,726

, we can find that Obj and CA both show decreasing trends with the increase in DisB. Besides, the number of radars deployed on the existing buoys (R1E, R2E) gradually decreases. This is because the number of existing buoys to deploy the radars decreases owing to the increasing DisB. Specifically, when DisB = 25 m, there are no radars to be deployed on the new buoys since all discrete locations have their existing buoys.

5. Conclusions

In this study, we determine the optimal deployment locations of radars in two-way navigation channels and surrounding areas, aiming at maximizing the total crossing frequency of grids covered by deployed radars. Specifically, different types of radars (with different coverage radii) and buoys (existing buoys and newly built buoys) are involved. A mixed-integer linear programming model is proposed to formulate our problem.

Then, sensitivity analyses are conducted concerning the impacts of budgets, the coverage radius of different types of radars, the distance between adjacent discrete locations, and the distribution of the existing buoys. There are several findings, as follows. (1) When the budget is small, more radars should be deployed on the existing buoys than on newly built buoys. However, as the budget increases, the number of radars deployed on new buoys (and the number of new buoys built) will increase. (2) The coverage radius of radars can significantly affect the number of radars to be deployed. (3) The distance between adjacent discrete locations will affect the computational time and optimal solution of our model. (4) When the existing buoys are more densely distributed, the coverage ratio will be higher, and the objective function will be larger than when they are less densely distributed.

The studied problem could be extended in many directions. For instance, the shape of the two-way navigation channel can be irregular. It may be an “L” shape or a “Y” shape. Addressing the deployment of radars for navigation channels of complex shapes is an interesting future research topic. Moreover, we did not consider the uncertainty of vessel traffic volume. Stochastic optimization models are required to address the deployment of radars in the context of uncertain vessel traffic volumes.