Frontiers in Computing and Intelligent Systems ISSN: 2832-6024 | Vol. 2, No. 3, 2022 106 Review of Research on Vehicle Routing Problem and Related Algorithms Jingru Ding Shanghai University, Shanghai 200444, China Abstract: This paper briefly introduces the relevant theories and wide applications of vehicle routing problem, and then summarizes some common exact algorithms and heuristic algorithms for solving the vehicle routing problem. Finally, two algorithms are summarized for solving the vehicle routing problem of different scales. For the vehicle routing problem of smaller scale, the exact algorithm can directly solve the exact optimal solution of the problem; However, the vehicle routing problem with large scale is generally solved by heuristic algorithm. Keywords: Vehicle routing problem; Exact algorithm; Heuristic algorithm. 1. Introduction Vehicle Routing Problem (VRP) was first proposed by two scientists Dantzing and Ramser in 1959. It is an NP-hard problem. The VRP problem has been widely concerned by scholars since it was proposed. The VRP problem can be described as: a group of fleets provide distribution services for a group of customers with distribution needs to meet certain distribution goals. The vehicle starts from the distribution center and needs to return to the distribution center after completing the distribution task. In the process of distribution, vehicles also need to comply with constraints such as time window, vehicle capacity limit, etc. Vehicle routing problem is one of the most basic problems in network optimization problems. This kind of problem has a wide range of application scenarios in life. It is often used in the scenarios such as the route planning of goods distribution vehicles of express logistics enterprises, the establishment of bus routes, and the scheduling of air and railway schedules. Because of its wide range of application scenarios, it also has great development value in economy. According to practical applications, scholars have proposed many variants for vehicle routing problems. The algorithms used to solve vehicle routing problems are generally divided into two types: exact algorithms and heuristic algorithms. 2. Variants of vehicle routing problem With the continuous development of real logistics, the basic vehicle routing problem is not enough to meet all needs. Therefore, scholars put forward different types of vehicle routing problems according to different customer needs. For various types of vehicle routing problems, the mathematical models established are very different, and the solution methods are also different. According to different research objects in vehicle routing problems, vehicle routing problems are simply divided into the following categories. (1) Vehicle Routing Problem with Time Windows VRP with Time Windows is the most common variant of the vehicle routing problem. In the actual distribution process, because customers have a variety of needs for time, the vehicle routing problem with time windows is generated. The vehicle must be within the time window when serving customers. (2) Capacitated Vehicle Routing Problem The vehicle routing problem with capacity constraints is a variant of the vehicle routing problem derived from the reality. In CVRP, the customer's demand is known, while the vehicle's loading capacity has an upper limit. The vehicle starts from the distribution center and serves the customer points in the distribution network. During the distribution process, the vehicle's loading capacity is required to not exceed the upper limit of the vehicle's capacity. (3) Multi-vehicle Vehicle Routing Problem In the research of vehicle routing problem, most of the vehicles from the distribution center are assumed to be homogeneous, that is, the single-vehicle vehicle routing problem (Homogeneous VRP). In this problem, the vehicle model is the same, the capacity is the same, and the fuel consumption per kilometer is the same. Controlling the vehicle model variable is conducive to the study of other factors. When considering the distribution situation of the actual logistics distribution network, according to the different nature of the goods, such as the size, weight, and the need for refrigeration, there are also differences in the distribution vehicle models, so the vehicle routing problem of multiple models also has its research significance. (4) Multi-depot Vehicle Routing Problem MDVRP is a variant of the basic VRP. The basic VRP has only one distribution center. Vehicles start from the distribution center to serve customers, and return to the distribution center after completing the distribution service. In order to reduce the distribution cost and optimize the distribution path, MDVRP is proposed based on the VRP problem of a single distribution center. According to the distribution of customer locations and the demand of customer points, the location of distribution centers and the distribution of goods are determined. (5) Open Vehicle Routing Problem The traditional vehicle routing problem is generally closed vehicle routing problem, that is, the vehicle needs to return to the distribution center after completing the distribution service from the distribution center. For self-operated logistics enterprises such as JD, closed VRP is generally used. Nowadays, third-party logistics is becoming more and more developed, and there is no restriction to return the vehicles to the distribution center after delivery. This kind of problem is OVRP. 107 (6) Dynamic Vehicle Routing Problem In the basic VRP problem, it is assumed that the customer needs are known in advance and the information is static. In the actual logistics network, customer demand is unknown and changing, and distribution road conditions are also non- static. For example, the delivery of takeout is a typical DVRP problem. The customer order information is constantly updated, and the distribution road conditions are also constantly changing. Therefore, the complexity of DVRP problem is far greater than that of static VRP problem. 3. The exact algorithm for vehicle routing problem (1) Branch-and-Bound, (B&B) This algorithm applies the branch method to solve integer programming and mixed integer programming problems. For the original large problem that is difficult to solve, it can be divided into smaller and smaller sub-problems to solve. Branching is to divide the feasible solution set into smaller subsets, and then generate new sub-problems. The optimal solution is obtained by solving the linear relaxation of these problems by simplex method. The search process is to define the optimal solution of the subset, and discard the sub- problem when its boundary does not contain the optimal solution of the original problem. When all nodes of the search tree are processed, the algorithm stops. (2) Branch-and-Cut, (B&C) This algorithm includes three types of combination technologies: automatic problem preprocessing, cutting plane generation and intelligent branch and bound technology. Automatic problem preprocessing includes checking the formulas provided by users to find fixed variables, eliminate redundant constraints and tighten constraints. The generation of cutting plane can reduce the feasible region of linear relaxation without eliminating the feasible solution. (3) Branch-and-Price, (B&P) The principle of B&P is similar to that of B&C, but B&P focuses more on column generation. The pricing sub-problem is the separation problem of dual linear programming, which is used to identify the column to enter the base. If such a column is found, the linear programming will be re-optimized, otherwise it will branch. You can combine B&P and B&C, the so-called branch-and-cut-and-price (BCP), to obtain a more stringent lower bound. (4) Dynamic Programming, (DP) DP aims to find the optimal strategy for the whole problem. It can divide the problem into multiple stages, and each stage needs a decision strategy. DP needs to formulate appropriate recursive relations for each individual problem. The solution process starts from the last step and moves forward step by step to find the optimal strategy at this stage each time, until the optimal strategy is found from the initial stage of the problem and the optimal solution of the whole problem is generated. 4. The heuristics algorithm for vehicle routing problem (1) Genetic Algorithm The algorithm simulates the mechanism of biological evolution to construct solutions. The general process of genetic algorithm mainly includes: encoding and decoding, generating initial population, computing fitness, selection, crossover, mutation, etc. The main idea of genetic algorithm is to simulate the evolution process of "natural selection, survival of the fittest" in nature. After defining the coding scheme of the problem in advance, the genetic algorithm first codes a solution of the problem, and uses a random number to initialize the population. After decoding the solution, use the customized fitness function to calculate the fitness of each individual. The fitness selection function is used to select the corresponding individuals with better fitness and generate new offspring after crossing and mutation. This process will always produce individuals suitable for fitness selection function until the end condition of iteration is reached. The whole iterative process of the algorithm is like the process of natural evolution and selection. (2) Simulated Annealing Algorithm The algorithm mainly simulates the process of physical annealing, which is a process of high temperature solid melting material cooling and then re-solidifying from liquid to crystalline solid. In the process of annealing, if the temperature drops too fast, it may lead to the formation of an amorphous solid structure with high internal atomic energy. At this time, in the optimization problem, it is equivalent to obtaining the local optimal solution of the problem. If the rate of temperature drop is appropriate, the atoms in the crystalline solid can be arranged in order to form a low energy, stable and regular crystalline solid structure. At this time, in the optimization problem, it is equivalent to obtaining the global optimal solution of the problem. Therefore, introducing this process into the field of combinatorial optimization, the simulated annealing algorithm needs a good annealing process to make the solution gradually orderly in the process of cooling to avoid falling into the local optimal solution. (3) Tabu Search Algorithm When all the neighborhoods are non-improved solutions, TS can accept the non-improved solution to jump out of the local optimum, and replace the current solution when finding a better neighborhood. When the local optimal solution is reached, TS continues to search by selecting the candidate solution that is worse than the current solution. TS introduces the concept of tabu table to avoid the cycle. Tabu table is used to record the tabu movement. The movement into the tabu table is prohibited within the number of cycles of the tabu length to avoid falling into the cycle. The tabu can be removed after the number of cycles of the tabu length. (4) Iterated Local Search Algorithm ILS is a simple and effective meta-heuristic method. The local search algorithm can be used for the initial solution until the local optimum is reached, and then the local search can be restarted to disturb the previous solution. Through this perturbation, the local optimum can be skipped. When the conditions to be met are met, the new solution can be accepted as the current solution. The perturbation operator can be regarded as a large random shift of the current solution. The operator should retain part of the solution and strongly interfere with the other part of the solution to generate a new solution. (5) Variable Neighborhood Search Algorithm VNS continues to explore the neighborhood of the current solution, and will accept the new solution only when it is improved. This way can ensure that the current solution is the optimal solution and has the hope of obtaining a better solution. The main cycle of VNS consists of three stages: concussion, local search and movement. The goal of oscillation is to perturb the solution to obtain the starting point of local search. Systematic increase of neighborhood 108 selection can increase the diversity of solutions. (6) Particle Swarm Optimization Algorithm PSO simulates the social behavior and movement of natural organisms, such as bird habitat and fish clustering. In each iteration, a particle moves from one position to another in the decision space, making optimal use of the cooperation between particles, and the success of some particles will affect the behavior of their peers. Each particle adjusts its position to the global optimum in turn according to two conditions: the best position for its access and the best position for group access. The particle neighborhood defines the degree of communication between particles. The use of large neighborhood can strengthen the search for the global optimal solution, and the use of small neighborhood can strengthen the diversity of search space. 5. Conclusion The vehicle routing problem has always been the research focus of scholars at home and abroad. Through continuous theoretical research, various variants and mathematical models have been derived. In order to solve these problems, new algorithms have also been proposed. The mathematical model of vehicle routing problem is a 0-1 mixed integer programming model, so solving a vehicle routing problem is essentially solving a mixed integer programming model. At present, there are many methods to solve this kind of mixed integer programming problem, which are generally divided into two methods: precise algorithm and heuristic algorithm. The precise algorithm can directly solve the exact optimal solution of the problem, but it can only be used to solve the vehicle routing problem with a small scale; For large-scale problems, it is usually difficult to find the optimal solution of the problem in a certain time by precise algorithms, so the precise algorithms cannot be applied to solve a class of large- scale vehicle routing problems. The heuristic algorithm can be divided into single scheme meta-heuristic algorithm, population-based meta-heuristic algorithm and hybrid heuristic algorithm according to its source. It can solve the vehicle routing problem of a larger scale of examples in a certain time, but it may not be able to obtain the optimal solution of the problem, and in many cases, it can only obtain the approximate feasible solution of the problem. References [1] Dantzig G B, Ramser J H. The Truck Dispatching Problem[J]. Management Science,1959, 6(1):80-91. [2] Letchford A N, Lysgaard J, Eglese R W. A branch-and-cut algorithm for the capacitated open vehicle routing problem[J]. Journal of the Operational Research Society, 2007, 58(12): 1642-1651. [3] Letchford A N, Lysgaard J, Eglese R W. A branch-and-cut algorithm for the capacitated open vehicle routing problem[J]. Journal of the Operational Research Society, 2007, 58(12): 1642-1651. [4] Wu Z, Zhang J. A branch-and-price algorithm for two-echelon electric vehicle routing problem[J]. Complex & Intelligent Systems, 2021: 1-16. [5] Bellman R. DYNAMIC PROGRAMMING[M]. OXFORD UNIV. PRESS, 1957. [6] Holland J. Adaptation in natural and artificial systems: an introductory analysis with application to biology[J]. Control & Artificial Intelligence, 1975. [7] Holland J. Adaptation in natural and artificial systems: an introductory analysis with application to biology[J]. Control & Artificial Intelligence, 1975. [8] Tang, Elise. A TABU search heuristic for the team orienteering problem[J]. Computers & operations research,2005,32 (6):1379-1407. [9] Vansteenwegen P, Souffriau W, Berghe G V, et al. A guided local search metaheuristic for the team orienteering problem[J]. European journal of operational research,2009,196(1):118-127. [10] Archetti C, Hertz A, Speranza M G. Metaheuristics for the team orienteering problem[J]. Journal of heuristics,2007,13(1):49- 76. [11] Muthuswamy S, Lam S S. Discrete particle swarm optimization for the team orienteering problem[J]. Memetic computing,2011,3(4):287-303. https://shu-primo.hosted.exlibrisgroup.com.cn/primo-explore/fulldisplay?docid=TN_cdi_gale_infotracacademiconefile_A132255644&context=PC&vid=shu&lang=zh_CN&search_scope=default_scope&adaptor=primo_central_multiple_fe&tab=default_tab&query=any,contains,A%20TABU%20search%20heuristic%20for%20the%20team%20orienteering%20problem&offset=0 https://shu-primo.hosted.exlibrisgroup.com.cn/primo-explore/fulldisplay?docid=TN_cdi_gale_infotracacademiconefile_A132255644&context=PC&vid=shu&lang=zh_CN&search_scope=default_scope&adaptor=primo_central_multiple_fe&tab=default_tab&query=any,contains,A%20TABU%20search%20heuristic%20for%20the%20team%20orienteering%20problem&offset=0 https://shu-primo.hosted.exlibrisgroup.com.cn/primo-explore/fulldisplay?docid=TN_cdi_gale_infotracacademiconefile_A350825920&context=PC&vid=shu&lang=zh_CN&search_scope=default_scope&adaptor=primo_central_multiple_fe&tab=default_tab&query=any,contains,A%20guided%20local%20search%20metaheuristic%20for%20the%20team%20orienteering%20problem&offset=0 https://shu-primo.hosted.exlibrisgroup.com.cn/primo-explore/fulldisplay?docid=TN_cdi_gale_infotracacademiconefile_A350825920&context=PC&vid=shu&lang=zh_CN&search_scope=default_scope&adaptor=primo_central_multiple_fe&tab=default_tab&query=any,contains,A%20guided%20local%20search%20metaheuristic%20for%20the%20team%20orienteering%20problem&offset=0 https://shu-primo.hosted.exlibrisgroup.com.cn/primo-explore/fulldisplay?docid=TN_cdi_gale_infotracacademiconefile_A157183557&context=PC&vid=shu&lang=zh_CN&search_scope=default_scope&adaptor=primo_central_multiple_fe&tab=default_tab&query=any,contains,Metaheuristics%20for%20the%20team%20orienteering%20problem&offset=0 https://shu-primo.hosted.exlibrisgroup.com.cn/primo-explore/fulldisplay?docid=TN_cdi_gale_infotracacademiconefile_A157183557&context=PC&vid=shu&lang=zh_CN&search_scope=default_scope&adaptor=primo_central_multiple_fe&tab=default_tab&query=any,contains,Metaheuristics%20for%20the%20team%20orienteering%20problem&offset=0 https://shu-primo.hosted.exlibrisgroup.com.cn/primo-explore/fulldisplay?docid=TN_cdi_crossref_primary_10_1007_s12293_011_0071_x&context=PC&vid=shu&lang=zh_CN&search_scope=default_scope&adaptor=primo_central_multiple_fe&tab=default_tab&query=any,contains,Discrete%20particle%20swarm%20optimization%20for%20the%20orienteering%20problem&offset=0 https://shu-primo.hosted.exlibrisgroup.com.cn/primo-explore/fulldisplay?docid=TN_cdi_crossref_primary_10_1007_s12293_011_0071_x&context=PC&vid=shu&lang=zh_CN&search_scope=default_scope&adaptor=primo_central_multiple_fe&tab=default_tab&query=any,contains,Discrete%20particle%20swarm%20optimization%20for%20the%20orienteering%20problem&offset=0