VRP modeler
Get notified of new posts
I created a python package named vrp-model: the first Vehicle Routing Problem (VRP) modeler that offers a unified API to connect with several dedicated VRP solvers. In this post, I explain what it is and how to use it.
What is the Vehicle Routing Problem?¶
According to wikipedia, the VRP is:
(..) a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" The problem first appeared, as the truck dispatching problem, in a paper by George Dantzig and John Ramser in 1959, in which it was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. However, variants of the problem consider, e.g, collection of solid waste and the transport of the elderly and the sick to and from health-care facilities. The standard objective of the VRP is to minimise the total route cost. Other objectives, such as minimising the number of vehicles used or travelled distance are also considered.
The VRP generalises the travelling salesman problem (TSP), which is equivalent to requiring a single route to visit all locations. As the TSP is NP-hard, the VRP is also NP-hard.
VRP has many direct applications in industry. Vendors of VRP routing tools often claim that they can offer cost savings of 5%–30%. Commercial solvers tend to use heuristics due to the size and frequency of real world VRPs they need to solve.
Introduction / motivation¶
In one of the first posts on this blog I talked about data standards and modelling tools. And I gave as example the VRP: the problem itself has been studied long enough to have it's own data standard, well-known instances and a community of researchers and companies working on it. In spite of all that, there's not, to my knowledge at least, a library that handles the modelling and connects to VRP solvers, e.g. à la PuLP with mixed integer programming problems.
This is what vrp-model achieves: a way to model once, and then connect to any VRP solver/ engine.
Show me some code¶
The API looks like this:
from vrp_model import Model
from vrp_model.solvers.pyvrp import PyVRPSolver
model = Model()
depot = model.add_depot(label="hub")
vehicle = model.add_vehicle(10, depot, label="truck1")
job = model.add_job(3)
result = PyVRPSolver({"time_limit": 2.0, "msg": False}).solve(model)
solution = model.solution
assert result.mapped_status.name == "FEASIBLE"
It currently supports the VRP solvers I think have the most functionality: pyvrp, ortools, nextroute, vroom.
Installation¶
Installing the modeler, just like pulp, allows to install solvers as optional dependencies:
pip install vrp-model
pip install "vrp-model[pyvrp]" # one optional extra
pip install "vrp-model[pyvrp,ortools,vroom,nextroute]" # multiple extras
Features¶
One of the best reasons to have a modelling library is not to learn how each individual solver implements each feature. In this case, I have abstracted everything that I think is common enough to be used (mainly, because I've used it in some project).
This is a limited comparison for each solver currently available through the modeler:
| Feature | pyvrp | ortools | nextroute | vroom |
|---|---|---|---|---|
| Capacity (one or more resource dimensions; demands on jobs, caps on vehicles) | ✓ | ✓ | ✓ | ✓ |
| Hard time windows at jobs | ✓ | ✓ | ✓ | ✓ |
| Hard time windows at vehicles (shift / availability) | ✓ | ✓ | ✓ | ✓ |
| Pickup–delivery pairs (precedence and same vehicle) | ✓ | ✓ | ✓ | ✓ |
| Multi-depot (vehicles may start/end at different depots) | ✓ | ✓ | ✓ | ✓ |
| Heterogeneous fleet (distinct vehicle definitions) | ✓ | ✓ | ✓ | ✓ |
| Service time at jobs (added into time accounting) | ✓ | ✓ | ✓ | ✓ |
| Vehicle fixed use cost (activation / fixed cost per route) | ✓ | ✓ | ✓ | ✓ |
| Maximum route distance per vehicle | ✓ | ✓ | ✓ | ✓ |
| Maximum route duration / shift length per vehicle | ✓ | ✓ | ✓ | ✓ |
Optional jobs / prize-collecting (mandatory vs skip penalty via prize) |
✓ | ✓ | ✗ | ✗ |
| Job groups (mutually exclusive job alternatives) | ✓ | ✓ | ✗ | ✗ |
Flexible time windows (linear soft penalties via TimeWindowFlex) |
✗ | ✓ | ✗ | ✗ |
| Route overtime (extra duration allowed + unit penalty on overage) | ✓ | ✓ | ✗ | ✗ |
| Skills (jobs require a subset of vehicle skills) | ✗ | ✓ | ✓ | ✓ |
Maximum wait / time slack at nodes (max_slack_time on vehicles) |
✗ | ✓ | ✗ | ✗ |
This of course means that the library will not cover everything a solver offers. In particular, ortools has the possibility to add arbitrarily CP constraints which will always be more flexible. Having said that, it should be possible (now or at some point) to access the solver internals to implement whatever additional logic is needed. This is the approach we follow in PuLP. That way, you always start with a PuLP model and only access the solver for additional options if it's necessary or when a limited benchmark has been done.
And how do we deal with different levels of features?
Feature compatibility¶
The most common VRP solvers are standard but not 100% standard. And the idea of this library is to also bring solvers that may be good at what they do, even if they have limited features.
The library detects, given a problem instance, what functionality the user is requesting. And then it matches those with what the chosen solver allows. If the solver (or the API call to it) does not handle the features, then we raise an error before trying to call the solver.
This can also bring information to the solver providers about which features are available in other solvers, with the aim of standardizing the problem structure even further.
Validation¶
Something I think it's critical is to be able to check an instance before solving: for inconsistencies in data that will lead to an error or an infeasible problem. Also after solving by the way: calculate the cost of a given plan, check for feasibility, etc.
So far there are some methods already implemented that do just that. The better and more precise the checks are, the better the user experience will become.
Input / Output¶
The modeller itself has some basic internal data structure. And it connects to vrplib to import/ export vrp instances in the VRPLIB format.
In the future, I guess we could implement some json-like format to import instances in a more web-friendly way.
Testing and use¶
I want to start using this library for the next VRP problem I may have to solve soon. And that is the reason why I wanted to support a reasonable number of features and solvers as a first version. I'm sure many more improvements, changes and fixes will happen once I get to use it.
My hope is that this library will make benchmarking between VRP solvers easier, at least for relatively standard routing problems.
Next steps¶
I have many solvers I have yet to add, for example some exact solvers with limited features such as vrpsolvereasy, vrpy that I would like to test.
On top of that, I would like to include implementations of generic solvers/ modellers such as Hexaly, MIP (gurobi et al) via PuLP, CP via cpmpy, timefold, solverforge, etc.
I currently leave these integrations as motivation for the reader / user / developer.