Package backend.TSP

Class TemplateTSP

java.lang.Object
backend.TSP.TemplateTSP
All Implemented Interfaces:
TSP
Direct Known Subclasses:
TSP2
public abstract class TemplateTSP extends Object implements TSP
Template for solving a TSP instance using branch-and-bound.

This abstract class implements the generic search flow and leaves two strategy points to subclasses: bound(Long, Collection) and iterator(Long, Collection, Graph). The methods and fields use a Graph instance supplied to #chercheSolution(int, Graph).

Notes on behavior: - All public methods operate on the Graph instance stored in g. - The search respects a time limit (milliseconds) passed to #chercheSolution(int, Graph). When the limit is exceeded the search returns early.

  • Field Details

  • Constructor Details

    • TemplateTSP

      public TemplateTSP(int timeLimit, Graph g)

  • Method Details

    • chercheSolution

      public void chercheSolution()
      Start the branch-and-bound search to find a TSP solution.
      Specified by:
      chercheSolution in interface TSP
      Parameters:
      timeLimit - time limit in milliseconds; if <= 0 the method returns immediately without searching
      g - the Graph to solve; stored in this instance Side effects: populates solutionOrder and coutMeilleureSolution when a solution is found. The method returns early if the time limit elapses.

    • getSolutionOrder

      public LinkedList<Long> getSolutionOrder()
      Return the full solution found by the last search as an ordered list of node ids
      Specified by:
      getSolutionOrder in interface TSP
      Returns:
      the solution ordered as a LinkedList of node ids

    • getSolutionOrderWithArrivalTime

      public LinkedList<Pair<Long,LocalTime>> getSolutionOrderWithArrivalTime()
      Return the full solution found by the last search as an ordered set of node ids.
      Specified by:
      getSolutionOrderWithArrivalTime in interface TSP
      Returns:
      the solution ordered as a LinkedHashSet of node ids with their time of arrival

    • getSolutionPath

      public LinkedHashSet<Map<Pair<Long,Long>,LinkedList<Long>>> getSolutionPath()
      Return the full solution found by the last search as an ordered set of maps of paths between points of interest.
      Specified by:
      getSolutionPath in interface TSP
      Returns:
      the solution ordered as a LinkedHashSet of maps of paths (from node to node)

    • getCoutSolution

      public double getCoutSolution()
      Return the cost of the best solution found by the last search.
      Specified by:
      getCoutSolution in interface TSP
      Returns:
      the cost as a double, or -1 when no graph is set

    • validateIncompleteOrder

      public boolean validateIncompleteOrder(List<Long> order)
      Validate the solution order
      Parameters:
      List - order
      Returns:
      true if the solution is valid, false otherwise

    • bound

      protected abstract double bound(Long sommetCourant, Collection<Long> nonVus)
      Compute a lower bound for the cost of completing the tour.
      Parameters:
      sommetCourant - current node id
      nonVus - collection of not-yet-visited node ids
      Returns:
      a lower bound (minimum possible additional cost) for paths in the current graph that start at sommetCourant, visit all nonVus exactly once and return to the start

    • iterator

      protected abstract Iterator<Long> iterator(Long sommetCrt, Collection<Long> nonVus, Graph g)
      Provide an iterator over candidate successors of sommetCrt.
      Parameters:
      sommetCrt - current node id
      nonVus - collection of nodes not yet visited
      g - the Graph instance (same as this.g)
      Returns:
      an Iterator over node ids from nonVus that are valid successors of sommetCrt. Implementations should return an empty iterator rather than null when there are no candidates.