Prize-collecting and benchmark instances

[N-Wouda]

This is a feature request and discussion. I have a prize-collecting problem for which I'm going to make some benchmark instances (based on the topologies of the Solomon instances). Can I:

1) Make these in a format vprlib understands? Can vrplib handle prizes? 2) Add such benchmarks to vrplib/make them available for reading?

[N-Wouda]

(I wouldn't mind picking up support for prizes if you're interested @leonlan)

[leonlan]

Hi @N-Wouda!

Make these in a format vprlib understands? Can vrplib handle prizes?

vrplib can handle very general VRPLIB instances (see the new updated README), so it should be possible to handle prizes as well. The only question is how to call the "prize" data section. AFAIK there is no convention for that. Assuming that the prize-collecting variant of the VRP requires a single additional prize parameter for every customer, then the following example should work:

NAME: Example
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 0 0
2 1 0
SERVICE_TIME_SECTION
1 0
2 3
PRIZE_SECTION
1 0
2 100
EOF

Reading this instance returns the following output:

{'name': 'Example',
 'edge_weight_type': 'EUC_2D',
 'node_coord': array([[0, 0], [1, 0]]),
 'service_time': array([0, 3]),
 'prize': array([  0, 100]),
 'edge_weight': array([[0., 1.], [1., 0.]])}

Alternatively, you could include edge weights explicitly.

NAME: Example
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORAT: FULL_MATRIX
NODE_COORD_SECTION
1 0 0
2 1 0
SERVICE_TIME_SECTION
1 0
2 3
PRIZE_SECTION
1 0
2 100
EDGE_WEIGHT_SECTION
0   100
100  0
EOF

To make your own instance you could use the write_instance function that I wrote some time ago. See this https://github.com/leonlan/VRPLIB/blob/7c5a6a6c550a4556f26425257ca5353852b884c5/cvrplib/write/write_instance.py commit. It's not in main yet, but that's something I plan to add some time soon.

Add such benchmarks to vrplib/make them available for reading?

Do you mean by this if we could make the PCVRP instances available for downloading like it's possible for CVRPLIB instances now?

If so, then that's possible if these instances are hosted somewhere. We could add them to a Github repository hosted by the VRPLIB organization, just like I did for the EURO-NeurIPS instances (https://github.com/VRPLIB/VRPTW). Note that these instances are not available for downloading right now, it's just a prototype idea.

[N-Wouda]

Good to know, thanks!

Do you mean by this if we could make the PCVRP instances available for downloading like it's possible for CVRPLIB instances now?

Yeah, maybe? I'm not sure yet how general they'll be, but right now there's basically nothing in terms of prize-collecting out there. These benchmarks could be a start.

[leonlan]

Sure, we can do that. Let me know when you have the instances and then we can work out this idea.

[N-Wouda]

Thanks for the help!

Re. the benchmarks: I'm going to host the prize-collecting instances and solutions in PyVRP/Instances for now.