cspy DocumentationΒΆ

cspy is an open source Python package that gathers some algorithms to solve the (resource) Constrained Shortest Path (CSP) problem. The CSP problem has been studied in the mathematical optimisation literature as allows the modelling of a wide range of problems. They have proven useful in a wide variety of problems including: the vehicle routing problem with time windows, the technician routing and scheduling problem, the capacitated arc-routing problem, on-demand transportation systems, aircraft scheduling, and, airport ground movement.

By setting different options when calling the algorithms, one can have up to five different algorithms (exact and metaheuristic).

  • Monodirectional forward labeling algorithm (exact);

  • Monodirectional backward labeling algorithm (exact);

  • Bidirectional labeling algorithm with static halfway point (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).

Features implemented include: generic resource extension functions (Inrich 2005) (not restricted to additive resources), generic resource consumptions (not restricted to non-negative values), and, increased efficiency (when compared to other implementations of monodirectional algorithms).

cspy is installable via pip (see Getting Started) or the source code is made available here.