discrete_optimization.vrptw package

Subpackages

• discrete_optimization.vrptw.solvers package
  • Submodules
  • discrete_optimization.vrptw.solvers.cpsat module
    • CpSatVRPTWSolver
      • CpSatVRPTWSolver.problem
      • CpSatVRPTWSolver.variables
      • CpSatVRPTWSolver.get_task_start_or_end_variable()
      • CpSatVRPTWSolver.init_model()
      • CpSatVRPTWSolver.problem
      • CpSatVRPTWSolver.retrieve_solution()
      • CpSatVRPTWSolver.set_warm_start()
  • discrete_optimization.vrptw.solvers.dp module
    • DpVrptwSolver
      • DpVrptwSolver.hyperparameters
      • DpVrptwSolver.init_model()
      • DpVrptwSolver.problem
      • DpVrptwSolver.retrieve_solution()
      • DpVrptwSolver.scaling
      • DpVrptwSolver.set_warm_start()
      • DpVrptwSolver.transitions
  • discrete_optimization.vrptw.solvers.ortools_routing module
    • OrtoolsVrpTwSolver
      • OrtoolsVrpTwSolver.gpdp_problem
      • OrtoolsVrpTwSolver.init_model()
      • OrtoolsVrpTwSolver.problem
      • OrtoolsVrpTwSolver.solve()
      • OrtoolsVrpTwSolver.solver
  • Module contents

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]

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

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:

VRPTWProblem

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)

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(solution: VRPTWSolution) → Dict[str, float]

Evaluates a VRPTWSolution. Calculates distances, time window violations, and capacity violations.

get_attribute_register() → EncodingRegister

Returns how the Solution should be encoded.

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

get_dummy_solution() → VRPTWSolution

Returns a dummy solution (one vehicle per customer).

get_makespan_upper_bound() → int

Get a upper bound on global makespan.

get_objective_register() → ObjectiveRegister

Returns the objective definition.

Returns (ObjectiveRegister): object defining the objective criteria.

get_solution_type() → type

Returns the class implementation of a Solution.

Returns (class): class object of the given Problem.

satisfy(solution: VRPTWSolution) → 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.vrptw.problem.VRPTWSolution(problem: VRPTWProblem, routes: List[List[int]] | None = None, scaling: float = 1.0)

Bases: SchedulingSolution[int], AllocationSolution[int, int]

Solution class for the VRPTW problem.

problem

The problem instance.

Type:

VRPTWProblem

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

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() → VRPTWSolution

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

get_start_time(task: int) → int

is_allocated(task: int, unary_resource: int) → bool

Return the usage of the unary resource for the given task.

Parameters:

• task

• unary_resource

Returns:

lazy_copy() → VRPTWSolution

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

Module contents