Keywords

1 Introduction

The multi-objective optimization problem of vehicle routing is a hot issue in many industries in recent years, because it is more fully considered for real-world constraints and has always been a hot issue in shipping transport. Vehicle path planning issues with time window constraints are also the most concerned. Over the years, all kinds of problems have been studied at home and abroad.

For vehicle routing optimization problems with time window constraints, a large degree of research staff chose to use genetic algorithm or improved genetic algorithm to solve the problem, because the adaptive and random searching characteristics of genetic algorithm. Enables it to have a good global search capability in multi-objective optimization. For example, a bat algorithm, a bat algorithm is an intelligent heuristic algorithm that is based on the echo location system of the bat. It is characterized by simple and robust model, but also has the disadvantage of premature convergence and slow convergence. Combining it with genetic algorithm has good convergence characteristics, and the resulting hybrid bat algorithm has strong advantage. Think of bat as a vehicle. The bat algorithm simulates the echo positioning function of the bat in nature by simulating the frequency of sound waves, loudness of sound, pulse rate (changing the speed of vehicle, vehicle body capacity, etc.), locating the target prey, locating (finding the optimal path between vehicle and destination), finishing predator (complete distribution), and updating the population position (using genetic algorithm’s local search, elite parent cross-operator, gene transposition, etc.). Iterate to the next predator. There are also a number of researchers who choose to use particle swarm optimization, ant colony algorithm, simulated annealing method, tabu search, and novel glowworm algorithm in recent years to solve this problem. Because the constraints of vehicle path optimization problem with time window limit vary widely, it is almost impossible to solve the central idea of solving, i.e., using different search strategies of various algorithms, under constraints, find out the optimal path to satisfy the current demand. Then iterate. For example, tabu search algorithm is a search process that uses memory to guide the algorithm, and takes advantage of the short-term memory boot algorithm to jump out locally optimal algorithm, memory the most recently searched solution, and disallow the move of the algorithm back to the previous solution. The simulated annealing method is a local search algorithm that enhances the diversity of the algorithm by introducing a probability mechanism to prevent the algorithm from becoming locally optimal. In this paper, several novel and widely applied algorithms are introduced and compared.

The first part introduces the research significance and present situation of vehicle path planning with time window limitation. The second part introduces what is the problem of vehicle path planning with time window limitation. The third part introduces four algorithms about VRPTW: Firefly algorithm, genetic algorithm, tabu search algorithm and bat algorithm. The last part, that is, the fourth part, sums up the advantages and limitations of these algorithms.

With the development of computer science in recent years, researchers in the world have made great contributions to the field of algorithms, and put forward a variety of intelligent optimization algorithms. Efficient intelligent group optimization algorithm.

2 VRPTW

VRPTW is a hot issue based on VRP. Due to the continuous development of VRP, the time window is added to the vehicle routing problem under the requirement that the demand point is required for the arrival time of the vehicle, and becomes the vehicle path problem with time window(VRP with Time Windows, VRPTW). A time window vehicle path problem(VRPTW) is a time window constraint that adds a customer’s access on the VRP. In VRPTW issues, the cost function also includes the latency and customer-required service time due to the early arrival of a customer, in addition to the driving costs.

In VRPTW, in addition to that limitation of the VRP problem, the vehicle must meet the time window limit of the demand point, while the time window limit of the demand point can be divided into two, one is hard time window, the hard window requires that the vehicle must arrive within the time window, while being late is rejected; Another is Soft Time Window, which does not necessarily arrive within the time window, but must be punished outside the time window to punish alternative wait and rejection as the maximum difference between the window and the hard time window.

The vehicle transit problem (VRPTW), which is limited by the time window, relative to the vehicle transit problem (VRP), must additionally take into account the shipping time and time window, which is mainly due to the customer’s deadline for service time and the earliest starting service time limit. Therefore, under this limitation, the original VRP problem must be taken into account in addition to the spatial path (Routing) considerations. At the same time, because the field station also has the limitation of time window and indirectly causes the limitation of the path length, it can be seen that the total patrol cost of VRPTW not only contains the transportation cost, but also considers the time cost, and the penalty cost which is not delivered within the time window limit. Therefore, it is very important to find a good solution, time and space.

3 Important Algorithms

Intelligent algorithm refers to the fact that in engineering practice, a number of comparisons are often brought into contact “New” Algorithms or theories such as simulated annealing, genetic algorithm, taboo search, neural network, etc. These algorithms or theories have some common characteristics (such as simulation of natural processes). They are useful in solving complex engineering problems.

In general, the intelligent optimization algorithm is to solve the problem. The optimization problem can be divided into (1) solving a function, optimizing the function optimization problem of the argument value with the smallest function value and (2) searching the optimal solution in a solution space, and minimizing the combination optimization problem of the target function value. Typical combinatorial optimization problems are: Travel Salesman Problem, TSP, Scheduling Problem, 0-1 knapsack problem, and Bin Packing Problem.

The optimization algorithms are many, and the classical algorithms include: linear programming, dynamic programming, etc.; The improved local search algorithm includes the climbing method, the steepest descent method and the like, and the simulated annealing, the genetic algorithm and the taboo search described herein are referred to as instructive searching methods. The neural network and chaos search belong to the dynamic evolution of the system.

In the optimization idea, a neighborhood function is often referred to, and its function is to indicate how to get a new solution from the current solution. The specific implementation method is to be determined according to the specific problem.

In general, local search is based on the greedy idea to use the neighborhood function to search, if finding a solution better than the existing value, discard the former and take the latter. However, it can only be obtained “local minimal solution” That means, maybe it’s just a rabbit. “Mount Tai and Little World” But he didn’t find it. Simulated annealing, genetic algorithm, tabu search, neural network and so on have been improved from different angles and strategies. Global Minimum Solution And the like.

3.1 Firefly Algorithm

Firefly Algorithm are derived from the natural phenomenon of simulating natural phenomena in nature in the evening, and in the crowd-gathering activity of the lies, each of the lies is exchanged with the companion through the distribution of fluorescein and the companion for information exchange. In general, the brighter glow of the fluoresce, the stronger its number, will eventually appear to gather a lot of lies around the brighter Fireflies. The artificial lies algorithm is a novel intelligent optimization algorithm based on this phenomenon. In the artificial worm swarm optimization algorithm, each of the lies is regarded as a solution of the solution space, which is distributed in the search space as the initial solution, and then the movement of every lies in the space is carried out according to the movement mode of the nature lies. Through every generation of movement, the final made lies gather around the better lies, that is, to find a plurality of extreme points, thus achieving the aim of population optimization. The traditional Firefly algorithm is suitable for solving the problem of continuous optimization and can not solve the problem of discrete optimization of VRPTW. Therefore, it is necessary to improve the traditional Firefly algorithm.

Osaba et al. [1] put forward a Firefly algorithm. An evolutionary discrete firefly algorithm has a time window routing problem for a novel operator of a vehicle. This novel uses some new route optimization operators who have targeted extraction attempts to minimize the number of nodes in the current solution. Use the random path size, path size, the distance from the center of gravity. In other words, try deleting any path and then re-insert the extracted node. In order to transform continuous optimization problems to discrete problems, this paper proposed EDFA, each firefly in the swarm is a possible and feasible solution for the VRPTW [1].

Osaba et al. [2] put forward another Firefly algorithm. In this paper, they proposed DFA. Each Firefly represents a viable solution for the ACVRP- SPDVCFP. All lies are initialized randomly.

3.2 Genetic Algorithm

Genetic algorithm is a computational model to simulate the biological evolution process of Darwin’s theory of natural selection and genetics, which is a method of searching optimal solution by simulating the natural evolution process. Genetic algorithms are beginning with a population of potential solutions that represent problems, while one population is composed of a number of individuals encoded by the gene. Each individual is actually a chromosome bearing entity. Chromosome is the main vector of genetic material, i.e. the collection of multiple genes, whose internal representation is a gene combination, which determines the external representation of the individual’s shape, such as black hair, which is determined by a combination of genes that control this feature in the chromosome. Thus, a mapping from phenotype to genotype, i.e. coding, is required at the outset. Because of the complexity of gene coding, we tend to simplify, such as binary coding, generation of early generations, the principle of survival and survival of the fittest, and generation of more and more approximate solutions from generation to generation. In each generation, An individual is selected according to the fitness size of an individual in the problem domain, and cross and variation are combined by means of genetic operators of natural genetics to produce a population representing a new solution set. This process will result in the population, like the natural evolution, more adaptive to the environment than the previous generation, and the optimal individual in the last generation population is decoded and can be used as the approximate optimal solution for the problem.

The main feature of genetic algorithm is to directly operate the structural object without the limitation of derivation and function continuity. has inherent hidden parallelism and better global optimization ability; By adopting the method of probability optimization, the optimized search space can be automatically acquired and optimized, the search direction can be adjusted adaptively, and the determined rule is not needed.

Ombuki et al. [3] propose a paper. In this paper, VRPTW is represented as multi-objective optimization problem, and a genetic algorithm solution is proposed using Pareto ranking technique. The VRPTW is interpreted directly as a multi-target problem, where two target dimensions are the number of vehicles and the total cost (distance). One advantage of this approach is that the weights of the weighting and scoring formulas need not be derived. The result of our research is that the multi-objective optimization genetic algorithm returns a group of solutions that take into account the two dimensions. Our approach is quite effective and provides solutions that compete with the best solutions known in the literature, and are not biased towards the number of vehicles. A set of well-known reference data is used to compare the effectiveness of the proposed approach to VRPTW.

3.3 Tabu Search Heuristic

Taboo search heuristic is a meta-heuristic random search algorithm which selects a series of specific search directions as heuristic from an initial feasible solution. In order to avoid the local optimal solution, the TS search is flexible “Memory” The technology is to record and select the optimization process that has been carried out, and guide the search direction of the next step, which is the establishment of Tabu table.

In order to find the global optimal solution, it should not be devoted to a particular area. The disadvantage of local search is that it is too greedy to search for a local area and its neighborhood, resulting in results that are not optimal. Tabu search is a part of the local optimal solution found, consciously avoiding it but not completely isolating it, thus obtaining more search intervals.

Taillard et al. [4] proposed a paper. In this paper, a taboo search algorithm is proposed to solve the problem of vehicle path with soft time window. In this problem, once the penalty has occurred, it is added to the target value allowing reordering at the customer location. The problem of vehicle routing with a hard time window can be simultaneously solved by adding a larger penalty value. In a taboo search, the neighborhood of the current solution is created by an exchange process where the sequence of successive customers (or fragments) is exchanged between the two paths. The Tabu search also leverages an adaptive memory that contains the routing of the best solution previously accessed. A new starting point for a taboo search is generated by a combination of routes taken from different solutions found in the memory. A number of known solutions are reported on classic test issues.

3.4 Bat Algorithm

Bats are the only mammals with wings, and they have advanced echo location capabilities. Most microbats are carnivorous animals. Mini bats use acoustic echo to locate, detect prey, avoid obstacles, and find themselves in the dark to find their habitat in the crack. The bats emit a loud voice and hear echoes reflected from the surrounding objects. For different bats, their impulses are related to hunting strategies. Most bats use a short and high-frequency signal scan around a filter, while others often use fixed-frequency signals for echo localization. The variation of its signal bandwidth depends on the species of bats and often increases by using more harmonics.

The algorithm of bats algorithm is to simulate bats in nature to detect prey using a random search algorithm, that is, a random search algorithm to avoid obstacles, that is, to simulate bats’ most basic detection, positioning and connection with optimized target functions by using ultrasound to detect obstacles or prey. The bionic principle of the BA algorithm maps the population of bats as NP feasible solutions in the D dimension problem space, and the optimization process and the search simulation are simulated into a population bat individual moving process and a fitness function value for searching the prey utilization solving problem to measure the position of the bats at the position of the bat, Analogy is an iterative process for optimizing and searching an individual’s superiority in the process of optimization and search.

Yongquan Zhou, Jian Xie, and Hongqing Zheng proposed a paper. In this paper, since the standard BA is a continuous optimization algorithm, the coding scheme of the BA cannot be directly used to solve the CVRP problem. In order to apply the BA to solve the CVRP problem, a suitable representation of the candidate solution scheme is a hybrid BAT algorithm designed for a specific problem. Each individual is a sequence with an integer to visit these customers’ orders.

4 Conclusion

Genetic algorithm, which is the earliest multi-objective optimization algorithm, has very deep research significance, but its limitation is obvious. Genetic algorithm has the inaccuracy of coding and coding. Moreover, a single genetic algorithm coding cannot fully express the constraints of optimization problems. One way to consider constraints is to apply a threshold to the unfeasible solution, so that the calculated time must be increased. Genetic algorithms generally have a lower efficiency than other conventional optimization methods. Genetic algorithms tend to converge prematurely. Genetic algorithm has no effective quantitative analysis on the accuracy, feasibility and computational complexity of the algorithm.

It can be seen from the optimization principle that the homing ability of bats is mainly dependent on the interaction and influence among bats, but the individual lacks variation mechanism, and once it is bound by a certain local extreme value, it is difficult to get rid of; and in the course of evolution, Super bats in the population may attract other individuals to gather rapidly around them, so that the diversity of the population is greatly decreased, while the convergence rate is greatly reduced and even evolution has stagnated due to the increasing approaching of the individual species, and the population loses the ability to further evolve. In many cases, especially for the optimization space with high dimension, multimodal and complex terrain, the algorithm does not converge to the global extreme value, so it is difficult to find the global optimal distribution in the local optimal neighborhood. Therefore, the improvement of the basic bat optimization algorithm should be put on improving the diversity of the population, so that the population can maintain the ability of continuous optimization during the iterative process. In contrast, the glow-worm algorithm simulates the light-emitting characteristics of the nature worm, and achieves the purpose of exchanging information by comparing the size of the fluorescein value so as to realize the optimization of the problem. The algorithm has the advantages of less parameters, simple operation, good stability and the like. In addition, the improved lies can autonomously look for the superior individual within the sensing range, reduce the degree of dependence on the excellent individuals, and additionally, by comparing the size of the neighborhood average distance, the individual movement step size can be appropriately adjusted within the sensing range, Thereby reducing the oscillation phenomenon and improving the solution precision.