ConstrainedShortestPaths.jl

Documentation for ConstrainedShortestPaths.

This package implements algorithms for solving Generalized Constrained Shortest Paths problems. It implements a simplified version of the framework from Parmentier 2017, restricted to acyclic directed graphs.

If you have any question/suggestion, feel free to create an issue or contact me.

Overview

This package supports the following setting:

• Let $D=(V, A)$ an acyclic directed graph.
• Let $o, d\in V$ origin and destination vertices.
• Let $\mathcal{P} \subset \mathcal{P}_{od}$ a subset of $o-d$ paths in $D$.
• Let $c$ a cost function you want to minimize on $\mathcal{P}$.

The generalized_constrained_shortest_path algorithm is able to solve the following shortest path problem:

\[\begin{aligned} \arg\min\quad & c(P)\\ \text{s.t.}\quad & P\in \mathcal{P} \end{aligned}\]

Installation

To install this package, open a julia REPL and run the following command in pkg mode:

add ConstrainedShortestPaths

Basic usage

Currently, this package implements three applications examples ready to use:

• The Usual shortest path problem (basic_shortest_path).
• The Shortest path with linear resource constraints resource constraints (resource_shortest_path).
• The Stochastic Vehicle Scheduling subproblem for the column generation formulation (stochastic_routing_shortest_path).

Advanced usage

If your shortest path problem is not one of those listed in the Basic usage section, it is still possible to solve it with this package. To do this, first read the Mathematical background section, then follow the Implement a custom problem tutorial.