# Research on Path and Sequence Planning for Multi-Cabin Onboard Transportation of Large Cruise Ships
## 3 Improved A-Star Algorithm Designing
### Reverse Planning Strategy for Cabin Transport Sequence Optimization  
Due to the complexity of the ship's internal structure and the density of the cabins, cabin blockage is a common issue. As a result, the determination of the optimal transport sequence is significantly influenced by the ship's spatial layout. Given that in a multi-cabin transport process, earlier cabins are likely to obstruct later ones, thus affecting the optimal transport paths of all subsequent cabins, the reverse planning strategy is proposed as a suitable method for determining the transport sequence of large cruise ship cabins. The core idea of the reverse planning strategy is to reverse the entire cabin transport timeline. This means assuming that all cabins have already been placed inside the ship, and then transporting them from their respective end points back to their starting points, according to a principle whereby no two cabins interfere with each other's movement. When selecting cabins, priority is given to those that will not cause blockages during the transportation process, and further selection is made to identify those that can be installed in parallel, enabling fast follow-up transport. Once a batch of cabins has been fully transported, the next batch is selected and moved, continuing until all cabins have been transported. Thus, the reverse planning strategy not only determines the transport sequence of all cabins without affecting the optimal transport path, but also shortens the time gap between preceding and subsequent tasks, which ultimately helps to reduce the overall construction time. Selection Principle for Removable Cabins  
Since the reverse planning strategy involves treating all cabins that have not yet been removed as grid obstacles in the grid map, the first step is to select the cabins that can currently be removed. Using the improved A-Star algorithm, the shortest transport path for each cabin is optimized. From these, cabins that will not cause blockage during transport are selected as the removable cabins. Once the removable cabins are determined, the shortest transport time for these cabins is calculated. If there are cabins whose transport time remains unchanged, these are prioritized as installable cabins. The specific process for selecting removable cabins is shown in Figure 5.  
Selection Principle for Installation  
To ensure the safe installation of the cabins, a certain safety distance must be maintained around each one during installation. This means that while installing the current cabin, no other cabins can be moved into the surrounding area. Therefore, when selecting cabins for installation, it is essential not only to consider whether the shortest transport time of the current cabin remains unchanged, but also to verify that a sufficient safety distance exists between the current cabin and other cabins that are ready for transport. It is also important to note that there is a maximum limit to the number of cabins that can be installed simultaneously within the entire transport area. The selected cabins for installation cannot exceed this maximum limit. This ensures that the installation process remains within the  
Figure 5: Selecting the cabins that can be removed. available space and adheres to the operational constraints, thus avoiding potential conflicts and optimizing the overall workflow. The specific process for selecting cabins for installation is shown in Figure 6.  
(3) Selection Principle for Transportation  
Once all the selected cabins for installation have been installed, the next step is to select cabins from the installed ones for transportation. It is important to note that there is a maximum limit to the number of cabins that can be transported at the same time within the entire transportation area. Therefore, the number of cabins being transported simultaneously cannot exceed this limit.