or-toolsheuristicsvehicle-routing

OR-Tools: Difference between Path Cheapest Arc and Global Cheapest Arc


The OR-Tools documentation (https://developers.google.com/optimization/routing/routing_options) for the VRP routing options describes the two first solution strategies the following way:

Can someone explain me what the difference between the two heuristics is? Unfortunately I haven't found any other information on the internet or the documentation.


Solution

  • The first one grows a route by extending it.

    The second one connect the closest nodes together until it creates routes.