Adding vehicles to initial pool changes solution

[Dvz99]

Hi all,

I'm running 9.11.4210 in Python and have a VRP scenario with 47 clients. All constraints allow the clients to be served by 1 vehicle. Therefore, setting data["num_vehicles"] to 1 is sufficient. When I set data["num_vehicles"] to 2, obviously still only 1 vehicle is used. However, when running again with data["num_vehicles"] = 2, I get a different route:

data["num_vehicles"] = 1: Objective = 1405807, 1 vehicle used
data["num_vehicles"] = 2: Objective = 1406686, 1 vehicle used

When changing data["num_vehicles"] to other values (3,4,5 etc), the result is consistent and stays 1406686.

This occurs with various first solution strategies. Sometimes solutions are the same, but running with an additional metaheuristic for 20 seconds will result in different solutions again.

Is this a known issue? Why does the available number of vehicles slightly change the solution, despite still only 1 vehicle used?

EDIT: I have included a code example and distance matrix. The matrix is a nonsymmetric 54x54 numpy distance matrix constructed from distances on a streetnetwork (in meters, multiplied by 100).

data["num_vehicles"] = 1 gives me Objective: 7122120
data["num_vehicles"] = 2 (or any other number >1) gives me Objective: 7100025

code.zip

[jmarca]

You haven’t really shared enough information. What did you add after the call to parameters = pywrapcp.DefaultRoutingSearchParameters()What is the time limit, did you turn on gls, did you turn on logging to see what is going on, etc. My guess is the single vehicle run is stuck in a *local* minimum while the two (or more) vehicle runs are able to escape it because of the extra flexibility from two vehicles. If you tweak the parameters the solver can break out of that minimum. JamesOn Dec 4, 2024, at 08:02, dvz ***@***.***> wrote: Hi all, I'm running 9.11.4210 and have a VRP scenario with 47 clients. All constraints allow the clients to be served by 1 vehicle. Therefore, setting data["num_vehicles"] to 1 is sufficient. When I set data["num_vehicles"] to 2, obviously still only 1 vehicle is used. However, when running again with data["num_vehicles"] = 2, I get a different route: data["num_vehicles"] = 1: Objective = 1405807, 1 vehicle used data["num_vehicles"] = 2: Objective = 1406686, 1 vehicle used When changing data["num_vehicles"] to other values (3,4,5 etc), the result is consistent and stays 1406686. Is this a known issue? Why does the available number of vehicles slightly change the solution, despite still only 1 vehicle used? —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[Dvz99]

Thank you for your reply!

See the code example. First solution strategy is PARALLEL_CHEAPEST_INSERTION, metaheuristic = GUIDED_LOCAL_SEARCH, with a 20s time limit. I turned on logging but don't know what to look for.

If your theory is right, why doesn't adding more than 2 vehicles improve the solution further?

[jmarca]

Ah I missed the zip file I will give it a scan tomorrow if I get a chance, but it’s a busy day for me so no promises. James