Heuristics and Metaheuristics

Introduction and context

Vehicle-routing and scheduling problems are among the most difficult decisions in supply-chain management. A planner may need to assign customers to vehicles, determine visit sequences, satisfy vehicle capacities and driver regulations, respect delivery time windows, and control distance, fuel, labor, and service costs. Exact optimization models can represent these requirements precisely, but their computational burden grows rapidly as the number of customers increases. For realistic instances, a decision must often be produced in seconds or minutes rather than hours or days.

Heuristics and metaheuristics address this practical tension. A heuristic is a problem-solving procedure that uses structured rules to obtain a good solution without guaranteeing optimality. A metaheuristic is a higher-level search strategy that guides or combines problem-specific procedures so that the search can explore promising regions while escaping local optima. Their value is not that they eliminate the need for optimization models, but that they provide flexible, scalable methods for obtaining high-quality feasible solutions under operational time limits.

This chapter develops constructive heuristics, savings methods, local search, tabu search, simulated annealing, genetic algorithms, variable-neighborhood search, and hybrid methods. Emphasis is placed on modeling assumptions, search mechanisms, evaluation, implementation, and managerial interpretation.

Learning objectives

By the end of this chapter, the reader should be able to:

1. Explain why route-planning problems motivate heuristic and metaheuristic methods.
2. Construct feasible routes using insertion, nearest-neighbor, and savings procedures.
3. Design local-search neighborhoods and evaluate route moves correctly.
4. Compare tabu search, simulated annealing, genetic algorithms, and variable-neighborhood search.
5. Combine exact optimization, heuristics, simulation, and operational data in hybrid methods.
6. Evaluate solution quality, robustness, computational effort, and implementation risk.

1. Problem setting and terminology

A capacitated vehicle-routing problem (CVRP) consists of a depot and a set of customers. Each customer has a demand, vehicles have capacity, and every customer must normally be visited once. A solution is a set of routes beginning and ending at the depot. In a time-window variant, customer i must be served within an interval [aᵢ, bᵢ]. In a pickup-and-delivery problem, precedence and vehicle-loading constraints also apply.

Let cᵢⱼ denote the cost of traveling from node i to node j, and let xᵢⱼ equal 1 if that arc is used and 0 otherwise. A basic routing objective is:

Here, Z may represent distance, monetary cost, emissions, or a weighted combination. The formula assumes that arc costs are known and additive. If travel times are uncertain, the cost may instead include expected delay, risk, or a penalty for unreliability. A multi-criteria objective can be written as:

where C_transport is transportation cost, C_labor is labor cost, C_late is lateness penalty, E is emissions, and w₁,…,w₄ are nonnegative managerial weights. The weights must be calibrated because arbitrary scaling can make one criterion dominate the others.

A solution is feasible only if it satisfies all applicable constraints. Typical constraints include vehicle capacity, maximum route duration, customer service windows, driver breaks, vehicle compatibility, depot hours, and precedence. A useful distinction is:

• Feasibility: all hard constraints are satisfied.
• Cost: the objective value of a feasible solution.
• Penalty: a quantified discouragement for violating a soft or temporarily relaxed constraint.
• Neighborhood: a set of solutions reachable from a current solution by one defined move.
• Local optimum: a solution with no improving neighbor under the selected neighborhood.
• Global optimum: the best solution over the complete feasible solution space.
• Diversification: directing search toward less-visited regions.
• Intensification: examining a promising region in greater detail.

A heuristic result should never be described as optimal unless optimality has been proven, for example by an exact method or a valid optimality certificate.

2. Why heuristics are necessary

Routing problems are combinatorial. Even a single-route traveling-salesperson problem has many possible sequences. With n customers, the number of undirected tours grows approximately as (n − 1)!/2. Adding multiple vehicles, capacities, time windows, and heterogeneous fleets produces a much larger constrained search space.

Exact mixed-integer programming can be highly effective for small or structured instances and is valuable for benchmarking. However, exact methods may face large branch-and-bound trees, weak linear relaxations, or substantial data uncertainty. Heuristics are especially useful when:

• decisions must be refreshed frequently;
• travel times and demands change during the day;
• the objective contains operational rules that are difficult to linearize;
• a good incumbent solution is more valuable than a delayed proof of optimality;
• planners require understandable and adjustable decision logic.

The central trade-off is speed and flexibility versus proof of optimality. A high-quality heuristic design therefore needs both a search mechanism and an evaluation protocol.

3. Constructive heuristics

Constructive heuristics begin with no complete solution and add customers or route components until a solution is formed. They are fast and usually provide the starting solution for local or metaheuristic search.

3.1 Nearest-neighbor construction

Nearest-neighbor construction starts at a depot, selects the nearest unserved feasible customer, appends that customer, and continues until no further feasible insertion is possible. A new route is then opened if customers remain.

The method is computationally simple, but it is myopic. An apparently nearby customer may have a restrictive time window or may be strategically important for connecting two distant clusters. Variants use generalized attractiveness rather than distance alone, such as:

where Aᵢⱼ is an attractiveness score, cᵢⱼ is travel cost, tᵢⱼ is travel time, pᵢⱼ is a penalty or risk measure, and α, β, γ are calibrated nonnegative coefficients. Lower Aᵢⱼ is preferred. The units of the terms must be made comparable, usually through normalization or monetary conversion.

3.2 Sequential and parallel insertion

Insertion heuristics begin with one or more partial routes. For an unserved customer u, the incremental cost of inserting u between consecutive nodes i and j is:

This expression is valid when the objective is additive travel cost and insertion does not alter other penalties. With time windows, capacity, or route-duration effects, the complete feasibility and cost change must be recalculated; the simple expression is then only a preliminary screening value.

A sequential insertion method completes one route before opening another. A parallel insertion method considers insertions across all currently open routes. Insertion priority may be based on regret. For customer u, if ∆c₁ and ∆c₂ are its best and second-best feasible insertion costs, the two-position regret is:

A large Rᵤ means that postponing customer u may cause a substantial loss of quality. Regret insertion therefore prioritizes customers whose placement is difficult or urgent.

3.3 Clarke–Wright savings algorithm

The savings algorithm begins with a separate route for every customer: depot–i–depot. It then considers merging routes containing i and j. The saving from replacing two depot legs with links i–j and j–i, in the symmetric case, is:

where 0 denotes the depot. A high positive saving indicates that joining i and j can reduce cost. Savings are sorted from largest to smallest, and a pair is merged if the resulting route remains feasible and i and j are eligible route endpoints.

The formula assumes symmetric costs, so cᵢⱼ = cⱼᵢ. For asymmetric travel, the direction must be considered and the savings calculation must use the actual directed arcs. The algorithm also assumes that the route merge does not violate capacity, duration, time-window, or compatibility constraints.

Illustrative calculation. Suppose c₀ᵢ = 12, c₀ⱼ = 15, and cᵢⱼ = 8 distance units. Then:

The separate routes use 54 distance units for the two customer visits, whereas the merged route uses 12 + 8 + 15 = 35 units, a saving of 19. This calculation concerns only the travel component; feasibility must still be checked.

The savings method is fast and often effective for geographically clustered customers. Its weaknesses are its greedy ordering, sensitivity to the initial route structure, and difficulty handling complex time-dependent or resource-constrained rules. Randomized savings lists and generalized savings scores can improve diversity.

4. Local search and neighborhood design

Local search starts from a feasible solution and repeatedly replaces it with a better neighboring solution. Common route neighborhoods include:

• Relocate: move one customer from one position or route to another.
• Swap: exchange two customers.
• 2-opt: remove two arcs and reconnect the route in the alternative order, reversing a segment.
• 2-opt\\*: exchange tails between two routes without necessarily reversing them.
• Or-opt: move a chain of two or three consecutive customers.
• Cross-exchange: exchange customer segments between routes.

For a symmetric route, a 2-opt move replacing arcs (i,j) and (k,l) with (i,k) and (j,l) has travel-cost change:

If ∆ < 0, the move improves the travel objective, provided feasibility is preserved. In asymmetric networks, reversing a segment changes arc directions and the full segment cost must be recalculated; the shortcut is not generally valid.

A search may use first improvement, accepting the first improving move found, or best improvement, evaluating all candidate moves and selecting the best. First improvement is usually faster per iteration; best improvement may make larger progress but requires more computation. Candidate lists, such as geographically nearest neighbors, reduce the number of evaluated moves but can exclude useful long-distance exchanges.

Pure descent terminates at a local optimum. This is not necessarily a poor solution: it is optimal only within the selected neighborhood, and a stronger neighborhood may reveal an improvement. Local search can also cycle if equal-cost moves are accepted without control.

5. Tabu search

Tabu search extends local search by using adaptive memory. A move or attribute of a move is placed on a tabu list for a specified tenure, preventing immediate reversal and encouraging exploration beyond local optima.

A typical iteration is:

1. Generate a candidate neighborhood.
2. Exclude tabu moves unless an aspiration condition applies.
3. Select the best admissible move, even if it worsens the objective.
4. Update the current solution and the best solution found.
5. Record the move attribute and update tabu tenure.

The aspiration criterion commonly permits a tabu move if it produces a solution better than the best known solution. Tabu status should often be assigned to attributes, such as a customer-to-route assignment or an arc, rather than an entire solution. This makes memory compact and flexible.

Short-term memory prevents cycling. Intermediate-term memory can reward frequently successful assignments, while long-term memory promotes diversification by penalizing overused arcs or encouraging rarely visited areas. Reactive tabu search changes tenure in response to observed cycling or stagnation.

Tabu search is powerful for routing because it can use complex, problem-specific neighborhoods and can continue through controlled infeasibility. If infeasible solutions are allowed, an evaluation function may be:

Here C(S) is the base cost, V terms are nonnegative violation magnitudes, and λ terms are penalty coefficients. Penalties must be large enough to discourage unacceptable violations but not so large that the search cannot traverse useful boundary regions. Dynamic penalties can increase when infeasibility persists and decrease when feasible solutions become scarce.

6. Simulated annealing

Simulated annealing accepts some worsening moves to escape local optima. If a candidate has objective change ∆ = F(S′) − F(S), an improving move with ∆ ≤ 0 is accepted. A worsening move is accepted with probability:

where T > 0 is the current temperature. The expression is dimensionally valid when ∆ and T are expressed in the same objective units, or when both are scaled consistently. A random number uniformly drawn from [0,1] is compared with P(accept).

Temperature is gradually reduced according to a cooling schedule, for example:

The initial temperature should permit a meaningful proportion of exploratory worsening moves. If it is too high, the search behaves almost randomly; if too low, the procedure becomes greedy. Cooling too quickly causes premature convergence, whereas cooling too slowly increases runtime. Reheating may be used after prolonged stagnation.

Unlike tabu search, simulated annealing does not require explicit memory of recent moves. It is simple and robust, but its performance depends strongly on temperature calibration, neighborhood scale, and stopping criteria.

7. Genetic algorithms

A genetic algorithm maintains a population of candidate solutions. It repeatedly selects parent solutions, applies crossover and mutation, evaluates offspring, and retains a new population. The basic stages are:

1. Generate an initial population, possibly including savings or insertion solutions.
2. Decode each chromosome into routes.
3. Evaluate cost and feasibility.
4. Select parents using a method such as tournament selection.
5. Produce offspring through a route-preserving crossover.
6. Mutate selected offspring.
7. Repair or penalize infeasible offspring.
8. Apply replacement and preserve an elite solution.

Representation is a central design issue. A simple customer permutation must be split into routes, often using a split dynamic program or a feasibility-aware decoder. Route-based representations may preserve route structure better but make crossover more difficult.

A standard permutation crossover such as partially mapped crossover can preserve each customer exactly once, but it does not automatically preserve capacity or time windows. Specialized operators, including route exchange, order crossover with split procedures, and edge recombination, are often preferable.

Mutation may relocate a customer, swap two customers, reverse a segment, or reassign a route. Excessive mutation destroys useful structure; insufficient mutation produces premature convergence. Diversity should be monitored through route similarity, allele frequencies, or objective dispersion.

Genetic algorithms are attractive for parallel exploration and multiobjective extensions. Their drawbacks include high evaluation cost, sensitivity to representation, and the possibility that many offspring are infeasible or structurally poor.

8. Variable-neighborhood search

Variable-neighborhood search (VNS) systematically changes the neighborhood structure because a solution that is locally optimal under one neighborhood may not be locally optimal under another. A basic VNS has three activities:

• Shaking: perturb the current solution in neighborhood k.
• Local improvement: apply local search, often using neighborhood N₁.
• Neighborhood change: if the new solution improves the incumbent, return to the first neighborhood; otherwise move to a larger or different neighborhood.

Typical neighborhoods progress from small to large: relocate, swap, 2-opt, 2-opt*, and cross-exchange. The method is conceptually simple but benefits from carefully selected neighborhood ordering. Large neighborhoods can be explored by sampling, restricted candidate lists, or adaptive large-neighborhood search rather than complete enumeration.

VNS is particularly useful when different types of structural error exist. For example, relocate may correct an individual assignment, while 2-opt corrects within-route sequencing and cross-exchange corrects poor route partitioning.

9. Hybrid and matheuristic methods

No single method dominates across all routing environments. Hybrid methods combine complementary strengths. A common architecture is:

Figure: A feedback architecture for hybrid route optimization.

A matheuristic embeds mathematical programming within a heuristic. Examples include solving a restricted set-partitioning model over routes generated by local search, using a mixed-integer model to optimize a selected neighborhood, or applying exact optimization to route sequencing after heuristic assignment. This approach can produce strong solutions without solving the full problem exactly.

Other useful hybrids include:

• savings construction followed by tabu search;
• genetic algorithms with local improvement of every offspring;
• VNS with an exact assignment subproblem;
• adaptive large-neighborhood search using destroy-and-repair operators;
• rolling-horizon reoptimization for dynamic routing;
• simulation-based evaluation of uncertain travel times.

The interface between methods should be explicit. A hybrid can fail if one component uses distance while another evaluates total cost including lateness, emissions, and driver hours.

10. Evaluating heuristic performance

A credible evaluation requires more than reporting the best route found once. Important measures include:

• objective value and cost components;
• percentage of instances solved feasibly;
• optimality gap when an exact benchmark is available;
• runtime and memory use;
• variability across random seeds;
• stability under demand and travel-time changes;
• service-level outcomes, such as on-time delivery;
• explainability and planner acceptance.

If Z_H is the heuristic objective and Z* is a known optimal objective for a minimization problem, the relative gap is:

This formula assumes Z* > 0 and comparable objective definitions. If the exact optimum is unknown, a lower bound L can be used cautiously:

The result is a bound relative to L, not necessarily the true optimality gap unless L is a valid lower bound.

Experiments should use representative instances, multiple independent runs for stochastic methods, fixed computational budgets, and statistical summaries such as mean, median, best, worst, and standard deviation. Comparisons must control for hardware, stopping rules, preprocessing, and objective functions. A method that obtains a slightly lower distance but violates service windows is not superior to a feasible alternative.

11. Worked mini-example: insertion and improvement

Consider a depot 0 and a current route 0–A–B–0. An unserved customer C is considered for insertion between A and B. Let c_AB = 10, c_AC = 6, and c_CB = 5. The incremental distance is:

Thus, inserting C increases distance by one unit. If the vehicle has sufficient residual capacity and the resulting arrival times satisfy all windows, the insertion is feasible. Suppose a different insertion between 0 and A increases distance by 4 units. A distance-only insertion heuristic chooses the A–B position.

Now suppose insertion between A and B causes a 12-minute time-window violation, with a penalty of 3 cost units per minute. Its penalized change is:

If the alternative insertion is feasible with increase 4, the alternative is preferred. This example illustrates why a travel-distance calculation alone is inadequate when service constraints are operationally important.

12. Illustrative case: urban grocery delivery

Background. Consider an illustrative grocery retailer operating 85 daily delivery orders from one urban depot. Orders have heterogeneous quantities, 30-minute delivery windows, and some refrigerated products. The fleet contains vans with two capacity classes. Traffic varies substantially between morning and afternoon.

Problem. The existing manual plan used fixed geographic zones. It produced feasible routes on ordinary days but generated overtime and late deliveries during peak traffic. Management wanted a plan in under five minutes because orders were confirmed continuously.

Analysis. Historical data showed that distance was not a sufficient objective. A route with fewer kilometers could still be worse if it crossed a congested corridor during a narrow time window. The team therefore used a generalized cost containing travel cost, overtime, lateness penalties, and a refrigeration-compatibility constraint. Travel times were estimated by time of day, with scenario testing for congestion.

Approach. A randomized savings heuristic created several initial route sets. Each was improved using VNS with relocate, swap, 2-opt*, and cross-exchange neighborhoods. A tabu component prevented repeated customer-route reversals. A small mixed-integer model selected among promising route patterns and assigned vehicle types. The final candidates were evaluated under several traffic scenarios.

Outcome. In the illustrative experiment, the hybrid method consistently produced feasible plans within the five-minute limit and reduced expected overtime relative to the zone-based baseline. The principal benefit was not simply lower distance; it was better alignment between route sequence, time windows, and congestion exposure. The result would require field validation before being treated as an empirical claim.

Learning points. First, the objective must reflect service consequences. Second, diversification through multiple initial solutions can be valuable. Third, a small exact subproblem may strengthen a heuristic without making the entire problem intractable. Fourth, planners need scenario results and override controls, not only a single algorithmic answer.

13. Challenges, governance, and contemporary practice

Heuristics are sensitive to data quality. Incorrect coordinates, outdated vehicle capacities, missing service times, and biased travel-time predictions can make an algorithmically excellent solution operationally unusable. Data validation and exception handling are therefore part of algorithm design.

Penalty functions create governance risks. If lateness penalties are set too low, the system may systematically sacrifice certain customers or neighborhoods. If an AI prediction model supplies travel times, its errors may be correlated with weather, infrastructure, or geographic disadvantage. Human review, transparent objective definitions, audit logs, and fairness monitoring are appropriate controls.

Sustainability objectives should be interpreted carefully. Distance is only a proxy for emissions. A more valid emissions estimate may depend on vehicle type, load, speed, idling, temperature, and energy source. Multiobjective methods can generate a Pareto set rather than hide trade-offs in one arbitrary weighted sum.

Contemporary implementations increasingly use real-time data, cloud computation, digital twins, and machine-learning forecasts. Machine learning is useful for predicting travel time or demand, but it does not replace combinatorial search. A robust architecture separates prediction from optimization, tracks prediction uncertainty, and evaluates plans under scenarios. Reinforcement learning and neural constructive policies are active research areas, but they require careful benchmarking against transparent classical heuristics and should not be deployed solely because they are technically fashionable.

14. Best-practice design principles

1. Define hard constraints, soft constraints, and penalty policies before selecting an algorithm.
2. Build a strong constructive solution, but use multiple starts when the problem is sensitive to initial structure.
3. Match neighborhoods to operational errors: relocation for assignment, 2-opt for sequencing, and cross-route moves for partitioning.
4. Use incremental cost calculations only when their assumptions hold; otherwise recompute affected route feasibility.
5. Separate intensification from diversification and monitor stagnation.
6. Compare stochastic methods using repeated runs and fixed computational budgets.
7. Benchmark small instances against exact solutions whenever possible.
8. Report feasibility, service levels, runtime, and variability—not only distance.
9. Validate candidate routes through simulation when travel times or demand are uncertain.
10. Provide human-readable route explanations, manual overrides, and audit trails.

Chapter Summary

Heuristics and metaheuristics provide scalable approaches to route planning when exact optimization is too slow, too rigid, or difficult to integrate with operational data. Constructive methods such as nearest-neighbor, insertion, and Clarke–Wright savings rapidly generate feasible starting solutions. Local search improves these solutions through carefully designed neighborhoods including relocate, swap, 2-opt, and cross-exchange.

Tabu search uses adaptive memory to prevent cycling and balance intensification with diversification. Simulated annealing accepts selected worsening moves according to a temperature-dependent probability. Genetic algorithms explore populations of solutions but require suitable representations, crossover operators, mutation, and repair. Variable-neighborhood search changes the neighborhood structure to escape local optima. Hybrid and matheuristic methods combine these techniques with exact subproblems, simulation, and predictive analytics.

Evaluation must consider feasibility, objective value, optimality gaps, runtime, repeatability, robustness, service performance, explainability, and governance. The strongest practical method is often not the most theoretically elaborate one, but the method whose objective, data, constraints, and operating decisions are aligned.

Key Terms

Heuristic: A structured procedure that seeks a good solution without guaranteeing optimality.

Metaheuristic: A high-level strategy that guides search across a broad solution space.

Constructive heuristic: A method that builds a solution incrementally.

Neighborhood: The set of solutions reachable through a defined move.

Local search: Iterative improvement through neighboring solutions.

Local optimum: A solution with no improvement in the selected neighborhood.

Regret insertion: An insertion rule prioritizing customers whose delayed placement is costly.

Savings algorithm: A route-merging method based on the reduction from joining separate routes.

Relocate move: Moving one customer or chain to another route position.

2-opt: A move replacing two arcs and reconnecting the route differently.

Tabu search: Local search using memory to restrict repeated moves.

Aspiration criterion: A rule allowing a tabu move when it meets a superior condition.

Simulated annealing: A stochastic search accepting some worsening moves using a temperature parameter.

Genetic algorithm: Population-based search using selection, crossover, and mutation.

Variable-neighborhood search: Search that systematically changes neighborhood structures.

Diversification: Exploration of less-visited regions of the search space.

Intensification: Detailed search around promising solutions.

Matheuristic: A hybrid combining mathematical programming with heuristic search.

Optimality gap: The relative difference between a solution and a known optimum or bound.

Penalty function: An objective augmentation that discourages constraint violations.

Review Questions

Short Answer Questions

1. Why can a heuristic be operationally valuable even when it does not prove optimality?
2. State the symmetric Clarke–Wright savings formula and define its terms.
3. What is the difference between intensification and diversification?
4. Why must a 2-opt cost shortcut be treated carefully in asymmetric networks?
5. What is the purpose of an aspiration criterion in tabu search?

Long Answer Questions

1. Compare constructive heuristics, local search, tabu search, simulated annealing, genetic algorithms, and VNS in terms of search behavior, strengths, and limitations.
2. Explain how time windows and soft constraints change the design of a routing heuristic.
3. Discuss representation, crossover, mutation, and repair choices in a genetic algorithm for vehicle routing.
4. Design an evaluation experiment for comparing two stochastic route-planning algorithms.
5. Explain how a matheuristic can combine a restricted exact model with heuristic route generation.

Analytical / Application Questions

1. A route contains arcs (i,j) and (k,l). Under symmetric travel costs, derive the 2-opt cost change and explain the feasibility checks required before accepting the move.
2. Design a hybrid algorithm for a grocery distributor with capacity constraints, time windows, uncertain traffic, and a five-minute planning limit. Justify the constructive method, neighborhoods, stopping rule, and evaluation measures.
3. A heuristic has a cost of 12,400, while an exact benchmark has cost 12,000. Calculate the percentage gap and explain why feasibility and computational time must also be reported.

Multiple Choice Questions with Answers

Question 1

Which condition is required before merging two routes in the Clarke–Wright savings algorithm?

A. The saving must be negative

B. The merged route must remain feasible

C. Both routes must contain the same customers

D. The depot must be removed

Correct Answer: B. The merged route must remain feasible

Question 2

If c₀ᵢ = 12, c₀ⱼ = 15, and cᵢⱼ = 8, what is the symmetric savings value?

A. 5

B. 11

C. 19

D. 35

Correct Answer: C. 19

Question 3

What is the main purpose of a tabu list?

A. To guarantee global optimality

B. To prevent or discourage cycling through recent moves

C. To eliminate all infeasible solutions permanently

D. To calculate travel times

Correct Answer: B. To prevent or discourage cycling through recent moves

Question 4

In simulated annealing, what happens to the acceptance probability of a worsening move when temperature decreases, assuming the worsening amount is fixed and positive?

A. It increases

B. It becomes exactly one

C. It decreases

D. It becomes independent of the worsening amount

Correct Answer: C. It decreases

Question 5

Which move transfers a customer from its current position to another position?

A. Relocate

B. Selection

C. Cooling

D. Aspiration

Correct Answer: A. Relocate

Question 6

A customer insertion replaces arc (i,j) with arcs (i,u) and (u,j). Under additive travel cost, what is the incremental travel cost?

A. cᵢⱼ − cᵢᵤ − cᵤⱼ

B. cᵢᵤ + cᵤⱼ − cᵢⱼ

C. cᵢᵤ − cᵤⱼ + cᵢⱼ

D. cᵢᵤ × cᵤⱼ × cᵢⱼ

Correct Answer: B. cᵢᵤ + cᵤⱼ − cᵢⱼ

Question 7

What distinguishes variable-neighborhood search from a single-neighborhood local search?

A. It never accepts an improving move

B. It systematically changes neighborhood structures

C. It requires a population of chromosomes

D. It can only solve unconstrained problems

Correct Answer: B. It systematically changes neighborhood structures

Question 8

Which genetic-algorithm component combines information from parent solutions?

A. Cooling schedule

B. Crossover

C. Tabu tenure

D. Penalty scaling

Correct Answer: B. Crossover

Question 9

A heuristic cost is 12,400 and the known optimum is 12,000. What is the relative gap?

A. 0.33%

B. 3.33%

C. 30%

D. 400%

Correct Answer: B. 3.33%

Question 10

Why might a hybrid route-planning method include a small mixed-integer programming subproblem?

A. To replace all operational data

B. To provide exact optimization over a restricted decision set

C. To ensure every heuristic is random

D. To remove the need for feasibility checks

Correct Answer: B. To provide exact optimization over a restricted decision set