Long-term plans

[leonlan]

This issue keeps track of plans for a new major release of VRPLIB. This is a long-term goal and will be developed in parallel with the needs of PyVRP.

vrplib (v1) was originally designed to support any kind of free-form VRPLIB instance, mainly because the VRPLIB format was not well defined. Its main use cases were reading the instances for the CVRP X-instances, the VRPTW EURO-NeurIPS instances and some of the LKH-3 instances.

PyVRP is continuously adding support for new VRP variants and we are extending the VRPLIB format to support this. At some point, we will have a large collection of VRPLIB instances and a better-defined format.

---

In view of these developments, I propose the following todos for the next major release:

• A well-defined VRPLIB format for many VRP variants. Basically https://pyvrp.org/dev/supported_vrplib_fields.html combined with the current README.
  • Supersede TSPLIB #94. We should probably not supersede TSPLIB95, because it contains a lot of specifications that are just not relevant. But we should definitely take inspiration from TSPLIB95.
    • Idem: LKH-3 has introduced extensions to the TSPLIB format that we should also have a look at.
  • Ragged arrays #108.
  • Handle rounding conventions #111. A common annoyance in benchmarking is how to deal with rounding conventions. This should be better defined.
  • This VRPLIB format definition can be version-controlled and could evolve together with the vrplib package.
• Reading instances and solutions should return a Instance or Solution object with well-defined VRPLIB attributes.
  • It would be nice to keep a flexible way of reading VRPLIB instances with undefined specifications/sections, so that we can easily extend the VRPLIB format.
  • Validate instance and solution data #99. If we have a well-defined format, we can also validate if an instance is VRPLIB-style or not.
  • We can switch over to a parsing grammar like lark or pyparsing.
• Maintain a library of VRPLIB instances
  • We already do this in PyVRP/Instances, but we only keep selected instances for benchmarking. There are many more VRPLIB instances that I have created that we don't have a place for anywhere. It would be nice to have these stored somewhere as well for others to use.
• Drop support for downloading instances. This is a legacy feature that originated from when this package was called cvrplib. Migrate to uv, drop Python 3.9, remove download functionality #129
• Read/write should be a no-op, meaning that when you read an instance and then write the instance, then this give precisely the same instance again.
• Drop support for Solomon instances.
• Return Python data structures instead of numpy arrays. Only keep numpy arrays for the distance matrix. This follows from Ragged arrays #108, where the ragged arrays cannot be easily returned as numpy arrays.
• Do not normalize indices. This currently happens in DEPOT_SECTION, where we subtract -1. This is inconsistent with the other data.
• Do not allow data to be specified both as specification and section (Raise when data is both specification and section #120).
• Write solution should allow empty routes.

[N-Wouda]

[ ] Read/write should be a no-op, meaning that when you read an instance and then write the instance, then this give precisely the same instance again.

I was going to write this out into a separate issue, but since it's already tracked here I won't have to :). It'll be good to have this in because it makes adapting instances to VRPLIB much easier.

[leonlan]

I'm going to check out the Lark parsing library. If we use the LALR(1) parsing algorithm, it will also generate a standalone parser which is very neat and then Lark is only a development dependency.

---

How to move forward with Lark

1. Collect or create input samples, that demonstrate key features or behaviors in the language you’re trying to parse.

This includes:

• PyVRP VRPLIB instances
• CVRPLIB VRP instances
• LKH3 VRP instances
• TSPLIB instances

2. Write a grammar. Try to aim for a structure that is intuitive, and in a way that imitates how you would explain your language to a fellow human.

We need to define what makes something a specification or section.

3. Try your grammar in Lark against each input sample. Make sure the resulting parse-trees make sense.

4. Use Lark’s grammar features to shape the tree: Get rid of superfluous rules by inlining them, and use aliases when specific cases need clarification.

5. You can perform steps 1-4 repeatedly, gradually growing your grammar to include more sentences.

6. Create a transformer to evaluate the parse-tree into a structure you’ll be comfortable to work with. This may include evaluating literals, merging branches, or even converting the entire tree into your own set of AST classes.

[leonlan]

We are no longer working towards the plans listed in this issue in the next major release. Instead, we will remove the download functionality and bump to the next major version.

Moving forward, we'll maintain vrplib in its current state without further interface modifications. While the existing implementation isn't ideal, it serves its original purpose well by providing easy reading functionality to academic benchmark instances.