DDOLib-Scala/org.ddolibscala/org.ddolibscala.example/org.ddolibscala.example.tsptw/TspTwFlb

TspTwFlb

org.ddolibscala.example.tsptw.TspTwFlb

class TspTwFlb(problem: TspTwProblem) extends FastLowerBound[TspTwState]

Implementation of a fast lower bound for the Traveling Salesperson Problem with Time Windows (TSPTW).

This class provides a heuristic lower bound on the total tour cost starting from a given TspTwState. The lower bound is computed by summing the shortest available edges from the current position, including all mandatory nodes that must be visited and a selection of optional nodes if needed to complete the tour. The bound also considers returning to the depot and respects time window constraints.

If any mandatory node is unreachable from the current state, or if completing the tour is impossible within the time windows, the bound returns scala.Int.MaxValue to indicate infeasibility.

Precomputes the cheapest outgoing edge for each node to speed up repeated lower bound calculations.

Value parameters

problem: the associated TSPTW problem instance

Attributes

Graph
Supertypes: trait FastLowerBound[TspTwState]

trait FastLowerBound[TspTwState]

class Object

trait Matchable

class Any

Members list

Value members

Concrete methods

Returns a very rough estimation (lower bound) of the optimal value that could be reached if state were the initial state.

Value parameters

state: the state for which the estimate is to be computed
variables: the set of unassigned variables

Attributes

Returns: a very rough estimation (lower bound) of the optimal value that could be reached if state were the initial state
Definition Classes: FastLowerBound

Inherited methods

Used by the solver. Convert the input and output of lowerBound from Java to Scala and vice versa.

Attributes

Definition Classes: FastLowerBound -> FastLowerBound
Inherited from:: FastLowerBound

In this article

Generated with