Skip to content

Concepts

Model

Using the Flowty Optimisation Solver you can solve models like

minkKckxk+(V,E)G(vVcvxv+eEcexe)+iNciyis.t. kKαjkxk+(V,E)G(vVαjvxv+eEαjexe)+iNαjiyi=bjjMxv,xe0(V,E)G,vV,eE0LkxkUkkKyi[R,Z,B]iN \begin{aligned} \min{ } & \sum_{k \in K} c_k x_k + \sum_{(V,E) \in G} \Big ( \sum_{v \in V} c_v x_v + \sum_{e \in E} c_e x_e \Big ) + \sum_{i \in N} c_i y_i \\ \text{s.t. } & \sum_{k \in K} \alpha_{jk} x_k + \sum_{(V,E) \in G} \Big (\sum_{v \in V} \alpha_{jv} x_v + \sum_{e \in E} \alpha_{je} x_e \Big ) + \sum_{i \in N} \alpha_{ji} y_i = b_j & & j \in M \\ & x_v, x_e \geq 0 && (V,E) \in G, v \in V, e \in E\\ & 0 \leq L^k \leq x_k \leq U^k && k \in K \\ & y_i \in [\mathbb{R}, \mathbb{Z}, \mathbb{B}] && i \in N \end{aligned}

where \(N\) is the set of general (master) variables, \(M\) is the set of constraints, \((g, s, t) \in K\) is the set of subproblems with graph \((V,E)=g \in G\), vertices \(V\), edges \(E\), resource constraints \(R_g\), and \(s,t \in V\) is the source and target for the feasible paths for the subproblem. Paths usage may be fractional, integral or binary.

Solve regular mixed integer programming models

Do not add subproblems and only use \(y\) variables.

Solve a resource constrained shortest path problem

Add exactly one subproblem and no \(y\) variables or constraints. Set lower and upper bounds to 1 and let the domain be binary.

Graphs

Graphs describe the connectivity of vertices using edges. All graphs are directed, have a source and a target vertex, and are weighted with costs.

Identical source and target is not supported.

Split node in two.

Multi-graphs and self-loops are not supported.

Insert node in middle of multi-edge and remove self-loops.

Resources

Each path is constrained in the network. This is handled in the dynamic programming algorithm by accumulating resources that are used for verifying bounds while traversing the graph.

In the dynamic programming algorithm labels represent states and a resource is an element in the state. The cost component of a label can be considered as an unbounded resource and hence results in a state element.

First Resource

The first resources defines the order in which the labels are handled. There must not exist a cycle in the graph with zero consumption for that resource.

Resource Update Functions (RUF)

Resource update function \(f_r\) defines how resource \(r \in R\) is updated from state \(S_i\) when traversing edge \((i,j) \in E\). Apply all RUFs to obtain new state \(S_j = \{ f_r(S_i) : r \in R \}\). A common RUF for an isolated resource \(r \in R\) is to add traveltime \(q_{ij}^r\) and wait for a window to open \(s_j^r = \max \{ l_v^r, s_i^r + q_{ij}^r \}\). Several commonly used RUFs are provided with Flowty.

Feasibility

State \(S\) is feasible if it satisfies all rules. A common rule is for an isolated resource \(r \in R\) to be within a window \([l_v^r, u_v^r]\) at vertex \(v \in V\), i.e., \(l_v^r \leq s^r \leq u_v^r\). Several commonly used rules are provided with Flowty.

Subproblems

Graph, source, target, lower bound, upper bound (on usage)