discrete_optimization.vrp.solver package

Submodules

discrete_optimization.vrp.solver.greedy_vrp module

class discrete_optimization.vrp.solver.greedy_vrp.GreedyVRPSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverVrp

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.solver.lp_vrp_iterative module

class discrete_optimization.vrp.solver.lp_vrp_iterative.VRPIterativeLP(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverVrp

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 intern model used to solve.

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

model: Model | None = None

problem: VrpProblem2D

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.solver.lp_vrp_iterative.build_graph_pruned_vrp(vrp_problem: VrpProblem2D) → 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.solver.lp_vrp_iterative.build_matrice_distance_np(customer_count: int, customers: Sequence[Customer2D]) → Tuple[ndarray, ndarray]

discrete_optimization.vrp.solver.lp_vrp_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.solver.lp_vrp_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.solver.lp_vrp_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.solver.lp_vrp_iterative.init_model_lp(g: nx.DiGraph, edges: Set[Edge], edges_in_customers: Dict[int, Set[Edge]], edges_out_customers: Dict[int, Set[Edge]], edges_in_merged_graph: Dict[Node, Set[Edge]], edges_out_merged_graph: Dict[Node, Set[Edge]], edges_warm_set: Set[Edge], 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[Edge, 'Var'], Dict[str | int, Any], Dict[str, Any], Dict[int, Any]]

discrete_optimization.vrp.solver.lp_vrp_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.solver.lp_vrp_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_model: VrpProblem, start_index: Tuple[int, int], end_index: Tuple[int, int]) → Tuple[List[Tuple[int, int]], float]

discrete_optimization.vrp.solver.lp_vrp_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.solver.lp_vrp_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.solver.lp_vrp_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.solver.lp_vrp_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.solver.lp_vrp_iterative_pymip module

class discrete_optimization.vrp.solver.lp_vrp_iterative_pymip.VRPIterativeLP_Pymip(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverVrp

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 intern model used to solve.

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

model: MyModelMilp | None = None

problem: VrpProblem2D

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.solver.lp_vrp_iterative_pymip.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, solver_name: str = 'CBC') → Tuple[MyModelMilp, Dict[Tuple[Tuple[int, int], Tuple[int, int]], Var], Dict[str | int, Any], Dict[str, Any], Dict[int, Any]]

discrete_optimization.vrp.solver.lp_vrp_iterative_pymip.retrieve_solutions(model: Model, x_var: Dict[Tuple[Tuple[int, int], Tuple[int, int]], Var], vehicle_count: int, g: DiGraph) → List[Tuple[DiGraph, Dict[int, DiGraph], Dict[int, Set[Tuple[Tuple[int, int], Tuple[int, int]]]]]]

discrete_optimization.vrp.solver.lp_vrp_iterative_pymip.update_model_2(model: MyModelMilp, x_var: Dict[Tuple[Tuple[int, int], Tuple[int, int]], Var], components_global: List[Tuple[Set[Tuple[int, 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]]]]) → None

discrete_optimization.vrp.solver.solver_ortools module

class discrete_optimization.vrp.solver.solver_ortools.BasicRoutingMonitor(do_solver: VrpORToolsSolver)

Bases: object

class discrete_optimization.vrp.solver.solver_ortools.FirstSolutionStrategy(value)

Bases: Enum

An enumeration.

PATH_MOST_CONSTRAINED_ARC = 1

SAVINGS = 0

class discrete_optimization.vrp.solver.solver_ortools.LocalSearchMetaheuristic(value)

Bases: Enum

An enumeration.

GUIDED_LOCAL_SEARCH = 0

SIMULATED_ANNEALING = 1

class discrete_optimization.vrp.solver.solver_ortools.VrpORToolsSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverVrp

init_model(**kwargs: Any) → None

Initialize intern model used to solve.

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

manager: RoutingIndexManager | None = None

retrieve(solution: Assignment) → VrpSolution

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.solver.solver_ortools.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.solver.vrp_solver module

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

Bases: SolverDO

problem: VrpProblem

Module contents