Package org.ddolib.examples.tsptw

Class TSPTWWidth

java.lang.Object

org.ddolib.examples.tsptw.TSPTWWidth

All Implemented Interfaces:

WidthHeuristic<TSPTWState>

public class TSPTWWidth
extends Object
implements WidthHeuristic<TSPTWState>

Heuristic for computing the width of a layer in the dynamic programming model for the Traveling Salesman Problem with Time Windows (TSPTW).

The width represents the maximum number of states to keep at a given layer. It is computed based on the number of variables, the current depth, and a user-defined factor.

Constructor Summary

Constructors

Constructor	Description
TSPTWWidth(int nbVars, int factor)	Constructs a width heuristic for TSPTW layers.

Method Summary

Modifier and Type	Method	Description
int	maximumWidth(TSPTWState state)	Computes the maximum width of a layer based on the current state.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

TSPTWWidth

public TSPTWWidth(int nbVars,
 int factor)

Constructs a width heuristic for TSPTW layers.

Parameters:

nbVars - the number of variables/nodes in the problem

factor - a scaling factor for the width calculation

Method Details

maximumWidth

public int maximumWidth(TSPTWState state)

Computes the maximum width of a layer based on the current state.

The width is calculated as: (depth + 1) * nbVars * factor. This allows the width to grow with the depth of the state in the DP model.

Specified by:

maximumWidth in interface WidthHeuristic<TSPTWState>

Parameters:

state - the state for which to compute the layer width

Returns:

the maximum number of states to keep at this layer