discrete_optimization.vrp.transformations package

Submodules

discrete_optimization.vrp.transformations.to_top module

Transformation from VRP to Team Orienteering Problem (TOP).

class discrete_optimization.vrp.transformations.to_top.VrpToTopTransformation(max_length_tours: float | None = None, reward_function=None)[source]

Bases: ProblemTransformation[Customer2DVrpProblem, VrpSolution, TeamOrienteeringProblem2D, VrpSolution]

Transform VRP (2D) to Team Orienteering Problem (TOP).

Mapping: - VRP customers → TOP customers with rewards - VRP vehicle routes → TOP tours - VRP capacity constraints → Dropped (TOP has no capacity) - Add max_length_tours constraint - Objective: minimize total distance → maximize total reward

Note: This transformation assigns uniform rewards (reward=1) to all customers. Users can modify rewards after transformation if needed.

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

Transform TOP solution back to VRP solution.

Parameters:

  • solution – TOP solution (uses VrpSolution representation)

  • source_problem – Original VRP problem

Returns:

Equivalent VRP solution

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

Transform VRP solution to TOP solution (for warmstart).

Parameters:

  • solution – VRP solution

  • target_problem – Target TOP problem

Returns:

Equivalent TOP solution

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward transformation (VRP → TOP).

transform_problem(source_problem: Customer2DVrpProblem) → TeamOrienteeringProblem2D[source]

Transform VRP to TOP.

Parameters:

source_problem – VRP problem instance (must be 2D)

Returns:

Equivalent TOP problem with rewards

discrete_optimization.vrp.transformations.to_vrptw module

Transformation from VRP to VRPTW.

class discrete_optimization.vrp.transformations.to_vrptw.VrpToVrptwTransformation(horizon: int | None = None, default_service_time: float = 0.0)[source]

Bases: ProblemTransformation[VrpProblem, VrpSolution, VRPTWProblem, VRPTWSolution]

Transform VRP to VRPTW (Vehicle Routing with Time Windows).

Mapping: - Vehicle routes → Vehicle routes with time windows - Customer demands → Customer demands - Vehicle capacities → Vehicle capacities - Add relaxed time windows: [0, horizon] for all customers - Add zero service times

VRP is a special case of VRPTW with relaxed (unconstrained) time windows. This transformation is EXACT in both directions when time windows are wide enough.

back_transform_solution(solution: VRPTWSolution, source_problem: VrpProblem) → VrpSolution[source]

Transform VRPTW solution back to VRP solution.

Parameters:

  • solution – VRPTW solution

  • source_problem – Original VRP problem

Returns:

Equivalent VRP solution

forward_transform_solution(solution: VrpSolution, target_problem: VRPTWProblem) → VRPTWSolution | None[source]

Transform VRP solution to VRPTW solution (for warmstart).

Parameters:

  • solution – VRP solution

  • target_problem – Target VRPTW problem

Returns:

Equivalent VRPTW solution

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (VRP → VRPTW).

This direction is EXACT: VRP is exactly VRPTW with relaxed time windows.

transform_problem(source_problem: VrpProblem) → VRPTWProblem[source]

Transform VRP to VRPTW.

Parameters:

source_problem – VRP problem instance

Returns:

Equivalent VRPTW problem with relaxed time windows

Module contents

Transformations from VRP to other problems.

class discrete_optimization.vrp.transformations.VrpToTopTransformation(max_length_tours: float | None = None, reward_function=None)[source]

Bases: ProblemTransformation[Customer2DVrpProblem, VrpSolution, TeamOrienteeringProblem2D, VrpSolution]

Transform VRP (2D) to Team Orienteering Problem (TOP).

Mapping: - VRP customers → TOP customers with rewards - VRP vehicle routes → TOP tours - VRP capacity constraints → Dropped (TOP has no capacity) - Add max_length_tours constraint - Objective: minimize total distance → maximize total reward

Note: This transformation assigns uniform rewards (reward=1) to all customers. Users can modify rewards after transformation if needed.

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

Transform TOP solution back to VRP solution.

Parameters:

  • solution – TOP solution (uses VrpSolution representation)

  • source_problem – Original VRP problem

Returns:

Equivalent VRP solution

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

Transform VRP solution to TOP solution (for warmstart).

Parameters:

  • solution – VRP solution

  • target_problem – Target TOP problem

Returns:

Equivalent TOP solution

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward transformation (VRP → TOP).

transform_problem(source_problem: Customer2DVrpProblem) → TeamOrienteeringProblem2D[source]

Transform VRP to TOP.

Parameters:

source_problem – VRP problem instance (must be 2D)

Returns:

Equivalent TOP problem with rewards

class discrete_optimization.vrp.transformations.VrpToVrptwTransformation(horizon: int | None = None, default_service_time: float = 0.0)[source]

Bases: ProblemTransformation[VrpProblem, VrpSolution, VRPTWProblem, VRPTWSolution]

Transform VRP to VRPTW (Vehicle Routing with Time Windows).

Mapping: - Vehicle routes → Vehicle routes with time windows - Customer demands → Customer demands - Vehicle capacities → Vehicle capacities - Add relaxed time windows: [0, horizon] for all customers - Add zero service times

VRP is a special case of VRPTW with relaxed (unconstrained) time windows. This transformation is EXACT in both directions when time windows are wide enough.

back_transform_solution(solution: VRPTWSolution, source_problem: VrpProblem) → VrpSolution[source]

Transform VRPTW solution back to VRP solution.

Parameters:

  • solution – VRPTW solution

  • source_problem – Original VRP problem

Returns:

Equivalent VRP solution

forward_transform_solution(solution: VrpSolution, target_problem: VRPTWProblem) → VRPTWSolution | None[source]

Transform VRP solution to VRPTW solution (for warmstart).

Parameters:

  • solution – VRP solution

  • target_problem – Target VRPTW problem

Returns:

Equivalent VRPTW solution

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (VRP → VRPTW).

This direction is EXACT: VRP is exactly VRPTW with relaxed time windows.

transform_problem(source_problem: VrpProblem) → VRPTWProblem[source]

Transform VRP to VRPTW.

Parameters:

source_problem – VRP problem instance

Returns:

Equivalent VRPTW problem with relaxed time windows