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
  • discrete_optimization.tsptw.solvers.optal module
    • OptalTspTwSolver
      • OptalTspTwSolver.build_command()
      • OptalTspTwSolver.init_model()
      • OptalTspTwSolver.problem
      • OptalTspTwSolver.retrieve_current_solution()
    • tsptw_to_dict()
  • discrete_optimization.tsptw.solvers.ortools_routing module
    • OrtoolsTspTwSolver
      • OrtoolsTspTwSolver.gpdp_problem
      • OrtoolsTspTwSolver.init_model()
      • OrtoolsTspTwSolver.problem
      • OrtoolsTspTwSolver.solve()
      • OrtoolsTspTwSolver.solver
  • 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(variable: 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)

get_attribute_register() → EncodingRegister

Returns how the Solution should be encoded.

Useful to find automatically available mutations for local search. Used by genetic algorithms Ga and Nsga.

This needs only to be implemented in child classes when GA or LS solvers are to be used.

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(variable: 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. 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() → 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

problem: TSPTWProblem

Module contents