VRPLIB v2

[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.
• 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.