The Lowest Contour Line Algorithm: A vehicles’ layout method for enhancing sortie mission reliability

Abstract

The vehicles’ layout is critical for amphibious landing operations, maritime emergency rescue, and roll-on/roll-off vessel loading. Conventional layout algorithms in Cartesian coordinates focus primarily on maximizing space utilization, yet they overlook congestion that may arise from equipment failures during actual layout, leading to a sharp decline in mission reliability. To address this issue, this paper proposes the Lowest Contour Line Algorithm based on polar-coordinate. Unlike traditional heuristic methods, it explicitly incorporates reliability metrics into the layout process, thereby producing layout schemes with higher sortie mission reliability. By arranging vehicles’ radially and deriving the initial contour from turning radii, the algorithm raises the lower bound of mission reliability. In addition, a scan-point placement strategy, a contour update mechanism, and a circuit breaker mechanism are proposed to balance space utilization and mission reliability. Comparative experiments with three baseline methods demonstrate that the proposed algorithm significantly improves sortie mission reliability while maintaining a number of layout units comparable to that of conventional approaches. The algorithm provides a novel technical solution for layout scenarios with stringent reliability requirements.

Keywords

Lowest Contour Line Algorithm sortie mission reliability vehicles’ layout 2D-layout algorithm

Introduction

In today’s intricate and complex social environment, sortie mission reliability plays a decisive role for various vehicles.¹ In complex scenarios such as emergency rescue,² logistics transportation,³ and military operations,⁴ sortie mission reliability is directly linked to the extent of mission accomplishment as well as the optimal allocation of vehicles and resources.⁵ Therefore, effectively enhancing sortie mission reliability has become a critical issue that urgently requires in-depth investigation and resolution in the field of vehicles’ layout.⁶

Sortie mission reliability primarily measures the probability that vehicles successfully execute a sortie mission within a closed space featuring a fixed exit.⁷ This metric not only depends on the vehicles’ technical performance but is also influenced by multiple factors, including the complexity of the layout space, the rationality of the layout plan, and the precision of human operations.⁸ Crucially, the appropriateness of the layout directly affects the sortie mission reliability of all vehicles within the closed space.

The essence of layout is, in reality, a two-dimensional nesting problem. Its core lies in how to arrange a series of smaller geometric shapes on a two-dimensional figure as rationally as possible to achieve the highest utilization rate.⁹ Based on the differences in the shapes of the components to be nested, the two-dimensional nesting problem can be subdivided into the two-dimensional regular nesting problem and the two-dimensional irregular nesting problem.¹⁰ Among these, the layout problem for vehicles is the most common and widely applied rectangular nesting problem within the realm of two-dimensional regular nesting problems.

In exploring solutions to the rectangular nesting problem, scholars generally tend to either employ exact algorithms for precise calculation or use heuristic algorithms to construct an initial solution, and then further approach or achieve the optimal solution with intelligent optimization algorithms.^11–13 In the domain of exact algorithms, methods such as linear programming, tree search, branch and bound, and integer programming models leverage their rigorous mathematical planning foundations to pursue an exact answer for the rectangular nesting problem.^14–16 These algorithms meticulously traverse the solution space and can quickly locate the optimal solution when the number of rectangles is relatively small.¹⁷ However, as the problem scale increases and the number of rectangles grows dramatically, the computational complexity of these exact algorithms escalates sharply, exhibiting exponential growth. This leads to prohibitively long computation times that are unsuitable for practical applications.¹⁸ Consequently, the research focus has gradually shifted from pursuing an absolute optimal solution to finding an acceptable near-optimal solution within a reasonable timeframe.¹⁹ In this context, heuristic algorithms have emerged; these algorithms not only focus on the quality of the nesting result but also highly value solving efficiency, striving to find the best balance between nesting quality and computation time.²⁰

Heuristic algorithms for solving the two-dimensional rectangular nesting problem primarily include the grid method, lane method, bottom-left algorithm, and Lowest Horizontal Line Algorithm, among others, each with its own approach.²¹ These heuristic algorithms have their respective advantages and disadvantages and are suitable for different types of nesting problems.

The grid method divides the nesting area into a series of small grid cells, then places rectangles into these cells. Bui et al. proposed a two-dimensional bin-packing strategy based on grid discretization, which partitions the nesting space into grid units with fixed resolution and achieves rapid item localization and gap filling by dynamically inspecting the occupancy status of the grids.²²

The lane method divides the nesting area into several horizontal “lanes” and sequentially places the rectangles in these lanes. Schwiddessen addressing the lane layout problem, proposed an approach that improves the constraints of semidefinite programming relaxation to optimize the sequential arrangement of facilities within a single lane.²³ However, when handling rectangles with complex shapes or vastly differing sizes, the grid partitioning and ordering strategies in these two methods can become complicated and challenging to optimize.

The bottom-left algorithm achieves nesting by starting from the lower-left corner and sequentially placing each rectangle at the lowest unoccupied position. Chehrazad et al. proposed a semi-discrete bottom-left algorithm that discretizes non-convex polygons into vertical line segments, thereby improving computational efficiency through sweep line techniques and dynamic resolution adjustments.²⁴ Liu introduced a weighted bottom-left algorithm that improves the matching strategy of the traditional residual bottom-left algorithm by dynamically adjusting weight factors.²⁵ Hougardy and Zondervan, through experiments on squares, demonstrated that even with the optimal ordering, the performance of the bottom-left algorithm remains limited, revealing its theoretical bounds.²⁶ These studies indicate that while such methods are simple and easy to implement, their basic placement strategies often fail to fully utilize the available space, resulting in nesting outcomes that are not sufficiently compact. The Lowest Horizontal Line Algorithm is one of the most widely applied layout techniques. At each step, it selects the lowest horizontal line that can accommodate the current rectangle and places the rectangle at the leftmost position on that line. Zhu and Shi proposed a Lowest Horizontal Line Algorithm that can dynamically adjust the vehicle deployment sequence and gap-filling strategy, thereby solving the two-dimensional nesting problem under certain spatial constraints.²⁷ Sun et al. further applied a segmented Lowest Horizontal Line Algorithm to the layout problem in scenarios with complex obstacles.²⁸ These methods generally achieve relatively compact nesting results when dealing with a large number of rectangles.

However, when applying the above algorithms for layout, it is usually assumed that the failure rate of the vehicles is zero, in other words, the layout is carried out under ideal conditions without considering the operational task reliability of the resulting layout scheme.²⁹ Although existing algorithms can achieve high spatial utilization, their linear layout in Cartesian coordinates tends to create a “serial congestion” bottleneck at the exit zone: if an exit vehicle fails, the sortie reliability of subsequent vehicles drops sharply. Such layout algorithms can no longer meet the ever-increasing reliability requirements of today.³⁰ To date, no layout algorithm under the stated problem formulation has explicitly coupled spatial utilization with sortie mission reliability.³¹ To bridge this critical gap, our earlier work proposed a method for calculating sortie mission reliability of shipborne vehicles’ layouts; however, it did not address how to optimize layouts to improve this reliability metric. Building on the reliability modeling framework developed previously, the present study extends it to the layout domain and, for the first time, incorporates reliability indices into layout algorithm design. For this reason, we propose the Lowest Contour Line Algorithm, which aims to enhance the sortie mission reliability of shipborne vehicles’ layouts without compromising space utilization.

Building on recent studies,^32,33 this paper makes three main contributions:

Theoretical contribution: We propose, for the first time, a polar-coordinate layout framework that replaces traditional point-based cartesian placement with radial placement, providing a new theoretical basis for reliability-oriented layout optimization.

Methodological contribution: The proposed scanning, contour update, and circuit breaker mechanisms integrate space-utilization objectives with reliability metrics.

Practical contribution: Experimental results show that the Lowest Horizontal Line Algorithm significantly improves sortie mission reliability while preserving the number of layout units. It is directly applicable to roll-on/roll-off vessels, landing-ship compartments, and maritime emergency-rescue scenarios.

The rest of this paper is organized as follows: Section 2 details the design process of the Lowest Contour Line Algorithm; Section 3 employs the Lowest Contour Line Algorithm, the Lowest Horizontal Line Algorithm, the grid method, and the lane method to solve the same vehicle layout problem; Section 4 presents a comparative analysis of the four algorithms based on the vehicle layout quantity and operational task reliability; and Section 5 concludes with final remarks and an outlook.

Materials and methods

The overall research methodology consists of three stages:

Algorithm design: We propose the Lowest Contour Line Algorithm, including all its design elements.

Performance evaluation: The algorithm is assessed from multiple perspectives through computational complexity analysis and parameter sensitivity analysis.

Benchmark comparison: Under identical test scenarios, the Lowest Contour Line Algorithm is compared with three baseline algorithms. The comparison results of the third stage are reported in Section 3.

This section briefly introduces the related foundational algorithm and then elaborates on the design rationale, key components, and layout process of the Lowest Contour Line Algorithm, followed by the performance evaluation.

Basic algorithm

As the basic algorithm for the Lowest Contour Line Algorithm, the Lowest Horizontal Line Algorithm first converts the layout space into a rectangular arrangement area based on the given coordinate origin and axes. Next, it initializes the boundary line, treating it as the lowest horizontal line. Then, for each vehicle inserted, it is placed on the smaller edge segment of the lowest horizontal line. If the width of that segment is greater than or equal to the width of the vehicle to be inserted, the vehicle is placed at that position and the lowest horizontal line is subsequently updated; otherwise, the lower segment of the lowest horizontal line is selected, the height of the adjacent segment is raised, and the lowest horizontal line is updated accordingly. Finally, these steps are repeated until either all vehicles have been arranged or there is no remaining layout space.

Problem analysis

The main aim of the Lowest Contour Line Algorithm is to achieve a layout scheme that ensures high reliability for sortie missions. Information on the definition, metrics, and assumptions of sortie mission reliability for shipborne vehicles can be found in Shi et al.⁷ (Note: Shi et al.⁷ reports the preliminary results of this study, focusing on the computation of sortie mission reliability for use in the present and subsequent study.)

Accordingly, similar to the basic algorithm, the layout space must first be transformed into an arrangement space with high reliability. This arrangement space is determined based on the provided spatial data, including entry and exit positions, safe distances between vehicles, and safe distances between vehicles and their environment, as well as vehicle data such as model, dimensions, quantity, failure rate, and turning radius.

A layout scheme applying the Lowest Contour Line Algorithm typically arranges the vehicles neatly at the exit, as shown in Figure 1(a). Here, the “√” symbol indicates that the vehicle is in a state where it can execute a sortie mission at the current moment, while the “X” symbol indicates that the vehicle is unable to perform a sortie mission at the current time. Meanwhile, the area enclosed by the blue line represents the layout zone, and the red line indicates the exit. In such a layout scheme, vehicles can only be dispatched for sortie missions in order of priority if they are close to the exit and have sufficient space for dispatching, as shown in Figure 1(b). If these vehicles fail, the subsequent vehicles will be prevented from being dispatched, thereby reducing the reliability of the sortie missions for the layout scheme.

Figure 1.

Low sortie mission reliability layout scheme: (a) initial vehicles state and (b) subsequent vehicles state.

To address this issue, in actual layout operations decision makers typically shift the queues of vehicles on both sides of the exit entirely in a direction away from the exit. The magnitude of this shift is usually determined by the turning radius of the vehicle in that queue nearest to the exit, as shown in Figure 2. The advantage of this layout scheme is that, in the initial state, there is a larger number of vehicles available for sortie; when one or several vehicles experience a fault, the remaining vehicles can still execute the sortie mission. Therefore, under the same vehicle failure rate, this type of layout scheme exhibits higher sortie mission reliability.

Figure 2.

High sortie mission reliability layout scheme.

The Lowest Contour Line Algorithm

In the baseline algorithm, vehicles are arranged sequentially starting from the lowest horizontal line in the Cartesian coordinate system, that is, closest to the origin. When the algorithm terminates, it usually results in one or more horizontal lines rather than a curve that enables vehicle turning. Therefore, in the Lowest Contour Line Algorithm, we first introduce a polar coordinate system to replace the original Cartesian coordinate system.

The establishment of the polar coordinate system

The pole and polar axis of the polar coordinate system are jointly determined by the arrangement space S and the exit P. Suppose that the arrangement space S is a typical rectangular space, with $S = [x_{1}, x_{2}] \times [y_{1}, y_{2}]$ , where $x_{1}, x_{2}$ and $y_{1}, y_{2}$ are the boundary coordinates of the rectangle. At the same time, assume that the exit $P = [x_{p}, x_{p}'] \times y_{p}$ is a line segment located on the edge of S. The midpoint of P is denoted as $P_{m} = [x_{m} \times y_{p} | x_{1} < x_{m} < x_{2} \land y_{1} < y_{2} < y_{p}]$ , where $x_{m} = (x_{p} + x_{p}') / 2$ . Then, the centroid of the arrangement space R is determined as the pole, and the line connecting the pole O in the direction of $P_{m}$ is defined as the polar axis. That is, the pole of the polar coordinate system is defined as $O = (O_{x}, O_{y}) = [(x_{1} + x_{2}) / 2, (y_{1} + y_{2}) / 2]$ , and the polar axis is $\vec{{OP}_{m}}$ . If an arbitrary point $P' = (x', y') = (ρ, θ)$ is given, then $ρ = \sqrt{{(x' - O_{x})}^{2} + {(y' - O_{y})}^{2}}$ . Therefore, the polar coordinate system can be expressed by the following equation: $P' = (x', y') = (O_{x} + ρ \cos (θ + π / 2), O_{y} + ρ \sin (θ + π / 2))$ . Here, ρ is the distance from point $P'$ to the pole O, and θ is the angle formed with the polar axis.

In the polar coordinate system, the vehicles’ positions are determined by their distances from the pole and the angles they make with the polar axis. This transformation not only simplifies the process of computing the vehicles’ positions but also helps us better understand the relative spatial relationships among the vehicles. Secondly, in order to ensure that there is sufficient transfer space between the output deployment plan and the exit to facilitate the vehicles in executing sortie missions, we introduce the concept of contour line.

Initial contour line

Compared to the Lowest Horizontal Line Algorithm, which determines the initial horizontal line using the coordinate origin, coordinate axes, and the layout space, the Lowest Contour Line Algorithm determines the initial contour line using the pole, the polar axis, vehicle dimensions, the minimum layout spacing between vehicles and the exit, the vehicles’ maximum turning radius, and the layout space.

The initial contour line is composed of the layout baseline and portions of the boundaries of the layout region. The layout baseline is a curve formed by the collection of vehicle layout base points that satisfy the initial sortie conditions. As the given initial conditions change, the expression of the layout baseline will change accordingly.

Assume there is a layout space S with an exit P located outside of S. Let P_m be the midpoint of P and let the centroid of S be the pole O; then $\vec{{OP}_{m}}$ is the polar axis. Currently, there are N vehicles arranged in S. Each vehicle has a length L and width W, the minimum layout spacing between the vehicles and the exit is $| \vec{{OP}_{m}} |$ , and the maximum turning radius of a vehicle is R. Then, the schematic diagram for determining the initial contour line is shown in Figure 3.

Figure 3.

Schematic diagram for determining the initial contour line.

In the diagram:

The black rectangle represents the arranged vehicles.

The rectangle composed of red and blue solid and dashed lines represents the external contour of the environment.

The rectangle composed of brown and blue solid and dashed lines represents the layout space S.

The red line segment represents the exit P.

The blue arc represents the layout baseline.

The blue arc together with the blue solid and dashed lines forms the initial contour line.

The point C is the center point of the vehicle that meets the initial dispatch conditions.

Thus, based on the above initial conditions, the trajectory equation can be determined as equation (1).

ρ_{c} (θ) = (| \vec{{OP}_{m}} | - R) \cos θ + \sqrt{R^{2} - {(| \vec{{OP}_{m}} | - R)}^{2} \sin^{2} θ}

(1)

Point D is the layout base point corresponding to the vehicle, and the set of points (D) forms the layout baseline. Its mathematical expression is equation (2).

{\begin{matrix} ρ_{D} (θ) = \sqrt{{(ρ_{C} \cos θ + L / 2)}^{2} + {(ρ_{C} \sin θ + W / 2)}^{2}} \\ α_{D} (θ) = \arctan [(ρ_{C} \sin θ + W / 2) / (ρ_{C} \cos θ + L / 2)] \end{matrix}

(2)

Scanning line

Unlike the Lowest Horizontal Line Algorithm, where vehicles are preferentially placed at positions with smaller X and Y coordinates, the Lowest Contour Line Algorithm introduces the concept of scanning line. Beginning from the polar axis and using a given step angle $Δ$ , the scanning line uniformly sweeps across the entire layout space. As shown in Figure 3, the gray rays $\vec{OD}$ represent the scanning line. As a scanning line sweeps through the layout space, it intersects with the contour line, forming vehicle layout baseline points.

These baseline points represent candidate locations where vehicles might be placed. To ensure that the vehicles can be dispatched smoothly, these candidate positions must be evaluated, and the final vehicle placement points are determined by selecting positions that satisfy the dispatch conditions and do not cause spatial conflicts. Moreover, the choice of the scanning line’s step angle $Δ$ has a significant impact on both the algorithm’s efficiency and the accuracy of the results. By reasonably setting the value of $Δ$ , it is possible to improve the algorithm’s running efficiency while ensuring the quality of the results.

Transition degree

In order to ensure that all vehicles in the layout scheme are placed within the layout area and share a unified orientation, a key metric called the “Tr” is defined as equation (3). The mathematical expression for the transition degree is shown below. The transition degree indicates the direction of change in the position of a vehicle’s center point as the layout transitions from one state to another within the layout space. Specifically, it represents the change in offset of the vehicle’s center point relative to the layout baseline point during the layout process.

Tr = (Lt, Lb, Rb, Rt)

(3)

Here, Lt, Lb, Rb, and Rt, respectively, indicate that the center point of the vehicle is located at the rear-right, front-right, front-left, and rear-left of the layout baseline point, with distances such that $| \vec{LtO} | = | \vec{LbO} | = | \vec{RbO} | = | \vec{RtO} | = (\sqrt{W^{2} + L^{2}}) / 2$ , and the angle formed with the polar axis is $\arctan (W / L)$ . A schematic diagram of the transition degree is shown in Figure 4.

Figure 4.

Schematic diagram of the transition degree.

At the start of the algorithm, the initial transition degree is set as Tr = Lt, and the total angle swept by the scanning line is recorded as $Δ' = 0$ . With each scanning line step, $Δ'$ is incremented by $Δ$ , that is, $Δ' = Δ' + Δ$ . If $Δ' \geq 90^{°}$ , then the transition degree is adjusted to Tr = Lb; if $Δ' \geq 180^{°}$ , then Tr = Rb; if $Δ' \geq 270^{°}$ , then Tr = Rt. When $Δ' \geq 360^{°}$ , the transition degree is reset by setting Tr = Lt and $Δ' = 0$ .

Contour update

In the Lowest Contour Line Algorithm, the contour is dynamically updated as vehicles are laid out. Each time the transition degree is reset, the algorithm recalculates and updates the contour based on the current lowest contour and the outer contour information of the vehicles that have already been laid out.

Specifically, the new level’s lowest contour is formed by the outer contours of the vehicles laid out in the current level that are both facing the extreme point and exposed, along with the connecting lines between them, as shown in Figure 5. In this figure, the blue curve represents the initial contour, while the orange polyline indicates the updated second-level lowest contour.

Figure 5.

Contour update mechanism diagram.

This update process ensures that subsequent vehicle layouts are based on the latest spatial information, thereby avoiding spatial conflicts and enhancing the rationality and compactness of the layout scheme. At the same time, through continual updates of the contour, the Lowest Contour Line Algorithm can gradually construct a layout scheme that meets both the reliability requirements for deployment tasks and a high degree of space utilization.

Circuit breaker mechanism

To ensure that the algorithm terminates correctly, a circuit breaker mechanism is proposed. Assume that the total energy of the layout is $E$ , and an initial energy threshold $ε$ is set, with the following characteristics:

The initial energy is 0, and the energy cannot drop below 0.

Each time the state of the Transition Degree changes, the energy increases by 1.

Each time a vehicle is laid out, the energy decreases by 1.

If the energy exceeds this threshold, the circuit breaker is triggered, at which point the algorithm terminates and outputs the layout scheme.

The design of the circuit breaker mechanism is intended to prevent the algorithm from entering into an infinite loop or generating unreasonable layout schemes. In practical applications, the energy threshold must be adjusted according to the specific scenarios and requirements. If the threshold is set too low, the algorithm may terminate prematurely, failing to produce a correct layout scheme; if it is set too high, it could increase both the running time and computational complexity of the algorithm.

Algorithm pseudocode

The complete pseudocode of the Lowest Contour Line Algorithm is given below:

The Lowest Contour Line Algorithm
Input: layout space information (length, width, exit-location); spatial constraint information (layout requirements); vehicles’ information (quantity, dimensions); step angle $Δ$ ; circuit breaker threshold $ε$ . Output: layout scheme $R$ . Initialize polar coordinate system: $θ = 0$ . Initialize state variables: $Δ' = 0$ , $Tr = Lt$ , $E = 0$ . Calculate the initial contour line. Whilethe number of remaining vehicles is not zero and $E \leq ε$ do Scan by step angle $Δ$ , set $Δ' = Δ' + Δ$ Ifthe condition for Tr update is triggered then Update $Tr$ state, set $E + = 1$ If $Δ' \geq 360^{°}$ then Update the contour line Set $Δ' - = 360^{°}$ End Calculate the placement reference point $D$ Determine the vehicle center point $C$ Ifspatial constraints are satisfied then Record layout information in $R$ Set $E - = 1$ Else Discard current the point $C$ and $D$ End End End Return $R$

The Lowest Contour Line Algorithm

Input: layout space information (length, width, exit-location); spatial constraint information (layout requirements); vehicles’ information (quantity, dimensions); step angle

Δ

; circuit breaker threshold

ε

.
Output: layout scheme

R

.
Initialize polar coordinate system:

θ = 0

.
Initialize state variables:

Δ' = 0

Tr = Lt

E = 0

.
Calculate the initial contour line.
Whilethe number of remaining vehicles is not zero and

E \leq ε

do
Scan by step angle

Δ

, set

Δ' = Δ' + Δ

Ifthe condition for Tr update is triggered then
Update

Tr

state, set

E + = 1

Δ' \geq 360^{°}

then
Update the contour line
Set

Δ' - = 360^{°}

End
Calculate the placement reference point

D

Determine the vehicle center point

C

Ifspatial constraints are satisfied then
Record layout information in

R

Set

E - = 1

Else
Discard current the point

C

and

D

End
End
End
Return

R

Hyperparameter description

All hyperparameters used in the minimum-contour algorithm and their ranges are listed in Table 1. The parameter values adopted in this study were determined through sensitivity analysis to balance layout efficiency, reliability, and computational cost.

Table 1.

Hyperparameters of the Lowest Contour Line Algorithm.

Hyperparameter	Range	Value	Rationale
$Δ$	0.05°–0.3°	0.15°	A smaller step increases computation time, whereas a larger step reduces space utilization
$ε$	2–6	3	A small threshold wastes layout space; a large threshold causes redundant search and increases computation time

Computational complexity analysis

This section analyzes the time and space complexity of the Lowest Contour Line Algorithm.

The time complexity of the Lowest Contour Line Algorithm consists of three components:

Scan-line advancement: The scan line starts from the polar axis and sweeps the entire layout space with step angle $Δ θ$ . The number of scans is $2 π / Δ θ$ , so the scan-line advancement complexity is $O (2 π / Δ θ)$ .

Contour update: The contour is formed by the outer boundary of already placed vehicles. Updating requires traversing all placed vehicles, with time complexity, where $N$ is the number of placed vehicles.

Overall time complexity: The algorithm performs multiple scans and contour updates; therefore, the total time complexity is $O (N \cdot (2 π / Δ θ))$ .

Space complexity analysis: The algorithm stores the positions and orientations of placed vehicles: $O (N)$ ; current contour information: $O (N)$ ; and layout boundary information: $O (1)$ . Hence, the space complexity is $O (N)$ .

To validate the above analysis, we tested runtime and memory usage on problems of different scales. The experimental environment was Intel Core i7-10700 CPU @ 2.9 GHz, 16 GB RAM, Windows 10, Python 3.8. The test results are summarized in Table 2.

Table 2.

Validation of computational complexity for different problem sizes.

Number of vehicles	Average runtime (s)	Memory (MB)	Theoretical time complexity	Empirical time complexity
30	0.52 ± 0.08	12.3	$O (30)$	$O (30)$
60	1.85 ± 0.21	24.1	$O (60)$	$O (58)$
90	4.23 ± 0.35	38.7	$O (90)$	$O (87)$

Note. Empirical time complexity is estimated from the ratio of runtime to the number of vehicles.

3. Comparison with baseline methods:

As shown in Table 3, the time complexity of the lowest contour algorithm is slightly higher than that of the lowest skyline algorithm because polar-coordinate scanning requires more computational steps. However, this increase is acceptable given the substantial improvement in reliability, which outweighs the added computational cost.

Table 3.

Computational complexity comparison of four algorithms.

Algorithm	Time complexity	Space complexity	Average runtime (s)
Lowest Contour Line Algorithm	$O (2 π / Δ θ)$	$O (N)$	1.85
Lowest Horizontal Line Algorithm	$O (N^{2})$	$O (N)$	1.62
Grid method	$O (W \cdot H / g^{2})$	$O (W \cdot H / g^{2})$	2.34
Lane method	$O (N \cdot L)$	$O (N)$	1.71

Note. $W$ and $H$ are the length and width of the layout space, $g$ is the grid size, and $L$ is the number of lanes.

Parameter sensitivity analysis

By systematically adjusting the step angle $(Δ θ)$ and circuit breaker threshold values, we construct a sensitivity analysis model with diverse parameter combinations. This model evaluates whether the algorithm maintains superior performance over the baseline approach across three key metrics: mission reliability, vehicle layout quantity, and computational time.

Model 1: Step angle adjustment:

Parameter setup: Baseline configuration $Δ θ = 0 . 15^{°}$ (reference model).

Sensitivity tests:

Submodel 1a: Decreased step angle $Δ θ = 0 . 10^{°}$ (↑scanning precision, ↑computational load).

Submodel 1b: Increased step angle $Δ θ = 0 . 20^{°}$ (↓scanning precision, ↓computational load).

Evaluation metrics:

Mission reliability (under 0.5% and 5% failure rates).

Average vehicle layout quantity.

Computational time variation.

Model 2: Circuit breaker threshold adjustment:

Parameter setup: Baseline threshold = 4 (reference model).

Sensitivity tests:

Submodel 2a: Reduced threshold to 3 (early termination, ↓ iterations).

Submodel 2b: Increased threshold to 5 (delayed termination, ↑ iterations).

Evaluation metrics:

Mission reliability (under 0.5% and 5% failure rates).

Average vehicle layout quantity.

Computational time variation.

The comparative sensitivity analysis results are shown in Table 4.

Table 4.

Sensitivity analysis model for sortie mission reliability comparison.

Model	Failure rate (0.5% OR, 95% CI)	Failure rate (5% OR, 95% CI)	Vehicle layout quantity (units)	Computational time change (%)
Baseline (original parameters)	1.90 (1.41–2.56)	1.83 (1.32–2.54)	75.1	0
Submodel 1a (Δθ = 0.10°)	1.85 (1.32–2.58)	1.78 (1.25–2.53)	75.5	40
Submodel 1b (Δθ = 0.20°)	1.72 (1.21–2.45)	1.65 (1.14–2.38)	74.2	−40
Submodel 2a (threshold = 3)	1.92 (1.40–2.63)	1.85 (1.33–2.57)	73.9	−12
Submodel 2b (threshold = 5)	1.88 (1.35–2.59)	1.81 (1.29–2.53)	76.7	15

From Table 4, it can be observed that compared to the baseline algorithm, even with step angle adjustments, the Lowest Contour Line Algorithm still demonstrates significantly higher mission reliability, while vehicle layout quantity fluctuates within ≤3%. Computational time decreases by 40% when the step angle is increased.

Under different circuit-breaker thresholds, the reliability advantage of the Lowest Contour Line Algorithm remains robust: When threshold = 5, the vehicle layout quantity increases by 2.1%, but computational time rises by 15%. When threshold = 3, the layout quantity decreases by 1.5%, while computational time is reduced.

Algorithm flow

Based on the aforementioned fundamental elements, the layout flow of the Lowest Contour Line Algorithm is as follows:

Based on the given layout space information and vehicle data, determine the layout region, the pole, the polar axis, and other relevant parameters.

Identify the lowest contour line.

Advance the scanning line by a given angular step $Δ$ .

Determine the intersection point between the scanning line and the lowest contour line.

Using the intersection point as a reference, deploy vehicles according to the transition degree.

Evaluate whether the vehicle layout meets the specified spatial requirements—including those between vehicles and between vehicles and the environment. If the layout is valid, record the position and vehicle data; otherwise, discard this intersection point and continue stepping.

Update the relevant information according to the definitions of transition degree and circuit breaker.

If the transition degree is reset, update the lowest contour line.

Repeat the above steps until the algorithm’s energy reaches the threshold, triggering the circuit breaker mechanism and terminating the algorithm.

Results

In order to demonstrate the practicality of the Lowest Contour Line Algorithm and to show that its generated layout scheme offers higher sortie mission reliability compared to other layout algorithms, this section applies the Lowest Contour Line Algorithm, the Lowest Horizontal Line Algorithm, the grid method, and the lane method to the same problem, each producing 10 distinct layout schemes. Meanwhile, the quantity of vehicles laid out in each layout scheme is recorded, and the sortie mission reliability for each scheme is calculated using the method in Shi et al.⁷

Experimental setup

Given a rectangular layout space with a length of 50 m and a width of 20 m; along its wide side there is an exit, that is, 4 m wide, with the center of the exit aligned with the midpoint of that side. Currently, there are three types of vehicles, with the vehicle information provided in Table 5. The requirements are that the minimum straight-line distance between a vehicle and the exit is 3 m, the minimum safety distance between vehicles is 0.5 m, and the minimum safety distance between vehicles and the environment is 0.5 m.

Table 5.

Information on each vehicle type.

Vehicle type	Length (m)	Width (m)	Quantity	Turning radius (m)
1	5	2.5	30	6
2	4	2	30	5
3	3	1.5	30	4

To ensure a fair comparison, all algorithms were evaluated under identical constraints, layout spaces, vehicles’ datasets, and comparable parameter-tuning procedures.

For each algorithm, 10 independent layout schemes were generated using different random seeds; all reported results are the averages over these 10 runs. The Wilcoxon rank-sum test was employed to assess statistical significance between algorithms (ρ < 0.05 was considered significant). Reliability of sortie mission was then computed for each layout under two failure-rate intervals, 0%–1% and 1%–10%. The low failure rate interval (0%–1%) represents normal operating conditions with regular maintenance, consistent with typical failure rates of military and emergency-response vehicles in routine use. The high failure rate interval (1%–10%) corresponds to harsh operating conditions such as extreme weather, battlefield environments, and aging vehicles, in line with failure rates reported in field operations.

Lowest Contour Line Algorithm

Using the proposed Lowest Contour Line Algorithm, a layout for the problem described in Section 3.1 was generated, with a step angle of $Δ$ = 0.15 and a fuse threshold of 4. Ten layout schemes were generated using the Lowest Contour Line Algorithm. The number of vehicles laid out in each scheme is shown in Figure 6.

Figure 6.

Vehicle quantity chart for each layout scheme under the Lowest Contour Line Algorithm.

It can be seen from the above charts that the layout schemes obtained using the Lowest Contour Line Algorithm have an average vehicle layout quantity of 75.1, with a maximum of 78 and a minimum of 70. At the same time, the sortie mission reliability for each layout scheme is calculated, as shown in Figures 7 and 8.

Figure 7.

Sortie mission reliability graph of Lowest Contour Line Algorithm under low failure rates (0%–1%).

Figure 8.

Sortie mission reliability graph of Lowest Contour Line Algorithm under high failure rates (1%–10%).

Lowest Horizontal Line Algorithm

Using the Lowest Horizontal Line Algorithm to layout the problem described in Section 3.1. Ten layout schemes were generated using the lowest horizontal algorithm. The number of vehicles laid out in each scheme is shown in Figure 9.

Figure 9.

Vehicle quantity chart for each layout scheme under the Lowest Horizontal Line Algorithm.

It can be seen from the above charts that the layout schemes obtained using the Lowest Horizontal Line Algorithm is 74.8, with a maximum of 81 and a minimum of 71. At the same time, the sortie mission reliability for each layout scheme is calculated, as shown in Figures 10 and 11.

Figure 10.

Sortie mission reliability graph of Lowest Horizontal Line Algorithm under low failure rates (0%–1%).

Figure 11.

Sortie mission reliability graph of Lowest Horizontal Line Algorithm under high failure rates (1%–10%).

Figure 10 shows that at a low failure rate (0.5%), the average reliability is only 0.9584, which is attributed to the linear arrangement of vehicles in the exit area (Figure 1(a)), resulting in a significant chain reaction effect of failures. When the failure rate increases to 5%, the average reliability sharply drops to 0.4113, validating the vulnerability of the serial vehicle layout.

Grid method

Using the grid method to layout the problem described in Section 3.1. Ten layout schemes were generated using the grid method. The number of vehicles laid out in each scheme is shown in Figure 12.

Figure 12.

Vehicle quantity chart for each layout scheme under the grid method.

It can be seen from the above charts that the layout schemes obtained using the grid method is 74.6, with a maximum of 78 and a minimum of 68. At the same time, the sortie mission reliability for each layout scheme is calculated, as shown in Figures 13 and 14.

Figure 13.

Sortie mission reliability graph of grid method under low failure rates (0%–1%).

Figure 14.

Sortie mission reliability graph of grid method under high failure rates (1%–10%).

The grid method inherently leads to spatial waste due to mismatches between vehicle dimensions and fixed grid divisions. Additionally, grid boundaries restrict vehicle steering paths, resulting in an average reliability of merely 0.4277 under high failure rates (5%).

Lane method

Using the lane method to layout the problem described in Section 3.1. Ten layout schemes were generated using the lane method. The number of vehicles laid out in each scheme is shown in Figure 15.

Figure 15.

Vehicle quantity chart for each layout scheme under the lane method.

It can be seen from the above charts that the layout schemes obtained using the lane method is 74.6, with a maximum of 77 and a minimum of 72. At the same time, the sortie mission reliability for each layout scheme is calculated, as shown in Figures 16 and 17.

Figure 16.

Sortie mission reliability graph of lane method under low failure rates (0%–1%).

Figure 17.

Sortie mission reliability graph of lane method under high failure rates (1%–10%).

The lane strategy simplifies the overall layout by separating traffic, yet the vehicles inside each lane remain serially dependent. At a low failure rate of 0.5%, its average reliability is 0.9340, lower than the 0.9868 achieved by the Lowest Contour Line Algorithm.

Summary of experimental results

Across all forty layout schemes generated by four algorithms, the key findings are:

The Lowest Contour Line Algorithm achieves the highest average number of placed vehicles (75.1), which is 0.4% higher than the Lowest Horizontal Line Algorithm (74.8), and 0.7% higher than the grid method and lane method (74.6), with a 95% confidence interval of (−0.2, 0.8), which is not statistically significant (ρ = 0.58).

Under low failure rates (0.5%), the average reliability of the proposed algorithm is 0.9868, which is 2.9% higher than the Lowest Horizontal Line Algorithm (0.9584), 2.4% higher than the grid method (0.9632), and 5.3% higher than the lane method (0.9340), with a 95% confidence interval of (1.7%, 3.9%), which is statistically significant (ρ = 0.003).

Under high failure rates (5%), the average reliability of the proposed algorithm is 0.4716, which is 14.7% higher than the Lowest Horizontal Line Algorithm (0.4113), 9.2% higher than the grid method (0.4277), and 29.4% higher than the lane method (0.3644).

Discussion

In the previous section, by utilizing the Lowest Contour Line Algorithm, the Lowest Horizontal Line Algorithm, the grid method, and the lane method to solve the same problem, a total of 40 layout schemes were obtained. At the same time, relevant data concerning the number of vehicles in the layouts and the sortie mission reliability for each algorithm’s generated layout scheme were briefly described. This section will compare the four algorithms based on the corresponding data sets.

First, based on the data from Figures 6, 9, 12, and 15, a comparison chart of vehicle quantity for the four layout algorithms has been plotted, as shown in Figure 18. From Figure 18, it can be observed that the Lowest Contour Line Algorithm yields the highest average number of vehicles; its maximum value is second only to that of the Lowest Horizontal Line Algorithm, and its minimum value is not the lowest among the four layout methods.

Figure 18.

Vehicle count comparison among four layout algorithms.

Next, based on the data from Figures 7, 10, 13, and 16, a comparison chart of the average sortie mission reliability of the four layout algorithms under low failure rates (0%–1%) has been plotted, as shown in Figure 19. From Figure 19, it is evident that under low fault rate conditions, the Lowest Contour Line Algorithm exhibits a significantly higher average sortie mission reliability compared to the other three algorithms.

Figure 19.

Comparison chart of the average sortie mission reliability for the four layout algorithms under low failure rates (0%–1%).

Finally, based on the data from Figures 8, 11, 14, and 17, a comparison chart of the average sortie mission reliability of the four layout algorithms under high failure rates (1%–10%) has been plotted, as shown in Figure 20. It can be observed from Figure 20 that under failure rates of 1%–5%, the Lowest Contour Line Algorithm still achieves a higher average sortie mission reliability than the other three algorithms. Although, starting from a failure rate of 5%, the sortie mission reliability of the Lowest Contour Line Algorithm gradually converges with that of the other three algorithms, it still manages to maintain a certain advantage.

Figure 20.

Comparison chart of the average sortie mission reliability for the four layout algorithms under high failure rates (1%–10%).

As shown in Figure 18, the number of units layout out by the Lowest Contour Line Algorithm does not differ significantly from that of the baseline algorithms. This result stems from equivalent space-filling efficiency: the contour-update mechanism in the proposed method follows the same “fill the smallest available space first” logic. Unlike the baselines, however, the filling direction is radial rather than linear. Therefore, the theoretical maximum space utilization achievable by the Lowest Contour Line Algorithm is identical to that of the baseline methods.

The reliability improvements observed in Figures 19 and 20 are not incidental experimental artifacts, but rather arise from a fundamental architectural difference between polar layouts and traditional Cartesian linear layouts. In Cartesian layouts, vehicles form a continuous queue aligned with the exit, which is prone to serial congestion. In contrast, the polar arrangement of the Lowest Contour Line Algorithm provides each unit near the exit with a direct path, thereby localizing the impact of failures. This is the core reason for the reliability gain and is consistent with classical queueing theory: under equal throughput, parallel channels are more stable than serial ones.

Moreover, the reliability advantage of the Lowest Contour Line Algorithm increases as the vehicles’ failure rate rises. This aligns with the “weakest-link effect” inherent to baseline layouts: at low failure rates, the probability of any single failure is small and layout differences are minor; as the failure rate increases, the likelihood of failures grows super-linearly, making the proposed algorithm markedly superior. This finding indicates that the Lowest Contour Line Algorithm is particularly suitable for high-risk scenarios such as battlefield deployment and maritime disaster relief.

It should be noted, however, that the applicability of the Lowest Contour Line Algorithm is currently limited. The most appropriate scenarios involve layout spaces with a single exit, such as compartments of landing ships or roll-on/roll-off vessels and maritime emergency rescue situations. For multi-exit layout spaces, future work will extend the placement mechanism to accommodate more complex boundary conditions.

Conclusions

To address the sortie mission reliability challenges in the domain of vehicle layout, this study proposed a layout algorithm that focuses on sortie mission reliability—namely, the Lowest Contour Line Algorithm. The development of this algorithm is intended to overcome the limitations of traditional methods and provide a more efficient solution strategy for layout problems.

The Lowest Contour Line Algorithm introduces a polar coordinate system as a substitute for the Cartesian coordinate system, thereby simplifying the calculation of vehicle positions and facilitating the understanding of their relative spatial relationships. The algorithm first determines the pole and polar axis of the layout space, and then, based on factors such as the safe distance between vehicles and the safe distance between vehicles and the environment, establishes the initial contour line. As a scanline continuously sweeps through the layout space, it intersects the contour line to form a set of intersection points that represent potential locations for vehicle layout. The algorithm also defines a “transition degree” to ensure that the vehicles maintain a consistent orientation, and it dynamically updates the contour line based on the transition degree and the positions of vehicles already laid out. Additionally, a fuse mechanism is incorporated to guarantee the proper termination of the algorithm.

The complete algorithmic process involves steps including determining the layout area, identifying the lowest contour line, stepping the scanline, evaluating intersection points, laying out vehicles, updating information and contour lines, and continuing these steps until the fuse mechanism triggers termination. Furthermore, to assess the practical effectiveness of the Lowest Contour Line Algorithm, this study conducted a comparative analysis with several widely used methods, including the Lowest Horizontal Line Algorithm, the grid method, and the lane method. The experimental results indicate that: the polar-coordinate-based spatial arrangement framework effectively improves the sortie mission reliability of shipborne vehicles; core mechanisms such as contour-line updating ensure both compactness of the layout and the effectiveness and efficiency of the algorithm; and under identical scenarios, the proposed algorithm increases sortie mission reliability by 3%–29% compared with baseline methods, while preserving space utilization.

It is well known that perfecting an algorithm is a continuous process of iteration and optimization. Accordingly, future work will focus on reducing the computational complexity of the algorithm in large-scale scenarios and integrating it with other artificial intelligence techniques. Combining the Lowest Contour Line Algorithm with heuristic methods, intelligent optimization algorithms, and artificial neural networks is expected to enhance its capability in handling special-shaped vehicles and complex layouts. At the same time, we will explore the algorithm’s potential applications in other fields, with the hope of expanding its application scope and providing efficient solutions to a wider range of practical problems.

Footnotes

Acknowledgements

The authors would like to thank the associate editor and all the reviewers for their constructive suggestions.

Handling Editor: Aarthy Esakkiappan

ORCID iD

Han Shi

Author contributions

Conceptualization, H.S. and N.W. Methodology, H.S. and Q.L. Software, H.S. Validation, H.S. Formal analysis, H.S. Investigation, H.S. Resources, H.S. and N.W. Data curation, H.S. Writing—original draft preparation, H.S. Writing—review and editing, H.S. Visualization, H.S. Supervision, N.W. Project administration, Q.L. Funding acquisition, Q.L. All authors have read and agreed to the published version of the manuscript.

Funding

The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was funded by the Central University Basic Research Business Fund Project of Harbin Engineering University under grant no. 3072021CFJ0707.

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Data availability statement

The original contributions presented in the study are included in the article; further inquiries can be directed to the corresponding author.

References

Mohril

Solanki

Majumdar

, et al. Novel selective maintenance approach to ensure mission reliability of armored vehicles considering multiple deployment roles in distinct operating profiles. Def Sci J 2024; 74(4): 447–459.

Dong

Zhang

. Research status and development suggestions of high mobility multi-functional emergency rescue equipment. IOP Conf Ser Earth Environ Sci 2018; 252: 032153.

Sun

Zhang

, et al. Research on cold chain logistics transportation scheme under complex conditional constraints. Sustainability 2023; 15(10): 8431.

Longhorn

Muckensturm

Florek

. Determining the optimal mix of theater vehicles during military sustainment operations. Mil Oper Res 2025; 30(1): 2025.

Long

Sun

, et al. Collaborative vehicle dispatching for resilient and fair emergency response. In: 2021 IEEE international conference on industrial engineering and engineering management (IEEE IEEM21), Singapore, Singapore, 13–16 December 2021, pp.22–36. New York: IEEE.

, et al. Assessing mission reliability for unmanned aerial vehicle system in the face of uncertain shocks. Arab J Sci Eng 2024; 50: 15473–15486.

Shi

Wang

Liu

. Calculation method for sortie mission reliability of shipborne unmanned vehicle group. J Mar Sci Eng 2024; 12(8): 1309.

Pusia.

. Optimal stowage on Ro–Ro decks for efficiency and safety. J Mar Eng Technol 2021; 20(1): 17–33.

Zhao

, et al. A novel improved hybrid particle swarm optimisation based genetic algorithm for the solution to layout problems. In: 2014 11th World Congress on intelligent control and automation (WCICA), Shenyang, China, 29 June–4 July 2014, pp.54–98. New York: IEEE.

10.

Neuenfeldt

Silva

Francescatto

, et al. The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview. Comput Oper Res 2021; 137: 105521.

11.

Hansen

Fagerholt

Stalhane

, et al. An adaptive large neighborhood search heuristic for the planar storage location assignment problem: application to stowage planning for roll-on roll-off ships. J Heuristics 2020; 26(6): 885–912.

12.

Sun

Luan

. Amphibious vehicle layout optimization based on adaptive elite genetic algorithm. In: 2019 IEEE international conference on mechatronics and automation (ICMA), Tianjin, China, 4–7 August 2019, pp.110–122. New York: IEEE.

13.

Guo

Zhang

, et al. Efficient 2D irregular layout by vector superposition NFP and mixed-integer programming. Expert Syst Appl 2023; 230: 120548.

14.

Zhang

Tian

, et al. A two-phase stowage approach for passenger–cargo RoRo ship based on 2D-KP: coping with complex rotation and safe navigation constraints. IEEE Access 2020; 8: 95807–95822.

15.

Guo

Zhang

, et al. Two-dimensional irregular packing problems: a review. Front Mech Eng 2022; 8: 966691.

16.

Luo

Zhou

. An improved differential evolution algorithm combined with vector NFP and mixed-integer programming for solving 2D irregular layout problem. Expert Syst Appl 2025; 298(Pt A): 129621.

17.

Choi

Woo

. An optimization method of spatial placement for effective vehicle loading. J Korea Inst Inf Commun Eng 2020; 24(2): 186–191.

18.

Zhang

Yao

Zhang

, et al. A block-based heuristic search algorithm for the two-dimensional guillotine strip packing problem. Eng Appl Artif Intell 2024; 134: 108624.

19.

Ovstebo

Hvattum

Faherholt

. Optimization of stowage plans for RoRo ships. Comput Oper Res 2011; 38(10): 1425–1434.

20.

Zhai

Jin

Yan

, et al. Heuristic-based vehicle arrangement for Ro–Ro ships. Sci Rep 2025; 14(1): 30889.

21.

Bezerra

VMR

Leao

AAS

Oliveira

, et al. Models for the two-dimensional level strip packing problem—a review and a computational evaluation. J Oper Res Soc 2019; 71(4): 606–627.

22.

Bui

Baker

Barlow

, et al. A grid-based heuristic for two-dimensional packing problems. In: 2011 IEEE Congress on evolutionary computation (CEC), New Orleans, LA, USA, 5–8 June 2011, pp.54–63. New York: IEEE.

23.

Schwiddessen

. A semidefinite approach for the single row facility layout problem. In: Operations research proceedings 2021 (eds Trautmann

Gnägi

), 2022. Lecture notes in operations research. Cham: Springer.

24.

Chehrazad

Roose

Wauters

. A fast and scalable bottom-left-fill algorithm to solve nesting problems using a semi-discrete representation. Eur J Oper Res 2022; 300(3): 809–826.

25.

Liu

. A weighted surplus rectangle algorithm for rectangle packing problem. In: 2024 43rd Chinses control conference (CCC 2024), Kunming, China, 28–31 July 2024, pp.63–89. New York: IEEE.

26.

Hougardy

Zondervan

. The bottom-left algorithm for the strip packing problem. In: Combinatorial algorithms (IWOCA 2024) (eds Rescigno

Vaccaro

), Ischia, Italy, 1–3 July 2024. Lecture notes in computer science, vol. 14764. Cham: Springer.

27.

Zhu

Shi

. A heuristic approach to stowage planning for ro-ro ships. In: Proc. SPIE 13064, Seventh International Conference on Traffic Engineering and Transportation System (ICTETS 2023), 20 February 2024, p. 1306421. https://doi.org/10.1117/12.3015799.

28.

Sun

Wang

, et al. A semi-automated approach to stowage planning for Ro–Ro ships. Ocean Eng 2022; 247: 110648.

29.

Shi

Wang

, et al. Reliability calculation method of shipborne vehicles’ sortie mission for dynamic network structure. Comput Intell Neurosci 2022; 2022: 8547961.

30.

Liu

Hua

, et al. Optimizing two-dimensional irregular packing: a hybrid approach of genetic algorithm and linear programming. Appl Sci 2023; 13(22): 12474.

31.

Wei

Wang

. Two-dimensional layout algorithm for improving the utilization rate of rectangular parts. Appl Sci 2026; 16(2): 1042.

32.

Belge

Altan

Hacıoğlu

. Metaheuristic optimization-based path planning and tracking of quadcopter for payload hold-release mission. Electronics 2022; 11(8): 1208.

33.

Altan

Hacıoğlu

. Model predictive control of three-axis gimbal system mounted on UAV for real-time target tracking under external disturbances. Mech Syst Signal Process 2020; 138: 106548.