discrete_optimization.tsp.transformations package

Submodules

discrete_optimization.tsp.transformations.to_gpdp module

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

TSP can be modeled as a GPDP with: - Single vehicle - No pickup/delivery pairs - No time windows - No capacity constraints

class discrete_optimization.tsp.transformations.to_gpdp.TspToGpdpTransformation(compute_graph: bool = False)[source]

Bases: ProblemTransformation[TspProblem, TspSolution, GpdpProblem, GpdpSolution]

Transform TSP to GPDP.

TSP is a special case of GPDP with: - Single vehicle - No pickup/delivery pairs - No time windows - No capacity constraints - All nodes must be visited

This transformation is EXACT: - All TSP constraints are preserved in GPDP - Solution quality is preserved in both directions

back_transform_solution(solution: GpdpSolution, source_problem: TspProblem) → TspSolution[source]

Transform GPDP solution back to TSP solution.

Parameters:

  • solution – GPDP solution (should have 1 vehicle)

  • source_problem – Original TSP problem

Returns:

Equivalent TSP solution

forward_transform_solution(solution: TspSolution, target_problem: GpdpProblem) → GpdpSolution | None[source]

Transform TSP solution to GPDP solution (for warmstart).

Parameters:

  • solution – TSP solution

  • target_problem – Target GPDP problem

Returns:

Equivalent GPDP solution with single vehicle trajectory

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (TSP → GPDP).

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

transform_problem(source_problem: TspProblem) → GpdpProblem[source]

Transform TSP to GPDP using the existing ProxyClass implementation.

Parameters:

source_problem – TSP problem instance

Returns:

Equivalent GPDP problem with 1 vehicle and no constraints

discrete_optimization.tsp.transformations.to_tsptw module

Transformation from TSP to TSPTW.

TSP is a special case of TSPTW with relaxed (infinite) time windows.

class discrete_optimization.tsp.transformations.to_tsptw.TspToTsptwTransformation(horizon: int | None = None)[source]

Bases: ProblemTransformation[TspProblem, TspSolution, TSPTWProblem, TSPTWSolution]

Transform TSP to TSPTW.

Mapping: - Tour → Tour with relaxed time windows - No time constraints → Wide time windows [0, horizon] - Depot → Depot with wide time window - Distance matrix → Distance matrix (preserved)

This transformation is EXACT: - TSP is exactly TSPTW with relaxed (unconstrained) time windows - All TSP constraints are preserved - Solution quality is identical

back_transform_solution(solution: TSPTWSolution, source_problem: TspProblem) → TspSolution[source]

Transform TSPTW solution back to TSP solution.

Parameters:

  • solution – TSPTW solution

  • source_problem – Original TSP problem

Returns:

Equivalent TSP solution

forward_transform_solution(solution: TspSolution, target_problem: TSPTWProblem) → TSPTWSolution | None[source]

Transform TSP solution to TSPTW solution (for warmstart).

Parameters:

  • solution – TSP solution

  • target_problem – Target TSPTW problem

Returns:

Equivalent TSPTW solution

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (TSP → TSPTW).

This direction is EXACT: TSP is exactly TSPTW with wide time windows.

transform_problem(source_problem: TspProblem) → TSPTWProblem[source]

Transform TSP to TSPTW.

Parameters:

source_problem – TSP problem instance

Returns:

Equivalent TSPTW problem with relaxed time windows

discrete_optimization.tsp.transformations.to_vrp module

Transformation from TSP to VRP.

This transformation is EXACT: TSP is a special case of VRP with 1 vehicle, infinite capacity (or zero demands), and all customers must be visited.

class discrete_optimization.tsp.transformations.to_vrp.TspToVrpTransformation[source]

Bases: ProblemTransformation[TspProblem, TspSolution, VrpProblem, VrpSolution]

Transform TSP to VRP.

Mapping: - Single tour → Single vehicle route - All nodes must be visited → All customers served - No capacity constraints → Infinite capacity (or zero demands) - Start/end depot → VRP start/end depot

This transformation is EXACT: - TSP is exactly VRP with 1 vehicle and no capacity constraints - All TSP constraints are preserved in VRP formulation

Solution mapping is exact in both directions: - TSP tour → VRP route for vehicle 0 - VRP route (single vehicle) → TSP tour

back_transform_solution(solution: VrpSolution, source_problem: TspProblem) → TspSolution[source]

Transform VRP solution back to TSP solution.

Parameters:

  • solution – VRP solution (should have 1 vehicle)

  • source_problem – Original TSP problem

Returns:

Equivalent TSP solution

forward_transform_solution(solution: TspSolution, target_problem: VrpProblem) → VrpSolution | None[source]

Transform TSP solution to VRP solution (for warmstart).

Parameters:

  • solution – TSP solution

  • target_problem – Target VRP problem

Returns:

Equivalent VRP solution with single vehicle route

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (TSP → VRP).

This direction is EXACT: TSP is a perfect subset of VRP.

transform_problem(source_problem: TspProblem) → VrpProblem[source]

Transform TSP to VRP.

Parameters:

source_problem – TSP problem instance

Returns:

Equivalent VRP problem with 1 vehicle

Module contents

Problem transformations for TSP (Traveling Salesman Problem).

class discrete_optimization.tsp.transformations.TspToGpdpTransformation(compute_graph: bool = False)[source]

Bases: ProblemTransformation[TspProblem, TspSolution, GpdpProblem, GpdpSolution]

Transform TSP to GPDP.

TSP is a special case of GPDP with: - Single vehicle - No pickup/delivery pairs - No time windows - No capacity constraints - All nodes must be visited

This transformation is EXACT: - All TSP constraints are preserved in GPDP - Solution quality is preserved in both directions

back_transform_solution(solution: GpdpSolution, source_problem: TspProblem) → TspSolution[source]

Transform GPDP solution back to TSP solution.

Parameters:

  • solution – GPDP solution (should have 1 vehicle)

  • source_problem – Original TSP problem

Returns:

Equivalent TSP solution

forward_transform_solution(solution: TspSolution, target_problem: GpdpProblem) → GpdpSolution | None[source]

Transform TSP solution to GPDP solution (for warmstart).

Parameters:

  • solution – TSP solution

  • target_problem – Target GPDP problem

Returns:

Equivalent GPDP solution with single vehicle trajectory

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (TSP → GPDP).

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

transform_problem(source_problem: TspProblem) → GpdpProblem[source]

Transform TSP to GPDP using the existing ProxyClass implementation.

Parameters:

source_problem – TSP problem instance

Returns:

Equivalent GPDP problem with 1 vehicle and no constraints

class discrete_optimization.tsp.transformations.TspToTsptwTransformation(horizon: int | None = None)[source]

Bases: ProblemTransformation[TspProblem, TspSolution, TSPTWProblem, TSPTWSolution]

Transform TSP to TSPTW.

Mapping: - Tour → Tour with relaxed time windows - No time constraints → Wide time windows [0, horizon] - Depot → Depot with wide time window - Distance matrix → Distance matrix (preserved)

This transformation is EXACT: - TSP is exactly TSPTW with relaxed (unconstrained) time windows - All TSP constraints are preserved - Solution quality is identical

back_transform_solution(solution: TSPTWSolution, source_problem: TspProblem) → TspSolution[source]

Transform TSPTW solution back to TSP solution.

Parameters:

  • solution – TSPTW solution

  • source_problem – Original TSP problem

Returns:

Equivalent TSP solution

forward_transform_solution(solution: TspSolution, target_problem: TSPTWProblem) → TSPTWSolution | None[source]

Transform TSP solution to TSPTW solution (for warmstart).

Parameters:

  • solution – TSP solution

  • target_problem – Target TSPTW problem

Returns:

Equivalent TSPTW solution

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (TSP → TSPTW).

This direction is EXACT: TSP is exactly TSPTW with wide time windows.

transform_problem(source_problem: TspProblem) → TSPTWProblem[source]

Transform TSP to TSPTW.

Parameters:

source_problem – TSP problem instance

Returns:

Equivalent TSPTW problem with relaxed time windows

class discrete_optimization.tsp.transformations.TspToVrpTransformation[source]

Bases: ProblemTransformation[TspProblem, TspSolution, VrpProblem, VrpSolution]

Transform TSP to VRP.

Mapping: - Single tour → Single vehicle route - All nodes must be visited → All customers served - No capacity constraints → Infinite capacity (or zero demands) - Start/end depot → VRP start/end depot

This transformation is EXACT: - TSP is exactly VRP with 1 vehicle and no capacity constraints - All TSP constraints are preserved in VRP formulation

Solution mapping is exact in both directions: - TSP tour → VRP route for vehicle 0 - VRP route (single vehicle) → TSP tour

back_transform_solution(solution: VrpSolution, source_problem: TspProblem) → TspSolution[source]

Transform VRP solution back to TSP solution.

Parameters:

  • solution – VRP solution (should have 1 vehicle)

  • source_problem – Original TSP problem

Returns:

Equivalent TSP solution

forward_transform_solution(solution: TspSolution, target_problem: VrpProblem) → VrpSolution | None[source]

Transform TSP solution to VRP solution (for warmstart).

Parameters:

  • solution – TSP solution

  • target_problem – Target VRP problem

Returns:

Equivalent VRP solution with single vehicle route

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (TSP → VRP).

This direction is EXACT: TSP is a perfect subset of VRP.

transform_problem(source_problem: TspProblem) → VrpProblem[source]

Transform TSP to VRP.

Parameters:

source_problem – TSP problem instance

Returns:

Equivalent VRP problem with 1 vehicle