A collection of algorithms for the (resource) Constrained Shortest Path (CSP) problem.
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:
- Monodirectional forward labeling algorithm (exact);
- Monodirectional backward labeling algorithm (exact);
- Bidirectional labeling algorithm with dynamic halfway point (exact) Tilk et al. (2017);
- Heuristic Tabu search (metaheuristic);
- Greedy elimination procedure (metaheuristic);
- Greedy Randomised Adaptive Search Procedure (GRASP) (metaheuristic). Adapted from Ferone et al. (2019);
- Particle Swarm Optimization with combined Local and Global Expanding Neighborhood Topology (PSOLGENT) (metaheuristic) Marinakis et al. (2017).
Please see the individual algorithms API Documentation for some toy examples and more details:
- Bidirectional and monodirectional algorithms
- Heuristic Tabu Search
- Greedy Elimination Procedure
- GRASP
- PSOLGENT
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
The generic gist to run the algorithms on a specific graph is to load the
algorithm of choice, say alg
, call the alg.run()
method, and query the
relevant result attributes,
alg.path
for a list with the nodes in the path;alg.total_cost
for the accumulated cost of the path;alg.consumed_resources
for the accumulated resource usage of the path.
I have included a few examples:
jpath
: Simple example showing the necessary graph adptations and the use of custom resource extension functions.cgar
: Complex example use ofcspy
in a column generation example applied to the aircraft recovery problem.vrpy
: (under development) external vehicle routing framework which usescspy
to solve different variants of the vehicle routing problem using column generation.
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
Then, go into the folder and run the tests using unittest
cd ~/path/newfolder
python3 -m unittest
Please make sure that the python package cspy is not already installed in your machine.
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 necessary, please perform documentation updates where appropriate (e.g. README.md, docs and CHANGELOG.md).
- Increase the version numbers and reference the changes appropriately. Note that the versioning scheme used is based on Semantic Versioning.
- Wait for approval for merging.
If you have a question or need help, feel free to raise an issue explaining it.
Alternatively, email me at [email protected]
.
If you'd like to cite this package, please use the following bib format:
@Misc{cspy,
author = {Torres Sanchez, David},
title = {{cspy : A Python package with a collection of algorithms for the (Resource) Constrained Shortest Path problem}},
year = {2019},
url = {\url{https://github.com/torressa/cspy}}
}