key: cord-0047499-7rrtlfwr authors: S S, Vinod Chandra; Anand Hareendran, S.; S, Saju Sankar title: Multi-objective Particle Swarm Optimisation for Cargo Packaging in Large Containers date: 2020-06-22 journal: Advances in Swarm Intelligence DOI: 10.1007/978-3-030-53956-6_37 sha: 2b1d5b1cb38652166a0be9761720665536bdc741 doc_id: 47499 cord_uid: 7rrtlfwr Cargo management in all mode of transports like airlines, ships and trucks is a challenging task. The way in which an optimal allocation of packages in different containers are done using a software controlled method. An agent based software module is enabled as a service for the optimum allocation of cargo packages in the container terminals. There are multiple factors that will affect this allocation - size, shape, weight of the cargo packets and the container. When we design an optimal allocation module in a software these components need to be addressed along with capacity of the container. Hence, a multi-objective optimization algorithm will improve the performance of cargo management software. In this paper we suggest a Mixed Species Particle Swarm Optimisation (MSPSO) procedure for optimal allocation of cargo packages in containers of different size and capacity. The redesigned version of cargo management software performs well with search space on normal time complexity. The simulated results gives an improved optimised allocation than normalised allocation of cargo packets. The improved implementation performed better in terms of efficient cargo package allocation. Optimised placement of cargo packets in containers is a challenging task. This is because size, shape and weight of the cargo packets are different. It is also noted that there may be difference in size, shape and capacity of the current selected container. When multiple containers are loaded in a terminal for shipment and different category cargo packers are trying to load, efficiency is a major concern [1] . This problem can be treated as a multi-objective task because more than one objective need to be considered while cargo packets are placed in a container. The size, shape and weight of the cargo packets as well as container are considered in the optimisation phase. Capacity of the container is also a major factor. Hence, space allocation in a container for each cargo packet is considered as a multiobjective optimal allocation problem. To make cost-effective cargo carrier operations, a major challenge is to make profitable packing. There is a software controlled mechanism, which handle this work effectively. If this software is built as an optimised model, then the costeffective performance can be increased. The agent based techniques are useful in optimum allocation of packets or in load balancing of the container. Genetic algorithm and Smell detection based optimum allocation techniques are making fruitful solution to this problem [2] [3] [4] . These agents generates single optimum solution by an objective function after operating a sequence of steps. But such intelligent agents cannot handle more than one objectives and cannot combine to form an optimised output. The cargo packets management in multiple containers is treated as multi-objective problem as we consider multiple sources (cargo packets in different size) and multiple destinations (containers in different shipment terminals). There are optimised models which helps effective cargo management softwares [5, 6] . The model works using integer linear programming based approach for effective load balancing. It is operated as a single objective optimisation technology. A multi-objective honey bee algorithm can be used to solve optimisation problems [7, 8] . Multi-objective honey bee algorithm shows dynamic and distributed computing behaviour of honey bees at separate colonies in meeting various resources for meeting their demands at individual destinations by maximising the profit [8] . The multi-objective optimisation technique is effectively used in multi-dimensional transportation problems. In this paper, we have addressed the cargo management problem using a multi-objective particle swarm optimisation technique. Our technique is focused in multi-objective optimisation for both the cargo as well as its container. The proposed model is referred as Mixed Species Particle Swarm Optimisation (MSPSO). Mixed species flocks preserve the principle of collision avoidance, velocity matching and flock cantering as followed by the single species flock. The individuals keep a distance from neighbours such that they don't plunge at others. They try to match the velocity of neighbours so that they do not fall out of the group and also try to move towards centre of the flock [9] . Figure 1 depicts the fleet of mixed species flocks of Rooks and Jackdaws with circles indicate paired a flight of Jackdaws. A mathematical model is derived from the mixed species flocking of birds. N species are assumed to flock together. Each species is expected to optimally arrive at the respective objectives. Same numbers of birds from each species participate in the flocking. Each bird is considered as a particle, x which occupy a random position in the search domain S n as specified by x ← random(s n ). All particle species has an initial velocity, which is assigned randomly. Each species has a limiting factor in curbing the maximum limit that is V max (N ) for each species N. V max (N ) and V min (N ) are determined such as to permit fair movement of a particle in the search domain. Too small value of V (N ) leads to slow convergence and too high value causes the particle move fly out of the search domain. Each species N is assigned objective function f (x(N )). Objective function is specified as Eq. 2 x ∈ X, f : In multi-objective optimisation, there is not an optimal solution which minimises all objective functions simultaneously. The objective is to determine Pareto optimal solutions which cannot improve any objective without degrading other objectives. The Pareto optimal set is determined for a specific multi-objective optimisation problems should be closer to true Pareto front and also should preserve the diversity of solutions. These two conditions are contradictory -when tried to preserve diversity, converge speed is reduced. Mixed species population has to be controlled in such a way that the species span over the entire solution space. The presence of local optimum with in specific neighbourhood has a significant effect on the quality of Pareto front determined. Considering all these parameters a mathematical model based on mixed species flocking for multi-objective optimisation is proposed. This model has five significant stages. There is a basic optimisation algorithm which controls the fleet of particles in the search space and has an enumeration for detecting the global best particle of the mixed species population [10] . To preserve the diversity of solution set and to evade premature convergence due to various local optimum solutions, dynamic adaptations are made to mixed species population. Procedure for particle depletion and particle augmentation that handles such issues. In order to obtain Pareto efficiency closer to the true optimum, a solution ranking scheme is also used which makes use of a tree heap data structure which avoids an additional external repository for storage of the partial solutions as used by particle swarm based multi-objective optimisation algorithms. Loading of cargo packets in a container is not an issue but optimally inserting these packets are very hard. This problem is a two dimensional problem that have more than one objective of packing like (1) maximum of I cargoes with width W and height H, (2) J items with w j ≤ W, h j ≤ H and weight ξ i . The objectives are (1) minimise the number of cargoes used K and (2) minimise the average deviation between the overall centre of gravity and the desired one. Usually the packets are placed randomly or placed one by one but not optimally placed. To solve the problem using multi-objective PSO, first we have to initialise the particles. In this work, we have to use solution from Bottom Left Fill (BLF) heuristic. To sort the rectangles for bottom left fill, according to some criteria like width, weight, area, perimeter etc. These criteria are aimed as objectives and the problem enters to a multi-objective problem. For an optimised output from these objectives create a multi-objective optimisation problem. Figure 2 gives the initialisation of bottom left fill. The items are moved to the top if intersection detected at the right. Figure 3(a) shows an item moved to the top if intersection detected at the right. In Fig. 3(b) , the item moved if there is a lower available space for an insertion. Now the optimisation part is required to explore. In the PSO, velocity depends on either pbest(PB) or gbest(GB), never both at the same time. Figure 4 gives two different solution options. We have to use the above multi-objective PSO procedure included into the cargo packing procedure. There are three stages in this procedure. In first stage of the procedure a partial swap between 2 cargoes followed by merge 2 cargoes then split 1 cargo. In the second stage randomly rotate the boxes in to the cargo and in the third stage a random shuffle is carried. Procedure for a particle the mutation modes are given below. Start of mutation If the probability < 0.33 then partial swap between 2 cargoes If the probability between 0.33 and 0.66 then merge last filled two cargoes into 1 cargo If the probability > 0.66 then split one cargo into 2 cargoes Rotate boxes in the cargo Intra cargo shuffle End mutation Procedure that included in a hybrid multi-objective PSO is proposed to solve cargo packing problem is given below 1. Build initial population 2. Cost function evaluation 3. Fitness sharing 4. Tournament selection 5. Generation of velocity vectors 6. Update position of particle in solution space 7. Mutation evaluation 8. Preservation of non-dominated particle in archive 9. If stopping criteria is not met go to step 2 10. End procedure The multi-objective optimisation procedure for cargo packing is establishing the fitness of all particles and to stimulate the particle progress towards optimal locale, method to determine the globally best particle, method for particle depletion, procedure for particle augmentation and a routine for solution ranking. The process is repeated for Max number of iterations so that the particles move to their global optimal positions to optimise respective objective functions. In our simulated inputs, there are 8 classes with 50 instances randomly generated with a size range: The proposed method is capable of evolving more optimal solution and its computational efficiency is good with a stopping function after 1000 iterations or no improvement in last 5 generations. This optimisation algorithm is a robust search optimisation algorithm that can create of variable length data structure with specialised mutation operator. The proposed algorithm performs consistently well with the best average performance on the performance metric. The simulated results for 1000 cargo packets of different size and weight is loaded in containers of different size and capacity is tested. Optimum allocation efficiency of the proposed method is given in Table 1 . Result shows the efficiency of cargo packet allocation in containers drastically improved when size and capacity of the container and cargo packets are different. This is because, the power of multi-objective optimisation PSO. A problem with N objective functions and P particles in the search space, the computational complexity is linear and has O(NP) complexity. It is further reduced as the non-dominated solutions are stored in heap tree where the worst case search complexity is only in terms of O(n) where n is the size of solution set required. The space complexity is O(n) which is the property of heap tree used for the storage of approximation set. This method is a strong prospect to be used for general multi objective optimization problem. Population based approach follows the trajectory of global best particle to obtain the pareto dominant solution set. Software can be designed by integrating a module that uses a parallel optimization technique. Proposed model performs well with search space discontinuous optimal regions also. It also performs well on non-separable problems with multiple local optima. But there are a few limitations also. Application of the method to practical optimization problems requires the adaptation of parameters as per specific problem. Solving a load balancing problem with a multi-objective particle swarm optimisation approach: application to aircraft cargo transportation Air cargo scheduling using genetic algorithms Smell detection agent based optimization algorithm Application of smell detection agent based algorithm for optimal path identification by SDN controllers Shipping optimisation systems (SOS): liner optimisation perspective Gaming rail cargo management: exploring and validating alternative modes of organization Multi dimensional honey bee foraging algorithm based on optimal energy consumption Multi modal foraging by honey bees toward optimizing profits at multiple colonies An approach using particle swarm optimization and rational kernel for variable length data sequence optimization The particle swarm: social adaptation of knowledge We thank to Girish Chandran, CEO of Kefi Tech Solutions, Technopark, Thiruvananthapuram for the help and test assistance that he had offered even between his busy schedule for data analysis and knowledge transfer phase.