Which method does OR-Tools use for solving VRP ?

[Zakouy]

Hello,

I'm currently using the OR-Tools to solve VRP instances by following this guide : https://developers.google.com/optimization/routing/vrp. However, I was wondering which method is used by functions provided to resolve that kind of problem ? It seems to be an heuristic method but I don't know exactly which one. Thank you for your help

[Mizux]

first solution strategy with various heuristic https://developers.google.com/optimization/routing/routing_options#first_sol_options then Local Search [optional] https://developers.google.com/optimization/routing/routing_options#local_search_options

[Zakouy]

I didn't even see this section, I feel a bit stupid.

Thanks a lot though !

[Mizux]

Maybe it was too hidden... Feel free to send us feedback, proposal to make it more reachable ;)

[Zakouy]

Actually it's not hidden at all, after your answer I even noticed there was a link to the answer I was looking for directly on the page I was on 😅

I guess I was just half-asleep...

Great work then !

[Arun0013]

Apart from the First Solution Heuristic strategy, does OR-Tools use the constraint programming solver to solve VRP?

If not, how are the the custom constraints (added using routing.solver().Add() function) handled by the tool?

I am not sure if the the heuristic first solution strategies would be able to adapt to these custom constraints.

[jakhon77]

If I decide to use Local Search, does First Solution Strategy become optional? Thank you!

[Mizux]

no, First Solution Strategy is "disabled" only if you provide an initial solution, THEN the local search is used to improve over it...

step 1: First solution Strategy or initial solution provided step 2: Guided Local search to improve it until time limit is reach.

[jakhon77]

Understood. Appreciate you being there for us!

[dxyzx0]

@Mizux Can or-tools handles vrptw with additional customized constraints like general linear constraints?

[watakandai]

https://github.com/google/or-tools/issues/1867#issuecomment-1132893555

I have the exact same question. I'm adding time constraints (not just time-window constraints), but I was wondering how the solvers adapt to these constraints. Are they defined as a penalty? If so, could you point to the code?

Thank you so much for the great work.

[Mizux]

@Mizux Can or-tools handles vrptw with additional customized constraints like general linear constraints?

Basically the routing lib is built on top of the Constraint Solver (CP) thus the code located in ortools/constraint_solver. When you use routing.solver().Add(...) you are basically accessing the underlying integer CP solver. Constraints added are used to validate the first solution as well as candidate generated by the local search...

side note: You currently can't append expression to the objective expression (hard coded in the routing code). but you can use some routing api to add some cost https://groups.google.com/g/or-tools-discuss/c/YCUNTmWr8Us/m/f_hFmRP9BQAJ

[watakandai]

Oh I see. So it's running CP under the hood when new constraints are added. That's why the computation slows down exponentially. Is Integer CP solver used only for obtaining the first solution? I'm assuming that the local search is being used after obtaining the first solution (& constraints are used to validate the candidate).

Edit:

I read the Documentation and the source code, and vaguely understood how it works.

I'll look into either defining my own routing search heuristics or editing the hard-coded objective function to minimize for the penalty function.

Thanks for the quick response.