Search code examples
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:

  • PATH_CHEAPEST_ARC: Starting from a route "start" node, connect it to the node which produces the cheapest route segment, then extend the route by iterating on the last node added to the route.
  • GLOBAL_CHEAPEST_ARC: Iteratively connect two nodes which produce the cheapest route segment.

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.