-
Notifications
You must be signed in to change notification settings - Fork 2.2k
Performance improvements in VRP with service times #4421
Replies: 5 comments · 4 replies
-
Did you turn on the matrix caching setting?
James
(edited on github because the email gateway result is terrible)
|
Beta Was this translation helpful? Give feedback.
All reactions
-
this parameter:
https://github.com/google/or-tools/blob/ed94162b910fa58896db99191378d3b71a5313af/ortools/constraint_solver/routing_parameters.proto#L598
Make it safely larger than your number of nodes.
The back and forth from c++ to python is dead slow
James
(edited because the email gateway at github was illegible.)
|
Beta Was this translation helpful? Give feedback.
All reactions
-
example usage: routing_parameters = pywrapcp.DefaultRoutingModelParameters()
routing_parameters.max_callback_cache_size = 2 * num_nodes * num_vehicles # excessive, but I really want caching
routing = pywrapcp.RoutingModel(manager, routing_parameters) |
Beta Was this translation helpful? Give feedback.
All reactions
-
Hi James, thanks a lot for your answers! If you have any other suggestions to improve performance that would be much appreciated! Thanks |
Beta Was this translation helpful? Give feedback.
All reactions
-
C++ will be faster for sure.
There is also the matrix dimension that does the same thing as the caching thing…you just give it a matrix of costs.
Finally, you’re setting infinity for some links and there seem to. be a lot of them. That number really only has to be large enough, say the size of the dimension capacity. And you can also go through every impossible pair and remove the downstream node from the set of next nodes.
James
|
Beta Was this translation helpful? Give feedback.
All reactions
-
Thanks again. I tried using lower numbers than infinity before and tried removing arcs like this:
It did not seem to improve performance. What exactly do you mean by the matrix dimension? Using
I will try implementing it in C++ then.. |
Beta Was this translation helpful? Give feedback.
All reactions
-
Translating the model into C++ did not really make a difference in the solver`s performance compared to python with activated callback cache (see code attached) : Code
|
Beta Was this translation helpful? Give feedback.
All reactions
-
I took your cpp code and just changed first solution strategy to SAVINGS. (v9.8, release mode) I0000 00:00:1729778857.782938 9040 main.cpp:212] Maximum of the route distances: 19020m |
Beta Was this translation helpful? Give feedback.
All reactions
-
AddMatrixDimension:
https://github.com/google/or-tools/blob/a533e7ad0f95f042b6aaccd18c9c8247f50ea4db/ortools/constraint_solver/routing.h#L445
https://github.com/google/or-tools/blob/a533e7ad0f95f042b6aaccd18c9c8247f50ea4db/ortools/constraint_solver/python/routing.i#L112
It just caches the matrix directly. There are no callbacks to python. It won’t be much of a speed up.
Another thought, try different initial heuristic strategies.
Otherwise, try to simplify your problem. Solve a simpler, less accurate problem (tens of minutes, for example)? Or partition the problem? Do you really need all vehicles at once? Or can you split the problem in half or fourths, and solve each sub problem in parallel?
James
|
Beta Was this translation helpful? Give feedback.
-
Hello everyone,
I have implemented a VRP in which there are 50 vehicles that start at fixed positions and have arbitrary end positions. These 50 vehicles should visit 100 nodes. There are no arcs between the start positions (sys.maxsize in transition matrix). There are arcs between start positions and nodes and between nodes themselves.
In addition, each node to be visited has a service time.
(see code attached)
Code
It takes over 60 seconds to find a solution that is acceptable for my use case. And about 120 seconds to get close to the optimum (see figure attached). Is this expected?
This is too long for my use case. I would rather need a close to optimal solution in under 10 seconds. Is this feasible with or-tools for this problem size?
If yes, what options are there to solve the problem faster? Can the implementation of the model be improved? Would you expect the solver to be much faster when implemented in C++ to avoid callback functions and data being passed between C++ and python?
Thanks a lot!
Or-tools version: 9.10.4067
Beta Was this translation helpful? Give feedback.
All reactions