# Is there existing code for the set partitioning formulation of routing problems?

The set partitioning formulation of routing problems is pretty well-accepted as perhaps the best exact method to solve routing problems. However, these methods are difficult to implement as many people know. I'm wondering is there some Python code out there that can solve these exact methods? Ideally it would be some code that could solve resource-constrained shortest path problems here. I would imagine that would be the most difficult part.

I did find this, however it doesn't seem to solve these routing problems exactly - it just uses some heuristic.

Any links to existing code/repositories would be appreciated, or any other ideas.

Python is not an efficient language, and solving the resource constrained shortest path is the bottleneck of the branch-and-cut-and-price algorithms for routing problems. Therefore, you won't find a state-of-the-art implementation where the resource constrained shortest path is solved in Python.

The state-of-the-art branch-and-cut-and-price for routing problems is VRPSolver. The code is available and written in C++.

• cspy solves the resource constrained shortest path. The core is implemented in C++, but as a python library it calls a precompiled version of the C++ code. Therefore the bottleneck is partially reduced. Note that cspy is the library that is used in vrpy, one of the links in OP's post. Commented Nov 12, 2023 at 9:50
• @Kuifje The question explicitly asks for a Python code that solves the resource constrained shortest path problem. Indeed, if the high level code is in Python but the code that solves the resource constrained shortest path problem is in C++, it's possible to get a branch-and-cut-and-price with better performances Commented Nov 12, 2023 at 10:20
• I agree with you ; I assume that the user wants python code to call and does not really care what is really happening behind the curtains (but happy to be wrong on this one). Assuming this holds, note that VRPSolver also has API's in python (and julia). Commented Nov 12, 2023 at 14:42

There is a Python interface for the VRPSolver that can be installed using the following code:

python -m pip install VRPSolverEasy


All the information is given in the Github page: https://github.com/inria-UFF/VRPSolverEasy