discrete_optimization.vrp package

Subpackages

• discrete_optimization.vrp.solvers package
  • Submodules
  • discrete_optimization.vrp.solvers.cpsat module
    • CpSatVrpSolver
      • CpSatVrpSolver.hyperparameters
      • CpSatVrpSolver.init_model()
      • CpSatVrpSolver.problem
      • CpSatVrpSolver.retrieve_solution()
      • CpSatVrpSolver.set_warm_start()
  • discrete_optimization.vrp.solvers.dp module
    • DpVrpSolver
      • DpVrpSolver.hyperparameters
      • DpVrpSolver.init_model()
      • DpVrpSolver.init_model_()
      • DpVrpSolver.retrieve_solution()
      • DpVrpSolver.set_warm_start()
      • DpVrpSolver.transitions
  • discrete_optimization.vrp.solvers.greedy module
    • GreedyVrpSolver
      • GreedyVrpSolver.solve()
  • discrete_optimization.vrp.solvers.lns_cpsat module
    • SubpathVrpConstraintHandler
      • SubpathVrpConstraintHandler.adding_constraint_from_results_store()
    • VrpConstraintHandler
      • VrpConstraintHandler.adding_constraint_from_results_store()
  • discrete_optimization.vrp.solvers.lp_iterative module
    • LPIterativeVrpSolver
      • LPIterativeVrpSolver.constraint_on_edge
      • LPIterativeVrpSolver.edges
      • LPIterativeVrpSolver.edges_in_customers
      • LPIterativeVrpSolver.edges_in_merged_graph
      • LPIterativeVrpSolver.edges_out_customers
      • LPIterativeVrpSolver.edges_out_merged_graph
      • LPIterativeVrpSolver.edges_warm_set
      • LPIterativeVrpSolver.init_model()
      • LPIterativeVrpSolver.model
      • LPIterativeVrpSolver.problem
      • LPIterativeVrpSolver.solve()
      • LPIterativeVrpSolver.x_var
    • build_graph_pruned_vrp()
    • build_matrice_distance_np()
    • build_the_cycles()
    • build_warm_edges_and_update_graph()
    • compute_start_end_flows_info()
    • init_model_lp()
    • plot_solve()
    • rebuild_tsp_routine()
    • reevaluate_solutions()
    • retrieve_solutions()
    • update_graph()
    • update_model_2()
  • discrete_optimization.vrp.solvers.ortools_routing module
    • BasicRoutingMonitor
    • FirstSolutionStrategy
      • FirstSolutionStrategy.PATH_MOST_CONSTRAINED_ARC
      • FirstSolutionStrategy.SAVINGS
    • LocalSearchMetaheuristic
      • LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
      • LocalSearchMetaheuristic.SIMULATED_ANNEALING
    • OrtoolsVrpSolver
      • OrtoolsVrpSolver.init_model()
      • OrtoolsVrpSolver.manager
      • OrtoolsVrpSolver.retrieve()
      • OrtoolsVrpSolver.solve()
    • status_description
  • discrete_optimization.vrp.solvers.vrp_solver module
    • VrpSolver
      • VrpSolver.problem
  • Module contents

Submodules

discrete_optimization.vrp.mutation module

class discrete_optimization.vrp.mutation.RelocateMove(index_vehicle_from: int, index_vehicle_to: int, index_from: int, index_to: int)

Bases: LocalMove

apply_local_move(solution: VrpSolution) → VrpSolution

backtrack_local_move(solution: VrpSolution) → VrpSolution

class discrete_optimization.vrp.mutation.RelocateVrpMutation(problem: VrpProblem, attribute: str | None = None, **kwargs: Any)

Bases: SingleAttributeMutation

attribute_type: VrpPaths

attribute_type_cls

alias of VrpPaths

mutate(solution: VrpSolution) → tuple[VrpSolution, LocalMove]

problem: VrpProblem

class discrete_optimization.vrp.mutation.SwapMove(index_vehicle_from: int, index_vehicle_to: int, index_from: int, index_to: int)

Bases: LocalMove

apply_local_move(solution: VrpSolution) → VrpSolution

backtrack_local_move(solution: VrpSolution) → VrpSolution

class discrete_optimization.vrp.mutation.SwapVrpMutation(problem: VrpProblem, attribute: str | None = None, **kwargs: Any)

Bases: SingleAttributeMutation

attribute_type: VrpPaths

attribute_type_cls

alias of VrpPaths

mutate(solution: VrpSolution) → tuple[VrpSolution, LocalMove]

problem: VrpProblem

class discrete_optimization.vrp.mutation.TwoOptVrpMutation(problem: VrpProblem, attribute: str | None = None, test_all: bool = False, nb_test: int | None = None, return_only_improvement: bool = False, **kwargs: Any)

Bases: Mutation

attribute_type: VrpPaths

attribute_type_cls

alias of VrpPaths

get_points(vehicle: int, it: int, jt: int, variable: VrpSolution) → tuple[BasicCustomer, BasicCustomer, BasicCustomer, BasicCustomer]

get_points_index(vehicle: int, it: int, jt: int, variable: VrpSolution) → tuple[int, int, int, int]

mutate(solution: VrpSolution) → tuple[VrpSolution, LocalMove]

mutate_and_compute_obj(solution: VrpSolution) → tuple[VrpSolution, LocalMove, dict[str, float]]

node_count: int

problem: VrpProblem

discrete_optimization.vrp.parser module

discrete_optimization.vrp.parser.get_data_available(data_folder: str | None = None, data_home: str | None = None) → list[str]

Get datasets available for vrp.

Params:

data_folder: folder where datasets for vrp whould be find.

If None, we look in “vrp” subdirectory of data_home.

data_home: root directory for all datasets. Is None, set by

default to “~/discrete_optimization_data “

discrete_optimization.vrp.parser.parse_file(file_path: str, start_index: int = 0, end_index: int = 0, vehicle_count: int | None = None) → Customer2DVrpProblem

discrete_optimization.vrp.parser.parse_input(input_data: str, start_index: int = 0, end_index: int = 0, vehicle_count: int | None = None) → Customer2DVrpProblem

discrete_optimization.vrp.plot module

discrete_optimization.vrp.plot.plot_vrp_solution(vrp_problem: Customer2DVrpProblem, solution: VrpSolution, ax: Any = None) → None

discrete_optimization.vrp.problem module

class discrete_optimization.vrp.problem.BasicCustomer(name: str | int, demand: float)

Bases: object

class discrete_optimization.vrp.problem.Customer2D(name: str | int, demand: float, x: float, y: float)

Bases: BasicCustomer

class discrete_optimization.vrp.problem.Customer2DVrpProblem(vehicle_count: int, vehicle_capacities: list[float], customer_count: int, customers: Sequence[Customer2D], start_indexes: list[int], end_indexes: list[int])

Bases: VrpProblem

customers: Sequence[Customer2D]

evaluate_function(vrp_sol: VrpSolution) → tuple[list[list[float]], list[float], float, list[float]]

evaluate_function_indexes(index_1: int, index_2: int) → float

class discrete_optimization.vrp.problem.VrpPaths

Bases: AttributeType

Specific attribute type for vrp.

class discrete_optimization.vrp.problem.VrpProblem(vehicle_count: int, vehicle_capacities: list[float], customer_count: int, customers: Sequence[BasicCustomer], start_indexes: list[int], end_indexes: list[int])

Bases: Problem

customers: Sequence[BasicCustomer]

evaluate(variable: VrpSolution) → dict[str, float]

Evaluate a given solution object for the given problem.

This method should return a dictionnary of KPI, that can be then used for mono or multiobjective optimization.

Parameters:

variable (Solution) – the Solution object to evaluate.

Returns: dictionnary of float kpi for the solution.

abstractmethod evaluate_function(var_tsp: VrpSolution) → tuple[list[list[float]], list[float], float, list[float]]

abstractmethod evaluate_function_indexes(index_1: int, index_2: int) → float

get_attribute_register() → EncodingRegister

Returns how the Solution should be encoded.

Useful to find automatically available mutations for local search. Used by genetic algorithms Ga and Nsga.

This needs only to be implemented in child classes when GA or LS solvers are to be used.

Returns (EncodingRegister): content of the encoding of the solution

get_dummy_solution() → VrpSolution

Create a trivial solution for the problem.

Should satisfy the problem ideally. Does not exist for all kind of problems.

get_objective_register() → ObjectiveRegister

Returns the objective definition.

Returns (ObjectiveRegister): object defining the objective criteria.

get_solution_type() → type[Solution]

Returns the class implementation of a Solution.

Returns (class): class object of the given Problem.

get_stupid_solution() → VrpSolution

satisfy(variable: VrpSolution) → bool

Computes if a solution satisfies or not the constraints of the problem.

Parameters:

variable – the Solution object to check satisfability

Returns (bool): boolean true if the constraints are fulfilled, false elsewhere.

class discrete_optimization.vrp.problem.VrpSolution(problem: VrpProblem, list_start_index: list[int], list_end_index: list[int], list_paths: list[list[int]], capacities: list[float] | None = None, length: float | None = None, lengths: list[list[float]] | None = None)

Bases: Solution

change_problem(new_problem: Problem) → None

If relevant to the optimisation problem, change the underlying problem instance for the solution.

This method can be used to evaluate a solution for different instance of problems. It should be implemented in child classes when caching subresults depending on the problem.

Parameters:

new_problem (Problem) – another problem instance from which the solution can be evaluated

Returns: None

copy() → VrpSolution

Deep copy of the solution.

The copy() function should return a new object containing the same input as the current object, that respects the following expected behaviour: -y = x.copy() -if do some inplace change of y, the changes are not done in x.

Returns: a new object from which you can manipulate attributes without changing the original object.

lazy_copy() → VrpSolution

This function should return a new object but possibly with mutable attributes from the original objects.

A typical use of lazy copy is in evolutionary algorithms or genetic algorithm where the use of local move don’t need to do a possibly costly deepcopy.

Returns (Solution): copy (possibly shallow) of the Solution

problem: VrpProblem

discrete_optimization.vrp.problem.build_evaluate_function(vrp_problem: VrpProblem) → Callable[[VrpSolution], tuple[list[list[float]], list[float], float, list[float]]]

discrete_optimization.vrp.problem.compute_length(start_index: int, end_index: int, solution: list[int], list_customers: Sequence[BasicCustomer], method: Callable[[int, int], float]) → tuple[list[float], float, float]

discrete_optimization.vrp.problem.compute_length_np(start_index: int, end_index: int, solution: list[int] | ndarray, np_points: ndarray) → tuple[list[float] | ndarray, float]

discrete_optimization.vrp.problem.length(point1: Customer2D, point2: Customer2D) → float

discrete_optimization.vrp.problem.sequential_computing(vrp_sol: VrpSolution, vrp_problem: VrpProblem) → tuple[list[list[float]], list[float], float, list[float]]

discrete_optimization.vrp.problem.stupid_solution(vrp_problem: VrpProblem) → tuple[VrpSolution, dict[str, float]]

discrete_optimization.vrp.problem.trivial_solution(vrp_problem: VrpProblem) → tuple[VrpSolution, dict[str, float]]

discrete_optimization.vrp.solvers_map module

discrete_optimization.vrp.solvers_map.look_for_solver(domain: VrpProblem) → list[type[VrpSolver]]

discrete_optimization.vrp.solvers_map.look_for_solver_class(class_domain: type[VrpProblem]) → list[type[VrpSolver]]

discrete_optimization.vrp.solvers_map.return_solver(method: type[VrpSolver], problem: VrpProblem, **kwargs: Any) → VrpSolver

discrete_optimization.vrp.solvers_map.solve(method: type[VrpSolver], problem: VrpProblem, **kwargs: Any) → ResultStorage

discrete_optimization.vrp.utils module

discrete_optimization.vrp.utils.build_graph(vrp_problem: VrpProblem) → tuple[Graph, ndarray]

discrete_optimization.vrp.utils.compute_length_matrix(vrp_problem: VrpProblem) → tuple[ndarray, ndarray]

discrete_optimization.vrp.utils.prune_search_space(vrp_problem: VrpProblem, n_shortest: int = 10) → tuple[ndarray, ndarray]

Module contents