[TRNSPRTPCE-147] k shortest paths with include constraint Created: 10/Sep/19  Updated: 13/Mar/20  Resolved: 06/Feb/20

Status: Verified
Project: transportpce
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Improvement Priority: Low
Reporter: Jonas MÃ¥rtensson Assignee: Ahmed Triki
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: 0 minutes
Time Spent: 4 days
Original Estimate: Not Specified


 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?


Generated at Wed Feb 07 20:42:22 UTC 2024 using Jira 8.20.10#820010-sha1:ace47f9899e9ee25d7157d59aa17ab06aee30d3d.