Genetic Algorithm Learning Operators to Solve the Vehicle Routing Problem

Genetic Algorithm Learning Operators to Solve the Vehicle Routing Problem Souad Abdoune and Menouar Boulif LIMOSE laboratory, Department of Computer Science, Mhamed Bouguerra University Boumerdes, Algeria [email protected], [email protected] Abstract In recent years, researchers have focused on solving real-world optimization problems that impact logistics and transportation. Among these, the Vehicle Routing Problem (VRP) and its various variants have gained significant attention due to their wide ranging applications. One of the most widely used techniques for solving VRP is the Genetic Algorithm (GA). As part of the Evolutionary Intelligence approaches, GA leverages its operators to learn how to adapt its prospecting of the problem search space, in order to reach efficiently good solutions. This paper provides an overview of GA operators tailored to solve VRP, and evaluates different operator configurations for the Capacitated VRP by using a benchmark set taken from the literature, to trial their learning performance. Keywords: Evolutionary Intelligence, Combinatorial Optimization, Vehicle Routing Problem, Genetic Algorithm, Genetic operators, Selection, Crossover, Mutation. 1 Introduction Logistics, transportation, and supply chain management have been among the key areas of research in recent years. Two fundamental optimization challenges in these domains are the Traveling Salesman Problem (TSP) and the Vehicle Routing Problem. The TSP is a well-known combinatorial optimization problem where a salesman must visit a set of customers exactly once and return to the starting point while minimizing travel distance [1]. Over time, this concept has been extended to incorporate multiple vehicles and additional constraints beyond just minimizing the overall travel distance. This extension is known as the Vehicle Routing Problem (VRP) (Figure1). Figure 1: TSP vs. VRP VRP generalizes the TSP by determining a set of vehicle routes, each assigned to serve a group of customers with known demands. The objective is to minimize the total travel distance while satisfying problem-specific constraints [2]. Due to its broad real-world applications, researchers have continuously enhanced the classical VRP model by introducing additional constraints and various optimization criteria to make it more practical. 244 Different VRP constraints have led to the development of multiple VRP variants such as (Figure 2): •Capacitated VRP (CVRP): Involves a fleet of vehicles with limited capacity, where the total quantity delivered on each route must not exceed the vehicle’s capacity [3,4]. •Heterogeneous VRP (HVRP): If all vehicles have the same characteristics (e.g., volume, speed, capacity), the problem is considered homogeneous [5]; otherwise, it is heterogeneous [6]. •VRP with Time Windows (VRPTW): Considers customer availability, ensuring that deliveries are made within a predefined time window [3,7]. •Periodic VRP (PVRP): Deals with customers who require deliveries on a recurring schedule over a specific planning horizon [8]. •Multi-Depot VRP (MDVRP): Incorporates multiple distribution centers from which vehicles are dispatched to serve customers [9]. •Open VRP (OVRP): In this variant, vehicles are not required to return to the distribution center after completing their routes[10]. •Dynamic VRP (DVRP): Unlike static VRP, this version assumes that customer requests can change in real time during the delivery process. New requests may be added, existing ones may be canceled, or delivery conditions may change, requiring continuous route re-optimization [10,11]. Figure 2: Some VRP variations The objective function in VRP varies depending on the problem context. It may be defined by using one of the following criteria or a combination of them: •minimize total distance, •minimize travel cost, •minimize penalties, •maximize customer satisfaction, •maximize service quality. These criteria will be revisited with full details in section 2.3 Over the years, various solution approaches have been proposed to tackle the complexity of different VRP variants. These approaches are broadly classified into exact and approximate methods. Since VRP is NP-hard, and thus, finding an optimal solution for large instances is computationally expensive, exact methods become impractical for large-scale problems. Instead, approximate methods (heuristics and meta-heuristics) are the preferred choice. Among them, Genetic Algorithms (GA) have gained popularity due to their ability to explore large solution spaces efficiently and produce high-quality solutions. 245 In VRP applications, the performance of Genetic Algorithms can be boosted or hindered by the operators to be used, which directly influence solution quality. Indeed, GA operators give the GA its ability to learn from generation to generation how to correct its trajectory towards promising areas of the solutions’ search space. This paper surveys the different GA operators applied to solve VRP. The remainder of this paper is organized as follows: Section 2 provides an overview of the Genetic Algorithm. Section 3 presents different GA operators applied to VRP, Sections 4 and 5 describe the experimental methodology and the results and discussion, respectively. Finally, Section 4 concludes the paper with insights and future research directions. 2 Genetic Algorithm learning mechanism Genetic Algorithms are a class of metaheuristic optimization techniques inspired by the principles of natural selection and evolution, as described by Charles Darwin [12,13,14]. GAs, even in their basic form, embody key concepts of Artificial Intelligence as they can learn,adapt and search for good solutions to problems difficult to solve by humans. GAs are particularly effective in solving complex optimization problems by intelligently exploring the search space and finding optimal or near-optimal solutions within a reasonable time frame. This makes GAs highly useful for NP-hard problems, such as the Vehicle Routing Problem and its variants. GAs work by maintaining a population of candidate solutions that can learn across multiple generations through the application of genetic operators, including selection, crossover, and mutation. These operations guide the search towards high-quality solutions. 2.1 Key concepts in GAs To understand how GAs function, the following fundamental concepts should be introduced [15,16]: •Population: A set of chromosomes, each representing a potential solution to the problem. •Chromosome: An encoded representation of a solution in a specific format (e.g., sequence of customer visits in VRP). •Gene: A component of a chromosome that represents a decision variable (e.g., a customer or a route segment). •Allele: A specific value that a gene can take. •Offspring: New chromosomes produced through crossover and mutation operations. •Objective function: A function that evaluates the fitness (quality) of each solution, based on the problem’s optimization goal (e.g., minimizing total travel cost). 2.2 Genetic Algorithm process The standard process of a GA follows these steps (Figure 3) [17]: 1. Initialization: Generate an initial population of candidate solutions, either randomly or using problem-specific heuristics. 2. Evaluation: Compute the fitness of each chromosome in the population using the objective function. 3. Selection: Choose parent solutions from the population based on their fitness values, ensuring that better solutions have a higher chance of being selected. 4. Reproduction (Crossover & Mutation): •Crossover: Combine genetic material from two parent solutions to generate offspring. •Mutation: Introduce small random modifications to maintain diversity in the population. 5. Replacement: Replace some or all of the existing population with newly generated offspring, forming the next generation. 246 6. Termination condition: Check if a predefined stopping criterion is met (e.g., reaching a maximum number of generations, convergence of solutions, or stability in fitness values). If the criterion is met, return the best chromosome as the final solution; otherwise, repeat the process from step 2. Figure 3: Genetic algorithm flowchart 2.3 Optimization Criteria in VRP The Vehicle Routing Problem encompasses a variety of optimization objectives, which vary depending on the problem variant and practical application domain. Traditionally, the primary objective in VRP is to minimize the total distance travelled or to optimize the number of routes (vehicles). However, many real-world scenarios introduce additional or alternative goals, such as minimizing total travel time, reducing fuel consumption, balancing the workload among vehicles, or maximizing customer satisfaction by respecting service time windows and delivery preferences. When applying Genetic Algorithms to solve VRP, the fitness function is a critical component that encodes these objectives into a quantifiable criterion. Depending on the VRP variant, the fitness function can be single-objective (minimizing total cost) or multi-objective (minimizing cost while maximizing service quality), and often involves penalization terms for constraint violations such as time windows. For instance, VRP with Time Window and Capacitated VRP, infeasible solutions may be penalized based on the degree of violation. Furthermore, the GA must be carefully tailored to preserve feasibility during the search process while maintaining diversity in the population. By clearly defining and incorporating these objectives into the evolution process and evaluation mechanisms, GA can effectively explore the solution space and adapt to different VRP scenarios. 247 2.4 Learning mechanisms in Genetic Algorithms Since Genetic Algorithms are inspired by biological evolution they are designed to adapt their behaviour over time, a property often referred to as learning. This feature is further stressed in Adaptive GAs, whre the probabilities of applying genetic operators (selection, crossover, mutation) are dynamically adjusted based on their historical performance across generations. This process enables the algorithm to emphasize the most successful operators, improving convergence speed and maintaining population diversity [18]. Self-adaptive GAs go a step further by encoding control parameters directly into the chromosomes, allowing these parameters to evolve alongside the solutions themselves. This mechanism enables the algorithm to autonomously learn optimal operator settings and adjust to the characteristics of the problem over time [19]. For example, in dynamic VRPs, such approaches automatically increase mutation rates when new customer requests arrive, enabling faster adaptation to changing conditions. Recently, hybrid approaches have combined self-adaptation with reinforcement learning or deep learning to further enhance the algorithm’s ability to navigate complex and dynamic search spaces. These learning-driven strategies are particularly valuable in solving real-world optimization problems such as the Vehicle Routing Problem, where constraints and environmental conditions can vary significantly. Such mechanisms highlight the potential of learning-enabled GAs to intelligently and autonomously explore the solution space, aligning with the goal of achieving robust and efficient optimization in logistics and transportation. Different Genetic Algorithm operators are designed for specific problem domains. The next section surveys the GA operators commonly applied to VRP. 3 GA operators for VRP The effectiveness of GAs in solving the Vehicle Routing Problem largely depends on the choice and implementation of the genetic operators. These operators play a crucial role in guiding the search process, maintaining population diversity, and ensuring convergence toward high quality solutions. While the fundamental GA operators (selection, crossover, and mutation) are common across different optimization problems, their adaptation to VRP requires specialized mechanisms to handle route based representations, feasibility constraints, and solution quality. Various modifications of selection, crossover, and mutation have been proposed in the literature to enhance GA performance in VRP. After presenting the initial steps of the GA to solve VRP, the most widely used operators are described in what follows. 3.1 Chromosome representation The encoding method directly impacts GA’s ability to find optimal or near-optimal solutions efficiently. The chromosome representation in GA is crucial for determining good solutions to VRP. However, discussing all the encoding approaches is beyond the scope of this work. Instead, we present the presentation that allows to understand the described operators. Among the various encoding techniques proposed in the literature, path representation is the most widely used for VRP. In this approach[14]: •Customers are represented by integer identifiers, with each integer corresponding to a specific customer •The order of these integers within the chromosome defines the sequence of customer visits •The Depot Index (typically 0) indicates the start and end points of each route, segmenting the chromosome into separate routes •Each route is marked by a depot index, with customers visited in the order specified by the sequence of integers This encoding structure provides a direct and clear representation of customer visit sequences and vehicle routes, as shown in Figure 4a. After constructing the full chromosome, depot indexes can be removed to improve readability, as demonstrated in Figure 4b. 248 (a) with depot index (b) without depot index Figure 4: VRP chromosome representations 3.2 Selection operators The selection process in GAs determines which individuals (solutions) are chosen for reproduction. While no specific selection method is designed exclusively for the Vehicle Routing Problem (VRP) and its variants, the following widely used selection operators can be effectively applied: •Roulette wheel selection (RWS): assigns a probability to each chromosome based on its fitness. A virtual wheel is spun, and the chromosome closest to the stopping point is selected. Since elements with higher fitness occupy a larger portion of the wheel, they have a greater chance of being chosen[20]. •Elitism selection (ES): preserves the best solutions by directly transferring them to the next generation, ensuring that high-quality solutions are not lost during the evolutionary process [14]. •Rank selection (RS): orders chromosomes based on fitness and assigns selection probabilities accordingly. This method prevents highly fit individuals from dominating the selection process too early, leading to a more balanced exploration of the solution space [14]. •Tournament selection (TS): involves randomly selecting a subset of chromosomes and conducting a competition, where the one with the highest fitness is chosen. This method maintains diversity and prevents premature convergence to local optima [14]. 3.3 Crossover operators The crossover process in genetic algorithms mimics a natural biological phenomenon where genetic material is exchanged between parents to create offspring. The most fundamental crossover methods are one-point crossover and two-point crossover. In one-point crossover, a random cutting point along the chromosome is selected, and the segments of the chromosome are exchanged between two parent chromosomes [12]. In two-point crossover, two cutting points are selected, and the portion between these points is swapped between the parents [13]. While these methods are simple and intuitive, they are often not well-suited for combinatorial optimization problems like the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP). One of the main issues is that these basic crossover methods can generate duplicate genes or customer visits within the chromosomes, which is a critical problem in TSP and VRP, where each customer must be visited exactly once in a valid solution. As a result, offspring created through these methods may require post-crossover repair to remove duplicates and restore feasibility. To address these limitations,several advanced and specialized crossover techniques have been developed. These methods aim to preserve the validity of the solution, ensuring that the offspring generated do not violate the constraints (such as visiting each customer exactly once) and enhancing the efficiency of the genetic search process. Some of the key techniques are: •Order crossover: This recombination technique is designed for permutation-based problems such as the VRP. It preserves the relative ordering of cities by transferring a contiguous segment from one parent while filling the remaining positions with elements from the second parent in their original 249 sequence, ensuring that no duplicates occur. The process begins with the selection of two cut points, defining a subsequence to be directly copied into the offspring. The remaining positions are then filled by sequentially inserting elements from the other parent, starting immediately after the second cut point and skipping those already present in the offspring (see Figure 5) [20,21,22]. Figure 5: Order crossover •Cycle crossover: this method used for permutation problems. It works by identifying cycles of genes between two parent solutions and transferring them to the offspring. The process starts by copying genes from Parent 1 to the offspring, then follows the positions of corresponding genes in Parent 2 to complete the cycle. Once a cycle is finished, the remaining genes are copied from the other parent. This ensures a valid permutation without duplicates, preserving the relative order of genes from both parents. It’s particularly useful for problems like TSP or VRP. (see Figure 6) [23,24,25]. Figure 6: Cycle crossover •Partially mapped crossover: This method works by selecting a random subsequence from one parent and copying it into the offspring. The remaining positions in the offspring are filled with genes from the other parent in the order they appear, while preserving the relative order of the cities from the first parent. This technique avoids duplicates and preserves the structure of the parent solutions (see Figure 7) [26,27]. Figure 7: Partially mapped crossover •Order based crossover: This method begins by randomly selecting a set of positions in Parent 1. Next, the genes from Parent 2 are copied into Child 1, excluding the genes located in the 250 selected positions of Parent 1. Finally, loop over parent 1 and transfer to child 1 the genes that are not already transferred to it. This ensures that the offspring maintains a valid permutation and preserves key structural properties from both parents. (see Figure 8) [28,29,30]. Figure 8: Order based crossover 3.4 Mutation operators Many mutation types are proposed in the literature, such as: •Exchange (or Swap) mutation: This mutation operator randomly selects two cities in the tour and exchanges their positions as shown in Figure 9a [31,23,32]. •Insertion mutation: The insertion mutation operator randomly chooses a city in the tour, removes it from this tour, and inserts it in a randomly selected place as shown in Figure 9b [33,34]. •Inversion mutation: This operator randomly selects a sub-tour, removes it from the tour, then inserts it in reversed order at a randomly selected position (see Figure 9c) [33,35,34]. (a) Exchange (b) Insertion (c) Inversion Figure 9: Mutation operators 251 4 Experimental Methodology To support the theoretical analysis of genetic algorithm (GA) operators, namely, selection, mutation, and crossover, this study conducted a set of experiments evaluating various combinations of these operators. In total, 48 distinct GA configurations are examined. The objective is to assess the influence of these operators on the algorithms performance in solving the Capacitated Vehicle Routing Problem (CVRP), using a well-established benchmark set [36]. Our experimental analysis focuses on the A-n32-k5 instance, which is characterized by the following features: •31 customer locations, each associated with a specific demand. •A homogeneous fleet consisting of 5 vehicles with identical capacity. •A known optimal total distance of 784 kilometers. The experimental setup adopted in this study includes: •Population size: 100 individuals. •Maximum number of generations: 500. •Constraint-handling strategy: penalty functions are applied to penalize individuals that violate the problem’s constraints, including capacity limitations and the number of available vehicles. 5 Results and Discussion The results in Table 1demonstrate significant variability in performance across the 48 genetic operator combinations. Notably, the OBX crossover paired with inversion mutation and elite selection achieved the lowest distance of 838.42 km, which is close to the benchmarks optimal distance (784 km) by just 6.9%. This configuration also exhibited moderate computation time (4.69 s), suggesting a favourable balance between solution quality and computational effort. Conversely, configurations using CX crossover with insertion mutation (1214.52 km) highlight the risks of poor operator synergy, where premature convergence and limited exploration lead to suboptimal solutions. Table 2underscores the superiority of OBX crossover, which achieved both the lowest best-case distance (838.42 km) and the lowest average (950.11 km). In contrast, CX crossover exhibited the highest worst-case distance (1214.52 km) and average (1025.71 km), indicating instability in maintaining solution quality. Table 2: Distance results for Crossover operators Crossover operator Best Worst Average PMX 875.50 1183.41 1016.87 OX 897.57 1089.07 984.62 OBX 838.42 1143.70 950.11 CX 870.60 1214.52 1025.71 Additionally, Table 3 summarizes the performance of each mutation operator across all selection and crossover combinations. The inversion mutation yielded the most promising results overall, providing both the lowest best-case distance and the lowest average distance. This demonstrates its advantage in maintaining solution quality while efficiently exploring the solution space. Table 3: Performances of Mutation operators Mutation operator Best Worst Average Insertion 967.48 1214.52 1059.82 Swap 863.99 1146.60 960.86 Inversion 838.42 1178.33 962.25 252