discrete_optimization.vrp.solvers package

Submodules

discrete_optimization.vrp.solvers.cpsat module

class discrete_optimization.vrp.solvers.cpsat.CpSatVrpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OrtoolsCpSatSolver, VrpSolver, WarmstartMixin

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='cut_transition', default=False, depends_on=None, name_in_kwargs='cut_transition'), IntegerHyperparameter(name='nb_cut', default=None, depends_on=None, name_in_kwargs='nb_cut', low=1, high=100, step=1, log=False), CategoricalHyperparameter(name='optional_node', default=False, depends_on=None, name_in_kwargs='optional_node')]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

init_model(**args: Any) → None

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

problem: VrpProblem

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → Solution

Construct a do solution from the cpsat solver internal solution.

It will be called each time the cpsat solver find a new solution. At that point, value of internal variables are accessible via cpsolvercb.Value(VARIABLE_NAME).

Parameters:

cpsolvercb – the ortools callback called when the cpsat solver finds a new solution.

Returns:

the intermediate solution, at do format.

set_warm_start(solution: VrpSolution, debug_mode: bool = False) → None

Make the solver warm start from the given solution.

discrete_optimization.vrp.solvers.dp module

class discrete_optimization.vrp.solvers.dp.DpVrpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: VrpSolver, DpSolver

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='solver', default=<class 'builtins.CABS'>, depends_on=None, name_in_kwargs='solver')]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

init_model(**kwargs)

DP model for CVRP Directly adapted from https://github.com/domain-independent-dp/didp-rs/blob/main/didppy/examples/cvrp.ipynb

init_model_(**kwargs)

DP model for CVRP Directly adapted from https://github.com/domain-independent-dp/didp-rs/blob/main/didppy/examples/cvrp.ipynb

retrieve_solution(sol: Solution) → Solution

set_warm_start(solution: VrpSolution) → None

transitions: dict

discrete_optimization.vrp.solvers.greedy module

class discrete_optimization.vrp.solvers.greedy.GreedyVrpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: VrpSolver

solve(**kwargs: Any) → ResultStorage

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

discrete_optimization.vrp.solvers.lns_cpsat module

class discrete_optimization.vrp.solvers.lns_cpsat.SubpathVrpConstraintHandler(problem: VrpProblem, fraction_segment_to_fix: float = 0.9)

Bases: OrtoolsCpSatConstraintHandler

adding_constraint_from_results_store(solver: CpSatVrpSolver, result_storage: ResultStorage, **kwargs: Any) → Iterable[Constraint]

class discrete_optimization.vrp.solvers.lns_cpsat.VrpConstraintHandler(problem: VrpProblem, fraction_segment_to_fix: float = 0.9)

Bases: OrtoolsCpSatConstraintHandler

adding_constraint_from_results_store(solver: CpSatVrpSolver, result_storage: ResultStorage, **kwargs: Any) → Iterable[Constraint]

discrete_optimization.vrp.solvers.lp_iterative module

class discrete_optimization.vrp.solvers.lp_iterative.LPIterativeVrpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: VrpSolver

constraint_on_edge: dict[int, Any] | None = None

edges: set[Edge]

edges_in_customers: dict[int, set[Edge]]

edges_in_merged_graph: dict[Node, set[Edge]]

edges_out_customers: dict[int, set[Edge]]

edges_out_merged_graph: dict[Node, set[Edge]]

edges_warm_set: set[Edge]

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

model: Model | None = None

problem: Customer2DVrpProblem

solve(**kwargs: Any) → ResultStorage

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

x_var: dict[Edge, Var] | None = None

discrete_optimization.vrp.solvers.lp_iterative.build_graph_pruned_vrp(vrp_problem: Customer2DVrpProblem) → tuple[DiGraph, DiGraph, dict[int, set[tuple[tuple[int, int], tuple[int, int]]]], dict[int, set[tuple[tuple[int, int], tuple[int, int]]]], dict[tuple[int, int], set[tuple[tuple[int, int], tuple[int, int]]]], dict[tuple[int, int], set[tuple[tuple[int, int], tuple[int, int]]]]]

discrete_optimization.vrp.solvers.lp_iterative.build_matrice_distance_np(customer_count: int, customers: Sequence[Customer2D]) → tuple[ndarray, ndarray]

discrete_optimization.vrp.solvers.lp_iterative.build_the_cycles(x_solution: set[tuple[tuple[int, int], tuple[int, int]]], component: set[tuple[int, int]], start_index: tuple[int, int], end_index: tuple[int, int]) → tuple[list[tuple[int, int]], dict[tuple[int, int], int]]

discrete_optimization.vrp.solvers.lp_iterative.build_warm_edges_and_update_graph(vrp_problem: VrpProblem, vrp_solution: VrpSolution, graph: DiGraph, edges: set[tuple[tuple[int, int], tuple[int, int]]], edges_in_merged_graph: dict[tuple[int, int], set[tuple[tuple[int, int], tuple[int, int]]]], edges_out_merged_graph: dict[tuple[int, int], set[tuple[tuple[int, int], tuple[int, int]]]], edges_in_customers: dict[int, set[tuple[tuple[int, int], tuple[int, int]]]], edges_out_customers: dict[int, set[tuple[tuple[int, int], tuple[int, int]]]]) → tuple[list[list[tuple[tuple[int, int], tuple[int, int]]]], set[tuple[tuple[int, int], tuple[int, int]]]]

discrete_optimization.vrp.solvers.lp_iterative.compute_start_end_flows_info(start_indexes: list[int], end_indexes: list[int]) → tuple[dict[int, dict[str, Any]], dict[int, dict[str, Any]]]

discrete_optimization.vrp.solvers.lp_iterative.init_model_lp(g: DiGraph, edges: set[tuple[tuple[int, int], tuple[int, int]]], edges_in_customers: dict[int, set[tuple[tuple[int, int], tuple[int, int]]]], edges_out_customers: dict[int, set[tuple[tuple[int, int], tuple[int, int]]]], edges_in_merged_graph: dict[tuple[int, int], set[tuple[tuple[int, int], tuple[int, int]]]], edges_out_merged_graph: dict[tuple[int, int], set[tuple[tuple[int, int], tuple[int, int]]]], edges_warm_set: set[tuple[tuple[int, int], tuple[int, int]]], fraction: float, start_indexes: list[int], end_indexes: list[int], vehicle_count: int, vehicle_capacity: list[float], do_lns: bool = False, include_backward: bool = True, include_triangle: bool = False) → tuple[Model, dict[tuple[tuple[int, int], tuple[int, int]], Var], dict[str | int, Any], dict[str, Any], dict[int, Any]]

discrete_optimization.vrp.solvers.lp_iterative.plot_solve(solutions: list[dict[int, set[tuple[tuple[int, int], tuple[int, int]]]]], customers: Sequence[Customer2D], rebuilt_solution: list[dict[int, list[tuple[int, int]]]], cost: list[float], rebuilt_obj: list[float]) → None

discrete_optimization.vrp.solvers.lp_iterative.rebuild_tsp_routine(sorted_connected_component: list[tuple[set[tuple[int, int]], int]], paths_component: dict[int, list[tuple[int, int]]], node_to_component: dict[tuple[int, int], int], indexes: dict[int, dict[tuple[int, int], int]], graph: DiGraph, edges: set[tuple[tuple[int, int], tuple[int, int]]], evaluate_function_indexes: Callable[[int, int], float], vrp_problem: VrpProblem, start_index: tuple[int, int], end_index: tuple[int, int]) → tuple[list[tuple[int, int]], float]

discrete_optimization.vrp.solvers.lp_iterative.reevaluate_solutions(solutions: list[tuple[DiGraph, dict[int, DiGraph], dict[int, set[tuple[tuple[int, int], tuple[int, int]]]]]], vehicle_count: int, g: DiGraph, vrp_problem: VrpProblem) → tuple[dict[int, set[tuple[tuple[int, int], tuple[int, int]]]], dict[int, list[tuple[int, int]]], float, dict[int, list[tuple[set[tuple[int, int]], int]]], list[tuple[set[tuple[int, int]], int]], list[dict[int, list[tuple[set[tuple[int, int]], int]]]], list[list[tuple[set[tuple[int, int]], int]]]]

discrete_optimization.vrp.solvers.lp_iterative.retrieve_solutions(model: Model, x_var: dict[Edge, 'Var'], vehicle_count: int, g: nx.DiGraph) → list[tuple[nx.DiGraph, dict[int, nx.DiGraph], dict[int, set[Edge]]]]

discrete_optimization.vrp.solvers.lp_iterative.update_graph(g: DiGraph, edges: set[tuple[tuple[int, int], tuple[int, int]]], edges_in_customers: dict[int, set[tuple[tuple[int, int], tuple[int, int]]]], edges_out_customers: dict[int, set[tuple[tuple[int, int], tuple[int, int]]]], edges_in_merged_graph: dict[tuple[int, int], set[tuple[tuple[int, int], tuple[int, int]]]], edges_out_merged_graph: dict[tuple[int, int], set[tuple[tuple[int, int], tuple[int, int]]]], edges_missing: set[tuple[tuple[int, int], tuple[int, int]]], customers: Sequence[Customer2D]) → tuple[DiGraph, set[tuple[tuple[int, int], tuple[int, int]]], dict[int, set[tuple[tuple[int, int], tuple[int, int]]]], dict[int, set[tuple[tuple[int, int], tuple[int, int]]]], dict[tuple[int, int], set[tuple[tuple[int, int], tuple[int, int]]]], dict[tuple[int, int], set[tuple[tuple[int, int], tuple[int, int]]]]]

discrete_optimization.vrp.solvers.lp_iterative.update_model_2(model: Model, x_var: dict[Edge, 'Var'], components_global: dict[int, list[tuple[set[Node], int]]], edges_in_customers: dict[int, set[Edge]], edges_out_customers: dict[int, set[Edge]]) → None

discrete_optimization.vrp.solvers.ortools_routing module

class discrete_optimization.vrp.solvers.ortools_routing.BasicRoutingMonitor(do_solver: OrtoolsVrpSolver)

Bases: object

class discrete_optimization.vrp.solvers.ortools_routing.FirstSolutionStrategy(value)

Bases: Enum

An enumeration.

PATH_MOST_CONSTRAINED_ARC = 1

SAVINGS = 0

class discrete_optimization.vrp.solvers.ortools_routing.LocalSearchMetaheuristic(value)

Bases: Enum

An enumeration.

GUIDED_LOCAL_SEARCH = 0

SIMULATED_ANNEALING = 1

class discrete_optimization.vrp.solvers.ortools_routing.OrtoolsVrpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: VrpSolver

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

manager: RoutingIndexManager | None = None

retrieve(solution: Assignment) → VrpSolution

solve(time_limit: int | None = 100, **kwargs: Any) → ResultStorage

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

discrete_optimization.vrp.solvers.ortools_routing.status_description = {0: 'ROUTING_NOT_SOLVED', 1: 'ROUTING_SUCCESS', 2: 'ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED', 3: 'ROUTING_FAIL', 4: 'ROUTING_FAIL_TIMEOUT', 5: 'ROUTING_INVALID', 6: 'ROUTING_INFEASIBLE', 7: 'ROUTING_OPTIMAL'}

Mapping from status integer to description string.

This maps the integer returned by routing_model.status to the corresponding string.

We use the attributes of RoutingModel to construct the dictionary. https://developers.google.com/optimization/routing/routing_options#search_status

discrete_optimization.vrp.solvers.vrp_solver module

class discrete_optimization.vrp.solvers.vrp_solver.VrpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

problem: VrpProblem

Module contents