discrete_optimization.tsptw.transformations package

Submodules

discrete_optimization.tsptw.transformations.to_gpdp module

Transformation from TSPTW to GPDP (General Pickup and Delivery Problem).

TSPTW can be modeled as a GPDP with: - Single vehicle - No pickup/delivery pairs - Time windows for all nodes - No capacity constraints

class discrete_optimization.tsptw.transformations.to_gpdp.TsptwToGpdpTransformation(compute_graph: bool = False)

Bases: ProblemTransformation[TSPTWProblem, TSPTWSolution, GpdpProblem, GpdpSolution]

Transform TSPTW to GPDP.

TSPTW is a special case of GPDP with: - Single vehicle - Time windows for each node - No pickup/delivery pairs - No capacity constraints - All nodes must be visited

This transformation is EXACT: - All TSPTW constraints are preserved in GPDP - Time windows are directly mapped - Solution quality is preserved in both directions

back_transform_solution(solution: GpdpSolution, source_problem: TSPTWProblem) → TSPTWSolution

Transform GPDP solution back to TSPTW solution.

Parameters:

• solution – GPDP solution (should have 1 vehicle)

• source_problem – Original TSPTW problem

Returns:

Equivalent TSPTW solution

forward_transform_solution(solution: TSPTWSolution, target_problem: GpdpProblem) → GpdpSolution | None

Transform TSPTW solution to GPDP solution (for warmstart).

Parameters:

• solution – TSPTW solution

• target_problem – Target GPDP problem

Returns:

Equivalent GPDP solution with single vehicle trajectory

get_forward_metadata() → TransformationMetadata

Metadata for forward problem transformation (TSPTW → GPDP).

This direction is EXACT: TSPTW is a special case of GPDP.

transform_problem(source_problem: TSPTWProblem) → GpdpProblem

Transform TSPTW to GPDP using the existing ProxyClass implementation.

Parameters:

source_problem – TSPTW problem instance

Returns:

Equivalent GPDP problem with 1 vehicle and time windows

discrete_optimization.tsptw.transformations.to_vrptw module

Transformation from TSPTW to VRPTW.

TSP with Time Windows is a special case of VRP with Time Windows: - Single vehicle - No capacity constraints (zero demands) - Time windows for each customer - All customers must be visited

class discrete_optimization.tsptw.transformations.to_vrptw.TsptwToVrptwTransformation(default_service_time: float = 0.0)

Bases: ProblemTransformation[TSPTWProblem, TSPTWSolution, VRPTWProblem, VRPTWSolution]

Transform TSPTW to VRPTW.

Mapping: - Single tour → Single vehicle route - Time windows → Customer time windows - All customers must be visited → All customers served - No capacity constraints → Zero demands + infinite capacity - Depot with time window → VRPTW depot with time window

This transformation is EXACT in both directions: - TSPTW is exactly VRPTW with 1 vehicle and no capacity constraints - All TSPTW constraints (time windows) are preserved in VRPTW - Solution mapping is exact both ways

back_transform_solution(solution: VRPTWSolution, source_problem: TSPTWProblem) → TSPTWSolution

Transform VRPTW solution back to TSPTW solution.

Parameters:

• solution – VRPTW solution (should have 1 vehicle)

• source_problem – Original TSPTW problem

Returns:

Equivalent TSPTW solution

forward_transform_solution(solution: TSPTWSolution, target_problem: VRPTWProblem) → VRPTWSolution | None

Transform TSPTW solution to VRPTW solution (for warmstart).

Parameters:

• solution – TSPTW solution

• target_problem – Target VRPTW problem

Returns:

Equivalent VRPTW solution with single vehicle route

get_forward_metadata() → TransformationMetadata

Metadata for forward problem transformation (TSPTW → VRPTW).

This direction is EXACT: TSPTW is exactly VRPTW with 1 vehicle, no capacity, and time windows.

transform_problem(source_problem: TSPTWProblem) → VRPTWProblem

Transform TSPTW to VRPTW.

Parameters:

source_problem – TSPTW problem instance

Returns:

Equivalent VRPTW problem with 1 vehicle and no capacity constraints

Module contents

Transformations from TSPTW to other problems.

class discrete_optimization.tsptw.transformations.TsptwToGpdpTransformation(compute_graph: bool = False)

Bases: ProblemTransformation[TSPTWProblem, TSPTWSolution, GpdpProblem, GpdpSolution]

Transform TSPTW to GPDP.

TSPTW is a special case of GPDP with: - Single vehicle - Time windows for each node - No pickup/delivery pairs - No capacity constraints - All nodes must be visited

This transformation is EXACT: - All TSPTW constraints are preserved in GPDP - Time windows are directly mapped - Solution quality is preserved in both directions

back_transform_solution(solution: GpdpSolution, source_problem: TSPTWProblem) → TSPTWSolution

Transform GPDP solution back to TSPTW solution.

Parameters:

• solution – GPDP solution (should have 1 vehicle)

• source_problem – Original TSPTW problem

Returns:

Equivalent TSPTW solution

forward_transform_solution(solution: TSPTWSolution, target_problem: GpdpProblem) → GpdpSolution | None

Transform TSPTW solution to GPDP solution (for warmstart).

Parameters:

• solution – TSPTW solution

• target_problem – Target GPDP problem

Returns:

Equivalent GPDP solution with single vehicle trajectory

get_forward_metadata() → TransformationMetadata

Metadata for forward problem transformation (TSPTW → GPDP).

This direction is EXACT: TSPTW is a special case of GPDP.

transform_problem(source_problem: TSPTWProblem) → GpdpProblem

Transform TSPTW to GPDP using the existing ProxyClass implementation.

Parameters:

source_problem – TSPTW problem instance

Returns:

Equivalent GPDP problem with 1 vehicle and time windows

class discrete_optimization.tsptw.transformations.TsptwToVrptwTransformation(default_service_time: float = 0.0)

Bases: ProblemTransformation[TSPTWProblem, TSPTWSolution, VRPTWProblem, VRPTWSolution]

Transform TSPTW to VRPTW.

Mapping: - Single tour → Single vehicle route - Time windows → Customer time windows - All customers must be visited → All customers served - No capacity constraints → Zero demands + infinite capacity - Depot with time window → VRPTW depot with time window

This transformation is EXACT in both directions: - TSPTW is exactly VRPTW with 1 vehicle and no capacity constraints - All TSPTW constraints (time windows) are preserved in VRPTW - Solution mapping is exact both ways

back_transform_solution(solution: VRPTWSolution, source_problem: TSPTWProblem) → TSPTWSolution

Transform VRPTW solution back to TSPTW solution.

Parameters:

• solution – VRPTW solution (should have 1 vehicle)

• source_problem – Original TSPTW problem

Returns:

Equivalent TSPTW solution

forward_transform_solution(solution: TSPTWSolution, target_problem: VRPTWProblem) → VRPTWSolution | None

Transform TSPTW solution to VRPTW solution (for warmstart).

Parameters:

• solution – TSPTW solution

• target_problem – Target VRPTW problem

Returns:

Equivalent VRPTW solution with single vehicle route

get_forward_metadata() → TransformationMetadata

Metadata for forward problem transformation (TSPTW → VRPTW).

This direction is EXACT: TSPTW is exactly VRPTW with 1 vehicle, no capacity, and time windows.

transform_problem(source_problem: TSPTWProblem) → VRPTWProblem

Transform TSPTW to VRPTW.

Parameters:

source_problem – TSPTW problem instance

Returns:

Equivalent VRPTW problem with 1 vehicle and no capacity constraints