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.MutationRelocate(vrp_problem: VrpProblem)

Bases: Mutation

static build(problem: VrpProblem, solution: VrpSolution, **kwargs) → MutationRelocate

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

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

class discrete_optimization.vrp.mutation.MutationSwap(vrp_problem: VrpProblem)

Bases: Mutation

static build(problem: VrpProblem, solution: VrpSolution, **kwargs) → MutationSwap

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

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

class discrete_optimization.vrp.mutation.MutationTwoOptVrp(vrp_problem: VrpProblem, test_all: bool = False, nb_test: int | None = None, return_only_improvement: bool = False, **kwargs: Any)

Bases: Mutation

static build(problem: VrpProblem, solution: VrpSolution, **kwargs) → MutationTwoOptVrp

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(variable: VrpSolution) → tuple[VrpSolution, LocalMove]

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

node_count: int

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

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

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

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

get_attribute_register() → EncodingRegister

Returns how the Solution should be encoded.

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

get_dummy_solution() → VrpSolution

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.

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

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