discrete_optimization.tsptw package

Subpackages

• discrete_optimization.tsptw.solvers package
  • Submodules
  • discrete_optimization.tsptw.solvers.cpsat module
    • CpSatTSPTWSolver
      • CpSatTSPTWSolver.problem
      • CpSatTSPTWSolver.variables
      • CpSatTSPTWSolver.init_model()
      • CpSatTSPTWSolver.problem
      • CpSatTSPTWSolver.retrieve_solution()
      • CpSatTSPTWSolver.set_warm_start()
  • discrete_optimization.tsptw.solvers.dp module
    • DpTspTwSolver
      • DpTspTwSolver.hyperparameters
      • DpTspTwSolver.init_model()
      • DpTspTwSolver.problem
      • DpTspTwSolver.retrieve_solution()
      • DpTspTwSolver.transitions
  • Module contents

Submodules

discrete_optimization.tsptw.parser module

discrete_optimization.tsptw.parser.get_data_available(data_folder: str | None = None, data_home: str | None = None) → list[str]

Get datasets available for tsptw.

Params:

data_folder: folder where datasets for tsptw whould be find.

If None, we look in “tsptw” subdirectory of data_home.

data_home: root directory for all datasets. Is None, set by

default to “~/discrete_optimization_data “

discrete_optimization.tsptw.parser.parse_tsptw_file(filepath: str) → TSPTWProblem

Parses a TSP-TW problem file in the specified format.

Parameters:

filepath – The path to the TSP-TW instance file.

Returns:

An instance of the TSPTWProblem class.

discrete_optimization.tsptw.problem module

class discrete_optimization.tsptw.problem.TSPTWProblem(nb_nodes: int, distance_matrix: ndarray, time_windows: List[Tuple[int, int]], depot_node: int = 0)

Bases: Problem

Traveling Salesman Problem with Time Windows (TSP-TW) Problem class.

evaluate(solution: TSPTWSolution) → Dict[str, float]

Evaluates a solution by calculating the makespan and time window violations.

This evaluation assumes the distance matrix D[u,v] includes the service time at node u. The timeline is calculated as follows: 1. Arrival at node v = Start of service at u + D[u,v] 2. Start of service at v = max(Arrival at v, Earliest time for v) 3. Violation at v = max(0, Start of service at v - Latest time for v)

evaluate_from_encoding(int_vector: List[int], encoding_name: str) → Dict[str, float]

get_attribute_register() → EncodingRegister

Returns how the Solution should be encoded.

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

get_dummy_solution() → TSPTWSolution

Returns a simple, non-random dummy solution (e.g., customers in order).

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: TSPTWSolution) → 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.tsptw.problem.TSPTWSolution(problem: TSPTWProblem, permutation: List[int], arrival_times: Dict[int, float] | None = None, start_service_times: Dict[int, float] | None = None, makespan: float | None = None, tw_violation: float | None = None)

Bases: Solution

Solution class for the TSP-TW problem.

problem

The problem instance.

Type:

TSPTWProblem

permutation

A list of customer node indices in the order they are visited. The depot is not included in this list.

Type:

List[int]

arrival_times

A dictionary mapping each node index to its arrival time.

Type:

Dict[int, float]

start_service_times

A dictionary mapping each node to the time service begins.

Type:

Dict[int, float]

makespan

The total time of the tour, from leaving the depot to returning. This is the primary objective.

Type:

float

tw_violation

The total violation of time windows (sum of lateness at each node).

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

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.

lazy_copy() → TSPTWSolution

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

Module contents