Supporting new VRP variants¶

On this page we describe some guidelines and ‘gotchas’ to think about while adding support for new VRP variants to PyVRP. These are given as hints. To make these guidelines concrete, we take examples from our experience adding support for prize-collecting VRPs, which was added to PyVRP in version 0.3.0. For reference, the pull request implementing prize-collecting is available here.

Adding support for new VRP variants starts with thinking about where to add the new problem data needed to solve it. In the case of prize-collecting, this meant adding the prize: int and required: bool fields to the Client object:

• The prize field indicates the prize obtained for visiting the client;

• The required field indicates whether the client must be part of a feasible solution, regardless of the prize.

Adding such data requires modifying the Client class, which is written in C++. After changing C++ functionality, don’t forget to update the Python bindings and type stub files with the new changes!

When adding new data fields, it is particularly important to think about sane default values. For example, the standard CVRP and VRPTW do not consider prizes, and all clients must be visited in those problem settings. It thus makes sense to make prize-collecting an opt-in feature, with defaults prize = 0 and required = True.

With the required problem data now available, the next step is to think about what needs to change in terms of the objective, and how to support its evaluation. This is not always required: for example, if your VRP variant only introduces additional constraints, you can typically skip this step. In the case of prize-collecting, however, the prizes must be added to the objective.

This requires modifying the Solution’s and CostEvaluator’s implementation of the cost components. In particular, we updated the Solution to also compute the total value of all uncollected prizes, and changed cost() to compute

where \(x_{ij} \in \{0, 1\}\) indicates if arc \((i, j)\) is used, and \(y_i \in \{0, 1\}\) indicates if client \(i\) is visited.

The next step is to modify the search methods in pyvrp.search to respect the constraints of the new VRP variant. Depending on the VRP variant in question, this might be simple, or it could be a lot of work: if you are unsure whether your VRP variant will be a lot of work to support, please consider opening an issue for discussion first.

In the pyvrp.search module, either changes need to be made to the operators, or the LocalSearch object. In the case of prize-collecting, it was the latter: we added support for evaluating (and applying) moves that inserted a client into the solution, or removed a client from it. The required evaluation logic was easy to write by looking at the implementation of Exchange10.

With those changes in place, a basic implementation supporting the new VRP variant is typically already functional. This is more than sufficient for an initial patch, so please open a pull request around this time. To get that pull request merged, two more things are required:

• Tests exercising the new or modified code. These tests should check edge cases that are not supported (are errors raised when they should?), and ensure the basic functionality is correct.

• Benchmark results, on existing benchmark instances (see benchmarking for an explanation of how we benchmark), and possibly on benchmark instances for the new VRP variant. Benchmarks on existing instances ensures the new code does not cause a performance regression, and benchmarks on new instances ensures we have a baseline for the newly supported VRP variant. New benchmark instances are not strictly necessary if the changes are very small (e.g., only adding a single new constraint) - this will be decided on a case-by-case basis during review of your pull request.

With a basic implementation in place, PyVRP should now be able to find solutions for the new VRP variant. Of course, it might be possible to further improve the implementation. In the case of prize-collecting, after the initial implementation, we also:

• Modified the computation of the granular neighbourhood in compute_neighbours() to take prizes into account.

• Updated various statistics to display the number of clients in a solution.

• Changed neighbours() to return None in case a client is not in the solution.

Such changes may come about later, as we further improve support for a new VRP variant: the pull request adding initial support should ideally be kept as simple as possible.

We hope that the guidelines on this page will prove helpful when adding support for a new VRP variant.