Metadata-Version: 2.4
Name: routepricer
Version: 1.0.0
Summary: Python interface to PathWyse: a C++ library for Resource Constrained Shortest Path Problems (RCSPP)
Author: PathWyse developers
Maintainer-email: Sharabh Shukla <sharabh2019@gmail.com>
License-Expression: GPL-3.0-or-later
Project-URL: Repository, https://github.com/sharabhshukla/route-pricer
Project-URL: Upstream, https://github.com/pathwyse/pathwyse
Keywords: rcspp,shortest-path,column-generation,pricing,routing,optimization,operations-research
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: C++
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Intended Audience :: Science/Research
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

<div align="center">

<h1>RoutePricer</h1>

[![PyPI](https://img.shields.io/pypi/v/routepricer?color=4584b6)](https://pypi.org/project/routepricer/)
![Python](https://img.shields.io/badge/Python-3.10%2B-4584b6?logo=python&logoColor=white)
![C++](https://img.shields.io/badge/C%2B%2B-20%2B-4584b6?logo=c%2B%2B&logoColor=white)
![License](https://img.shields.io/badge/License-GPLv3-4584b6?logo=&logoColor=white)

**A Python package to model and solve Resource Constrained Shortest Path Problems (RCSPP).**

</div>

---

## Acknowledgment

RoutePricer is built on [PathWyse](https://github.com/pathwyse/pathwyse), an open-source C++ library for the RCSPP developed by Salani, Basso, and Giuffrida. All solver algorithms and the C++ core are the work of the PathWyse authors; RoutePricer packages that engine, together with its Python interface, as an easy-to-install PyPI distribution. The upstream library is described in the paper: https://doi.org/10.1080/10556788.2023.2296978

---

RoutePricer brings a state-of-the-art exact RCSPP solver to Python with a single `pip install`. It is particularly suited for problems arising as pricing subproblems in column generation, as well as routing and scheduling applications with multiple constraints — vehicle routing, crew rostering, and path-based scheduling among them.

The compiled C++ core is embedded directly in the wheel, so there is nothing to build or link: install the package and start solving.

---

## Installation

```
pip install routepricer
```

Prebuilt wheels are provided for Linux, macOS, and Windows (CPython 3.10–3.14). On other platforms, pip falls back to the source distribution, which requires a C++20 compiler.

---

## A quick look

```python
from routepricer import PWSolver

pw = PWSolver()
pw.readProblem("instances/toy.txt")
pw.setupAlgorithms()
pw.solve()
pw.printBestSolution()
```

Example output:

```
[ Solution ]
  Solution Status                 : Optimal
  Obj                             : -10435
  Tour Length                     : 4
  Tour                            : 0 2 1 4 
  Consumption                     : 9 
```

Problems can also be built programmatically — define the graph topology, arc costs, and resource consumptions directly from Python instead of reading an instance file. See `examples/python_application/pathwyse_instance_creation.py`.

---

## Supported problems

RoutePricer focuses on resource constrained shortest path problems with one or more monotone resources. It supports acyclic networks and includes specialized techniques for elementary variants on cyclic networks through relaxation schemes.

The current version includes support for common resources such as capacity, time, node limits, and time windows. These can be combined to model a variety of problems, including routing and scheduling with cumulative constraints, and pricing subproblems in column generation.

The underlying framework is extensible: new types of resources can be implemented in C++ by extending the Resource class, making it possible to model custom constraints for a wide range of practical and research problems.

---

## Main techniques

The solver includes the following techniques and features:

- **Bi-directional search:** Dynamic programming labeling algorithms are implemented in both mono-directional and bi-directional [Righini and Salani, 2006] fashion;
- **Relaxation schemes:** Decremental State Space Relaxation (DSSR) [Righini and Salani, 2008], NG-path relaxations (NG) [Baldacci et al., 2011] and hybridizations [Martinelli et al., 2014] are included to tackle the Elementary RCSPP;
- **Dynamic half-way point:** The budget of the critical resource is automatically adjusted in bidirectional algorithms, similarly to [Sadykov et al., 2020];
- **Candidate and join strategies:** multiple methods for selecting candidates and performing join operations in labeling algorithms;
- **A\*-based algorithm:** a custom implementation of the A* algorithm proposed by [Ahmadi et al. 2021] is provided for single resource acyclic problems.

The solver also supports simple heuristics, bucket-based label organization (PWBucket), and features data collection tools.

---

## Instances and configuration

A toy instance is provided under `instances/toy.txt` to verify the installation. Additional benchmark instances from the literature are available under `instances/`:

- `instances/spprclib/` — SPPRCLIB [Jepsen et al., 2008]
- `instances/dimacs/` — DIMACS 9th Challenge
- `instances/longestpath/` — LongestPath [Salani et al., 2024]

The instance format is described in: [Instance Format](https://pathwyse.github.io/pathwyse/documentation/INSTANCE/)

A `pathwyse.set` file in the working directory can be used to control the main configuration parameters. A complete description of the available options is provided in: [Parameters](https://pathwyse.github.io/pathwyse/documentation/PARAMETERS_TABLE/)

---

## Building from source

The repository also contains the full C++ library and a standalone command-line solver, which can be compiled with CMake by following the upstream instructions: [Installation](https://pathwyse.github.io/pathwyse/documentation/INSTALL/)

Once compiled, instances can be solved from the command line:

```
./bin/pathwyse path-to-instance
```

To build the Python package itself from a checkout:

```
pip install .
```

---

## Documentation

The Python API surface (`PWSolver`) mirrors the upstream Solver class, which provides the main interface for interacting with the library programmatically. Full documentation, including API references and tutorials, is available in the upstream docs: https://pathwyse.github.io/pathwyse/

---

## License

RoutePricer is released under the GNU General Public License v3.0, the same license as the open-source version of PathWyse.

Upstream PathWyse is distributed under a dual licensing scheme: an Enterprise version with additional features and extended support is available from the PathWyse authors for academic collaborations and under a commercial license for non-open source projects. For further information, contact: pathwyse@supsi.ch

---

## How to cite

If you use RoutePricer in your research, please cite the upstream PathWyse paper:

Salani, M., Basso, S., & Giuffrida, V. (2024).  
PathWyse: a flexible, open-source library for the resource constrained shortest path problem.  
Optimization Methods and Software. https://doi.org/10.1080/10556788.2023.2296978
