Crossover operators¶
The pyvrp.crossover module provides operators that are responsible for generating a new Solution offspring from two parent solutions.
- ordered_crossover(parents: tuple[Solution, Solution], data: ProblemData, cost_evaluator: CostEvaluator, rng: RandomNumberGenerator) Solution[source]¶
Performs an ordered crossover (OX) operation between the two given parents. The clients between two randomly selected indices of the first route are copied into a new solution, and any missing clients that are present in the second route are then copied in as well. See [1] for details.
Warning
This operator explicitly assumes the problem instance is a TSP. You should use a different crossover operator if that is not the case.
- Parameters:
- parents: tuple[Solution, Solution]¶
The two parent solutions to create an offspring from.
- data: ProblemData¶
The problem instance.
- cost_evaluator: CostEvaluator¶
Cost evaluator object. Unused by this operator.
- rng: RandomNumberGenerator¶
The random number generator to use.
- Returns:
A new offspring.
- Return type:
- Raises:
ValueError – When the given data instance is not a TSP, particularly, when there is more than one vehicle in the data.
References
[1]I. M. Oliver, D. J. Smith, and J. R. C. Holland. 1987. A study of permutation crossover operators on the traveling salesman problem. In Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application. 224 - 230.
- selective_route_exchange(parents: tuple[Solution, Solution], data: ProblemData, cost_evaluator: CostEvaluator, rng: RandomNumberGenerator) Solution[source]¶
The selective route exchange crossover (SREX) operator due to Nagata and Kobayashi [1] combines routes from both parents to generate a new offspring solution. It does this by carefully selecting routes from the second parent that could be exchanged with routes from the first parent. This often results in incomplete offspring that can then be repaired using a search method.
Note
Since SREX exchanges routes, it is not an appropriate crossover operator for TSP instances where each solution consists of just one route. SREX warns when used for TSPs, and another crossover operator should ideally be used when solving such instances.
- Parameters:
- parents: tuple[Solution, Solution]¶
The two parent solutions to create an offspring from.
- data: ProblemData¶
The problem instance.
- cost_evaluator: CostEvaluator¶
The cost evaluator used to evaluate the offspring.
- rng: RandomNumberGenerator¶
The random number generator to use.
- Returns:
A new offspring.
- Return type:
References
[1]Nagata, Y., & Kobayashi, S. (2010). A Memetic Algorithm for the Pickup and Delivery Problem with Time Windows Using Selective Route Exchange Crossover. Parallel Problem Solving from Nature, PPSN XI, 536 - 545.