Academic Journal of Science and Technology ISSN: 2771-3032 | Vol. 10, No. 2, 2024 78 Ship Emergency Material Allocation Model Based on NSGA-II Algorithm Jialin Yang* The Twentieth Research Institute of China Electronics Technology Group Corporatio, Xi’an, 710000, China * Corresponding author: yangjialin97@126.com Abstract: The process of ship material resupply is studied to illustrate the importance of the material resupply process; the common emergency material scheduling problem is compared with the material resupply problem to analyze the similarities and differences; analogous to the part of the emergency material scheduling problem to design the material resupply algorithm, and finally, a material resupply mission is taken as an example to use this paper's algorithm for solving the model and verifying the feasibility of the algorithm. Keywords: Modeling, maritime resupply, transportation scheduling, nsga-ii. 1. Introduction Materiel is an important factor affecting the maneuverability and endurance of large ship formations, and also determines the success or failure of certain ocean missions to a certain extent. A reasonable resource allocation and material supply program can provide critical material supplementation for the fleet, reduce the risk factor and improve the success rate of ocean missions. Traditionally, the logistic and material protection for the fleet of ocean-going missions only relies on the experience of the decision makers to formulate the shore-based protection program, which has the problems of low efficiency and high cost of material protection. Ship formation in the implementation of ocean- going combat missions, some of the tasks of the material needs before the trip can be predicted, but there will still be sudden combat missions lead to some of the fleet's material emergency, and rely on the shore-based material security program is obviously unable to meet the urgent requirements of the ship formation of the material. Although the integrated supply ship can implement the accompanying supply for the fleet, but relying solely on the integrated supply ship is often difficult to sudden large quantities of material needs. When there is a sudden lack of supplies, the comprehensive supply ship to return to the shore base for material re-supply obviously can not meet the time requirements, at this time, as a shore base and the fleet of ships transfer station of the maritime transport fleet, as a maritime logistics center, greatly shorten the comprehensive supply ship to carry out the time of the material replenishment. For the fleet of ships carrying out tasks in distant oceans, the sea transportation fleet is an essential part of the material replenishment link. Constructing the sectional relay material replenishment mode with the sea transportation fleet as the intermediate station can greatly enhance the material replenishment efficiency and shorten the material replenishment time, the specific replenishment process is shown in Figure 1. Figure 1. Segmented relay replenishment model. The process of replenishment through the transportation team can be called the process of "material resupply", and the problem of material resupply can be defined as the replenishment of the integrated supply ship or combat ship by assigning the appropriate transportation ship to the appropriate route according to the material demand, the availability of the transportation fleet and so on, with the goal of shortening the time of transportation and replenishment and reducing the risk of transportation, and completing the resupply of the integrated supply ship under the condition of reducing the transportation cost as much as possible. The goal is to shorten the transportation and supply time as much as possible and reduce the transportation risk, so as to complete the re-supply of the comprehensive supply ship under the condition of reducing the transportation cost as much as possible. At present, most of the scholars mainly focus on expanding the TSP problem[1][2][3] for the research of the sea supply problem, only a small part of the scholars 79 mathematically describe the supply process, and only a very few scholars study the process of re-supply of materials. In this paper, the process of material resupply will be studied, combined with the special needs of maritime transport scheduling, to establish a fitting multi-objective optimization model, and select the appropriate algorithm for analysis and solution. 2. Model Analysis Regarding the process of resupply of emergency supplies at sea, to a certain extent, there are similarities with the problem of emergency relief supplies scheduling[4][5] , researching and analyzing the emergency relief supplies scheduling, and learning the existing research results will have a certain reference value for the research of resupply of emergency supplies at sea. However, the problem of resupply of emergency supplies at sea and the problem of emergency relief supplies dispatch because of the different conditions of the real environment, the need to achieve different goals, there is also a great deal of difference, can not be completely generalized. The following paper will specifically analyze the differences between the two:. Emergency relief material scheduling problem, generally is required to material in accordance with a certain order, the specified types of materials in the specified time to the demand point, most researchers will convert the problem into different categories, the first category is the scheduling problem into the shortest driving path of the study, but also need to take into account the post-disaster road smoothness to the speed of transportation materials caused by the impact of the second category is the material scheduling problem into the The second type is to transform the material dispatching problem into the selection of material supply points, when there are multiple material supply points with different quantities and types of materials, how to select the rescue material supply points; the third type is the distribution of rescue materials[6] , because the rescue behavior requires a large amount of rescue materials in a short time, and the damaged areas are also facing the possibility of suffering from secondary damages, the initial stage of the rescue materials can't completely cover each relief point, which requires the rescuers to make a study on the distribution of rescue materials in different disaster points. The initial phase of relief materials cannot completely cover each relief point, requiring the rescuer to make trade-offs in the allocation of relief materials to different disaster points. In this paper, the maritime emergency supplies resupply problem is studied in the comprehensive supply ship in urgent need of supplies, the transportation fleet to the comprehensive supply ship emergency transportation of supplies process, due to the special nature of the maritime ocean mission, the lack of any material has deepened the dedication of the failure of the ocean mission, so the study of the problem does not need to consider a certain kind of material needs to reduce the distribution of the gap type transportation, the comprehensive supply ship need Therefore, the study of this problem does not need to consider the gap type transportation for a certain material that needs to reduce the distribution. When a comprehensive supply ship or, in some special cases, a ship in a formation makes a demand for supplies, it is necessary to decide how to reasonably assign the transport ship, determine the type and quantity of supplies to be replenished and the transport route, so that the transport task can be completed in the shortest possible time. It can be seen that there is a great similarity between the problem of emergency relief material dispatching and the problem studied in this paper. Since this paper only focuses on the process of "transportation fleet - demand for material ships", the transportation fleet can be likened to the supply point of the emergency relief material scheduling problem, and the demand for material ships can be likened to the disaster point, the researcher needs to take into account the choice of the supply point and the type and quantity of materials, so that the target demand can reach the Optimization. For example, in his research on multi-objective allocation and scheduling of emergency relief supplies, Zhang Guofu takes "the smallest amount of unsatisfied supplies", "the shortest path" and "the best path reliability" as the optimization objectives, while other scholars' optimization objectives are "the best path reliability". The optimization objectives of other scholars are also similar. Unlike the problem of scheduling emergency relief supplies, the problem studied in this paper has its own special environmental background. First of all, due to the transportation fleet itself is both the material supply point and the transportation vehicle, so this paper does not consider the choice of the type of vehicle for transporting materials when studying the problem. Because of this particular condition of sea navigation, so in the transportation route selection, do not need additional planning transportation fleet sailing route, only along the shortest route sailing can be. And the material is the key to determine the ocean voyage mission, unlike the emergency relief material scheduling problem may be due to the interference of the real situation, strategically select some gaps, in this paper, the total amount of material transported by the transportation fleet, at least the total amount of material transported by the transportation fleet, at least should be saturated. Considering the practical application scenarios of the problem in this paper, this paper takes the shortest time and the smallest cost as the goal to establish the multi-objective model. 3. Modeling. 3.1. Scene description Assuming that the fleet of ships carrying out ocean-going missions is in a state of material shortage, the comprehensive supply ship as a supply ship cannot fully meet the material needs of the fleet, and the transportation fleet is urgently needed for material replenishment. At this time, the sea is calm, do not need to consider the sea wind and waves on the transportation fleet sailing speed caused by the impact of the transport fleet at this time the transportation fleet to the integrated supply ship of the access road is also no obstacles to the transportation fleet will not have security concerns and damage hidden danger, the transportation fleet can be unimpeded sailing to the integrated supply ship. Assuming that only one integrated supply ship is deployed for this ocean mission, and there is a fleet of transportation ships that can transport goods to the integrated supply ship, the ship selected for the mission will transport goods equal to the upper limit of its transportation capacity, and the goods needed by the integrated supply ship can be supplied in excess of the amount, but cannot be short of the amount. Then this paper assumes that the resupply of supplies in this scenario is a scheduling problem that contains multiple salvage points, a single 80 demand point (i.e., an integrated supply ship), and multiple types of supplies, which is described as follows: Transportation fleet A has n transportation ships 𝒜 a , a , . . . , a , the resupply rendezvous point is C,; the shipsa The quantity of material j that can be supplied isx ,; the quantity of material j demanded at the demand point isd ,- the sailing distance from the transportation fleet A to the rendezvous point C is s the speed of the ship is sa The speed of the ship isυ , - shipa the cost of transportation of the ship is per sailing unit h (assuming that no cost is incurred during the resupply operation); - the time of the ship's resupply operation is s, - the speed of the ship is sa The resupply operation time of the ship ist (assuming that this time is independent of the type and quantity of supplies), the total time for the completion of emergency supply resupply is T, and the total cost is H. Where the time for the completion of the emergency supply resupply mission is defined as the period from the time the transportation mission is ordered to the time when the last ship completes the resupply mission. 3.2. Objective function Assuming that all feasible transportation fleet planning scenarios areφ , a multi-objective model can be developed as follows: minT α 1 minH α h ∗ s 2 S.t.α ∈ φ The following constraints are also satisfied. ∑ x d (3) It is assumed that the total number of vessels deployed for the emergency resupply mission will be the primary vessel and that the emergency resupply mission will be the primary vessel for the emergency resupply mission. The resupply task completion time T can be calculated as T max t , t . (4) Where equation (1) indicates the minimum time required to complete the entire resupply process, equation (2) indicates the minimum cost required to complete the entire resupply process, and equation (3) indicates that the total amount of material transported by the transportation fleet in the course of resupply should be greater than or equal to the material requirements of the ships to be resupplied. It should be noted that the traditional single-objective approach of simply pursuing one objective leads to the result that the solution scheme deviates from the actual requirements in other objectives. For example, simply pursuing the shortest completion time of the resupply process may result in a much higher and much higher transportation cost, whereas the aforementioned multi-objective optimization has the advantage of maintaining a better balance between multiple objectives as much as possible, i.e., the Pareto optimal solution, to find a solution that is acceptable on all objectives. Moreover, unlike single- objective optimization which only gives a single solution at the end, multi-objective optimization gives a set of Pareto solutions at the end, which increases the choice of the decision maker, who can choose a reasonable solution from the Pareto-solution set according to the actual demand. 4. Solving the Emergency Supply Resupply Problem Based on NSGA- II Algorithm. 4.1. Algorithmic evolutionary process. In this paper, we use the non-dominated sorting genetic algorithm NSGA-II based on -Pareto solution- for To solve, the NSGA-II-algorithm evolutionary flow is[7][8][9] : - (1) - Randomly generate an initial parent population with a population size of -N- - P , and generate an offspring population by genetic operators (crossover, mutation) Q whose population size is also -N.-. (2) - Combine the parent population -P : and the offspring populationQ : merge to form a synthetic population of size - 2N-R ; perform a fast nondominated sorting to reclassify - R all -2N- individuals in it are reclassified by nondominated ordinal number (rank) to obtain the rank -F1;F2;F3......; the local crowding distances of individuals in each nondominated stratum are calculated and sorted, - (3) - N - individuals are selected as the new parent population based on the sorting resultsP . : (4) - Generation of new offspring populations by genetic operators (selection, crossover, mutation) -Q . : (5)- Repeat -(2)- to -(4)- steps until the maximum number of iterations set by the algorithm is reached. : 4.2. Algorithmic application process. (1) Coding method: In NSGA-II algorithm, the chromosome coding methods usually include binary coding and real number coding. In order to be more convenient and easy to use when performing crossover and mutation operations, binary coding is used in this paper. Specifically, a binary vector -x- is used to denote the target allocation scheme, with 1 indicating that the ship is selected to participate in the transportation and 0 indicating that the ship is not selected.... (2) -Initial value assignment: the initial value of a variable is generated by a random function. - (3) -Fitness function: given a virtual fitness value based on the non-dominated sort order, hierarchical sorting, by storing the current solution and all individuals in the population hierarchically, so that the best individuals will not be lost and the population level will be improved rapidly. - (4)-Genetic operator: contains selection operator, crossover operator, mutation operator, selection operator adopts round- robin system to select operator, i.e., randomly select -2 individuals, if the nondominated sorting number is different, then select the individual with small rank of the number; if the number is the same, then select the less crowded individual around it, which can make the evolution towards the direction of nondominated solution and uniform dispersion, crossover operator adopts analog binary crossover operator, and polynomial variation operator is used for the variation operator. (5) -Running parameters: take population size -500, 81 probability of variation -0.1, probability of crossover -0.9, number of running generations -50- . - 4.3. Examples and Analysis of Results. Assuming that a transportation fleet A has 8 transportation ships, the re-supply rendezvous point (i.e., the integrated resupply ship) requires a total of 3 types of supplies, L1, L2, and L3, and the requirements are (20, 19, and 18), respectively. The sailing time, resupply time, cost of each resupply and the quantity of 3 kinds of materials that can be provided by each transportation ship are listed in Table 1. The resupply point bureau fleet is 500 kilometers. It is necessary to plan the ships to be dispatched and the respective quantities of supplies to be provided so that the resupply mission is completed in the shortest possible time and the total cost is minimized. Table 1. Fleet material transportation capacity. a a a a a a a a Speed (m/s) 7 5 6 8 7 5 6 8 Loading and unloading time (s) 6000 6012 6100 6404 6202 5770 6880 6808 (manufacturing, production etc) costs 27 24 23 29 26 24 30 28 L1 loading capacity 5 5 6 9 8 5 9 8 L2 loading capacity 8 3 4 7 6 3 9 7 L3 loading capacity 9 6 6 6 8 6 9 8 Taking the population size of 500, the variance probability of 0.2, and the crossover probability of 0.8, the nsga-ii algorithm is applied to run for 500 generations, and the Pareto optimal solution obtained by the algorithm is shown in Figure 2. Weighing the balance between cost and time, the final choice of transportation ship number isa , anda , , anda and.a . Figure 2. Pareto optimal solution set. 5. Concluding Remarks In this paper, on the basis of elaborating the necessity of resupply at sea, we discuss the problem of resupply at sea for ocean-going fleet and establish a multi-objective planning model for resupply at sea. The NSGA-II algorithm is used to solve the problem of fleet transportation selection in the process of resupply at sea, and reasonable planning is obtained, and the conclusion proves the feasibility of the algorithm. The model and algorithm can help to guarantee the long-time and high-intensity mission requirements of the ship formation. However, at the same time, the selection of validation use cases in this paper is relatively simple, and a larger scale and more data volume should be considered to validate the algorithm in the future. References [1] DONG Peng,HUANG Jiashuai,SHI Huaibin. Research on maritime lateral replenishment planning based on two-stage optimization model [J]. Firepower and Command and Control, 2021, 46(08):64-70. [2] FENG Zhi. Exploration of the Problem of Maritime Supply Guarantee for Ocean-going Ships[J]. China Market. 2021(12):155-156. DOI:10.13939/j.cnki.zgsc.2021.12.155. [3] DONG Peng,WU Chong,YU Peng.Simulation study on sea supply planning for ship formation under Delivery Boy strategy[J]. Journal of Naval Engineering University, 2020, 32(05): 50-54. [4] ZHANG Xia,WANG Huichao,LI Yongtun et al. Research on emergency resource dispatching considering demand under sudden flooding[J]. China Safety Production Science and Technology,2023,19(12):187-192. [5] YUAN Ruiping,WANG Wei,LI Juntao et al. Research on multimodal transportation scheduling of multi-stage emergency supplies under uncertainty[J]. Operations Research and Management,2023,32(06):33-39. [6] LU Jianfeng,HAN Shuang,ZHAO Jiahong. Optimization study of continuous consumption emergency supplies dispatching considering the risk of shortage[J]. Highway Transportation Science and Technology,2023,40(02):246-254. [7] Yusoff Y, Ngadiman M S, Zain A M. Overview of NSGA-II for optimizing machining process parameters[J]. Procedia Engineering, 2011, 15: 3978-3983. [8] Verma S, Pant M, Snasel V. A comprehensive review on NSGA-II for multi-objective combinatorial optimization problems[J]. Ieee Access, 2021, 9: 57757-57791. [9] Seshadri A. A fast elitist multiobjective genetic algorithm: NSGA-II[J]. MATLAB Central, 2 006, 182: 182-197.