Open call: do you have hard-to-solve instances? #564

N-Wouda · 2024-04-03T15:20:22Z

N-Wouda
Apr 3, 2024
Maintainer

PyVRP solves instances for many different vehicle routing variants very well, often reaching best-known solutions, or approaching those closely. At the same time, PyVRP is still fairly young: it has not been tested on a lot of instances outside of academia. As a consequence, we do not really know how PyVRP behaves when faced with real-world instances that might not be as nice to solve as the academic benchmarks we often use for comparison.

So, this discussion is an open call to anyone using PyVRP to provide instances that PyVRP currently struggles to solve. This can either be because it's hard to find a feasible solution, because of poor convergence, or any other aspect that makes the problem difficult for PyVRP. We are interested in learning more from such instances, and use that knowledge to improve PyVRP's robustness and performance going forward.

Important

It is much easier for us if you provide an instance by serialising a ProblemData object using Python's builtin pickle module. Please then also specify the version of PyVRP you use.

It would be immensely helpful if you have a contrasting solver that does perform well on the instance. A good solution from such an alternative solver will help us quickly understand:

Whether the issue is PyVRP-specific;
What can be gained in terms of solution quality.

Note

If you want to share your instances but would rather not do so publicly in this discussion thread, feel free to send them via email.

ravenblackdusk · 2025-02-18T12:55:33Z

ravenblackdusk
Feb 18, 2025

@N-Wouda We are experimenting with using PyVRP to replace our production or-tools. PyVRP seems to be not good at finding feasible solutions for lots of edges with a really big number.
Imagine you find a solution for a single vehicle VRPTW, then you would want to re-optimize by adding a few stops or changing vehicle departure time, but you cannot change the order of stops in the original solution, you can only add the new stops in between. I've implemented this by using edges with high numbers(8_388_608) so that they would never appear in the solution. For example if we had A->B in the original solution I would replace any edge from A to any other node other than B and the new stops to 8_388_608. Note that this is not the only use case where I have to use 8_388_608. This will either take a very long time to find the feasible solution, or not be able to find it at all.
or-tools can solve such re-optimizations in a few seconds, which is expected because the problem has much less variability.
library versions:
pyvrp==0.9.1
vrplib==1.4.0
vrp.txt

round_func = "none"
    if (key := str(round_func)) in ROUND_FUNCS:
        round_func = ROUND_FUNCS[key]
    parser = _InstanceParser(parse_vrplib(request.data.decode(), True), round_func)
    instance = _ProblemDataBuilder(parser).data()
    vehicle_type = instance.vehicle_type(0)
    model = Model.from_data(instance.replace(vehicle_types=[], distance_matrices=[parser.instance["edge_distance"]]))
    # noinspection PyProtectedMember
    model.add_vehicle_type(vehicle_type.num_available, vehicle_type.capacity, model._depots[0], model._depots[1],
                           vehicle_type.fixed_cost, vehicle_type.tw_early, vehicle_type.tw_late,
                           vehicle_type.max_duration, vehicle_type.max_distance, 1, 38, name=vehicle_type.name)
    solution = model.solve(MultipleCriteria(
        [MaxIterations(parser.instance.get("max_iterations", 3000)),
         NoImprovement(parser.instance.get("no_improvement", 1000)),
         MaxRuntime(timedelta(minutes=5).total_seconds())]), display=False).best

2 replies

N-Wouda Feb 18, 2025
Maintainer Author

Hi @ravenblackdusk, thanks for sharing an instance and a description of your problem! I hope to have time later this week to have a good look at it.

N-Wouda May 25, 2025
Maintainer Author

Apologies for my late response, I've just had a look at your instance. The instance has:

2 depots
295 clients
1 vehicle (1 vehicle type)

So it's a TSP. Furthermore, the instance has:

Service times and time windows;
Two clients with prizes / optional, so the vast majority of clients are required;
A large mutually exclusive client group.

What makes this really challenging to solve is the very limited freedom the duration matrix gives us. See for example the following matrix plot, where all yellow arcs are forbidden/infeasible. This is such a constrained problem that I don't think PyVRP is really the best tool - I am not surprised that OR-Tools does much better here, being based around a constraint programming solver.

@ravenblackdusk would you happen to have a feasible solution we could compare with? I think we might need to improve our (random) initialisation procedure to handle this, and it'd be helpful to have something we can compare against for testing.

ravenblackdusk · 2025-06-02T07:49:55Z

ravenblackdusk
Jun 2, 2025

@N-Wouda

PyVRP returns this solution for me. This is the relevant code for the solution:

dumps = json.dumps({"problemId": parser.instance["name"], "organizationId": parser.instance["organization_id"],
                        "optimizationId": parser.instance["optimization_id"],
                        "optimizationPhase": parser.instance["optimization_phase"],
                        "withBreak": parser.instance["with_break"],
                        "startEpochMilli": parser.instance["start_epoch_milli"], "date": parser.instance["date"],
                        "tags": parser.instance["tags"], "reOptimizedStopIds": parser.instance["re_optimized_stop_ids"],
                        "distance": solution.distance(), "distanceCost": solution.distance_cost(),
                        "duration": solution.duration(), "durationCost": solution.duration_cost(),
                        "numMissingClients": solution.num_missing_clients(), "routes": [
            {"visits": [visit for visit in route.visits()], "distance": route.distance(),
             "distanceCost": route.distance_cost(), "duration": route.duration(), "durationCost": route.duration_cost(),
             "endTime": route.end_time(), "startTime": route.start_time(), "travelDuration": route.travel_duration(),
             "serviceDuration": route.service_duration(), "waitDuration": route.wait_duration(),
             "timeWarp": route.time_warp(), } for route in solution.routes()]})

please tell me if you need the solution in a different format, or a different solution.

now that you're talking about initialization, it might also be good to allow the user to provide an initial solution, PyVRP can then guarantee to return a solution that is not worse than the initial solution. In my case which is what we call a reoptimization, the initial solution will be the solution to the original optimization.
another idea that might be a workaround from my side: if I want to ensure the sequence A -> B -> C; instead of setting the cost of A -> C to infinite, I can set it to A -> B + B -> C; then in theory PyVRP should never choose A -> C over A -> B -> C as it can visit 3 instead of 2; that is if PyVRP has enough time to evaluate A -> B -> C(I've not tested this yet). This however doesn't solve everything and is a burden on the developer.

1 reply

N-Wouda Jun 12, 2025
Maintainer Author

Hi @ravenblackdusk, warm-starting from user-provided initial solutions has come up before, in #710. Perhaps the discussion and code presented there is of use to you? I have also opened a feature request for it, in #855. We'll try to pick this up as part of the next release (in a month or so)!

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Open call: do you have hard-to-solve instances? #564

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{editor}}'s edit

{{editor}}'s edit

Uh oh!

Replies: 2 comments 3 replies

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{editor}}'s edit

{{editor}}'s edit

Uh oh!

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{editor}}'s edit

{{editor}}'s edit

Uh oh!

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{title}}

Uh oh!

Select a reply

Uh oh!

Uh oh!

Open call: do you have hard-to-solve instances? #564

Uh oh!

Uh oh!

N-Wouda Apr 3, 2024 Maintainer

Replies: 2 comments · 3 replies

Uh oh!

Uh oh!

ravenblackdusk Feb 18, 2025

Uh oh!

N-Wouda Feb 18, 2025 Maintainer Author

Uh oh!

Uh oh!

N-Wouda May 25, 2025 Maintainer Author

Uh oh!

ravenblackdusk Jun 2, 2025

Uh oh!

N-Wouda Jun 12, 2025 Maintainer Author

N-Wouda
Apr 3, 2024
Maintainer

Replies: 2 comments 3 replies

ravenblackdusk
Feb 18, 2025

N-Wouda Feb 18, 2025
Maintainer Author

N-Wouda May 25, 2025
Maintainer Author

ravenblackdusk
Jun 2, 2025

N-Wouda Jun 12, 2025
Maintainer Author