Is there some articles or other materials about the detail of the tools implementation？

[lmingde]

I want know the algorithm in VRP, Is there some articles or other materials about the detail of the tool implementation？

[Mizux]

Not I'm aware off. You can look at the source code: https://github.com/google/or-tools/blob/master/ortools/constraint_solver/routing.cc node: I would recommend a good IDE (i.e. with good code completion) to navigate through the source code.

Otherwise you can find here reference to which methods are currently in use... extracted from: or-tools/ortools/constraint_solver/routing_enums.proto

[lmingde]

@Mizux could you tell me what the algorithm use in the VRP in the tools ? exact or heuristic or meta heuristic method? It's better if you give me some paper(or link) about these methods.

[Mizux]

You can found few papers in the link above according to the "First Solution Strategy" you use.

Default Search Parameter:

      "first_solution_strategy: AUTOMATIC "
      "use_filtered_first_solution_strategy: true "
      "savings_neighbors_ratio: 0 "
      "savings_add_reverse_arcs: false "
      "local_search_operators {"
      "  use_relocate: true"
      "  use_relocate_pair: true"
      "  use_relocate_neighbors: false"
      "  use_exchange: true"
      "  use_cross: true"
      "  use_cross_exchange: false"
      "  use_two_opt: true"
      "  use_or_opt: true"
      "  use_lin_kernighan: true"
      "  use_tsp_opt: false"
      "  use_make_active: true"
      "  use_relocate_and_make_active: false"  // costly if true by default
      "  use_make_inactive: true"
      "  use_make_chain_inactive: false"
      "  use_swap_active: true"
      "  use_extended_swap_active: false"
      "  use_node_pair_swap_active: true"
      "  use_path_lns: false"
      "  use_full_path_lns: false"
      "  use_tsp_lns: false"
      "  use_inactive_lns: false"
      "}"
      "local_search_metaheuristic: AUTOMATIC "
      "guided_local_search_lambda_coefficient: 0.1 "
      "use_depth_first_search: false "
      "optimization_step: 1 "
      "solution_limit: 0x7FFFFFFFFFFFFFFF "  // kint64max
      "time_limit_ms: 0x7FFFFFFFFFFFFFFF "   // kint64max
      "lns_time_limit_ms: 100 "
      "use_light_propagation: true "
      "fingerprint_arc_cost_evaluators: true ";

src: https://github.com/google/or-tools/blob/96f95aebf91b1aba2408d5c050eb5a1583aaa6b3/ortools/constraint_solver/routing.cc#L656-L694

Automatic First solution Strategy:

  // Automatic
  // TODO(user): make this smarter.
  if (pickup_delivery_pairs_.empty()) {
    first_solution_decision_builders_[FirstSolutionStrategy::AUTOMATIC] =
        first_solution_decision_builders_
            [FirstSolutionStrategy::PATH_CHEAPEST_ARC];
  } else {
    first_solution_decision_builders_[FirstSolutionStrategy::AUTOMATIC] =
        first_solution_decision_builders_
            [FirstSolutionStrategy::PARALLEL_CHEAPEST_INSERTION];
  }
}

src: https://github.com/google/or-tools/blob/96f95aebf91b1aba2408d5c050eb5a1583aaa6b3/ortools/constraint_solver/routing.cc#L4251-L4262

[lperron]

This is local search and meta-heuristics on top of a Constraint Programming solver.

Unfortunately, we have not published anything. The ideas are well described in the following paper: https://www.researchgate.net/publication/226021015_A_Constraint_Programming_Toolkit_for_Local_Search

Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le lun. 5 nov. 2018 à 13:32, Mizux notifications@github.com a écrit :

You can found few papers in the link above according the "First Solution Strategy" you use

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/920#issuecomment-435858179, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17UsTwBdOSO1D1SDHeN4Mq5J6xV3Lks5usC_rgaJpZM4YOT5n .

[Mizux]

The CP-SAT solver uses a lazy clause generation solver on top of an SAT solver. The best description is a presentation from Peter Stuckey called Search is Dead

[Mizux]

https://github.com/or-tools/awesome_or-tools