PyVRP

The top-level pyvrp module exposes several core classes needed to run the VRP solver. These include the core GeneticAlgorithm, and the Population that manages Individual solutions. Most classes take parameter objects that allow for advanced configuration - but sensible defaults are also provided. Finally, after running, the GeneticAlgorithm returns a Result object. This object can be used to obtain the best observed solution, and detailed runtime statistics.

Hint

Have a look at the examples to see how these classes relate!

class GeneticAlgorithmParams

collect_statistics = False

intensify_on_best = True

intensify_probability = 0.15

nb_iter_no_improvement = 20000

repair_probability = 0.8

class GeneticAlgorithm(data: pyvrp._ProblemData.ProblemData, penalty_manager: pyvrp._PenaltyManager.PenaltyManager, rng: pyvrp._XorShift128.XorShift128, population: pyvrp.Population.Population, local_search: pyvrp.educate.LocalSearch.LocalSearch, crossover_op: CrossoverOperator, params: GeneticAlgorithmParams = GeneticAlgorithmParams())

run(stop: pyvrp.stop.StoppingCriterion)

Runs the genetic algorithm with the provided stopping criterion.

Parameters:

stop: Stopping criterion to use. The algorithm runs until the first time the stopping criterion returns True.

Returns:

Result: A Result object, containing statistics and the best found solution.

class Individual(data: pyvrp._ProblemData.ProblemData, penalty_manager: pyvrp._PenaltyManager.PenaltyManager, rng: pyvrp._XorShift128.XorShift128)

The Individual class encodes VRP solutions.

cost()

Returns the current cost of the individual’s solution.

Note

These costs depend on the current penalty values maintained by the PenaltyManager used to construct the individual.

Returns:

int: The current cost of this individual.

get_neighbours()

Returns a list of neighbours for each client, by index. Also includes the depot at index 0, which only neighbours itself.

Returns:

list: A list of (pred, succ) tuples that encode for each client their predecessor and successors in this individual’s routes.

get_routes()

The solution this individual encodes, as a list of routes.

Note

This list is of length num_vehicles, but there could be a number of empty routes. These empty routes are all in the higher indices (guarantee). Use num_routes() to determine which of the lower indices contain non-empty routes.

Returns:

list: A list of routes, where each route is a list of client numbers. The routes each start and end at the depot (0), but that is implicit: the depot is not part of the returned routes.

has_excess_capacity()

Returns whether this individual violates capacity constraints.

Returns:

bool: True if the individual is not capacity feasible, False otherwise.

has_time_warp()

Returns whether this individual violates time window constraints.

Returns:

bool: True if the individual is not time window feasible, False otherwise.

is_feasible()

Whether this individual is feasible. This is a shorthand for checking has_excess_capacity() and has_time_warp() both return false.

Returns:

bool: Whether the solution of this individual is feasible with respect to capacity and time window constraints.

num_routes()

Number of non-empty routes in this solution.

Returns:

int: Number of non-empty routes.

class PenaltyParams(init_capacity_penalty: int = ..., init_time_warp_penalty: int = ..., repair_booster: int = ..., num_registrations_between_penalty_updates: int = ..., penalty_increase: float = ..., penalty_decrease: float = ..., target_feasible: float = ...)

The penalty manager parameters. These parameters control how the penalties are updated throughout the search. See the property descriptions for an explanation of the arguments.

property init_capacity_penalty

Initial penalty on excess capacity. This is the amount by which one unit of excess load capacity is penalised in the objective, at the start of the search.

Returns:

int: Initial capacity penalty.

property init_time_warp_penalty

Initial penalty on time warp. This is the amount by which one unit of time warp (time window violations) is penalised in the objective, at the start of the search.

Returns:

int: Initial time warp penalty.

property num_registrations_between_penalty_updates

Number of feasibility registrations between penalty value updates. The penalty manager updates the penalty terms every once in a while based on recent feasibility registrations. This parameter controls how often such updating occurs.

Returns:

int: Number of feasibility registrations between penalty updates.

property penalty_decrease

Amount \(p_d \in [0, 1]\) by which the current penalties are decreased when sufficient feasible solutions (see target_feasible) have been found amongst the most recent registrations. The penalty values \(v\) are updated as \(v \gets p_d v\).

Returns:

float: Penalty decrease parameter \(p_d\).

property penalty_increase

Amount \(p_i \ge 1\) by which the current penalties are increased when insufficient feasible solutions (see target_feasible) have been found amongst the most recent registrations. The penalty values \(v\) are updated as \(v \gets p_i v\).

Returns:

float: Penalty increase parameter \(p_i\).

property repair_booster

A repair booster value \(r \ge 1\). This value is used to temporarily multiply the current penalty terms, to force feasibility. See also get_penalty_booster().

Returns:

int: The repair booster value \(r\).

property target_feasible

Target percentage \(p_f \in [0, 1]\) of feasible registrations in the last num_registrations_between_penalty_updates registrations. This percentage is used to update the penalty terms: when insufficient feasible solutions have been registered, the penalties are increased; similarly, when too many feasible solutions have been registered, the penalty terms are decreased. This ensures a balanced population, with a fraction \(p_f\) feasible and a fraction \(1 - p_f\) infeasible solutions.

Returns:

float: Target percentage of feasible solutions in the population \(p_f\).

class PenaltyManager(vehicle_capacity: int, params: PenaltyParams)

get_penalty_booster()

Returns a penalty booster context manager. When entered, the penalty booster increases the penalties of this penalty manager until the context manager is exited again. See repair_booster for the amount by which the penalty terms are increased.

Examples

>>> pm = PenaltyManager(...)
>>> with pm.get_penalty_booster():
>>>     ...

load_penalty(load: int)

register_load_feasible(is_load_feasible: bool)

register_time_feasible(is_time_feasible: bool)

tw_penalty(time_warp: int)

class PopulationParams(min_pop_size: int = ..., generation_size: int = ..., nb_elite: int = ..., nb_close: int = ..., lb_diversity: float = ..., ub_diversity: float = ...)

generation_size

lb_diversity

property max_pop_size

min_pop_size

nb_close

nb_elite

ub_diversity

class Population(data: ~pyvrp._ProblemData.ProblemData, penalty_manager: ~pyvrp._PenaltyManager.PenaltyManager, rng: ~pyvrp._XorShift128.XorShift128, diversity_op: ~typing.Callable[[~pyvrp._Individual.Individual, ~pyvrp._Individual.Individual], float], params: ~pyvrp._SubPopulation.PopulationParams = <pyvrp._SubPopulation.PopulationParams object>)

Creates a Population instance.

Parameters:

data: Data object describing the problem to be solved.
penalty_manager: Penalty manager to use.
rng: Random number generator.
diversity_op: Operator to use to determine pairwise diversity between solutions. Have a look at pyvrp.diversity for available operators.
params, optional: Population parameters. If not provided, a default will be used.

Methods

`add`(individual)	Adds the given individual to the population.
`get_binary_tournament`()	Selects an individual from this population by binary tournament.
`num_feasible`()	Returns the number of feasible individuals in the population.
`num_infeasible`()	Returns the number of infeasible individuals in the population.
`restart`()	Restarts the population.
`select`()	Selects two (if possible non-identical) parents by binary tournament, subject to a diversity restriction.

__iter__() → Generator[Individual, None, None]

Iterates over the individuals contained in this population.

Yields:

iterable: An iterable object of individuals.

__len__() → int

Returns the current population size.

Returns:

int: Population size.

add(individual: Individual)

Adds the given individual to the population. Survivor selection is automatically triggered when the population reaches its maximum size.

Parameters:

individual: Individual to add to the population.

get_binary_tournament() → Individual

Selects an individual from this population by binary tournament.

Returns:

Individual: The selected individual.

num_feasible() → int

Returns the number of feasible individuals in the population.

Returns:

int: Number of feasible individuals.

num_infeasible() → int

Returns the number of infeasible individuals in the population.

Returns:

int: Number of infeasible individuals.

restart(): Restarts the population. All individuals are removed and a new initial population population is generated.

select() → Tuple[Individual, Individual]

Selects two (if possible non-identical) parents by binary tournament, subject to a diversity restriction.

Returns:

tuple: A pair of individuals (parents).

class Client

Simple data object storing all client data as properties.

Attributes:

demand: The amount this client’s demanding.
service_duration: This client’s service duration, that is, the amount of time we need to visit the client for.
tw_early: Earliest time at which we can visit this client.
tw_late: Latest time at which we can visit this client.
x: Horizontal coordinate of this client, that is, the ‘x’ part of the client’s (x, y) location tuple.
y: Vertical coordinate of this client, that is, the ‘y’ part of the client’s (x, y) location tuple.

demand

service_duration

tw_early

tw_late

x

y

class ProblemData(coords: List[Tuple[int, int]], demands: List[int], nb_vehicles: int, vehicle_cap: int, time_windows: List[Tuple[int, int]], service_durations: List[int], duration_matrix: List[List[int]])

Creates a problem data instance. This instance contains all information needed to solve the vehicle routing problem.

Parameters:

coords: Array of (x, y) coordinates. The first coordinate at index 0 is assumed to be the depot.
demands: Array of client demands. The demand at index 0 is assumed to be the depot’s demand, and should be zero.
nb_vehicles: The number of vehicles in this problem instance.
vehicle_cap: Homogenous vehicle capacity for all vehicles in the problem instance.
time_windows: Array of (early, late) time windows. The time window at index 0 is assumed to be the depot’s time window, and describes the overall time horizon.
service_durations: Array of service durations, that is, the length of time needed to service a customer upon visiting. The service duration at index 0 is assumed to be the depot’s service time, and should be zero.
duration_matrix: A matrix that gives the travel times between clients (and the depot at index 0). Does not have to be symmetric.

Notes

All array data assume that the data at or involving index 0 relates to the depot, and all other indices specify client information.

client(client: int)

Returns client data for the given client.

Parameters:

client: Client number whose information to retrieve.

Returns:

Client: A simple data object containing the requested client’s information.

depot()

Returns ‘client’ information for the depot, which is stored internally as the client with number 0.

Returns:

Client: A simple data object containing the depot’s information.

dist(first: int, second: int)

Returns the travel duration between the first and second argument, according to this instance’s travel duration matrix.

Parameters:

first: Client or depot number.
second: Client or depot number.

Returns:

int: Travel duration between the given clients.

distance_matrix()

Returns the travel duration matrix used for distance/duration computations.

Returns:

Any: Travel duration matrix.

property num_clients

Number of clients in this problem instance.

Returns:

int: Number of clients in the instance.

property num_vehicles

Number of vehicles in this problem instance.

Returns:

int: Number of vehicles in the instance.

property vehicle_capacity

Returns the homogenous vehicle capacities of all vehicles in this problem data instance.

Returns:

int: Capacity of each vehicle in the instance.

read(where: str | ~pathlib.Path, instance_format: str = 'vrplib', round_func: str | ~typing.Callable[[~numpy.ndarray], ~numpy.ndarray] = <function no_rounding>) → ProblemData

Reads the VRPLIB file at the given location, and returns a ProblemData instance.

Parameters:

where

File location to read. Assumes the data on the given location is in VRPLIB format.

instance_format, optional

File format of the instance to read, one of 'vrplib' (default) or 'solomon'.

round_func, optional

Optional rounding function. Will be applied to round data if the data is not already integer. This can either be a function or a string:

'round' rounds the values to the nearest integer;

'trunc' truncates the values to be integral;

'trunc1' or 'dimacs' scale and truncate to the nearest decimal;

'none' does no rounding. This is the default.

Returns:

ProblemData: Data instance constructed from the read data.

read_solution(where: str | Path) → List[List[int]]

Reads a solution in VRPLIB format from file at the given location, and returns the routes contained in it.

Parameters:

where: File location to read. Assumes the solution in the file on the given location is in VRPLIB solution format.

Returns:

list: List of routes, where each route is a list of client numbers.

class Result(best: Individual, stats: Statistics, num_iterations: int, runtime: float)

Stores the outcomes of a single run. An instance of this class is returned once the GeneticAlgorithm completes.

Parameters:

best: The best observed solution.
stats: A Statistics object containing runtime statistics. These are only collected and available if statistics were collected for the given run.
num_iterations: Number of iterations performed by the genetic algorithm.
runtime: Total runtime of the main genetic algorithm loop.

Raises:

ValueError: When the number of iterations or runtime are negative.

Methods

`cost`()	Returns the cost (objective) value of the best solution.
`has_statistics`()	Returns whether detailed statistics were collected.
`is_feasible`()	Returns whether the best solution is feasible.

cost() → float

Returns the cost (objective) value of the best solution.

Returns:

float: Objective value.

has_statistics() → bool

Returns whether detailed statistics were collected. If statistics are not availabe, the plotting methods cannot be used.

Returns:

bool: True when detailed statistics are available, False otherwise.

is_feasible() → bool

Returns whether the best solution is feasible.

Returns:

bool: True when the solution is feasible, False otherwise.

show_versions()

This function prints version information that is useful when filing bug reports.

Examples

Calling this function should print information like the following (dependency versions in your local installation will likely differ):

>>> import pyvrp
>>> pyvrp.show_versions()
INSTALLED VERSIONS
------------------
     pyvrp: 1.0.0
     numpy: 1.24.2
matplotlib: 3.7.0
    vrplib: 1.0.1
      tqdm: 4.64.1
     tomli: 2.0.1
    Python: 3.9.13

class Statistics(runtimes: ~typing.List[float] = <factory>, num_iterations: int = 0, feas_stats: ~typing.List[~pyvrp.Statistics._Datum] = <factory>, infeas_stats: ~typing.List[~pyvrp.Statistics._Datum] = <factory>)

The Statistics object tracks various (population-level) statistics of genetic algorithm runs. This can be helpful in analysing the algorithm’s performance.

Methods

`collect_from`(population)	Collects statistics from the given population object.
`from_csv`(where[, delimiter])	Reads a Statistics object from the CSV file at the given filesystem location.
`to_csv`(where[, delimiter, quoting])	Writes this Statistics object to the given location, as a CSV file.

collect_from(population: Population)

Collects statistics from the given population object.

Parameters:

population: Population instance to collect statistics from.

classmethod from_csv(where: Path | str, delimiter: str = ',', **kwargs)

Reads a Statistics object from the CSV file at the given filesystem location.

Parameters:

where: Filesystem location to read from.
delimiter: Value separator. Default comma.
kwargs: Additional keyword arguments. These are passed to csv.DictReader.

Returns:

Statistics: Statistics object populated with the data read from the given filesystem location.

to_csv(where: Path | str, delimiter: str = ',', quoting: int = 0, **kwargs)

Writes this Statistics object to the given location, as a CSV file.

Parameters:

where: Filesystem location to write to.
delimiter: Value separator. Default comma.
quoting: Quoting strategy. Default only quotes values when necessary.
kwargs: Additional keyword arguments. These are passed to csv.DictWriter.

class XorShift128(seed: int)

__call__()

__init__(seed: int)

static max()

static min()

rand()

randint(high: int)