Implement a custom problem

In this tutorial, you will learn how to use this package to solve your own custom constrained shortest path problem.

First of all, make sure you read the Mathematical background. In order to use the generalized_constrained_shortest_path on your custom problem, you need to define a few different types and methods:

  • Types that need to be implemented:
    • Resources types (backward and forward)
    • Expansion functions (backward and forward)
  • Methods that need to be implemented:
    • Base.<= between two forward resources
    • Base.minimum of a vector of backward resources
    • Make forward functions callable on forward resources
    • Make backward function callable on backward resources
    • A callable cost function

You can checkout examples already implemented in the src/examples folder of this package.

Example on the unidimensional resource shortest path

We illustrate this on the same problem a in Shortest path with linear resource constraints but simplified with only one constraint.

using ConstrainedShortestPaths
using Graphs, SparseArrays
import Base: <=, minimum


Forward and backward resources for this example are in the same space:

struct Resource

Base.<= and Base.minimum

function <=(r1::Resource, r2::Resource)
    return r1.c <= r2.c && r1.w <= r2.w

function minimum(R::Vector{Resource})
    return Resource(minimum(r.c for r in R), minimum(r.w for r in R))
minimum (generic function with 14 methods)

Expansion functions

Same as the resources, the forward and backward expansion functions coincide in this example.

struct ExpansionFunction

function (f::ExpansionFunction)(q::Resource)
    return Resource(f.c + q.c, f.w + q.w)

Cost function

struct Cost

function (cost::Cost)(fr::Resource, br::Resource)
    return fr.w + br.w <= cost.W ? fr.c + br.c : Inf

Test on an instance

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)
I = [src(e) for e in edges(graph)]
J = [dst(e) for e in edges(graph)]
d = sparse(I, J, distance_list)

W = 1.0

cost_list = [[0.0], [0.0], [10.0], [0.0], [0]]
w = [0.0 for i in 1:nb_vertices, j in 1:nb_vertices, k in 1:1]
for ((i, j), k) in zip(edge_list, cost_list)
    w[i, j, :] = k

# origin forward resource and backward forward resource set to 0
resource = Resource(0.0, 0.0)

# forward and backward expansion functions are equal
If = [src(e) for e in edges(graph)]
Jf = [dst(e) for e in edges(graph)]
f = [ExpansionFunction(d[i, j], w[i, j]) for (i, j) in zip(If, Jf)]
F = sparse(If, Jf, f);

instance = CSPInstance(graph, resource, resource, Cost(W), F, F)
(; p_star, c_star) = generalized_constrained_shortest_path(instance)
@info "Result" c_star p_star

This page was generated using Literate.jl.