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

groups

Returns all client groups currently in the model.

locations

Returns all locations (depots and clients) in the current model.

profiles

Returns all routing profiles currently in the model.

vehicle_types

Returns the vehicle types in the current model.

Methods

add_client(x, y[, delivery, pickup, ...])

Adds a client with the given attributes to the model.

add_client_group([required])

Adds a new, possibly optional, client group to the model.

add_depot(x, y, *[, name])

Adds a depot with the given attributes to the model.

add_edge(frm, to, distance[, duration, profile])

Adds an edge \((i, j)\) between frm (\(i\)) and to (\(j\)).

add_profile()

Adds a new routing profile to the model.

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, collect_stats, display, ...])

Solve this model.

property locations : list[Client | Depot]

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 groups : list[ClientGroup]

Returns all client groups currently in the model.

property profiles : list[Profile]

Returns all routing profiles currently in the model.

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, delivery: int = 0, pickup: int = 0, service_duration: int = 0, tw_early: int = 0, tw_late: int = np.iinfo(np.int64).max, release_time: int = 0, prize: int = 0, required: bool = True, group: ClientGroup | None = None, *, name: str = '') Client[source]

Adds a client with the given attributes to the model. Returns the created Client instance.

Raises:

ValueError – When group is not None, and the given group is not part of this model instance, or when a required client is being added to a mutually exclusive client group.

add_client_group(required: bool = True) ClientGroup[source]

Adds a new, possibly optional, client group to the model. Returns the created group.

add_depot(x: int, y: int, *, name: str = '') Depot[source]

Adds a depot with the given attributes to the model. Returns the created Depot instance.

add_edge(frm: Client | Depot, to: Client | Depot, distance: int, duration: int = 0, profile: Profile | None = None) 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.

Note

If profile is not provided, the edge is a base edge that will be set for all profiles in the model. Any profile-specific edge takes precendence over a base edge with the same frm and to locations.

add_profile() Profile[source]

Adds a new routing profile to the model.

add_vehicle_type(num_available: int = 1, capacity: int = 0, start_depot: Depot | None = None, end_depot: Depot | None = None, fixed_cost: int = 0, tw_early: int = 0, tw_late: int = np.iinfo(np.int64).max, max_duration: int = np.iinfo(np.int64).max, max_distance: int = np.iinfo(np.int64).max, unit_distance_cost: int = 1, unit_duration_cost: int = 0, profile: Profile | None = None, *, name: str = '') VehicleType[source]

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

Note

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

Raises:

ValueError – When the given depot or profile arguments are not in this model instance.

data() ProblemData[source]

Creates and returns a ProblemData instance from this model’s attributes.

solve(stop: StoppingCriterion, seed: int = 0, collect_stats: bool = True, display: bool = True, params: SolveParams = SolveParams()) Result[source]

Solve this model.

Parameters:
stop: StoppingCriterion

Stopping criterion to use.

seed: int = 0

Seed value to use for the random number stream. Default 0.

collect_stats: bool = True

Whether to collect statistics about the solver’s progress. Default True.

display: bool = True

Whether to display information about the solver progress. Default True. Progress information is only available when collect_stats is also set, which it is by default.

params: SolveParams = SolveParams()

Solver parameters to use. If not provided, a default will be used.

Returns:

A Result object, containing statistics (if collected) and the best found solution.

Return type:

Result

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

Stores an edge connecting two locations.

Raises:

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

Attributes

distance

duration

frm

to

class Profile[source]

Stores a routing profile.

A routing profile is a collection of edges with distance and duration attributes that together define a complete distance and duration matrix. These can be used to model, for example, the road uses of different types of vehicles, like trucks, cars, or bicyclists. Each VehicleType is associated with a routing profile.

Methods

add_edge(frm, to, distance[, duration])

Adds a new edge to this routing profile.

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

Adds a new edge to this routing profile.

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())[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()

Genetic algorithm parameters. If not provided, a default will be used.

Raises:

ValueError – When the population is empty.

Methods

run(stop[, collect_stats, display])

Runs the genetic algorithm with the provided stopping criterion.

run(stop: StoppingCriterion, collect_stats: bool = True, display: bool = False)[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.

collect_stats: bool = True

Whether to collect statistics about the solver’s progress. Default True.

display: bool = False

Whether to display information about the solver progress. Default False. Progress information is only available when collect_stats is also set.

Returns:

A Result object, containing statistics (if collected) and the best found solution.

Return type:

Result

class PenaltyParams(repair_booster: int = 12, solutions_between_updates: int = 50, penalty_increase: float = 1.34, penalty_decrease: float = 0.32, target_feasible: float = 0.43)[source]

The penalty manager parameters.

Parameters:
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 booster_cost_evaluator().

solutions_between_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 solutions_between_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.

repair_booster

A repair booster value.

Type:

int

solutions_between_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 solutions_between_updates registrations.

Type:

float

class PenaltyManager(params: PenaltyParams = PenaltyParams(), initial_penalties: tuple[int, int, int] = (20, 6, 6))[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.

Note

Consider initialising using init_from() to compute initial penalty values that are scaled according to the data instance.

Parameters:
params: PenaltyParams = PenaltyParams()

PenaltyManager parameters. If not provided, a default will be used.

initial_penalties: tuple[int, int, int] = (20, 6, 6)

Initial penalty values for unit load (idx 0), duration (1), and distance (2) violations. Defaults to (20, 6, 6) for backwards compatibility. These values are clipped to the range [MIN_PENALTY, MAX_PENALTY].

Methods

booster_cost_evaluator()

Get a cost evaluator using the boosted current penalty values.

cost_evaluator()

Get a cost evaluator using the current penalty values.

init_from(data[, params])

Initialises from the given data instance and parameter object.

register(sol)

Registers the feasibility dimensions of the given solution.

classmethod init_from(data: ProblemData, params: PenaltyParams = PenaltyParams()) PenaltyManager[source]

Initialises from the given data instance and parameter object. The initial penalty values are computed from the problem data.

Parameters:
data: ProblemData

Data instance to use when computing penalty values.

params: PenaltyParams = PenaltyParams()

PenaltyManager parameters. If not provided, a default will be used.

register(sol: Solution)[source]

Registers the feasibility dimensions of the given solution.

cost_evaluator() CostEvaluator[source]

Get a cost evaluator using the current penalty values.

booster_cost_evaluator() CostEvaluator[source]

Get a cost evaluator using the boosted current penalty values.

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)

Parameter configuration for the Population.

min_pop_size

Minimum subpopulation size. This is the size of the subpopulation after survivor selection.

generation_size

The size of a single generation, that is, the number of new solutions inserted into a subpopulation between survivor selections.

nb_elite

Number of elite solutions. This number of fittest solutions are always survivors.

nb_close

Number of close solutions. These are used to determine similarity between solutions, which is an important component of fitness.

lb_diversity

A lower bound on the diversity of the solutions selected for tournament. See select() for details.

ub_diversity

An upper bound on the diversity of the solutions selected for tournament. See select() for details.

Attributes

max_pop_size

Returns the maximum subpopulation size.

generation_size

lb_diversity

min_pop_size

nb_close

nb_elite

ub_diversity

property max_pop_size : int

Returns the maximum subpopulation size.

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)

Inserts the given solution in the appropriate feasible or infeasible (sub)population.

clear()

Clears the population by removing all solutions currently in the population.

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.

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.

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

Iterates over the solutions contained in this population.

__len__() int[source]

Returns the current population size.

num_feasible() int[source]

Returns the number of feasible solutions in the population.

num_infeasible() int[source]

Returns the number of infeasible solutions in the population.

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

Inserts the given solution in the appropriate feasible or infeasible (sub)population.

Note

Survivor selection is automatically triggered when the subpopulation reaches its maximum size, given by max_pop_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

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, 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.

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

Optional rounding function that is applied to all data values in the instance. This can either be a function or a string:

  • 'round' rounds the values to the nearest integer;

  • 'trunc' truncates the values to an integer;

  • 'dimacs' scales by 10 and truncates the values to an integer;

  • 'exact' scales by 1000 and rounds to the nearest integer.

  • '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 the give file 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.

summary()

Returns a nicely formatted result summary.

cost() float[source]

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

is_feasible() bool[source]

Returns whether the best solution is feasible.

summary() str[source]

Returns a nicely formatted result summary.

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 SolveParams(genetic: GeneticAlgorithmParams = GeneticAlgorithmParams(), penalty: PenaltyParams = PenaltyParams(), population: PopulationParams = PopulationParams(), neighbourhood: NeighbourhoodParams = NeighbourhoodParams(), node_ops: list[type[NodeOperator]] = NODE_OPERATORS, route_ops: list[type[RouteOperator]] = ROUTE_OPERATORS)[source]

Solver parameters for PyVRP’s hybrid genetic search algorithm.

Parameters:
genetic: GeneticAlgorithmParams = GeneticAlgorithmParams()

Genetic algorithm parameters.

penalty: PenaltyParams = PenaltyParams()

Penalty parameters.

population: PopulationParams = PopulationParams()

Population parameters.

neighbourhood: NeighbourhoodParams = NeighbourhoodParams()

Neighbourhood parameters.

node_ops: list[type[NodeOperator]] = NODE_OPERATORS

Node operators to use in the search.

route_ops: list[type[RouteOperator]] = ROUTE_OPERATORS

Route operators to use in the search.

Attributes

genetic

neighbourhood

node_ops

penalty

population

route_ops

Methods

from_file(loc)

Loads the solver parameters from a TOML file.

classmethod from_file(loc: str | Path)[source]

Loads the solver parameters from a TOML file.

solve(data: ProblemData, stop: StoppingCriterion, seed: int = 0, collect_stats: bool = True, display: bool = False, params: SolveParams = SolveParams()) Result[source]

Solves the given problem data instance.

Parameters:
data: ProblemData

Problem data instance to solve.

stop: StoppingCriterion

Stopping criterion to use.

seed: int = 0

Seed value to use for the random number stream. Default 0.

collect_stats: bool = True

Whether to collect statistics about the solver’s progress. Default True.

display: bool = False

Whether to display information about the solver progress. Default False. Progress information is only available when collect_stats is also set, which it is by default.

params: SolveParams = SolveParams()

Solver parameters to use. If not provided, a default will be used.

Returns:

A Result object, containing statistics (if collected) and the best found solution.

Return type:

Result

class Statistics(collect_stats: bool = True)[source]

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

Parameters:
collect_stats: bool = True

Whether to collect statistics at all. This can be turned off to avoid excessive memory use on long runs.

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.

is_collecting

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 = csv.QUOTE_MINIMAL, **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 = csv.QUOTE_MINIMAL

Quoting strategy. Default only quotes values when necessary.

**kwargs

Additional keyword arguments. These are passed to csv.DictWriter.

class CostEvaluator(load_penalty: int, tw_penalty: int, dist_penalty: int)

Creates a CostEvaluator instance.

This class stores various penalty terms, and can be used to determine the costs of certain constraint violations.

Parameters:
load_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.

dist_penalty: int

The penalty for each unit of distance in excess of the vehicle’s maximum distance constraint.

Methods

cost(self, solution)

Hand-waving some details, each solution consists of a set of non-empty routes \(\mathcal{R}\).

dist_penalty(self, distance, max_distance)

Computes the time warp penalty for the given time warp.

load_penalty(self, load, capacity)

Computes the total excess load penalty for the given load and vehicle capacity.

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 non-empty routes \(\mathcal{R}\). Each route \(R \in \mathcal{R}\) is a sequence of edges, starting and ending at a depot. Each route \(R\) has an assigned vehicle type, through which the route is equipped with a fixed vehicle cost \(f_R\), and unit distance and duration costs \(c^\text{distance}_R\) and \(c^\text{duration}_R\), respectively. Let \(V_R = \{i : (i, j) \in R \}\) be the set of locations visited by route \(R\), and \(d_R\) and \(t_R\) the total route distance and duration, respectively. The objective value is then given by

\[\sum_{R \in \mathcal{R}} \left[ f_R + c^\text{distance}_R d_R + c^\text{duration}_R t_R \right] + \sum_{i \in V} p_i - \sum_{R \in \mathcal{R}} \sum_{i \in V_R} p_i,\]

where the first part lists each route’s fixed, distance and duration costs, respectively, 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.

dist_penalty(self, distance: int, max_distance: int) int

Computes the time warp penalty for the given time warp.

load_penalty(self, load: int, capacity: int) int

Computes the total excess load penalty for the given load and vehicle capacity.

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.

delivery(self)

Total client delivery load on this route.

distance(self)

Total distance travelled on this route.

distance_cost(self)

Total cost of the distance travelled on this route.

duration(self)

Total route duration, including travel, service and waiting time.

duration_cost(self)

Total cost of the duration of this route.

end_depot(self)

Location index of the route's ending depot.

end_time(self)

End time of the route. This is equivalent to

excess_distance(self)

Distance in excess of the vehicle's maximum distance constraint.

excess_load(self)

Pickup or delivery load in excess of the vehicle's capacity.

has_excess_distance(self)

Returns whether this route violates maximum distance constraints.

has_excess_load(self)

Returns whether this route violates capacity constraints.

has_time_warp(self)

Returns whether this route violates time window or maximum duration constraints.

is_feasible(self)

Returns whether this route is feasible.

pickup(self)

Total client pickup load on this route.

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_depot(self)

Location index of the route's starting depot.

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.

delivery(self) int

Total client delivery load on this route.

distance(self) int

Total distance travelled on this route.

distance_cost(self) int

Total cost of the distance travelled on this route.

duration(self) int

Total route duration, including travel, service and waiting time.

duration_cost(self) int

Total cost of the duration of this route.

end_depot(self) int

Location index of the route’s ending depot.

end_time(self) int
End time of the route. This is equivalent to

start_time + duration - time_warp.

excess_distance(self) int

Distance in excess of the vehicle’s maximum distance constraint.

excess_load(self) int

Pickup or delivery load in excess of the vehicle’s capacity.

has_excess_distance(self) bool

Returns whether this route violates maximum distance constraints.

has_excess_load(self) bool

Returns whether this route violates capacity constraints.

has_time_warp(self) bool

Returns whether this route violates time window or maximum duration constraints.

is_feasible(self) bool

Returns whether this route is feasible.

pickup(self) int

Total client pickup load on this route.

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_depot(self) int

Location index of the route’s starting depot.

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 vehicle’s 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.

distance_cost(self)

Total cost of the distance travelled on routes in this solution.

duration(self)

Total duration of all routes in this solution.

duration_cost(self)

Total cost of the duration of all routes in this solution.

excess_distance(self)

Returns the total distance in excess of maximum duration constraints, 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.

has_excess_distance(self)

Returns whether this solution violates maximum distance constraints.

has_excess_load(self)

Returns whether this solution violates capacity constraints.

has_time_warp(self)

Returns whether this solution violates time window or maximum duration 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.

is_group_feasible(self)

Returns whether this solution is feasible w.r.t.

make_random(data, rng)

Creates a randomly generated solution.

neighbours(self)

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

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.

routes(self)

The solution's routing decisions.

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.

distance_cost(self) int

Total cost of the distance travelled on routes in this solution.

duration(self) int

Total duration of all routes in this solution.

duration_cost(self) int

Total cost of the duration of all routes in this solution.

excess_distance(self) int

Returns the total distance in excess of maximum duration constraints, over all routes.

excess_load(self) int

Returns the total excess load over all routes.

fixed_vehicle_cost(self) int

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

has_excess_distance(self) bool

Returns whether this solution violates maximum distance constraints.

Returns:

True if the solution is not feasible with respect to the maximum distance constraints of the vehicles servicing routes in this solution. False otherwise.

Return type:

bool

has_excess_load(self) bool

Returns whether this solution violates capacity constraints.

has_time_warp(self) bool

Returns whether this solution violates time window or maximum duration constraints.

is_complete(self) bool

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

is_feasible(self) bool

Whether this solution is feasible.

is_group_feasible(self) bool

Returns whether this solution is feasible w.r.t. the client group restrictions.

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

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

num_clients(self) int

Number of clients in this solution.

Warning

An empty solution typically indicates that there is a significant difference between the values of the prizes of the optional clients and the other objective terms. This hints at a scaling issue in the data.

num_missing_clients(self) int

Number of required clients that are not in this solution.

num_routes(self) int

Number of routes in this solution.

prizes(self) int

Returns the total collected prize value over all routes.

routes(self) list[Route]

The solution’s routing decisions.

Returns:

A list of routes. Each Route starts and ends at a depot, but that is implicit: the depot is not part of the returned routes.

Return type:

list

time_warp(self) int

Returns the total time warp load over all routes.

uncollected_prizes(self) int

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

class Client(x: int, y: int, delivery: int = 0, pickup: int = 0, service_duration: int = 0, tw_early: int = 0, tw_late: int = np.iinfo(np.int64).max, release_time: int = 0, prize: int = 0, required: bool = True, group: int | None = None, *, 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.

delivery: int = 0

The amount this client demands from the depot. Default 0.

pickup: int = 0

The amount this client ships back to the depot. Default 0.

service_duration: int = 0

Amount of time a vehicle needs to spend at this client before resuming its route. Service should start (but not necessarily end) within the [tw_early, tw_late] interval. Default 0.

tw_early: int = 0

Earliest time at which this client may be visited to start service. Default 0.

tw_late: int = np.iinfo(np.int64).max

Latest time at which this client may be visited to start service. Unconstrained if not provided.

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. If this client is not required, the prize needs to be sufficiently large to offset any travel cost before this client will be visited in a solution.

required: bool = True

Whether this client must be part of a feasible solution. Default True. Make sure to also update the prize value when setting this argument to False.

group: int | None = None

Indicates membership of the given client group, if any. By default clients are not part of any groups.

name: str = ''

Free-form name field for this client. Default empty.

x

Horizontal coordinate of this client.

y

Vertical coordinate of this client.

delivery

Client delivery amount, shipped from depot.

pickup

Client pickup amount, returned back to depot.

service_duration

Amount of time a vehicle needs to spend at this client before resuming its route.

tw_early

Earliest time at which this client may be visited to start service.

tw_late

Latest time at which this client may be visited to start service.

release_time

Earliest time at which a vehicle may leave the depot to visit this client.

prize

Prize collected by visiting this client.

required

Whether visiting this client is required.

group

Indicates membership of the given client group, if any.

name

Free-form name field for this client.

Attributes

delivery

group

name

pickup

prize

release_time

required

service_duration

tw_early

tw_late

x

y

class ClientGroup(clients: list[int] = [], required: bool = True)

A client group that imposes additional restrictions on visits to clients in the group.

Note

Only mutually exclusive client groups are supported for now.

Parameters:
clients: list[int] = []

The clients in the group.

required: bool = True

Whether visiting this client group is required.

clients

The clients in the group.

required

Whether visiting this client group is required.

mutually_exclusive

When True, exactly one of the clients in this group must be visited if the group is required, and at most one if the group is not required.

Raises:

ValueError – When the given clients contain duplicates, or when a client is added to the group twice.

Attributes

clients

mutually_exclusive

required

Methods

add_client(self, client)

clear(self)

__iter__(self) Iterator
__len__(self) int
add_client(self, client: int) None
clear(self) None
class Depot(x: int, y: int, *, name: str = '')

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

Parameters:
x: int

Horizontal coordinate of this depot, that is, the ‘x’ part of the depot’s (x, y) location tuple.

y: int

Vertical coordinate of this depot, that is, the ‘y’ part of the depot’s (x, y) location tuple.

name: str = ''

Free-form name field for this depot. Default empty.

x

Horizontal coordinate of this depot.

y

Vertical coordinate of this depot.

name

Free-form name field for this depot.

Attributes

name

x

y

class VehicleType(num_available: int = 1, capacity: int = 0, start_depot: int = 0, end_depot: int = 0, fixed_cost: int = 0, tw_early: int = 0, tw_late: int = np.iinfo(np.int64).max, max_duration: int = np.iinfo(np.int64).max, max_distance: int = np.iinfo(np.int64).max, unit_distance_cost: int = 1, unit_duration_cost: int = 0, profile: int = 0, *, name: str = '')

Simple data object storing all vehicle type data as properties.

Parameters:
num_available: int = 1

Number of vehicles of this type that are available. Must be positive. Default 1.

capacity: int = 0

Capacity of this vehicle type. This is the maximum total delivery or pickup amount the vehicle can store along the route. Must be non-negative. Default 0.

start_depot: int = 0

Depot (location index) where vehicles of this type start their routes. Default 0 (first depot).

end_depot: int = 0

Depot (location index) where vehicles of this type end routes. Default 0 (first depot).

fixed_cost: int = 0

Fixed cost of using a vehicle of this type. Default 0.

tw_early: int = 0

Start of the vehicle type’s shift. Default 0.

tw_late: int = np.iinfo(np.int64).max

End of the vehicle type’s shift. Unconstrained if not provided.

max_duration: int = np.iinfo(np.int64).max

Maximum route duration. Unconstrained if not explicitly provided.

max_distance: int = np.iinfo(np.int64).max

Maximum route distance. Unconstrained if not explicitly provided.

unit_distance_cost: int = 1

Cost per unit of distance travelled by vehicles of this type. Default 1.

unit_duration_cost: int = 0

Cost per unit of duration on routes serviced by vehicles of this type. Default 0.

profile: int = 0

This vehicle type’s routing profile. Default 0, the first profile.

name: str = ''

Free-form name field for this vehicle type. Default empty.

num_available

Number of vehicles of this type that are available.

capacity

Capacity (maximum total demand) of this vehicle type.

start_depot

Start location associated with these vehicles.

end_depot

End location associated with these vehicles.

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.

max_distance

Maximum travel distance of the route this vehicle type is assigned to. This is a very large number when the maximum distance is unconstrained.

unit_distance_cost

Cost per unit of distance travelled by vehicles of this type.

unit_duration_cost

Cost per unit of duration on routes using vehicles of this type.

profile

This vehicle type’s routing profile.

name

Free-form name field for this vehicle type.

Attributes

capacity

end_depot

fixed_cost

max_distance

max_duration

name

num_available

profile

start_depot

tw_early

tw_late

unit_distance_cost

unit_duration_cost

class ProblemData(clients: list[Client], depots: list[Depot], vehicle_types: list[VehicleType], distance_matrices: list[ndarray[int]], duration_matrices: list[ndarray[int]], groups: list[ClientGroup] = [])

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

Note

The matrices in the distance_matrices and duration_matrices arguments should have all depots in the lower indices, starting from index 0. See also the location() method for details.

Parameters:
clients: list[Client]

List of clients to visit.

depots: list[Depot]

List of depots. At least one depot must be passed.

vehicle_types: list[VehicleType]

List of vehicle types in the problem instance.

distance_matrices: list[ndarray[int]]

Distance matrices that give the travel distances between all locations (both depots and clients). Each matrix corresponds to a routing profile.

duration_matrices: list[ndarray[int]]

Duration matrices that give the travel durations between all locations (both depots and clients). Each matrix corresponds to a routing profile.

groups: list[ClientGroup] = []

List of client groups. Client groups have certain restrictions - see the definition for details. By default there are no groups, and empty groups must not be passed.

Raises:
  • ValueError – When the data is inconsistent.

  • IndexError – When the data references clients, depots, or groups that do not exist because the referenced index is out of range.

Attributes

num_clients

Number of clients in this problem instance.

num_depots

Number of depots in this problem instance.

num_groups

Number of client groups 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_profiles

Number of routing profiles in this problem 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.

distance_matrices(self)

Returns a list of all distance matrices in the problem instance.

distance_matrix(self, profile)

The full travel distance matrix associated with the given routing profile.

duration_matrices(self)

Returns a list of all duration matrices in the problem instance.

duration_matrix(self, profile)

The full travel duration matrix associated with the given routing profile.

group(self, group)

Returns the client group at the given index.

groups(self)

Returns a list of all client groups in the problem instance.

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).

clients(self) list[Client]

Returns a list of all clients in the problem instance.

depots(self) list[Depot]

Returns a list of all depots in the problem instance.

distance_matrices(self) list[ndarray[int]]

Returns a list of all distance matrices in the problem instance.

Note

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

distance_matrix(self, profile: int) ndarray[int]

The full travel distance matrix associated with the given routing profile.

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!

Parameters:
profile: int

Routing profile whose associated distance matrix to retrieve.

duration_matrices(self) list[ndarray[int]]

Returns a list of all duration matrices in the problem instance.

Note

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

duration_matrix(self, profile: int) ndarray[int]

The full travel duration matrix associated with the given routing profile.

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!

Parameters:
profile: int

Routing profile whose associated duration matrix to retrieve.

group(self, group: int) ClientGroup

Returns the client group at the given index.

Parameters:
group: int

Group index whose information to retrieve.

groups(self) list[ClientGroup]

Returns a list of all client groups in the problem instance.

location(self, idx: int) Client | Depot

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.

property num_clients : int

Number of clients in this problem instance.

property num_depots : int

Number of depots in this problem instance.

property num_groups : int

Number of client groups in this problem instance.

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.

property num_profiles : int

Number of routing profiles in this problem instance.

property num_vehicle_types : int

Number of vehicle types in this problem instance.

property num_vehicles : int

Number of vehicles in this problem instance.

replace(self, clients: list[Client] | None = None, depots: list[Depot] | None = None, vehicle_types: list[VehicleType] | None = None, distance_matrices: list[ndarray[int]] | None = None, duration_matrices: list[ndarray[int]] | None = None, groups: list[ClientGroup] | 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[Depot] | None = None

Optional list of depots.

vehicle_types: list[VehicleType] | None = None

Optional list of vehicle types.

distance_matrices: list[ndarray[int]] | None = None

Optional distance matrices, one per routing profile.

duration_matrices: list[ndarray[int]] | None = None

Optional duration matrices, one per routing profile.

groups: list[ClientGroup] | None = None

Optional client groups.

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.

vehicle_types(self) list[VehicleType]

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

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

all(self)

any(self)

count(self)

none(self)

reset(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
all(self) bool
any(self) bool
count(self) int
none(self) bool
reset(self) DynamicBitset
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) Annotated[list[int], FixedSize(4)]
exception ScalingWarning[source]

Raised when the distance or duration values in the problem are very large, which could cause the algorithm to suffer from numerical issues.

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).

exception PenaltyBoundWarning[source]

Raised when a penalty parameter has reached its maximum value. This means PyVRP struggles to find a feasible solution for the instance that’s being solved, either because the instance has no feasible solution, or it is just very hard to find one.