Aiming at some shortcomings of the genetic algorithm to solve the path planning in a global static environment, such as a low efficiency of population initialization, slow convergence speed, and easy-to-fall-into the local optimum, an improved genetic algorithm is proposed to solve the path planning problem. Firstly, the environment model is established by using the grid method; secondly, in order to overcome the difficulty of a low efficiency of population initialization, a population initialization method with directional guidance is proposed; finally, in order to balance the global and local optimization searching and to speed up the solution speed, the proposed non-common point crossover operator, range mutation operator, and simplification operator are used in combination with the one-point crossover operator and one-point mutation operator in the traditional genetic algorithm to obtain an improved genetic algorithm. In the simulation experiment, Experiment 1 verifies the effectiveness of the population initialization method proposed in this paper. The success rates in Map 1, Map 2, Map 3, and Map 4 were 56.3854%, 55.851%, 34.1%, and 24.1514%, respectively, which were higher than the two initialization methods compared. Experiment 2 verifies the effectiveness of the genetic algorithm (IGA) improved in this paper for path planning. In four maps, the path planning is compared with the five algorithms and the shortest distance is achieved in all of them. The two experiments show that the improved genetic algorithm in this paper has advantages in path planning.
This paper proposes an improved dual-center particle swarm optimization (IDCPSO) algorithm which can effectively improve some inherent defects of particle swarm optimization algorithms such as being prone to premature convergence and low optimization accuracy. Based on the in-depth analysis of the velocity updating formula, the most innovative feature is the vectorial decomposition of the velocity update formula of each particle to obtain three different flight directions. After combining these three directions, six different flight paths and eight intermediate positions can be obtained. This method allows the particles to search for the optimal solution in a wider space, and the individual extreme values are greatly improved. In addition, in order to improve the global extreme value, it is designed to construct the population virtual center and the optimal individual virtual center by using the optimal position and the current position searched by the particle. Combining the above strategies, an adaptive mutation factor that accumulates the coefficient of mutation according to the number of iterations is added to make the particle escape from the local optimum. By running the 12 typical test functions independently 50 times, the results show an average improvement of 97.9% for the minimum value and 97.7% for the average value. The IDCPSO algorithm in this paper is better than other improved particle swarm optimization algorithms in finding the optimum.
In this work, we aim to adjust vehicle speeds in real time by predicting the surrounding population density based on the spacing of customer locations. We comprehensively consider fixed costs, cargo loss costs, fuel costs, penalty costs, and environmental costs; build a cold chain distribution vehicle path optimization model with the goal of minimizing the total cost and maximizing customer satisfaction; and design a hybrid genetic algorithm solution optimization model. The algorithm dynamically adjusts the tournament scale through the standard deviation of the fitness value, uses the OX cross operator, determines the position of variation based on the customer information matrix, and performs local search optimization with the removal and insertion operators. Through comparison to other algorithms in the literature, the results show that the hybrid genetic algorithm not only improves customer satisfaction, but also maintains a lower total cost, which is obviously superior when solving the complex cold chain distribution path optimization problem; further comparison and analysis of the mathematical model in this paper with the single-dimension satisfaction model reveals that under the same satisfaction constraint threshold, the model in this paper can significantly reduce the system operating cost; we also deeply discuss the influence mechanism of vehicle traveling mode and customer point sparsity radius on distribution path planning.
The type-2 multi-objective integrated process planning and scheduling problem, as an NP-hard problem, is required to deal with both process planning and job shop scheduling, and to generate optimal schedules while planning optimal machining paths for the workpieces. For the type-2 multi-objective integrated process planning and scheduling problem, a mathematical model with the minimization objectives of makespan, total machine load, and critical machine load is developed. A multi-objective mayfly optimization algorithm with decomposition and adaptive neighborhood search is designed to solve this problem. The algorithm uses two forms of encoding, a transformation scheme designed to allow the two codes to switch between each other during evolution, and a hybrid population initialization strategy designed to improve the quality of the initial solution while taking into account diversity. In addition, an adaptive neighborhood search cycle based on the average distance of the Pareto optimal set to the ideal point is designed to improve the algorithm’s merit-seeking ability while maintaining the diversity of the population. The proposed encoding and decoding scheme can better transform the continuous optimization algorithm to apply to the combinatorial optimization problem. Finally, it is experimentally verified that the proposed algorithm achieves better experimental results and can effectively deal with type-2 MOIPPS.
This study addresses the joint scheduling problem of flexible job shop scheduling and automated guided vehicles with the objective of minimizing the makespan. We propose an efficient optimization approach based on a critical-path-driven variable neighborhood descent. The core contribution lies in the development of a critical path detection mechanism that incorporates transportation processes, along with the design of tailored neighborhood structures. Building on this foundation, a problem-specific variable neighborhood descent search strategy is implemented. Unlike traditional variable neighborhood descent approaches, the proposed critical path analysis accurately identifies bottleneck operations in both processing and transportation stages. The designed neighborhood structures effectively coordinate machine scheduling and automated guided vehicles transportation, enabling synergistic optimization. To enhance overall performance, auxiliary strategies such as an external memory archive and population diversity maintenance are integrated. Experimental results on multiple benchmark datasets demonstrate that the proposed method achieves significant improvements in solution quality compared to existing algorithms. Ablation experiments further confirm the critical role of the critical-path-driven variable neighborhood descent mechanism in enhancing algorithmic performance.
In this paper, we first extended the extended simplified discount {0-1} backpack problem (ESD {0-1} KP) and proposed the extended simplified discounted {0-1} knapsack problem with randomness (ESD {0-1} KP-R) model. Compared with the ordinary ESD {0-1} KP model, it increases the size and randomness of the term set, which is more suitable for the actual concept of "discount" and has stronger generalization. Then we used the improved memetic algorithm to solve the ESD {0-1} KP-R model. First, a greedy strategy with a relax variable was first designed to obtain the initial solution. Second, designed a crossover strategy with fuzzy sets to generate a good offspring population. Third, in order to overcome the shortcoming of memetic algorithms falling into local optimization, we designed a population diversity adjustment strategy with an information vector. This strategy combines the parent and child populations into a set of candidate solutions, and then divides all the solutions in the set into four categories according to the fitness and diversity of the solutions. Different selection methods can be used to adjust the diversity of the population while ensuring the quality of the solutions selected. In addition, based on the profit density for combinations of terms, three kinds of neighborhood structures were designed. They were used to improve the algorithm's searching ability, explore the neighborhood of local solutions, and jump out of the local optimum, respectively. The local search was performed by the variable neighborhood search algorithm. Finally, the effectiveness of the proposed improvement strategy and the feasibility of the proposed algorithm for solving the ESD {0-1} KP-R were demonstrated through experimental analysis on four types of instances.