Genetic Algorithm (GA)

Unlike single-solution methods like Simulated Annealing, GAs maintain a population of candidate solutions (chromosomes) that evolve simultaneously. This parallel search explores multiple regions of the solution space concurrently, reducing the risk of getting trapped in local optima. For a Vehicle Routing Problem (VRP) with 100 stops, a population might contain 200 distinct route configurations, each representing a complete delivery schedule.

The primary exploitation operator that combines genetic material from two parent solutions to produce offspring. In routing contexts, Order Crossover (OX) preserves the relative order of stops from one parent while inheriting subsequences from the other. For example:

• Parent A: [Depot → A → B → C → D → Depot]
• Parent B: [Depot → C → A → D → B → Depot]
• Offspring: [Depot → A → D → B → C → Depot] This preserves building blocks of high-quality route segments.

Mutation introduces stochastic diversity to prevent premature convergence. Common routing-specific mutations include:

• Swap Mutation: Exchange two randomly selected stops between routes
• Inversion Mutation: Reverse the order of a subsequence within a single route
• Scramble Mutation: Randomly shuffle a contiguous segment of stops
• Insertion Mutation: Remove a stop and reinsert it at a different position Mutation probability is typically kept low (1-5%) to balance exploration without destroying fit solutions.

The fitness function quantifies solution quality, driving evolutionary pressure. In last-mile optimization, fitness evaluates:

• Total route distance (minimization)
• On-Time In-Full (OTIF) compliance with time windows
• Vehicle capacity constraint violations (penalized heavily)
• Driver shift duration limits Tournament Selection picks k random individuals and selects the fittest, while Roulette Wheel Selection assigns selection probability proportional to fitness. Elitism preserves the best solutions unchanged to the next generation.

GAs are inherently unconstrained optimizers, so routing constraints require explicit handling:

• Penalty Functions: Add a cost term for each violated Capacitated VRP (CVRP) capacity or VRP with Time Windows (VRPTW) time window
• Repair Heuristics: Post-process infeasible offspring by removing over-capacity stops or reordering for time feasibility
• Decoder-Based Approaches: Encode only feasible solutions by design, using specialized representation schemes that guarantee constraint satisfaction
• Death Penalty: Simply reject and discard infeasible offspring, regenerating from the parent pool

Pure GAs excel at global exploration but converge slowly near optima. Memetic Algorithms hybridize GAs with local search heuristics:

• Apply 2-opt or Or-opt intra-route improvements to each offspring
• Use Large Neighborhood Search (LNS) destroy-and-repair as a mutation variant
• Integrate Adaptive LNS (ALNS) operator selection based on improvement history This Lamarckian evolution writes locally improved traits back into the chromosome, dramatically accelerating convergence on the Pareto Frontier for multi-objective cost-service trade-offs.

The foundational combinatorial optimization challenge that genetic algorithms are often deployed to solve. The VRP seeks to determine the optimal set of routes for a fleet of vehicles to service a geographically dispersed set of customers. A GA approaches this by encoding route sequences as chromosomes and evolving them to minimize total distance or time.

A critical VRP variant that introduces a strict capacity constraint to each vehicle. A GA must incorporate penalty functions or repair heuristics to ensure that evolved solutions do not exceed the vehicle's carrying limit. This constraint dramatically increases the search space complexity, making metaheuristics like GAs essential for finding feasible solutions in practical timeframes.

A VRP variant where each customer must be visited within a specific hard or soft time interval. A GA must evolve routes that satisfy both spatial and temporal constraints. The fitness function penalizes early arrivals (waiting time) and late arrivals (breach of contract), forcing the algorithm to discover sequences that balance distance minimization with strict schedule adherence.

A competing metaheuristic that mimics the metallurgical process of controlled cooling. Unlike a GA's population-based search, SA explores the solution space by probabilistically accepting worse solutions to escape local optima. The acceptance probability decreases over time via a temperature parameter. SA is often faster for single-route optimization, but GAs excel at exploring diverse fleet-wide configurations.

The process of simultaneously optimizing conflicting goals, such as minimizing fuel cost versus maximizing On-Time In-Full (OTIF) delivery rates. A GA handles this by evolving a Pareto frontier of non-dominated solutions. The fitness function assigns ranks based on dominance, allowing logistics directors to visualize the trade-off curve and select a routing strategy that balances cost against service level agreements.

An optimization heuristic that iteratively destroys and repairs a large portion of a solution. Adaptive LNS (ALNS) extends this by dynamically selecting from multiple destroy and repair operators based on their past performance. While LNS is a single-solution trajectory method, a GA can be hybridized with LNS by using the destroy/repair cycle as a sophisticated mutation operator to accelerate convergence.