PyVRP¶
The toplevel 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
Returns all client groups currently in the model.
Returns all locations (depots and clients) in the current model.
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[, 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\)) andto
(\(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, 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 vehicle_types : list[VehicleType]¶
Returns the vehicle types in the current model. The routes of the solution returned by
solve()
have a propertyvehicle_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:

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 notNone
, and the givengroup
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, tw_early: int =
0
, tw_late: int =np.iinfo(np.int64).max
, *, 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
) Edge [source]¶ Adds an edge \((i, j)\) between
frm
(\(i\)) andto
(\(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: 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
, *, 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
depot
is not provided. Raises:
ValueError – When the given
depot
is 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 whencollect_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:
 class Edge(frm: Client  Depot, to: Client  Depot, 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:
 Raises:
ValueError – When
repair_probability
is not in \([0, 1]\), ornb_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 whencollect_stats
is also set.
 Returns:
A Result object, containing statistics (if collected) and the best found solution.
 Return type:

class PenaltyParams(init_load_penalty: int =
20
, init_time_warp_penalty: int =6
, init_dist_penalty: int =6
, 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:
 init_load_penalty : ¶
Initial penalty on excess load. This is the amount by which one unit of excess load 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.
 init_dist_penalty : ¶
Initial penalty on excess distance. This is the amount by which one unit of excess distance 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
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.
 solutions_between_updates¶
Number of feasibility registrations between penalty value updates.
 Type:
 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:
 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:

class PenaltyManager(params: PenaltyParams =
PenaltyParams()
)[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()
¶ PenaltyManager parameters. If not provided, a default will be used.
 params: PenaltyParams =
Methods
Get a cost evaluator using the boosted current penalty values.
Get a cost evaluator using the current penalty values.
register
(sol)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
)¶ 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.
Returns the number of feasible solutions in the population.
Returns the number of infeasible solutions in the population.
select
(rng, cost_evaluator[, k])Selects two (if possible nonidentical) parents by tournament, subject to a diversity restriction.
tournament
(rng, cost_evaluator[, k])Selects a solution from this population by kary 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.
 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.

select(rng: RandomNumberGenerator, cost_evaluator: CostEvaluator, k: int =
2
) tuple[Solution, Solution] [source]¶ Selects two (if possible nonidentical) 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:

tournament(rng: RandomNumberGenerator, cost_evaluator: CostEvaluator, k: int =
2
) Solution [source]¶ Selects a solution from this population by kary 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:

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:
 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.
 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:
 Raises:
ValueError – When the number of iterations or runtime are negative.
Methods
cost
()Returns the cost (objective) value of the best solution.
Returns whether the best solution is feasible.
 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.
 genetic: GeneticAlgorithmParams =
Attributes
genetic
neighbourhood
node_ops
penalty
population
route_ops
Methods
from_file
(loc)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 whencollect_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:

class Statistics(collect_stats: bool =
True
)[source]¶ The Statistics object tracks various (populationlevel) statistics of genetic algorithm runs. This can be helpful in analysing the algorithm’s performance.
 Parameters:
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:
 Returns:
Statistics object populated with the data read from the given filesystem location.
 Return type:
 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:
Methods
cost
(self, solution)Handwaving some details, each solution consists of a set of nonempty 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 ¶
Handwaving some details, each solution consists of a set of nonempty 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.
 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.
depot
(self)Location index of the route's depot.
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_time
(self)End time of the route.
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)has_excess_load
(self)has_time_warp
(self)is_feasible
(self)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_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.
 end_time(self) int ¶
End time of the route. This is equivalent to
start_time + duration  time_warp
.
 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.
 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 mostslack()
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.
 class Solution(data: ProblemData, routes: list[Route]  list[list[int]])¶
Encodes VRP solutions.
 Parameters:
 Raises:
RuntimeError – When the given solution is invalid in one of several ways. In particular when the number of routes in the
routes
argument exceedsnum_vehicles
, when an empty route has been passed as part ofroutes
, 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 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.
 excess_distance(self) int ¶
Returns the total distance in excess of maximum duration constraints, 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:
 is_complete(self) bool ¶
Returns whether this solution is complete, which it is when it has all required clients.
 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:
 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:

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 (readonly) 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.
 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 =
''
¶ Freeform 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¶
Freeform 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¶
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 ¶

class Depot(x: int, y: int, tw_early: int =
0
, tw_late: int =np.iinfo(np.int64).max
, *, name: str =''
)¶ Simple data object storing all depot data as (readonly) 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.
 tw_early: int =
0
¶ Opening time of this depot. Default 0.
 tw_late: int =
np.iinfo(np.int64).max
¶ Closing time of this depot. Default unconstrained.
 name: str =
''
¶ Freeform name field for this depot. Default empty.
 x¶
Horizontal coordinate of this depot.
 y¶
Vertical coordinate of this depot.
 tw_early¶
Opening time of this depot.
 tw_late¶
Closing time of this depot.
 name¶
Freeform name field for this depot.
Attributes
name
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 =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
, *, 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 nonnegative. 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 =
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.
 name: str =
''
¶ Freeform name field for this vehicle type. Default empty.
 num_available: int =
 num_available¶
Number of vehicles of this type that are available.
 capacity¶
Capacity (maximum total demand) of this vehicle type.
 depot¶
Depot 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.
 name¶
Freeform name field for this vehicle type.
Attributes
capacity
depot
fixed_cost
max_distance
max_duration
name
num_available
tw_early
tw_late
unit_distance_cost
unit_duration_cost

class ProblemData(clients: list[Client], depots: list[Depot], vehicle_types: list[VehicleType], distance_matrix: ndarray[int], duration_matrix: ndarray[int], groups: list[ClientGroup] =
[]
)¶ Creates a problem data instance. This instance contains all information needed to solve the vehicle routing problem.
Note
The
distance_matrix
andduration_matrix
arguments should have all depots in the lower indices, starting from index0
. See also thelocation()
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_matrix: ndarray[int]¶
A matrix that gives the travel distances between all locations: both depots and clients.
 duration_matrix: ndarray[int]¶
A matrix that gives the travel durations between all locations: both depots and clients.
 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
Number of clients in this problem instance.
Number of depots in this problem instance.
Number of client groups in this problem instance.
Number of locations in this problem instance, that is, the number of depots plus the number of clients in the instance.
Number of vehicle types in this problem instance.
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_matrix
(self)The full travel distance matrix.
duration_matrix
(self)The full travel duration matrix.
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.
 distance_matrix(self) ndarray[int] ¶
The full travel distance matrix.
Note
This method returns a readonly view of the underlying data. No matrix is copied, but the resulting data cannot be modified in any way!
 duration_matrix(self) ndarray[int] ¶
The full travel duration matrix.
Note
This method returns a readonly view of the underlying data. No matrix is copied, but the resulting data cannot be modified in any way!
 group(self, group: int) ClientGroup ¶
Returns the client group at the given index.
 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 thannum_depots
, and a client if theidx
is bigger than that.
 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.

replace(self, clients: list[Client]  None =
None
, depots: list[Depot]  None =None
, vehicle_types: list[VehicleType]  None =None
, distance_matrix: ndarray[int]  None =None
, duration_matrix: 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_matrix: ndarray[int]  None =
None
¶ Optional distance matrix.
 duration_matrix: ndarray[int]  None =
None
¶ Optional duration matrix.
 groups: list[ClientGroup]  None =
None
¶ Optional client groups.
 clients: list[Client]  None =
 Returns:
A new ProblemData instance with possibly replaced data.
 Return type:
 vehicle_type(self, vehicle_type: int) VehicleType ¶
Returns vehicle type data for the given vehicle type.
 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:
Methods
all
(self)any
(self)count
(self)none
(self)reset
(self) __and__(self, other: DynamicBitset) DynamicBitset ¶
 __eq__(self, other: DynamicBitset) bool ¶
 __invert__(self) DynamicBitset ¶
 __or__(self, other: DynamicBitset) DynamicBitset ¶
 __xor__(self, other: DynamicBitset) DynamicBitset ¶
 reset(self) DynamicBitset ¶
 class RandomNumberGenerator(seed: int)¶
This class implements a XORshift pseudorandom number generator (RNG). It generates the next number of a sequence by repeatedly taking the ‘exclusive or’ (the
^
operator) of a number with a bitshifted version of itself. See here for more details.Methods
__call__
(self)max
()min
()rand
(self)randint
(self, high)state
(self) state(self) Annotated[list[int], FixedSize(4)] ¶
 exception EmptySolutionWarning[source]¶
Raised when an empty solution is being added to the Population. This is not forbidden, per se, but very odd.