discrete_optimization.vrptw package
Subpackages
- discrete_optimization.vrptw.solvers package
- discrete_optimization.vrptw.transformations package
Submodules
discrete_optimization.vrptw.parser module
- discrete_optimization.vrptw.parser.get_data_available(data_folder: str | None = None, data_home: str | None = None) list[str][source]
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.vrptw.parser.parse_vrptw_file(file_path: str) VRPTWProblem[source]
Parses a Solomon-style VRPTW instance file.
- Parameters:
file_path (str) – The path to the instance file (e.g., “RC1_2_10.TXT”).
- Returns:
An instance of the VRPTW problem.
- Return type:
discrete_optimization.vrptw.problem module
- class discrete_optimization.vrptw.problem.VRPTWProblem(nb_vehicles: int, vehicle_capacity: float, nb_nodes: int, distance_matrix: ndarray, time_windows: List[Tuple[int, int]], service_times: List[float], demands: List[float], depot_node: int = 0)[source]
Bases:
SchedulingProblem[int],AllocationProblem[int,int]Vehicle Routing Problem with Time Windows (VRPTW) Problem class.
This model includes: - Multiple vehicles with a shared capacity. - A single depot. - Customers with demand. - Customers with time windows (ready time, due date). - Customers with service times. - Objectives: 1) Minimize number of vehicles, 2) Minimize total distance.
- evaluate(variable: VRPTWSolution) Dict[str, float][source]
Evaluates a VRPTWSolution. Calculates distances, time window violations, and capacity violations.
- get_dummy_solution() VRPTWSolution[source]
Returns a dummy solution (one vehicle per customer).
- get_objective_register() ObjectiveRegister[source]
Returns the objective definition.
Returns (ObjectiveRegister): object defining the objective criteria.
- get_solution_type() type[source]
Returns the class implementation of a Solution.
Returns (class): class object of the given Problem.
- is_optional(task: int) bool[source]
Whether a task is optional or not.
It means that the task can be ignored in the solution. If absent of the solution, it can also be removed from the constraints.
Default to no optional task.
- satisfy(variable: VRPTWSolution) bool[source]
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.
- property tasks_list: list[int]
List of all tasks to schedule or allocate to.
- property unary_resources_list: list[int]
Available unary resources.
It can correspond to employees (rcpsp-multiskill), teams (workforce-scheduling), or a mix of several types.
- class discrete_optimization.vrptw.problem.VRPTWSolution(problem: VRPTWProblem, routes: List[List[int]] | None = None, scaling: float = 1.0)[source]
Bases:
SchedulingSolution[int],AllocationSolution[int,int]Solution class for the VRPTW problem.
- problem
The problem instance.
- Type:
- routes
List of routes. Each route is a list of customer node indices. The depot (start/end) is implicit and not included in these lists.
- Type:
List[List[int]]
- arrival_times
Maps vehicle index to a list of arrival times at customer nodes in its route.
- Type:
Dict[int, List[float]]
- start_service_times
Maps vehicle index to a list of service start times at customer nodes.
- Type:
Dict[int, List[float]]
- route_loads
Total demand for each route.
- Type:
List[float]
- route_distances
Total distance for each route.
- Type:
List[float]
- # Evaluated metrics
- total_distance
Sum of distances of all routes.
- Type:
float
- nb_vehicles_used
Number of routes used.
- Type:
int
- tw_violation
Total violation of time windows (sum of lateness).
- Type:
float
- capacity_violation
Total violation of vehicle capacities.
- Type:
float
- change_problem(new_problem: Problem) None[source]
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() VRPTWSolution[source]
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.
- get_end_time(task: int) int | AbsentValue[source]
Get end time of the task
- Hypothesis:
The returned time can have AbsentValue.ABSENT only if self.is_present(task) is False.
- Parameters:
task
Returns:
- get_start_time(task: int) int | AbsentValue[source]
Get start time of the task
- Hypothesis:
The returned time can have AbsentValue.ABSENT only if self.is_present(task) is False.
- Parameters:
task
Returns:
- is_allocated(task: int, unary_resource: int) bool[source]
Return the usage of the unary resource for the given task.
- Parameters:
task
unary_resource
Returns:
- is_present(task: int) bool[source]
Tell whether the task is present in the solution.
For allocation problem, default to “at least one unary resource has been allocated to the task”. To be overriden in child classes for problem having tasks present without allocation.
- lazy_copy() VRPTWSolution[source]
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: VRPTWProblem