Uploaded image for project: 'transportpce'
  1. transportpce
  2. TRNSPRTPCE-147

k shortest paths with include constraint

    XMLWordPrintable

Details

    • Improvement
    • Status: Verified
    • Low
    • Resolution: Done
    • None
    • None
    • None
    • None

    Description

      In the runKgraphs() method in PceGraph.java there is the following code:

      // local optimization. if 'include' constraint exists then increase amount of paths to return.
      // it's because this constraint is checked at the last step when part of good paths
      // are dropped by other constraints
      if (!pceHardConstraints.getListToInclude().isEmpty()) {
          kpathsToBring = kpathsToBring * 10;
          LOG.info("k = {}",kpathsToBring);
      }
      

      So the number of paths to be returned by the k shortest paths algorithm is increased by a factor 10 when there are include constraints. It is not clear to me why this is needed. From the jgrapht documentation it seems to me that the KShortestSimplePaths.getPaths method returns k paths fulfilling the constraints if such paths exist (i.e. it's not that it first calculates k paths and then removes some of them that doesn't fulfill the constraints) so why increase k in this case? Have I misunderstood the implementation?

      Attachments

        No reviews matched the request. Check your Options in the drop-down menu of this sections header.

        Activity

          People

            atriki Ahmed Triki
            ojnas Jonas MÃ¥rtensson
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved:

              Time Tracking

                Estimated:
                Original Estimate - Not Specified
                Not Specified
                Remaining:
                Remaining Estimate - 0 minutes
                0m
                Logged:
                Time Spent - 4 days
                4d