DDOLib-Scala
API
Generated with
DDOLib-Scala/org.ddolibscala/org.ddolibscala.example/org.ddolibscala.example.tsptw

org.ddolibscala.example.tsptw

package org.ddolibscala.example.tsptw

This package implements the acs, astar and ddo models for the Traveling Salesperson Problem with Time Window (TSPTW). The TSPTW (TSP with Time Windows) objective is to find the shortest possible route for a salesperson to visit a set of customers (or nodes) exactly once and return to the starting point, while respecting specified time windows for each customer.

Attributes

Members list

Type members

Classlikes

sealed trait Position

Trait to model the position of a vehicle in a TspTwProblem

Trait to model the position of a vehicle in a TspTwProblem

Attributes

Supertypes
class Object
trait Matchable
class Any
Known subtypes
class TspNode
class VirtualNodes
case class TimeWindow(start: Int, end: Int)

Represents a time window with a start and end time.

Represents a time window with a start and end time.

A TimeWindow defines an interval [start, end] during which an event, task, or visit must occur. Both start and end are inclusive and usually represented as integer time units (e.g., minutes, hours).

Typical usage is in scheduling problems such as the Traveling Salesman Problem with Time Windows (TSPTW), where each location or task has a limited time window in which it can be visited or executed.

Value parameters

end

the end of the time window (inclusive)

start

the beginning of the time window (inclusive)

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
case class TspNode(value: Int) extends Position

Unique position of the vehicle.

Unique position of the vehicle.

Value parameters

value

a position of the vehicle in the current route

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait Position
class Object
trait Matchable
class Any
Show all
object TspTwAstarMain

Example of TSPTW resolution with an A* solver.

Example of TSPTW resolution with an A* solver.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
object TspTwDdoMain

Example of TSPTW resolution with a DDO solver.

Example of TSPTW resolution with a DDO solver.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
class TspTwDominance extends Dominance[TspTwState]

Dominance relation for the Traveling Salesperson Problem with Time Windows (TSPTW).

Dominance relation for the Traveling Salesperson Problem with Time Windows (TSPTW).

This class defines a dominance rule between two TspTwState instances. Two states are comparable if they share the same current position and the same set of remaining locations to visit mustVisit. Among such comparable states, the state with the lower current time dominates the other.

Dominance is used to prune the search space: if a state is dominated by another, it can be safely discarded without losing optimality.

Attributes

Supertypes
trait Dominance[TspTwState]
class Object
trait Matchable
class Any
case class TspTwDominanceKey(position: Position, mustVisit: BitSet)

Key used for dominance checking in the Traveling Salesperson Problem with Time Windows (TSPTW).

Key used for dominance checking in the Traveling Salesperson Problem with Time Windows (TSPTW).

A TspTwDominanceKey uniquely identifies a group of states that share the same current position and the same set of locations that still must be visited . It is used by TspTwDominanceto determine which states can be compared for dominance.

Two states with the same dominance key are comparable: the state with the lower current time dominates the other, allowing pruning in the search.

Value parameters

mustVisit

the set of locations that must still be visited

position

the current position in the tour

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
class TspTwFlb(problem: TspTwProblem) extends FastLowerBound[TspTwState]

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

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

Supertypes
trait FastLowerBound[TspTwState]
class Object
trait Matchable
class Any
object TspTwProblem

Companion object of the TspTwProblem class.

Companion object of the TspTwProblem class.

Attributes

Companion
class
Supertypes
class Object
trait Matchable
class Any
Self type
class TspTwProblem(numNodes: Int, val timeMatrix: Int => Int => Int, val timeWindows: Array[TimeWindow], _optimal: Option[Double] = ..., name: Option[String] = ...) extends Problem[TspTwState]

Class representing an instance of the Traveling Salesperson Problem with Time Windows (TSPTW).

Class representing an instance of the Traveling Salesperson Problem with Time Windows (TSPTW).

Each node has a time window during which it must be visited, and travel between nodes is defined by a distance matrix. This class implements the org.ddolibscala.modeling.Problem trait for use in decision diagram solvers.

The problem instance can optionally provide the known optimal solution.

Value parameters

_optimal

if known, the optimal solution of this problem. Useful for tests

name

an optional name to override the default toString

numNodes

the number of nodes to route (including the start point)

timeMatrix

function such that timeMatrix(i)(j) returns the travel time between node i and node j

timeWindows

for each node, contains the associated time window

Attributes

Companion
object
Supertypes
trait Problem[TspTwState]
class Object
trait Matchable
class Any
class TspTwRanking extends StateRanking[TspTwState]

Ranking class for states in the Traveling Salesperson Problem with Time Windows (TSPTW).

Ranking class for states in the Traveling Salesperson Problem with Time Windows (TSPTW).

This class implements org.ddolibscala.modeling.StateRanking for TSPTWState and is used to order states within the same layer of a decision diagram. The ranking helps identify which states are better candidates for merging in a relaxed decision diagram.

The comparison is based on the number of nodes in the maybeVisit set: states with more nodes in maybeVisit are considered better candidates for merging and are ranked higher.

Attributes

Supertypes
trait StateRanking[TspTwState]
trait Comparator[TspTwState]
class Object
trait Matchable
class Any
Show all
class TspTwRelax(numVar: Int) extends Relaxation[TspTwState]

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

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

This class implements the org.ddolibscala.modeling.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.

Value parameters

numVar

number of variables/nodes in the associated TSPTW problem

Attributes

Supertypes
trait Relaxation[TspTwState]
class Object
trait Matchable
class Any
case class TspTwState(position: Position, time: Int, mustVisit: BitSet, maybeVisit: BitSet, depth: Int)

Represents a state in the dynamic programming model for the Traveling Salesperson Problem with Time Windows (TSPTW).

Represents a state in the dynamic programming model for the Traveling Salesperson Problem with Time Windows (TSPTW).

Each state encapsulates the current information about the vehicle's position, the set of nodes yet to visit, and timing information. This record is used both for individual states and for relaxed/merged states.

Value parameters

depth

a depth of the layer containing this state in the dynamic programming model

maybeVisit

a set representing nodes that might have been visited or not in merged states

mustVisit

a set representing all nodes that must still be visited

position

the current last position of the vehicle. Usually unique and represented by TspNode. In merged states, the vehicle can be "at any position at the same time," represented by VirtualNodes

time

the arrival time of the vehicle at the current position

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
case class VirtualNodes(nodes: Set[Int]) extends Position

Used for merged states. The vehicle can be at all the position of the merged states.

Used for merged states. The vehicle can be at all the position of the merged states.

Value parameters

nodes

all the position of the merged states.

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait Position
class Object
trait Matchable
class Any
Show all
Generated with