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 a Solution pool. 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 Model[source]¶

A simple interface for modelling vehicle routing problems with PyVRP.

Attributes

`locations`	Returns all locations (depots and clients) in the current model.
`vehicle_types`	Returns the vehicle types in the current model.

Methods

`add_client`(x, y[, demand, service_duration, ...])	Adds a client with the given attributes to the model.
`add_depot`(x, y[, tw_early, tw_late, name])	Adds a depot with the given attributes to the model.
`add_edge`(frm, to, distance[, duration])	Adds an edge \((i, j)\) between `frm` (\(i\)) and `to` (\(j\)).
`add_vehicle_type`([num_available, capacity, ...])	Adds a vehicle type with the given attributes to the model.
`data`()	Creates and returns a `ProblemData` instance from this model's attributes.
`from_data`(data)	Constructs a model instance from the given data.
`solve`(stop[, seed])	Solve this model.

property locations : list[Client]¶: Returns all locations (depots and clients) in the current model. The clients in the routes of the solution returned by solve() can be used to index these locations.

property vehicle_types : list[VehicleType]¶: Returns the vehicle types in the current model. The routes of the solution returned by solve() have a property vehicle_type() that can be used to index these vehicle types.

classmethod from_data(data: ProblemData) → Model[source]¶

Constructs a model instance from the given data.

Parameters:

data: ProblemData¶: Problem data to feed into the model.

Returns:

A model instance representing the given data.

Return type:

Model

add_client(x: int, y: int, demand: int = 0, service_duration: int = 0, tw_early: int = 0, tw_late: int = 0, release_time: int = 0, prize: int = 0, required: bool = True, name: str = '') → Client[source]¶: Adds a client with the given attributes to the model. Returns the created Client instance.

add_depot(x: int, y: int, tw_early: int = 0, tw_late: int = 0, name: str = '') → Client[source]¶: Adds a depot with the given attributes to the model. Returns the created Client instance.

add_edge(frm: Client, to: Client, distance: int, duration: int = 0) → Edge[source]¶

Adds an edge \((i, j)\) between frm (\(i\)) and to (\(j\)). The edge can be given distance and duration attributes. Distance is required, but the default duration is zero. Returns the created edge.

Raises:: ValueError – When either distance or duration is a negative value, or when self loops have nonzero distance or duration values.

add_vehicle_type(num_available: int = 1, capacity: int = 0, depot: Client | None = None, fixed_cost: int = 0, tw_early: int | None = None, tw_late: int | None = None, max_duration: int | None = None, name: str = '') → VehicleType[source]¶

Adds a vehicle type with the given attributes to the model. Returns the created vehicle type.

Note

The vehicle type is assigned to the first depot if depot is not provided.

Raises:: ValueError – When the given depot is not already added to this model instance.

data() → ProblemData[source]¶: Creates and returns a ProblemData instance from this model’s attributes.

solve(stop: StoppingCriterion, seed: int = 0) → Result[source]¶

Solve this model.

Parameters:

stop: StoppingCriterion¶: Stopping criterion to use.
seed: int = 0¶: Seed value to use for the PRNG, by default 0.

Returns:

The solution result object, containing the best found solution.

Return type:

Result

class Edge(frm: Client, to: Client, distance: int, duration: int)[source]¶

Stores an edge connecting two locations.

Attributes

distance
duration
frm
to

class GeneticAlgorithmParams(repair_probability: float = 0.8, nb_iter_no_improvement: int = 20000)[source]¶

Parameters for the genetic algorithm.

Parameters:

repair_probability : ¶: Probability (in \([0, 1]\)) of repairing an infeasible solution. If the reparation makes the solution feasible, it is also added to the population in the same iteration.
nb_iter_no_improvement : ¶: Number of iterations without any improvement needed before a restart occurs.

repair_probability¶

Probability of repairing an infeasible solution.

Type:: float

nb_iter_no_improvement¶

Number of iterations without improvement before a restart occurs.

Type:: int

Raises:: ValueError – When repair_probability is not in \([0, 1]\), or nb_iter_no_improvement is negative.

class GeneticAlgorithm(data: ProblemData, penalty_manager: PenaltyManager, rng: RandomNumberGenerator, population: Population, search_method: SearchMethod, crossover_op: Callable[[tuple[Solution, Solution], ProblemData, CostEvaluator, RandomNumberGenerator], Solution], initial_solutions: Collection[Solution], params: GeneticAlgorithmParams = GeneticAlgorithmParams(repair_probability=0.8, nb_iter_no_improvement=20000))[source]¶

Creates a GeneticAlgorithm instance.

Parameters:

data: ProblemData¶: Data object describing the problem to be solved.
penalty_manager: PenaltyManager¶: Penalty manager to use.
rng: RandomNumberGenerator¶: Random number generator.
population: Population¶: Population to use.
search_method: SearchMethod¶: Search method to use.
crossover_op: Callable[[tuple[Solution, Solution], ProblemData, CostEvaluator, RandomNumberGenerator], Solution]¶: Crossover operator to use for generating offspring.
initial_solutions: Collection[Solution]¶: Initial solutions to use to initialise the population.
params: GeneticAlgorithmParams = GeneticAlgorithmParams(repair_probability=0.8, nb_iter_no_improvement=20000)¶: Genetic algorithm parameters. If not provided, a default will be used.

Raises:

ValueError – When the population is empty.

Methods

`run`(stop)	Runs the genetic algorithm with the provided stopping criterion.

run(stop: StoppingCriterion)[source]¶

Runs the genetic algorithm with the provided stopping criterion.

Parameters:

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

Returns:

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

Return type:

Result

class PenaltyParams(init_capacity_penalty: int = 20, init_time_warp_penalty: int = 6, repair_booster: int = 12, num_registrations_between_penalty_updates: int = 50, penalty_increase: float = 1.34, penalty_decrease: float = 0.32, target_feasible: float = 0.43)[source]¶

The penalty manager parameters.

Parameters:

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.
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.
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_booster_cost_evaluator().
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.
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\).
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\).
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.

init_capacity_penalty¶

Initial penalty on excess capacity.

Type:: int

init_time_warp_penalty¶

Initial penalty on time warp.

Type:: int

repair_booster¶

A repair booster value.

Type:: int

num_registrations_between_penalty_updates¶

Number of feasibility registrations between penalty value updates.

Type:: int

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.

Type:: float

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.

Type:: float

target_feasible¶

Target percentage \(p_f \in [0, 1]\) of feasible registrations in the last num_registrations_between_penalty_updates registrations.

Type:: float

class PenaltyManager(params: PenaltyParams = PenaltyParams(init_capacity_penalty=20, init_time_warp_penalty=6, repair_booster=12, num_registrations_between_penalty_updates=50, penalty_increase=1.34, penalty_decrease=0.32, target_feasible=0.43))[source]¶

Creates a PenaltyManager instance.

This class manages time warp and load penalties, and provides penalty terms for given time warp and load values. It updates these penalties based on recent history, and can be used to provide a temporary penalty booster object that increases the penalties for a short duration.

Parameters:

params: PenaltyParams = PenaltyParams(init_capacity_penalty=20, init_time_warp_penalty=6, repair_booster=12, num_registrations_between_penalty_updates=50, penalty_increase=1.34, penalty_decrease=0.32, target_feasible=0.43)¶: PenaltyManager parameters. If not provided, a default will be used.

Methods

`get_booster_cost_evaluator`()	Get a cost evaluator for the boosted current penalty values.
`get_cost_evaluator`()	Get a cost evaluator for the current penalty values.
`register_load_feasible`(is_load_feasible)	Registers another capacity feasibility result.
`register_time_feasible`(is_time_feasible)	Registers another time feasibility result.

register_load_feasible(is_load_feasible: bool)[source]¶

Registers another capacity feasibility result. The current load penalty is updated once sufficiently many results have been gathered.

Parameters:

is_load_feasible: bool¶: Boolean indicating whether the last solution was feasible w.r.t. the capacity constraint.

register_time_feasible(is_time_feasible: bool)[source]¶

Registers another time feasibility result. The current time warp penalty is updated once sufficiently many results have been gathered.

Parameters:

is_time_feasible: bool¶: Boolean indicating whether the last solution was feasible w.r.t. the time constraint.

get_cost_evaluator() → CostEvaluator[source]¶

Get a cost evaluator for the current penalty values.

Returns:: A CostEvaluator instance that uses the current penalty values.
Return type:: CostEvaluator

get_booster_cost_evaluator()[source]¶

Get a cost evaluator for the boosted current penalty values.

Returns:: A CostEvaluator instance that uses the booster penalty values.
Return type:: CostEvaluator

class PopulationParams(min_pop_size: int = 25, generation_size: int = 40, nb_elite: int = 4, nb_close: int = 5, lb_diversity: float = 0.1, ub_diversity: float = 0.5)¶

Creates a parameters object to be used with Population.

Attributes

generation_size
lb_diversity
max_pop_size
min_pop_size
nb_close
nb_elite
ub_diversity

class Population(diversity_op: Callable[[Solution, Solution], float], params: PopulationParams | None = None)[source]¶

Creates a Population instance.

Parameters:

diversity_op: Callable[[Solution, Solution], float]¶: Operator to use to determine pairwise diversity between solutions. Have a look at pyvrp.diversity for available operators.
params: PopulationParams | None = None¶: Population parameters. If not provided, a default will be used.

Methods

`add`(solution, cost_evaluator)	Adds the given solution to the population.
`clear`()	Clears the population by removing all solutions currently in the population.
`get_tournament`(rng, cost_evaluator[, k])	Selects a solution from this population by k-ary tournament, based on the (internal) fitness values of the selected solutions.
`num_feasible`()	Returns the number of feasible solutions in the population.
`num_infeasible`()	Returns the number of infeasible solutions in the population.
`select`(rng, cost_evaluator[, k])	Selects two (if possible non-identical) parents by tournament, subject to a diversity restriction.

__iter__() → Generator[Solution, None, None][source]¶

Iterates over the solutions contained in this population.

Yields:: Solution – Solutions currently in this population.

__len__() → int[source]¶

Returns the current population size.

Returns:: Population size.
Return type:: int

num_feasible() → int[source]¶

Returns the number of feasible solutions in the population.

Returns:: Number of feasible solutions.
Return type:: int

num_infeasible() → int[source]¶

Returns the number of infeasible solutions in the population.

Returns:: Number of infeasible solutions.
Return type:: int

add(solution: Solution, cost_evaluator: CostEvaluator)[source]¶

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

Parameters:

solution: Solution¶: Solution to add to the population.
cost_evaluator: CostEvaluator¶: CostEvaluator to use to compute the cost.

clear()[source]¶: Clears the population by removing all solutions currently in the population.

select(rng: RandomNumberGenerator, cost_evaluator: CostEvaluator, k: int = 2) → tuple[Solution, Solution][source]¶

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

Parameters:

rng: RandomNumberGenerator¶: Random number generator.
cost_evaluator: CostEvaluator¶: Cost evaluator to use when computing the fitness.
k: int = 2¶: The number of solutions to draw for the tournament. Defaults to two, which results in a binary tournament.

Returns:

A solution pair (parents).

Return type:

tuple

get_tournament(rng: RandomNumberGenerator, cost_evaluator: CostEvaluator, k: int = 2) → Solution[source]¶

Selects a solution from this population by k-ary tournament, based on the (internal) fitness values of the selected solutions.

Parameters:

rng: RandomNumberGenerator¶: Random number generator.
cost_evaluator: CostEvaluator¶: Cost evaluator to use when computing the fitness.
k: int = 2¶: The number of solutions to draw for the tournament. Defaults to two, which results in a binary tournament.

Returns:

The selected solution.

Return type:

Solution

read(where: str | Path, instance_format: str = 'vrplib', round_func: str | Callable[[ndarray], ndarray] = 'none') → ProblemData[source]¶

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

Note

See the VRPLIB format explanation page for more details.

Parameters:

where: str | Path¶

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

instance_format: str = 'vrplib'¶

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

round_func: str | Callable[[ndarray], ndarray] = 'none'¶

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.

Raises:

TypeError – When round_func does not name a rounding function, or is not callable.
ValueError – When the data file does not provide information on the problem size.

Returns:

Data instance constructed from the read data.

Return type:

ProblemData

read_solution(where: str | Path) → list[list[int]][source]¶

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

Parameters:

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

Returns:

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

Return type:

list

class Result(best: Solution, stats: Statistics, num_iterations: int, runtime: float)[source]¶

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.
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.
`is_feasible`()	Returns whether the best solution is feasible.

cost() → float[source]¶

Returns the cost (objective) value of the best solution. Returns inf if the best solution is infeasible.

Returns:: Objective value.
Return type:: float

is_feasible() → bool[source]¶

Returns whether the best solution is feasible.

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

show_versions()[source]¶

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[source]¶

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, cost_evaluator)	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, cost_evaluator: CostEvaluator)[source]¶

Collects statistics from the given population object.

Parameters:

population: Population¶: Population instance to collect statistics from.
cost_evaluator: CostEvaluator¶: CostEvaluator used to compute costs for solutions.

classmethod from_csv(where: Path | str, delimiter: str = ',', **kwargs)[source]¶

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

Parameters:

where: Path | str¶: Filesystem location to read from.
delimiter: str = ','¶: Value separator. Default comma.
**kwargs¶: Additional keyword arguments. These are passed to csv.DictReader.

Returns:

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

Return type:

Statistics

to_csv(where: Path | str, delimiter: str = ',', quoting: int = 0, **kwargs)[source]¶

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

Parameters:

where: Path | str¶: Filesystem location to write to.
delimiter: str = ','¶: Value separator. Default comma.
quoting: int = 0¶: Quoting strategy. Default only quotes values when necessary.
**kwargs¶: Additional keyword arguments. These are passed to csv.DictWriter.

class CostEvaluator(capacity_penalty: int, tw_penalty: int)¶

Creates a CostEvaluator instance.

This class contains time warp and load penalties, and can compute penalties for a given time warp and load.

Parameters:

capacity_penalty: int¶: The penalty for each unit of excess load over the vehicle capacity.
tw_penalty: int¶: The penalty for each unit of time warp.

Methods

`cost`(self, solution)	Hand-waving some details, each solution consists of a set of routes \(\mathcal{R}\).
`load_penalty`(self, load, capacity)	Computes the total excess capacity penalty for the given load.
`penalised_cost`(self, solution)	Computes a smoothed objective (penalised cost) for a given solution.
`tw_penalty`(self, time_warp)	Computes the time warp penalty for the given time warp.

cost(self, solution: Solution) → int¶

Hand-waving some details, each solution consists of a set of routes \(\mathcal{R}\). Each route \(R \in \mathcal{R}\) is a sequence of edges, starting and ending at the depot. A route \(R\) has an assigned vehicle type \(t_R\), which has a fixed vehicle cost \(f_{t_R}\). Let \(V_R = \{i : (i, j) \in R \}\) be the set of locations visited by route \(R\). The objective value is then given by

\[\sum_{R \in \mathcal{R}} \left[ f_{t_R} + \sum_{(i, j) \in R} d_{ij} \right] + \sum_{i \in V} p_i - \sum_{R \in \mathcal{R}} \sum_{i \in V_R} p_i,\]

where the first part lists the vehicle and distance costs, and the second part the uncollected prizes of unvisited clients.

Note

The above cost computation only holds for feasible solutions. If the solution argument is infeasible, we return a very large number. If that is not what you want, consider calling penalised_cost() instead.

load_penalty(self, load: int, capacity: int) → int¶: Computes the total excess capacity penalty for the given load.

penalised_cost(self, solution: Solution) → int¶: Computes a smoothed objective (penalised cost) for a given solution.

tw_penalty(self, time_warp: int) → int¶: Computes the time warp penalty for the given time warp.

class Route(data: ProblemData, visits: list[int], vehicle_type: int)¶

A simple class that stores the route plan and some statistics.

Methods

`centroid`(self)	Center point of the client locations on this route.
`demand`(self)	Total client demand on this route.
`distance`(self)	Total distance travelled on this route.
`duration`(self)	Total route duration, including travel, service and waiting time.
`end_time`(self)	End time of the route.
`excess_load`(self)	Demand in excess of the vehicle's capacity.
`has_excess_load`(self)
`has_time_warp`(self)
`is_feasible`(self)
`prizes`(self)	Total prize value collected on this route.
`release_time`(self)	Earliest time at which this route can leave the depot.
`service_duration`(self)	Total duration of service on this route.
`slack`(self)	Time by which departure from the depot can be delayed without resulting in (additional) time warp or increased route duration.
`start_time`(self)	Start time of this route.
`time_warp`(self)	Amount of time warp incurred on this route.
`travel_duration`(self)	Total duration of travel on this route.
`vehicle_type`(self)	Index of the type of vehicle used on this route.
`visits`(self)	Route visits, as a list of clients.
`wait_duration`(self)	Total waiting duration on this route.

centroid(self) → tuple[float, float]¶: Center point of the client locations on this route.

demand(self) → int¶: Total client demand on this route.

distance(self) → int¶: Total distance travelled on this route.

duration(self) → int¶: Total route duration, including travel, service and waiting time.

end_time(self) → int¶: End time of the route. This is equivalent to start_time + duration - time_warp.

excess_load(self) → int¶: Demand in excess of the vehicle’s capacity.

has_excess_load(self) → bool¶

has_time_warp(self) → bool¶

is_feasible(self) → bool¶

prizes(self) → int¶: Total prize value collected on this route.

release_time(self) → int¶: Earliest time at which this route can leave the depot. Follows from the release times of clients visited on this route.

Note

The route’s release time should not be later than its start time, unless the route has time warp.

service_duration(self) → int¶: Total duration of service on this route.

slack(self) → int¶: Time by which departure from the depot can be delayed without resulting in (additional) time warp or increased route duration.

start_time(self) → int¶: Start time of this route. This is the earliest possible time at which the route can leave the depot and have a minimal duration and time warp. If there is positive slack(), the start time can be delayed by at most slack() time units without increasing the total (minimal) route duration, or time warp.

Note

It may be possible to leave before the start time (if the depot time window allows for it). That will introduce additional waiting time, such that the route duration will then no longer be minimal. Delaying departure by more than slack() time units always increases time warp, which could turn the route infeasible.

time_warp(self) → int¶: Amount of time warp incurred on this route.

travel_duration(self) → int¶: Total duration of travel on this route.

vehicle_type(self) → int¶: Index of the type of vehicle used on this route.

visits(self) → list[int]¶: Route visits, as a list of clients.

wait_duration(self) → int¶: Total waiting duration on this route.

class Solution(data: ProblemData, routes: list[Route] | list[list[int]])¶

Encodes VRP solutions.

Parameters:

data: ProblemData¶: Data instance.
routes: list[Route] | list[list[int]]¶: Route list to use. Can be a list of Route objects, or a lists of client visits. In case of the latter, all routes are assigned vehicles of the first type. That need not be a feasible assignment!

Raises:

RuntimeError – When the given solution is invalid in one of several ways. In particular when the number of routes in the routes argument exceeds num_vehicles, when an empty route has been passed as part of routes, when too many vehicles of a particular type have been used, or when a client is visited more than once.

Methods

`distance`(self)	Returns the total distance over all routes.
`excess_load`(self)	Returns the total excess load over all routes.
`fixed_vehicle_cost`(self)	Returns the fixed vehicle cost of all vehicles used in this solution.
`get_neighbours`(self)	Returns a list of neighbours for each client, by index.
`get_routes`(self)	The solution's routing decisions.
`has_excess_load`(self)	Returns whether this solution violates capacity constraints.
`has_time_warp`(self)	Returns whether this solution violates time window constraints.
`is_complete`(self)	Returns whether this solution is complete, which it is when it has all required clients.
`is_feasible`(self)	Whether this solution is feasible.
`make_random`(data, rng)	Creates a randomly generated solution.
`num_clients`(self)	Number of clients in this solution.
`num_missing_clients`(self)	Number of required clients that are not in this solution.
`num_routes`(self)	Number of routes in this solution.
`prizes`(self)	Returns the total collected prize value over all routes.
`time_warp`(self)	Returns the total time warp load over all routes.
`uncollected_prizes`(self)	Total prize value of all clients not visited in this solution.

distance(self) → int¶

Returns the total distance over all routes.

Returns:: Total distance over all routes.
Return type:: int

excess_load(self) → int¶

Returns the total excess load over all routes.

Returns:: Total excess load over all routes.
Return type:: int

fixed_vehicle_cost(self) → int¶

Returns the fixed vehicle cost of all vehicles used in this solution.

Returns:: Total fixed vehicle cost.
Return type:: int

get_neighbours(self) → list[tuple[int, int] | None]¶

Returns a list of neighbours for each client, by index.

Returns:: A list of (pred, succ) tuples that encode for each client their predecessor and successors in this solutions’s routes. None in case the client is not in the solution (or is a depot).
Return type:: list

get_routes(self) → list[Route]¶

The solution’s routing decisions.

Returns:: A list of routes. Each Route starts and ends at the depot (0), but that is implicit: the depot is not part of the returned routes.
Return type:: list

has_excess_load(self) → bool¶

Returns whether this solution violates capacity constraints.

Returns:: True if the solution is not capacity feasible, False otherwise.
Return type:: bool

has_time_warp(self) → bool¶

Returns whether this solution violates time window constraints.

Returns:: True if the solution is not time window feasible, False otherwise.
Return type:: bool

is_complete(self) → bool¶

Returns whether this solution is complete, which it is when it has all required clients.

Returns:: True if the solution visits all required clients, False otherwise.
Return type:: bool

is_feasible(self) → bool¶

Whether this solution is feasible. This is a shorthand for checking has_excess_load(), has_time_warp(), and is_complete().

Returns:: Whether the solution of this solution is feasible with respect to capacity and time window constraints, and has all required clients.
Return type:: bool

make_random(data: ProblemData, rng: RandomNumberGenerator) → Solution¶

Creates a randomly generated solution.

Parameters:

data: ProblemData¶: Data instance.
rng: RandomNumberGenerator¶: Random number generator to use.

Returns:

The randomly generated solution.

Return type:

Solution

num_clients(self) → int¶

Number of clients in this solution.

Returns:: Number of clients in this solution.
Return type:: int

num_missing_clients(self) → int¶

Number of required clients that are not in this solution.

Returns:: Number of required but missing clients.
Return type:: int

num_routes(self) → int¶

Number of routes in this solution.

Returns:: Number of routes.
Return type:: int

prizes(self) → int¶

Returns the total collected prize value over all routes.

Returns:: Value of collected prizes.
Return type:: int

time_warp(self) → int¶

Returns the total time warp load over all routes.

Returns:: Total time warp over all routes.
Return type:: int

uncollected_prizes(self) → int¶

Total prize value of all clients not visited in this solution.

Returns:: Value of uncollected prizes.
Return type:: int

class Client(x: int, y: int, demand: int = 0, service_duration: int = 0, tw_early: int = 0, tw_late: int = 0, release_time: int = 0, prize: int = 0, required: bool = True, name: str = '')¶

Simple data object storing all client data as (read-only) properties.

Parameters:

x: int¶: Horizontal coordinate of this client, that is, the ‘x’ part of the client’s (x, y) location tuple.
y: int¶: Vertical coordinate of this client, that is, the ‘y’ part of the client’s (x, y) location tuple.
demand: int = 0¶: The amount this client’s demanding. Default 0.
service_duration: int = 0¶: This client’s service duration, that is, the amount of time we need to visit the client for. Service should start (but not necessarily end) within the [tw_early, tw_late] interval. Default 0.
tw_early: int = 0¶: Earliest time at which we can visit this client. Default 0.
tw_late: int = 0¶: Latest time at which we can visit this client. Default 0.
release_time: int = 0¶: Earliest time at which this client is released, that is, the earliest time at which a vehicle may leave the depot to visit this client. Default 0.
prize: int = 0¶: Prize collected by visiting this client. Default 0.
required: bool = True¶: Whether this client must be part of a feasible solution. Default True.
name: str = ''¶: Free-form name field for this client. Default empty.

Attributes

demand
name
prize
release_time
required
service_duration
tw_early
tw_late
x
y

class VehicleType(num_available: int = 1, capacity: int = 0, depot: int = 0, fixed_cost: int = 0, tw_early: int | None = None, tw_late: int | None = None, max_duration: int | None = None, name: str = '')¶

Simple data object storing all vehicle type data as properties.

Note

If tw_early is set, then also tw_late must be provided to completely specify the shift duration (and vice versa). If neither are given, the shift duration defaults to the depot’s time window.

Parameters:

num_available: int = 1¶: Number of vehicles of this type that are available. Must be positive. Default 1.
capacity: int = 0¶: Capacity (maximum total demand) of this vehicle type. Must be non-negative. Default 0.
depot: int = 0¶: Depot (location index) that vehicles of this type dispatch from, and return to at the end of their routes. Default 0 (first depot).
fixed_cost: int = 0¶: Fixed cost of using a vehicle of this type. Default 0.
tw_early: int | None = None¶: Start of the vehicle type’s shift. Defaults to the depot’s opening time if not given.
tw_late: int | None = None¶: End of the vehicle type’s shift. Defaults to the depot’s closing time if not given.
max_duration: int | None = None¶: Maximum route duration. Unconstrained if not explicitly set.
name: str = ''¶: Free-form name field for this vehicle type. Default empty.

num_available¶: Number of vehicles of this type that are available.

depot¶: Depot associated with these vehicles.

capacity¶: Capacity (maximum total demand) of this vehicle type.

fixed_cost¶: Fixed cost of using a vehicle of this type.

tw_early¶: Start of the vehicle type’s shift, if specified.

tw_late¶: End of the vehicle type’s shift, if specified.

max_duration¶: Maximum duration of the route this vehicle type is assigned to. This is a very large number when the maximum duration is unconstrained.

name¶: Free-form name field for this vehicle type.

Attributes

capacity
depot
fixed_cost
max_duration
name
num_available
tw_early
tw_late

class ProblemData(clients: list[Client], depots: list[Client], vehicle_types: list[VehicleType], distance_matrix: list[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:

clients: list[Client]¶: List of clients to visit.
depots: list[Client]¶: List of depots. Depots should have no demand or service duration.
vehicle_types: list[VehicleType]¶: List of vehicle types in the problem instance.
distance_matrix: list[list[int]]¶: A matrix that gives the distances between clients (and the depot at index 0).
duration_matrix: list[list[int]]¶: A matrix that gives the travel times between clients (and the depot at index 0).

Attributes

`num_clients`	Number of clients in this problem instance.
`num_depots`	Number of depots in this problem instance.
`num_locations`	Number of locations in this problem instance, that is, the number of depots plus the number of clients in the instance.
`num_vehicle_types`	Number of vehicle types in this problem instance.
`num_vehicles`	Number of vehicles in this problem instance.

Methods

`centroid`(self)	Center point of all client locations (excluding depots).
`clients`(self)	Returns a list of all clients in the problem instance.
`depots`(self)	Returns a list of all depots in the problem instance.
`dist`(self, first, second)	Returns the travel distance between the first and second argument, according to this instance's travel distance matrix.
`distance_matrix`(self)	The full travel distance matrix.
`duration`(self, first, second)	Returns the travel duration between the first and second argument, according to this instance's travel duration matrix.
`duration_matrix`(self)	The full travel duration matrix.
`location`(self, idx)	Returns location data for the location at the given index.
`replace`(self[, clients, depots, ...])	Returns a new ProblemData instance with the same data as this instance, except for the given parameters, which are used instead.
`vehicle_type`(self, vehicle_type)	Returns vehicle type data for the given vehicle type.
`vehicle_types`(self)	Returns a list of all vehicle types in the problem instance.

centroid(self) → tuple[float, float]¶

Center point of all client locations (excluding depots).

Returns:: Centroid of all client locations.
Return type:: tuple

clients(self) → list[Client]¶

Returns a list of all clients in the problem instance.

Returns:: List of all clients in the problem instance.
Return type:: List[Client]

depots(self) → list[Client]¶

Returns a list of all depots in the problem instance.

Returns:: List of all depots in the problem instance.
Return type:: List[Client]

dist(self, first: int, second: int) → int¶

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

Parameters:

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

Returns:

Travel distance between the given clients.

Return type:

int

distance_matrix(self) → ndarray[int]¶: The full travel distance matrix.

Note

This method returns a read-only view of the underlying data. No matrix is copied, but the resulting data cannot be modified in any way!

duration(self, first: int, second: int) → int¶

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

Parameters:

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

Returns:

Travel duration between the given clients.

Return type:

int

duration_matrix(self) → ndarray[int]¶: The full travel duration matrix.

Note

This method returns a read-only view of the underlying data. No matrix is copied, but the resulting data cannot be modified in any way!

location(self, idx: int) → Client¶

Returns location data for the location at the given index. This can be a depot or a client: a depot if the idx argument is smaller than num_depots, and a client if the idx is bigger than that.

Parameters:

idx: int¶: Location index whose information to retrieve.

Returns:

A simple data object containing the requested location’s information.

Return type:

Client

property num_clients : int¶

Number of clients in this problem instance.

Returns:: Number of clients in the instance.
Return type:: int

property num_depots : int¶

Number of depots in this problem instance.

Returns:: Number of depots in the instance.
Return type:: int

property num_locations : int¶

Number of locations in this problem instance, that is, the number of depots plus the number of clients in the instance.

Returns:: Number of depots plus the number of clients in the instance.
Return type:: int

property num_vehicle_types : int¶

Number of vehicle types in this problem instance.

Returns:: Number of vehicle types in this problem instance.
Return type:: int

property num_vehicles : int¶

Number of vehicles in this problem instance.

Returns:: Number of vehicles in this problem instance.
Return type:: int

replace(self, clients: list[Client] | None = None, depots: list[Client] | None = None, vehicle_types: list[VehicleType] | None = None, distance_matrix: ndarray[int] | None = None, duration_matrix: ndarray[int] | None = None) → ProblemData¶

Returns a new ProblemData instance with the same data as this instance, except for the given parameters, which are used instead.

Parameters:

clients: list[Client] | None = None¶: Optional list of clients.
depots: list[Client] | None = None¶: Optional list of depots.
vehicle_types: list[VehicleType] | None = None¶: Optional list of vehicle types.
distance_matrix: ndarray[int] | None = None¶: Optional distance matrix.
duration_matrix: ndarray[int] | None = None¶: Optional duration matrix.

Returns:

A new ProblemData instance with possibly replaced data.

Return type:

ProblemData

vehicle_type(self, vehicle_type: int) → VehicleType¶

Returns vehicle type data for the given vehicle type.

Parameters:

vehicle_type: int¶: Vehicle type number whose information to retrieve.

Returns:

A simple data object containing the vehicle type information.

Return type:

VehicleType

vehicle_types(self) → list[VehicleType]¶

Returns a list of all vehicle types in the problem instance.

Returns:: List of all vehicle types in the problem instance.
Return type:: List[VehicleType]

class DynamicBitset(num_bits: int)¶

A simple dynamic bitset implementation. This class functions as a fast set for membership checks on the integers. That is particularly useful for testing if e.g. clients are in a solution or not.

Parameters:

num_bits: int¶: Number of integers in [0, num_bits) this bitset must be able to store. If num_bits is not a multiple of BLOCK_SIZE, the actual size is rounded up towards the next multiple.

Methods

`count`(self)

__and__(self, other: DynamicBitset) → DynamicBitset¶

__eq__(self, other: DynamicBitset) → bool¶

__getitem__(self, idx: int) → bool¶

__invert__(self) → DynamicBitset¶

__len__(self) → int¶

__or__(self, other: DynamicBitset) → DynamicBitset¶

__setitem__(self, idx: int, value: bool)¶

__xor__(self, other: DynamicBitset) → DynamicBitset¶

count(self) → int¶

class RandomNumberGenerator(seed: int)¶

This class implements a XOR-shift pseudo-random number generator (RNG). It generates the next number of a sequence by repeatedly taking the ‘exclusive or’ (the ^ operator) of a number with a bit-shifted version of itself. See here for more details.

Parameters:

seed: int¶: Seed used to set the initial RNG state.

Methods

`__call__`(self)
`max`()
`min`()
`rand`(self)
`randint`(self, high)
`state`(self)

__call__(self) → int¶

max() → int¶

min() → int¶

rand(self) → float¶

randint(self, high: int) → int¶

state(self) → list[int[4]]¶

exception EmptySolutionWarning[source]¶: Raised when an empty solution is being added to the Population. This is not forbidden, per se, but very odd.

exception ScalingWarning[source]¶: Raised when the distance or duration values in the problem are very large, which could cause the algorithm to start using forbidden edges as well.

exception TspWarning[source]¶: Raised when the problem is a TSP but a component is used that explicitly requires the presence of two or more vehicles (i.e., a proper VRP).