Shortest path with linear resource constraints
In this tutorial we want to solve the following resource constrained shortest path:
\[\begin{aligned} \min_{p\in \mathcal{P_{od}}} & \sum_{a\in p} c_a & \\ s.t. & \sum_{a\in p} w_a^k \leq W^k, & \forall k \in [K] \end{aligned}\]
using ConstrainedShortestPaths
using Graphs, SparseArrays
using GLMakie, GraphMakie
Let's create a simple graph:
nb_vertices = 4
graph = SimpleDiGraph(nb_vertices)
edge_list = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]
distance_list = [1, 2, -1, 1, 1]
for (i, j) in edge_list
add_edge!(graph, i, j)
end
I = [src(e) for e in edges(graph)]
J = [dst(e) for e in edges(graph)]
d = sparse(I, J, distance_list)
3×4 SparseArrays.SparseMatrixCSC{Int64, Int64} with 5 stored entries:
⋅ 1 2 ⋅
⋅ ⋅ -1 1
⋅ ⋅ ⋅ 1
We now add resource costs $w_a$ on edges, and a resource constraint of the form: $\sum\limits_{a\in P} w_a \leq W$
W = [1.0]
cost_list = [[0], [0], [10], [0], [0]]
w = [0.0 for i in 1:nb_vertices, j in 1:nb_vertices, k in 1:1]
for ((i, j), c) in zip(edge_list, cost_list)
w[i, j, :] = c
end
graphplot( graph; nodecolor=:red, nlabels=["i" for i in 1:nbvertices], elabels=["d=$(d[e.src, e.dst]), w=$(w[e.src, e.dst, :])" for e in edges(graph)], )
With these costs, the optimal path should be [1, 2, 4], with length 2.
p_star, c_star = resource_shortest_path(graph, 1, nb_vertices, W, d, w)
@info "Solution found" p_star c_star
┌ Info: Solution found
│ p_star =
│ 3-element Vector{Int64}:
│ 1
│ 2
│ 4
└ c_star = 2.0
This page was generated using Literate.jl.