A collection of algorithms for the (Resource) Constrained Shortest Path problem in Python / C++ / C#
OS | C++ | Python | Dotnet |
---|---|---|---|
Unix (linux + macos) | |||
Windows |
A collection of algorithms for the (resource) Constrained Shortest Path (CSP) problem.
Documentation here.
The CSP problem was popularised by Inrich and Desaulniers (2005). It was initially introduced as a subproblem for the bus driver scheduling problem, and has since then widely studied in a variety of different settings including: the vehicle routing problem with time windows (VRPTW), the technician routing and scheduling problem, the capacitated arc-routing problem, on-demand transportation systems, and, airport ground movement; among others.
More generally, in the applied column generation framework, particularly in the scheduling related literature, the CSP problem is commonly employed to generate columns.
Therefore, this library is of interest to the operational research community, students and academics alike, that wish to solve an instance of the CSP problem.
Currently, the exact and metaheuristic algorithms implemented include:
Please see the docs for individual algorithms Python or C++ API documentation, as well as some toy examples and further details.
Conceptual background and input formatting is discussed in the docs.
Module dependencies are:
Note that requirements.txt contains modules for development purposes.
Installing the cspy
package with pip
should also install all the required packages. You can do this by running the following command in your terminal
pip install cspy
or
python3 -m pip install cspy
# Imports
from cspy import BiDirectional
from networkx import DiGraph
from numpy import array
max_res, min_res = [4, 20], [1, 0]
# Create a DiGraph
G = DiGraph(directed=True, n_res=2)
G.add_edge("Source", "A", res_cost=[1, 2], weight=0)
G.add_edge("A", "B", res_cost=[1, 0.3], weight=0)
G.add_edge("A", "C", res_cost=[1, 0.1], weight=0)
G.add_edge("B", "C", res_cost=[1, 3], weight=-10)
G.add_edge("B", "Sink", res_cost=[1, 2], weight=10)
G.add_edge("C", "Sink", res_cost=[1, 10], weight=0)
# init algorithm
bidirec = BiDirectional(G, max_res, min_res)
# Call and query attributes
bidirec.run()
print(bidirec.path)
print(bidirec.total_cost)
print(bidirec.consumed_resources)
For more details see the Python API
#include "bidirectional.h"
namespace bidirectional {
void wrap() {
// Init
const std::vector<double> max_res = {4.0, 20.0};
const std::vector<double> min_res = {1.0, 0.0};
const int number_vertices = 5;
const int number_edges = 5;
auto bidirectional = std::make_unique<BiDirectional>(
number_vertices, number_edges, 0, 4, max_res, min_res);
// Populate graph
bidirectional->addNodes({0, 1, 2, 3, 4});
bidirectional->addEdge(0, 1, 0.0, {1, 2});
bidirectional->addEdge(1, 2, 0.0, {1, 0.3});
bidirectional->addEdge(2, 3, -10.0, {1, 3});
bidirectional->addEdge(2, 4, 10.0, {1, 2});
bidirectional->addEdge(3, 4, 0.0, {1, 10});
// Run and query attributes
bidirectional->run();
auto path = bidirectional->getPath();
auto res = bidirectional->getConsumedResources();
auto cost = bidirectional->getTotalCost();
}
} // namespace bidirectional
DoubleVector max_res = new DoubleVector(new List<double>() {4.0, 20.0});
DoubleVector min_res = new DoubleVector(new List<double>() {0.0, 0.0});
int number_vertices = 5;
int number_edges = 5;
BiDirectionalCpp alg = new BiDirectionalCpp(number_vertices, number_edges, 0, 4, max_res, min_res);
// Populate graph
alg.addNodes(new IntVector(new List<int>() {0, 1, 2, 3, 4}));
alg.addEdge(0, 1, -1.0, new DoubleVector(new List<double>() {1, 2}));
alg.addEdge(1, 2, -1.0, new DoubleVector(new List<double>() {1, 0.3}));
alg.addEdge(2, 3, -10.0, new DoubleVector(new List<double>() {1, 3}));
alg.addEdge(2, 4, 10.0, new DoubleVector(new List<double>() {1, 2}));
alg.addEdge(3, 4, -1.0, new DoubleVector(new List<double>() {1, 10}));
alg.setDirection("forward");
// Run and query attributes
alg.run();
IntVector path = alg.getPath();
DoubleVector res = alg.getConsumedResources();
double cost = alg.getTotalCost();
vrpy
: External vehicle routing framework which uses cspy
to solve different variants of the vehicle routing problem using column generation. Particulatly, see subproblem_cspy.py
.jpath
: Simple example showing the necessary graph adptations and the use of custom resource extension functions.Using docker, docker-compose is the easiest way.
To run the tests first, clone the repository into a path in your machine ~/path/newfolder
by running
git clone https://github.com/torressa/cspy.git ~/path/newfolder
cd ~/path/newfolder/tools/dev
./build
cd ~/path/newfolder/tools/dev
./build -c -p
Requirements:
Then use the wrapper Makefile
e.g. make
in the root dir runs the unit tests
This project is licensed under the MIT License - see the LICENSE.txt file for details.
If you find a bug or there are some improvements you'd like to see (e.g. more algorithms), please raise a new issue with a clear explanation.
When contributing to this repository, please first discuss the change you wish to make via an issue or email. After that feel free to send a pull request.
If you have a question or need help, feel free to raise an issue explaining it.
Alternatively, email me at torressa at tutanota.com
.
If you'd like to cite this package, please use the following bib format:
@article{torressa2020,
doi = {10.21105/joss.01655},
url = {https://doi.org/10.21105/joss.01655},
year = {2020},
publisher = {The Open Journal},
volume = {5},
number = {49},
pages = {1655},
author = {{Torres Sanchez}, David},
title = {cspy: A Python package with a collection of algorithms for the
(Resource) Constrained Shortest Path problem},
journal = {Journal of Open Source Software}
}