discrete_optimization.vrptw.solvers package

Submodules

discrete_optimization.vrptw.solvers.cpsat module

class discrete_optimization.vrptw.solvers.cpsat.CpSatVRPTWSolver(problem: VRPTWProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: SchedulingCpSatSolver[int], WarmstartMixin

CP-SAT solver for the Vehicle Routing Problem with Time Windows (VRPTW).

This solver uses a path-based formulation with time and load dimensions to find an optimal solution. It aims to minimize the number of vehicles used, and then the total distance.

problem

The VRPTW problem instance.

Type:

VRPTWProblem

variables

Stores CP-SAT model variables.

Type:

Dict[str, Any]

get_task_start_or_end_variable(task: int, start_or_end: StartOrEnd) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64

Retrieve the variable storing the start or end time of given task.

Parameters:

• task

• start_or_end

Returns:

init_model(scaling: int, cost_per_vehicle: int, **kwargs: Any) → None

Initialise the CP-SAT model.

problem: VRPTWProblem

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → VRPTWSolution

Build a VRPTWSolution from the CP-SAT solver’s callback.

set_warm_start(solution: VRPTWSolution) → None

Provides a warm start hint to the CP-SAT solver from an existing solution.

discrete_optimization.vrptw.solvers.dp module

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

Bases: DpSolver

Dynamic Programming solver for the VRPTW.

This model combines the state variables from the VRP (load, vehicle index) and the TSPTW (time) to solve the VRPTW.

State variables: - unvisited (Set): Set of customers not yet served. - location (Element): The current location of the active vehicle. - load (FloatResource): The current load of the active vehicle. - time (FloatResource): The current time (service start time) at the current location. - vehicles_ (Element): The index of the active vehicle (from 0 to m-1).

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='resource_var_load', default=False, depends_on=None, name_in_kwargs='resource_var_load'), CategoricalHyperparameter(name='resource_var_time', default=False, depends_on=None, name_in_kwargs='resource_var_time')]

Hyperparameters available for this solver.

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

• __init__()

• init_model() (when available)

• solve()

init_model(scaling: int = 1000, cost_per_vehicle: int = 1000000, **kwargs: Any) → None

DP model for VRPTW.

problem: VRPTWProblem

retrieve_solution(sol: Solution) → VRPTWSolution

Reconstructs the VRPTWSolution from the sequence of DP transitions. This logic is adapted from DpVrpSolver.

scaling: int

set_warm_start(solution: VRPTWSolution) → None

Provides a warm start hint to the DP solver from an existing solution. Converts a VRPTWSolution into a list of didppy.Transition objects.

transitions: dict

discrete_optimization.vrptw.solvers.ortools_routing module

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

Bases: SolverDO

gpdp_problem: GpdpProblem

init_model(time_limit=10, scaling: float = 100, cost_per_vehicle: int = 100000, **kwargs: Any) → None

Initialize internal model used to solve.

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

problem: VRPTWProblem

solve(callbacks: list[Callback] | None = None, **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

solver: OrtoolsGpdpSolver

Module contents