or-tools/src/constraint_solver/routing.cc File Reference

#include "constraint_solver/routing.h"
#include <stddef.h>
#include <string.h>
#include <algorithm>
#include "base/hash.h"
#include "base/callback.h"
#include "base/commandlineflags.h"
#include "base/integral_types.h"
#include "base/logging.h"
#include "base/scoped_ptr.h"
#include "base/bitmap.h"
#include "base/concise_iterator.h"
#include "base/map-util.h"
#include "base/stl_util.h"
#include "constraint_solver/constraint_solveri.h"
#include "graph/linear_assignment.h"

Go to the source code of this file.

Namespaces
namespace	operations_research
Classes
class	operations_research::MakePairActiveOperator
	Pair-based neighborhood operators, designed to move nodes by pairs (pairs are static and given). More...
class	operations_research::PairRelocateOperator
	Operator which moves a pair of nodes to another position. More...
class	operations_research::RoutingCache
	Cached callbacks. More...
class	operations_research::FastOnePathBuilder
	Decision builder building a solution with a single path without propagating. More...
class	operations_research::AllUnperformed
	Decision builder to build a solution with all nodes inactive. More...
Defines
#define	CP_ROUTING_PUSH_BACK_OPERATOR(operator_type)
#define	CP_ROUTING_PUSH_BACK_CALLBACK_OPERATOR(operator_type)
Functions
	DEFINE_bool (routing_no_lns, false,"Routing: forbids use of Large Neighborhood Search.")
	namespace operations_research
	DEFINE_bool (routing_no_relocate, false,"Routing: forbids use of Relocate neighborhood.")
	DEFINE_bool (routing_no_exchange, false,"Routing: forbids use of Exchange neighborhood.")
	DEFINE_bool (routing_no_cross, false,"Routing: forbids use of Cross neighborhood.")
	DEFINE_bool (routing_no_2opt, false,"Routing: forbids use of 2Opt neighborhood.")
	DEFINE_bool (routing_no_oropt, false,"Routing: forbids use of OrOpt neighborhood.")
	DEFINE_bool (routing_no_make_active, false,"Routing: forbids use of MakeActive/SwapActive/MakeInactive ""neighborhoods.")
	DEFINE_bool (routing_no_lkh, false,"Routing: forbids use of LKH neighborhood.")
	DEFINE_bool (routing_no_tsp, true,"Routing: forbids use of TSPOpt neighborhood.")
	DEFINE_bool (routing_no_tsplns, true,"Routing: forbids use of TSPLNS neighborhood.")
	DEFINE_bool (routing_use_extended_swap_active, false,"Routing: use extended version of SwapActive neighborhood.")
	DEFINE_int64 (routing_solution_limit, kint64max,"Routing: number of solutions limit.")
	Search limits.
	DEFINE_int64 (routing_time_limit, kint64max,"Routing: time limit in ms.")
	DEFINE_int64 (routing_lns_time_limit, 100,"Routing: time limit in ms for LNS sub-decisionbuilder.")
	DEFINE_bool (routing_guided_local_search, false,"Routing: use GLS.")
	Meta-heuritics.
	DEFINE_double (routing_guided_local_search_lamda_coefficient, 0.1,"Lamda coefficient in GLS.")
	DEFINE_bool (routing_simulated_annealing, false,"Routing: use simulated annealing.")
	DEFINE_bool (routing_tabu_search, false,"Routing: use tabu search.")
	DEFINE_bool (routing_dfs, false,"Routing: use a complete deoth-first search.")
	Search control.
	DEFINE_string (routing_first_solution,"","Routing: first solution heuristic;possible values are ""Default, GlobalCheapestArc, LocalCheapestArc, PathCheapestArc.")
	DEFINE_bool (routing_use_first_solution_dive, false,"Dive (left-branch) for first solution.")
	DEFINE_int64 (routing_optimization_step, 1,"Optimization step.")
	DEFINE_bool (routing_use_objective_filter, true,"Use objective filter to speed up local search.")
	Filtering control.
	DEFINE_bool (routing_use_path_cumul_filter, true,"Use PathCumul constraint filter to speed up local search.")
	DEFINE_bool (routing_use_pickup_and_delivery_filter, true,"Use filter which filters precedence and same route constraints.")
	DEFINE_bool (routing_cache_callbacks, false,"Cache callback calls.")
	Misc.
	DEFINE_int64 (routing_max_cache_size, 1000,"Maximum cache size when callback caching is on.")
	DEFINE_bool (routing_trace, false,"Routing: trace search.")
	DEFINE_bool (routing_search_trace, false,"Routing: use SearchTrace for monitoring search.")
	DEFINE_bool (routing_use_homogeneous_costs, true,"Routing: use homogeneous cost model when possible.")
	DEFINE_bool (routing_check_compact_assignment, true,"Routing::CompactAssignment calls Solver::CheckAssignment on the ""compact assignment.")
	_MSC_VER
LocalSearchOperator *	operations_research::MakePairActive (Solver *const solver, const IntVar *const *vars, const IntVar *const *secondary_vars, const RoutingModel::NodePairs &pairs, int size)
LocalSearchOperator *	operations_research::MakePairRelocate (Solver *const solver, const IntVar *const *vars, const IntVar *const *secondary_vars, const RoutingModel::NodePairs &pairs, int size)
int64	operations_research::CostFunction (int64 **eval, int64 i, int64 j)
	Evaluators.
Solver::DecisionModification	operations_research::LeftDive (Solver *const s)
	Left-branch dive branch selector.
Variables
static const int	operations_research::kUnassigned = -1
	namespace
static const int64	operations_research::kNoPenalty = -1

---

Define Documentation

#define CP_ROUTING_PUSH_BACK_CALLBACK_OPERATOR

(

operator_type

)

Value:

if (homogeneous_costs_) {                                             \
    operators.push_back(solver_->MakeOperator(nexts_.get(),             \
                                              size,                     \
                                              BuildCostCallback(),      \
                                              operator_type));          \
  } else {                                                              \
    operators.push_back(solver_->MakeOperator(nexts_.get(),             \
                                              vehicle_vars_.get(),      \
                                              size,                     \
                                              BuildCostCallback(),      \
                                              operator_type));          \
  }

Definition at line 2081 of file routing.cc.

#define CP_ROUTING_PUSH_BACK_OPERATOR

(

operator_type

)

Value:

if (homogeneous_costs_) {                                             \
    operators.push_back(solver_->MakeOperator(nexts_.get(),             \
                                              size,                     \
                                              operator_type));          \
  } else {                                                              \
    operators.push_back(solver_->MakeOperator(nexts_.get(),             \
                                              vehicle_vars_.get(),      \
                                              size,                     \
                                              operator_type));          \
  }

Definition at line 2069 of file routing.cc.

---

Function Documentation

DEFINE_bool	(	routing_check_compact_assignment	,
		true	,
		"Routing::CompactAssignment calls Solver::CheckAssignment on the ""compact assignment."
	)

_MSC_VER

DEFINE_bool	(	routing_use_homogeneous_costs	,
		true	,
		"Routing: use homogeneous cost model when possible."
	)

DEFINE_bool	(	routing_search_trace	,
		false	,
		"Routing: use SearchTrace for monitoring search."
	)

DEFINE_bool	(	routing_trace	,
		false	,
		"Routing: trace search."
	)

DEFINE_bool	(	routing_cache_callbacks	,
		false	,
		"Cache callback calls."
	)

Misc.

DEFINE_bool	(	routing_use_pickup_and_delivery_filter	,
		true	,
		"Use filter which filters precedence and same route constraints."
	)

DEFINE_bool	(	routing_use_path_cumul_filter	,
		true	,
		"Use PathCumul constraint filter to speed up local search."
	)

DEFINE_bool	(	routing_use_objective_filter	,
		true	,
		"Use objective filter to speed up local search."
	)

Filtering control.

DEFINE_bool	(	routing_use_first_solution_dive	,
		false	,
		"Dive (left-branch) for first solution."
	)

DEFINE_bool	(	routing_dfs	,
		false	,
		"Routing: use a complete deoth-first search."
	)

Search control.

DEFINE_bool	(	routing_tabu_search	,
		false	,
		"Routing: use tabu search."
	)

DEFINE_bool	(	routing_simulated_annealing	,
		false	,
		"Routing: use simulated annealing."
	)

DEFINE_bool	(	routing_guided_local_search	,
		false	,
		"Routing: use GLS."
	)

Meta-heuritics.

DEFINE_bool	(	routing_use_extended_swap_active	,
		false	,
		"Routing: use extended version of SwapActive neighborhood."
	)

DEFINE_bool	(	routing_no_tsplns	,
		true	,
		"Routing: forbids use of TSPLNS neighborhood."
	)

DEFINE_bool	(	routing_no_tsp	,
		true	,
		"Routing: forbids use of TSPOpt neighborhood."
	)

DEFINE_bool	(	routing_no_lkh	,
		false	,
		"Routing: forbids use of LKH neighborhood."
	)

DEFINE_bool	(	routing_no_make_active	,
		false	,
		"Routing: forbids use of MakeActive/SwapActive/MakeInactive ""neighborhoods."
	)

DEFINE_bool	(	routing_no_oropt	,
		false	,
		"Routing: forbids use of OrOpt neighborhood."
	)

DEFINE_bool	(	routing_no_2opt	,
		false	,
		"Routing: forbids use of 2Opt neighborhood."
	)

DEFINE_bool	(	routing_no_cross	,
		false	,
		"Routing: forbids use of Cross neighborhood."
	)

DEFINE_bool	(	routing_no_exchange	,
		false	,
		"Routing: forbids use of Exchange neighborhood."
	)

DEFINE_bool	(	routing_no_relocate	,
		false	,
		"Routing: forbids use of Relocate neighborhood."
	)

DEFINE_bool	(	routing_no_lns	,
		false	,
		"Routing: forbids use of Large Neighborhood Search."
	)

namespace operations_research

Neighborhood deactivation

DEFINE_double	(	routing_guided_local_search_lamda_coefficient	,
		0.	1,
		"Lamda coefficient in GLS."
	)

DEFINE_int64	(	routing_max_cache_size	,
		1000	,
		"Maximum cache size when callback caching is on."
	)

DEFINE_int64	(	routing_optimization_step	,
		1	,
		"Optimization step."
	)

DEFINE_int64	(	routing_lns_time_limit	,
		100	,
		"Routing: time limit in ms for LNS sub-decisionbuilder."
	)

DEFINE_int64	(	routing_time_limit	,
		kint64max	,
		"Routing: time limit in ms."
	)

DEFINE_int64	(	routing_solution_limit	,
		kint64max	,
		"Routing: number of solutions limit."
	)

Search limits.

DEFINE_string	(	routing_first_solution	,
		""	,
		"Routing: first solution heuristic;possible values are ""	Default,
		GlobalCheapestArc	,
		LocalCheapestArc	,
		PathCheapestArc."
	)

---

Variable Documentation

scoped_array<IntVar*> cumuls_

Definition at line 502 of file routing.cc.

const int cumuls_size_

Definition at line 503 of file routing.cc.

Solver::IndexEvaluator2* const evaluator_

Definition at line 504 of file routing.cc.

const int64 kUnassigned [static]

Definition at line 383 of file routing.cc.

RoutingModel* const model_

Definition at line 630 of file routing.cc.

const string name_

Definition at line 392 of file routing.cc.

std::vector<int64> node_path_starts_

Definition at line 391 of file routing.cc.

const int64 nodes_

Definition at line 629 of file routing.cc.

std::vector<int> pair_firsts_

Definition at line 552 of file routing.cc.

std::vector<int> pair_seconds_

Definition at line 553 of file routing.cc.

const int64 value_

Definition at line 661 of file routing.cc.

scoped_array<int64> values_

Definition at line 628 of file routing.cc.