(Elementary) shortest path problem with resource constraints

[ruthmair]

Why this Mod?

• Shortest path problem from given source node to target node minimizing total arc and/or node costs, subject to knapsack constraints for the whole path on further resources like distance/time/load on arcs and/or nodes.
• Costs are allowed to be negative potentially leading to loops along the path (even infinite loops if resource constraints are not restricting). If asking for "elementary" paths, loops are forbidden.
• Classical NP-hard combinatorial problem, often arising as subproblem of more complicated problems, e.g., in the pricing problem of route-based formulations for vehicle routing problems.
• State-of-the-art algorithms are labeling algorithms similar to dynamic programming that can be difficult to implement correctly and efficiently. For inefficient implementations, MILP might have comparable performance.

What will the API be?

• Graph-based input seems more appropriate instead of multiple matrices/arrays that may be inconsistent. Pandas dataframes are a good option.
• Resource "cost" is mandatory and serves as resource to minimize. All further resources with arbitrary names are optional for nodes and arcs.
• Node and arc values with the same resource name are accumulated along the path.

node_data = pd.DataFrame([
    {"node": 0, "cost": -3, "time": 4, "distance": 3},
    {"node": 1, "cost": 5, "time": 3, "distance": 7},
    {"node": 2, "cost": 6, "time": 1, "distance": 2},
    {"node": 3, "cost": -4, "time": 5, "distance": 3}
])

arc_data = pd.DataFrame([
    {"source": 0, "target": 1, "cost": 16, "distance": 1},
    {"source": 0, "target": 2, "cost": -13, "distance": 3},
    {"source": 1, "target": 2, "cost": 10, "distance": 2},
    {"source": 2, "target": 1, "cost": -4, "distance": 6},
    {"source": 1, "target": 3, "cost": 12, "distance": 3},
    {"source": 3, "target": 2, "cost": -9, "distance": 2}
])

limits = {
  "time": 10,
  "distance": 18
}

path, objective = solve_espprc(node_data=node_data, arc_data=arc_data, source=0, target=3, limits=limits, elementary=True)

Additional context

[simonbowly]

@torressa @ruthmair could we extend the existing shortest path mod with this version to avoid too much duplication? A simple shortest path problem would still be solvable by imposing no limits.

[torressa]

Indeed a simple shortest path can be used but only for some bounds. This problem has the following additional constraints (as well as others to enforce elementary paths):
$$\sum_{ij} a^r_{ij} x_{ij} \leq A^r,~~\forall r$$
Where $r$ is a resource (in Mario's example: limits.keys()). So this would need a change to the underlying min-cost flow formulation (the one in src/gurobi_optimods/network_util.py)

[simonbowly]

Yep, I mean we could do away with the min-cost-flow based implementation and only implement the more complex resource-constrained model. If re-using the network_util stuff over-complicates things, we can just have some duplication.

[ruthmair]

Ok, then I will take it from here.

[simonbowly]

@ruthmair @torressa FYI I removed the current shortest path implementation & docs from the main repo, and re-instated it on the branch simonbowly/rcsp, so you can use it as a starting point for docs and tests of a resource-constrained version.

[ruthmair]

I guess the public/private issue also made the rcsp fork unusable? This is no issue at all, I can just start with a new fork.

[simonbowly]

Yeah, new fork required I'm afraid, sorry about that.

[torressa]

@ruthmair Are you still working on this? Simon has given us the OK on writing a VRP mod! 😈

[ruthmair]

I still need to start working on this, but it is on my list.
Would you do a VRP mod based on column generation?

[torressa]

Yeah, why not? Would you say the formulation is better? We could have mod based on the formulation(s), or even better formulation(s) + heuristic to insert solutions via callback