Package org.ddolib.examples.tsptw

Class TSPTWRelax

java.lang.Object

org.ddolib.examples.tsptw.TSPTWRelax

All Implemented Interfaces:

Relaxation<TSPTWState>

public class TSPTWRelax
extends Object
implements Relaxation<TSPTWState>

Relaxation class for the Traveling Salesman Problem with Time Windows (TSPTW).

This class implements the Relaxation interface for TSPTWState. It provides methods to merge multiple states into a relaxed state and to relax the cost of transitions (edges) between states.

Constructor Summary

Constructors

Constructor	Description
TSPTWRelax(TSPTWProblem problem)	Initializes the relaxation for a given TSPTW problem.

Method Summary

Modifier and Type	Method	Description
TSPTWState	mergeStates(Iterator<TSPTWState> states)	Merges multiple TSPTW states into a single relaxed state.
double	relaxEdge(TSPTWState from, TSPTWState to, TSPTWState merged, Decision d, double cost)	Relaxes the cost of an edge (transition) between two states.

Methods inherited from class java.lang.Object

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

Constructor Details

TSPTWRelax

public TSPTWRelax(TSPTWProblem problem)

Initializes the relaxation for a given TSPTW problem.

Parameters:

problem - the TSPTW problem to process

Method Details

mergeStates

public TSPTWState mergeStates(Iterator<TSPTWState> states)

Merges multiple TSPTW states into a single relaxed state.

The merge operation consists of:

• Combining visited positions (union of all positions).
• Computing the intersection of all "must visit" sets.
• Building the "possibly visit" set as the union of all "must visit" and "possibly visit" sets, then removing the nodes that are mandatory.
• Selecting the minimum arrival time among all states.
• Keeping the depth of the last processed state.

Specified by:

mergeStates in interface Relaxation<TSPTWState>

Parameters:

states - an iterator over the states to merge

Returns:

a new TSPTWState representing the relaxed state

relaxEdge

public double relaxEdge(TSPTWState from,
 TSPTWState to,
 TSPTWState merged,
 Decision d,
 double cost)

Relaxes the cost of an edge (transition) between two states.

In this implementation, the cost is not modified, and the method simply returns the provided value. This method can be extended to apply more sophisticated relaxations if needed.

Specified by:

relaxEdge in interface Relaxation<TSPTWState>

Parameters:

from - the source state

to - the target state

merged - the state resulting from the merge or relaxation

d - the decision associated with this transition

cost - the cost of the transition

Returns:

the relaxed cost of the transition