Google OR-Tools: ortools/constraint_solver/routing

Google OR-Tools: ortools/constraint_solver/routing_filters.h Source File

14#ifndef ORTOOLS_CONSTRAINT_SOLVER_ROUTING_FILTERS_H_

15#define ORTOOLS_CONSTRAINT_SOLVER_ROUTING_FILTERS_H_

17#include <algorithm>

18#include <array>

19#include <cstdint>

20#include <functional>

21#include <initializer_list>

22#include <memory>

23#include <optional>

24#include <utility>

25#include <vector>

27#include "absl/functional/any_invocable.h"

28#include "absl/strings/string_view.h"

29#include "absl/types/span.h"

50 int path, int64_t capacity, int64_t span_upper_bound,

51 absl::Span<const DimensionValues::Interval> cumul_of_node,

52 absl::Span<const DimensionValues::Interval> slack_of_node,

53 absl::AnyInvocable<int64_t(int64_t, int64_t) const> evaluator,

58 std::optional<absl::AnyInvocable<int64_t(int64_t, int64_t) const>>

59 pre_travel_evaluator,

60 std::optional<absl::AnyInvocable<int64_t(int64_t, int64_t) const>>

61 post_travel_evaluator,

71 absl::Span<const std::pair<int64_t, int64_t>> interbreaks);

93 const RoutingModel& routing_model, bool filter_cost);

102

106

109 bool propagate_own_objective_value,

110 bool filter_objective_cost,

111 bool may_use_optimizers);

112

116

121

127 bool propagate_own_objective_value, bool filter_objective_cost);

128

131

132#if !defined(SWIG)

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

171 public:

172

173

174

175

177

178

180

181

183

191 int CommittedIndex(int node) const { return committed_index_[node]; }

193

194

195

196 PathState(int num_nodes, std::vector<int> path_start,

197 std::vector<int> path_end);

198

199

200

201

202 int NumNodes() const { return num_nodes_; }

203

204 int NumPaths() const { return num_paths_; }

205

206 int Start(int path) const { return path_start_end_[path].start; }

207

208 int End(int path) const { return path_start_end_[path].end; }

209

210

211

213 static constexpr int kLoop = -1;

214

215

216 int Path(int node) const { return committed_paths_[node]; }

217

218

219 const std::vector<int>& ChangedPaths() const { return changed_paths_; }

220

221 const std::vector<int>& ChangedLoops() const { return changed_loops_; }

222

223 ChainRange Chains(int path) const;

224

225 NodeRange Nodes(int path) const;

226

227

228

229

230

231

232

233

234 void ChangePath(int path, absl::Span<const ChainBounds> chains);

235

236

237 void ChangePath(int path, const std::initializer_list<ChainBounds>& chains) {

238 changed_paths_.push_back(path);

239 const int path_begin_index = chains_.size();

240 chains_.insert(chains_.end(), chains.begin(), chains.end());

241 const int path_end_index = chains_.size();

242 paths_[path] = {path_begin_index, path_end_index};

243

244 chains_.emplace_back(0, 0);

245 }

246

247

248 void ChangeLoops(absl::Span<const int> new_loops);

249

250

252

254

256

257

258

260 bool IsInvalid() const { return is_invalid_; }

261

262 private:

263

264

265

266 struct PathStartEnd {

267 PathStartEnd(int start, int end) : start(start), end(end) {}

268 int start;

269 int end;

270 };

271

272 struct PathBounds {

273 int begin_index;

274 int end_index;

275 };

276

277

278

279 void CopyNewPathAtEndOfNodes(int path);

280

281

282 void IncrementalCommit();

283

284

285 void FullCommit();

286

287

288 const int num_nodes_;

289 const int num_paths_;

290 std::vector<PathStartEnd> path_start_end_;

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318 std::vector<int> committed_nodes_;

319

320 std::vector<int> committed_paths_;

321

322 std::vector<int> committed_index_;

323 const int num_nodes_threshold_;

324 std::vector<ChainBounds> chains_;

325 std::vector<PathBounds> paths_;

326

327

328 std::vector<int> changed_paths_;

329 std::vector<int> changed_loops_;

330

331

332 bool is_invalid_ = false;

333};

334

335

337 public:

338 class Iterator {

339 public:

341 ++current_node_;

342 return *this;

343 }

344 int operator*() const { return *current_node_; }

346 return current_node_ != other.current_node_;

347 }

348

349 private:

350

352 explicit Iterator(const int* node) : current_node_(node) {}

353 const int* current_node_;

354 };

355

356

357

358 Chain(const int* begin_node, const int* end_node)

359 : begin_(begin_node), end_(end_node) {}

360

361 int NumNodes() const { return end_ - begin_; }

362 int First() const { return *begin_; }

363 int Last() const { return *(end_ - 1); }

366

368

369 private:

370 const int* const begin_;

371 const int* const end_;

372};

373

374

376 public:

377 class Iterator {

378 public:

380 ++current_chain_;

381 return *this;

382 }

384 return {first_node_ + current_chain_->begin_index,

385 first_node_ + current_chain_->end_index};

386 }

388 return current_chain_ != other.current_chain_;

389 }

390

391 private:

392

394 Iterator(const ChainBounds* chain, const int* const first_node)

395 : current_chain_(chain), first_node_(first_node) {}

397 const int* const first_node_;

398 };

399

400

401

403 const ChainBounds* const end_chain, const int* const first_node)

404 : begin_(begin_chain), end_(end_chain), first_node_(first_node) {}

405

408

410 return (begin_ == end_) ? *this : ChainRange(begin_ + 1, end_, first_node_);

411 }

412

414 return (begin_ == end_) ? *this : ChainRange(begin_, end_ - 1, first_node_);

415 }

416

417 private:

420 const int* const first_node_;

421};

422

423

424

426 public:

427 class Iterator {

428 public:

430 ++current_node_;

431 if (current_node_ == end_node_) {

432 ++current_chain_;

433

434

435 const ChainBounds bounds = *current_chain_;

436 current_node_ = first_node_ + bounds.begin_index;

437 end_node_ = first_node_ + bounds.end_index;

438 }

439 return *this;

440 }

441 int operator*() const { return *current_node_; }

443 return current_chain_ != other.current_chain_;

444 }

445

446 private:

447

449 Iterator(const ChainBounds* current_chain, const int* const first_node)

450 : current_node_(first_node + current_chain->begin_index),

451 end_node_(first_node + current_chain->end_index),

452 current_chain_(current_chain),

453 first_node_(first_node) {}

454 const int* current_node_;

455 const int* end_node_;

457 const int* const first_node_;

458 };

459

460

461

463 const int* first_node)

464 : begin_chain_(begin_chain),

465 end_chain_(end_chain),

466 first_node_(first_node) {}

467 Iterator begin() const { return {begin_chain_, first_node_}; }

468

469

470 Iterator end() const { return {end_chain_, first_node_}; }

471

472 private:

475 const int* const first_node_;

476};

477

478

479

480

481

482

484 std::unique_ptr<PathState> path_state,

485 const std::vector<IntVar*>& nexts);

486

490

495 absl::Span<const PickupDeliveryPair> pairs,

496 const std::vector<RoutingModel::PickupAndDeliveryPolicy>& vehicle_policies);

497

498

499

500

501

502

503

504

505

507 public:

512

519

520

521

523 std::vector<Interval> path_capacity,

524 std::vector<int> path_class,

525 std::vector<std::function<Interval(int64_t, int64_t)>>

526 demand_per_path_class,

527 std::vector<Interval> node_capacity,

529

530

531

532 bool Check() const;

533

534

535

537

539

540 private:

541 inline void UpdateCumulUsingChainRIQ(int first_index, int last_index,

544

545

546 void FullCommit();

547

548

549 void IncrementalCommit();

550

551

552 void AppendPathDemandsToSums(int path);

553

554

555

556

557

558 void UpdateRIQStructure(int begin_index, int end_index);

559

560 const PathState* const path_state_;

561 const std::vector<ExtendedInterval> path_capacity_;

562 const std::vector<int> path_class_;

563 const std::vector<std::function<Interval(int64_t, int64_t)>>

564 demand_per_path_class_;

565 std::vector<ExtendedInterval> cached_demand_;

566 const std::vector<ExtendedInterval> node_capacity_;

567

568

569

570

571

572 std::vector<int> index_;

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587 struct RIQNode {

593 };

594 std::vector<std::vector<RIQNode>> riq_;

595

596

597 const int maximum_riq_layer_size_;

598

599 const int min_range_size_for_riq_;

600};

601

602

603

604

605

606

607

608

610 Solver* solver, std::unique_ptr<DimensionChecker> checker,

611 absl::string_view dimension_name);

612#endif

613

615 public:

629

638

640 std::vector<PathData> path_data);

641

642 void Relax() const;

643

644 bool Check() const;

645

646 private:

648 std::vector<PathData> path_data_;

649};

650

652 Solver* solver, std::unique_ptr<LightVehicleBreaksChecker> checker,

653 absl::string_view dimension_name);

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

744 public:

746

747

748

750

751

752 int TreeSize() const { return tree_location_.size(); }

753

754

755 void PushBack(int64_t height, int64_t weight) {

756 elements_.push_back({.height = height, .weight = weight});

757 }

758

759

760

761

762

763

764

766

767

768

769

770

771

772

774 int end_index) const;

775

776 private:

777

778 struct Element {

779 int64_t height;

780 int64_t weight;

781 };

782

783

784 std::vector<Element> elements_;

785

786

787

788 struct TreeLocation {

789 int node_begin;

790 int node_end;

791 int sequence_first;

792 };

793 std::vector<TreeLocation> tree_location_;

794

795

796

797 struct Node {

798 int64_t pivot_height;

799 int pivot_index;

800 bool operator<(const Node& other) const {

801 return pivot_height < other.pivot_height;

802 }

803 bool operator==(const Node& other) const {

804 return pivot_height == other.pivot_height;

805 }

806 };

807 std::vector<Node> nodes_;

808

809

810

811

812

813

814

815

816

817 struct ElementInfo {

818 int64_t prefix_sum;

819 int left_index : 31;

820 unsigned int is_left : 1;

821 };

822

823

824

825

826

827

828

829

830

831

832

833

834

835 std::vector<std::vector<ElementInfo>> tree_layers_;

836

837

838

839

840 struct ElementRange {

841 int range_first_index;

842 int range_last_index;

843

844

845

846 bool range_first_is_node_first;

847

848 bool Empty() const { return range_first_index > range_last_index; }

849

850 int64_t Sum(const ElementInfo* elements) const {

851 return elements[range_last_index].prefix_sum -

852 (range_first_is_node_first

853 ? 0

854 : elements[range_first_index - 1].prefix_sum);

855 }

856

857 ElementRange RightSubRange(const ElementInfo* els, int pivot_index) const {

859 .range_first_index =

860 pivot_index +

861 (range_first_index - els[range_first_index].left_index),

862 .range_last_index =

863 pivot_index +

864 (range_last_index - els[range_last_index].left_index) -

865 static_cast<int>(els[range_last_index].is_left),

866 .range_first_is_node_first = false};

867 right.range_first_is_node_first = right.range_first_index == pivot_index;

868 return right;

869 }

870

871 ElementRange LeftSubRange(const ElementInfo* els) const {

872 return {.range_first_index = els[range_first_index].left_index,

873 .range_last_index = els[range_last_index].left_index -

874 !els[range_last_index].is_left,

875 .range_first_is_node_first = range_first_is_node_first};

876 }

877 };

878};

879

880

881

882

883

885 public:

896 const PathState* path_state, std::vector<int64_t> force_start_min,

897 std::vector<int64_t> force_end_min, std::vector<int> force_class,

898 std::vector<const std::function<int64_t(int64_t)>*> force_per_class,

899 std::vector<int> distance_class,

900 std::vector<const std::function<int64_t(int64_t, int64_t)>*>

901 distance_per_class,

902 std::vector<EnergyCost> path_energy_cost,

903 std::vector<bool> path_has_cost_when_empty);

906 int64_t CommittedCost() const { return committed_total_cost_; }

907 int64_t AcceptedCost() const { return accepted_total_cost_; }

908

909 private:

910 int64_t ComputePathCost(int64_t path) const;

911 void CacheAndPrecomputeRangeQueriesOfPath(int path);

912 void IncrementalCacheAndPrecompute();

913 void FullCacheAndPrecompute();

914

915 const PathState* const path_state_;

916 const std::vector<int64_t> force_start_min_;

917 const std::vector<int64_t> force_end_min_;

918 const std::vector<int> force_class_;

919 const std::vector<int> distance_class_;

920 const std::vector<const std::function<int64_t(int64_t)>*> force_per_class_;

921 const std::vector<const std::function<int64_t(int64_t, int64_t)>*>

922 distance_per_class_;

923 const std::vector<EnergyCost> path_energy_cost_;

924 const std::vector<bool> path_has_cost_when_empty_;

925

926

927 const int maximum_range_query_size_;

928

929

931 std::vector<int> force_rmq_index_of_node_;

932

933

935

936

938

939 std::vector<int> threshold_query_index_of_node_;

940

941 std::vector<int64_t> cached_force_;

942 std::vector<int64_t> cached_distance_;

943

944

945 int64_t committed_total_cost_;

946 int64_t accepted_total_cost_;

947 std::vector<int64_t> committed_path_cost_;

948};

949

951 Solver* solver, std::unique_ptr<PathEnergyCostChecker> checker,

952 absl::string_view dimension_name);

953

957 const PathState* path_state,

958 const std::vector<RoutingDimension*>& dimensions,

959 std::vector<LocalSearchFilterManager::FilterEvent>* filters);

960

962 const std::vector<RoutingDimension*>& dimensions,

963 const RoutingSearchParameters& parameters, bool filter_objective_cost,

964 bool use_chain_cumul_filter,

965 std::vector<LocalSearchFilterManager::FilterEvent>* filters);

966

968

970 public:

971 BasePathFilter(const std::vector<IntVar*>& nexts, int next_domain_size,

975 int64_t objective_min, int64_t objective_max) override;

977

978 protected:

980

981 int64_t GetNext(int64_t node) const {

984 : new_nexts_[node];

985 }

987 for (int64_t start : paths_metadata_.Starts()) {

989 }

990 return false;

991 }

992 int NumPaths() const { return paths_metadata_.NumPaths(); }

993 int64_t Start(int i) const { return paths_metadata_.Start(i); }

994 int64_t End(int i) const { return paths_metadata_.End(i); }

995 int GetPath(int64_t node) const { return paths_metadata_.GetPath(node); }

996 int Rank(int64_t node) const { return ranks_[node]; }

998 return touched_paths_.PositionsSetAtLeastOnce();

999 }

1000 bool PathStartTouched(int64_t start) const { return touched_paths_[start]; }

1002 return new_synchronized_unperformed_nodes_.PositionsSetAtLeastOnce();

1003 }

1004

1006

1007 private:

1008 virtual void OnBeforeSynchronizePaths(bool) {}

1009 virtual void OnAfterSynchronizePaths() {}

1010 virtual void OnSynchronizePathFromStart(int64_t) {}

1011 virtual bool InitializeAcceptPath() { return true; }

1012 virtual bool AcceptPath(int64_t path_start, int64_t chain_start,

1013 int64_t chain_end) = 0;

1014 virtual bool FinalizeAcceptPath(int64_t, int64_t) { return true; }

1016 void ComputePathStarts(std::vector<int64_t>* path_starts,

1017 std::vector<int>* index_to_path);

1018 bool HavePathsChanged();

1019 void SynchronizeFullAssignment();

1020 void UpdateAllRanks();

1021 void UpdatePathRanksFromStart(int start);

1022

1023 const PathsMetadata& paths_metadata_;

1024 std::vector<int64_t> node_path_starts_;

1025 SparseBitset<int64_t> new_synchronized_unperformed_nodes_;

1026 std::vector<int64_t> new_nexts_;

1027 std::vector<int> delta_touched_;

1028 SparseBitset<> touched_paths_;

1029

1030 std::vector<std::pair<int64_t, int64_t> > touched_path_chain_start_ends_;

1031

1032 std::vector<int> ranks_;

1033

1034 bool lns_detected_;

1035};

1036

1037

1038

1039

1040

1041

1042

1043

1044

1045

1046

1047

1048

1049

1050

1051

1052

1053

1054

1055

1056

1057

1058

1059

1060

1061

1062

1063

1064

1065

1066

1067

1068

1069

1070

1071

1072

1073

1074

1075

1076

1077

1078

1079

1080

1081

1082

1083

1084

1086 public:

1087

1088

1090 const std::vector<std::vector<double>>& rows);

1091

1092 double Evaluate(absl::Span<const double> values) const;

1093

1094 private:

1095

1096

1097 static constexpr int kBlockSize = 16;

1098 struct Block {

1099 std::array<double, kBlockSize> coefficients;

1100

1101 Block& BlockMultiplyAdd(const Block& other, double value) {

1102

1103

1104 for (int i = 0; i < kBlockSize; ++i) {

1105 coefficients[i] += other.coefficients[i] * value;

1106 }

1107 return *this;

1108 }

1109 Block& MaximumWith(const Block& other) {

1110 for (int i = 0; i < kBlockSize; ++i) {

1111 coefficients[i] = std::max(coefficients[i], other.coefficients[i]);

1112 }

1113 return *this;

1114 }

1115 double Maximum() const {

1116 return *std::max_element(coefficients.begin(), coefficients.end());

1117 }

1118 };

1119 std::vector<Block> blocks_;

1120 const int64_t num_variables_;

1121 const int64_t num_rows_;

1122};

1123

1124}

1125

1126#endif

~BasePathFilter() override=default

static const int64_t kUnassigned

Definition routing_filters.h:979

int NumPaths() const

Definition routing_filters.h:992

bool lns_detected() const

Definition routing_filters.h:1005

bool PathStartTouched(int64_t start) const

Definition routing_filters.h:1000

BasePathFilter(const std::vector< IntVar * > &nexts, int next_domain_size, const PathsMetadata &paths_metadata)

int64_t GetNext(int64_t node) const

Definition routing_filters.h:981

const std::vector< int64_t > & GetTouchedPathStarts() const

Definition routing_filters.h:997

bool Accept(const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max) override

bool HasAnySyncedPath() const

Definition routing_filters.h:986

int GetPath(int64_t node) const

Definition routing_filters.h:995

int Rank(int64_t node) const

Definition routing_filters.h:996

const std::vector< int64_t > & GetNewSynchronizedUnperformedNodes() const

Definition routing_filters.h:1001

void OnSynchronize(const Assignment *delta) override

int64_t Start(int i) const

Definition routing_filters.h:993

int64_t End(int i) const

Definition routing_filters.h:994

DimensionChecker(const PathState *path_state, std::vector< Interval > path_capacity, std::vector< int > path_class, std::vector< std::function< Interval(int64_t, int64_t)> > demand_per_path_class, std::vector< Interval > node_capacity, int min_range_size_for_riq=kOptimalMinRangeSizeForRIQ)

static constexpr int kOptimalMinRangeSizeForRIQ

Definition routing_filters.h:538

IntVarLocalSearchFilter(const std::vector< IntVar * > &vars)

int64_t Value(int index) const

bool IsVarSynced(int index) const

LightVehicleBreaksChecker(PathState *path_state, std::vector< PathData > path_data)

double Evaluate(absl::Span< const double > values) const

MaxLinearExpressionEvaluator(const std::vector< std::vector< double > > &rows)

PathEnergyCostChecker(const PathState *path_state, std::vector< int64_t > force_start_min, std::vector< int64_t > force_end_min, std::vector< int > force_class, std::vector< const std::function< int64_t(int64_t)> * > force_per_class, std::vector< int > distance_class, std::vector< const std::function< int64_t(int64_t, int64_t)> * > distance_per_class, std::vector< EnergyCost > path_energy_cost, std::vector< bool > path_has_cost_when_empty)

int64_t AcceptedCost() const

Definition routing_filters.h:907

int64_t CommittedCost() const

Definition routing_filters.h:906

Definition routing_filters.h:377

bool operator!=(Iterator other) const

Definition routing_filters.h:387

Chain operator*() const

Definition routing_filters.h:383

friend class ChainRange

Definition routing_filters.h:393

Iterator & operator++()

Definition routing_filters.h:379

Definition routing_filters.h:375

ChainRange DropLastChain() const

Definition routing_filters.h:413

ChainRange DropFirstChain() const

Definition routing_filters.h:409

ChainRange(const ChainBounds *const begin_chain, const ChainBounds *const end_chain, const int *const first_node)

Definition routing_filters.h:402

Iterator end() const

Definition routing_filters.h:407

Iterator begin() const

Definition routing_filters.h:406

Definition routing_filters.h:338

bool operator!=(Iterator other) const

Definition routing_filters.h:345

int operator*() const

Definition routing_filters.h:344

Iterator & operator++()

Definition routing_filters.h:340

Definition routing_filters.h:336

Chain(const int *begin_node, const int *end_node)

Definition routing_filters.h:358

int Last() const

Definition routing_filters.h:363

int NumNodes() const

Definition routing_filters.h:361

Iterator end() const

Definition routing_filters.h:365

int First() const

Definition routing_filters.h:362

Iterator begin() const

Definition routing_filters.h:364

Chain WithoutFirstNode() const

Definition routing_filters.h:367

Definition routing_filters.h:427

Iterator & operator++()

Definition routing_filters.h:429

bool operator!=(Iterator other) const

Definition routing_filters.h:442

friend class NodeRange

Definition routing_filters.h:448

int operator*() const

Definition routing_filters.h:441

Definition routing_filters.h:425

NodeRange(const ChainBounds *begin_chain, const ChainBounds *end_chain, const int *first_node)

Definition routing_filters.h:462

Iterator end() const

Definition routing_filters.h:470

Iterator begin() const

Definition routing_filters.h:467

Definition routing_filters.h:170

int NumNodes() const

Definition routing_filters.h:202

void ChangeLoops(absl::Span< const int > new_loops)

bool IsInvalid() const

Definition routing_filters.h:260

const std::vector< int > & ChangedLoops() const

Definition routing_filters.h:221

const std::vector< int > & ChangedPaths() const

Definition routing_filters.h:219

ChainBounds CommittedPathRange(int path) const

Definition routing_filters.h:192

ChainRange Chains(int path) const

static constexpr int kUnassigned

Definition routing_filters.h:212

int NumPaths() const

Definition routing_filters.h:204

void SetInvalid()

Definition routing_filters.h:259

NodeRange Nodes(int path) const

int Path(int node) const

Definition routing_filters.h:216

int End(int path) const

Definition routing_filters.h:208

PathState(int num_nodes, std::vector< int > path_start, std::vector< int > path_end)

static constexpr int kLoop

Definition routing_filters.h:213

void ChangePath(int path, const std::initializer_list< ChainBounds > &chains)

Definition routing_filters.h:237

int CommittedIndex(int node) const

Definition routing_filters.h:191

void ChangePath(int path, absl::Span< const ChainBounds > chains)

int Start(int path) const

Definition routing_filters.h:206

Definition routing_filters.h:743

void MakeTreeFromNewElements()

WeightedWaveletTree()=default

void PushBack(int64_t height, int64_t weight)

Definition routing_filters.h:755

int64_t RangeSumWithThreshold(int64_t threshold_height, int begin_index, int end_index) const

int TreeSize() const

Definition routing_filters.h:752

LocalSearchFilter * MakePickupDeliveryFilter(const RoutingModel &routing_model, const PathState *path_state, absl::Span< const PickupDeliveryPair > pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)

IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)

Returns a filter computing vehicle amortized costs.

bool FillDimensionValuesFromRoutingDimension(int path, int64_t capacity, int64_t span_upper_bound, absl::Span< const DimensionValues::Interval > cumul_of_node, absl::Span< const DimensionValues::Interval > slack_of_node, absl::AnyInvocable< int64_t(int64_t, int64_t) const > evaluator, DimensionValues &dimension_values)

IntVarLocalSearchFilter * MakeRouteConstraintFilter(const RoutingModel &routing_model)

Returns a filter tracking route constraints.

IntVarLocalSearchFilter * MakeSameVehicleCostFilter(const RoutingModel &routing_model)

Returns a filter computing same vehicle costs.

IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)

Returns a filter ensuring that max active vehicles constraints are enforced.

void AppendLightWeightDimensionFilters(const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)

IntVarLocalSearchFilter * MakeNodeDisjunctionFilter(const RoutingModel &routing_model, bool filter_cost)

Returns a filter ensuring that node disjunction constraints are enforced.

LocalSearchFilter * MakePathEnergyCostFilter(Solver *solver, std::unique_ptr< PathEnergyCostChecker > checker, absl::string_view dimension_name)

IntVarLocalSearchFilter * MakeCumulBoundsPropagatorFilter(const RoutingDimension &dimension)

Returns a filter handling dimension cumul bounds.

LocalSearchFilter * MakePathStateFilter(Solver *solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar * > &nexts)

ClosedInterval::Iterator end(ClosedInterval interval)

LocalSearchFilter * MakeLightVehicleBreaksFilter(Solver *solver, std::unique_ptr< LightVehicleBreaksChecker > checker, absl::string_view dimension_name)

IntVarLocalSearchFilter * MakePathCumulFilter(const RoutingDimension &dimension, bool propagate_own_objective_value, bool filter_objective_cost, bool may_use_optimizers)

Returns a filter handling dimension costs and constraints.

IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)

Returns a filter checking the current solution using CP propagation.

void FillPrePostVisitValues(int path, const DimensionValues &dimension_values, std::optional< absl::AnyInvocable< int64_t(int64_t, int64_t) const > > pre_travel_evaluator, std::optional< absl::AnyInvocable< int64_t(int64_t, int64_t) const > > post_travel_evaluator, PrePostVisitValues &visit_values)

IntVarLocalSearchFilter * MakeOrderedActivityGroupFilter(const RoutingModel &routing_model)

LocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model, const PathState *path_state)

Returns a filter checking that vehicle variable domains are respected.

void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters &parameters, bool filter_objective_cost, bool use_chain_cumul_filter, std::vector< LocalSearchFilterManager::FilterEvent > *filters)

LocalSearchFilter * MakeResourceAssignmentFilter(LocalDimensionCumulOptimizer *lp_optimizer, LocalDimensionCumulOptimizer *mp_optimizer, bool propagate_own_objective_value, bool filter_objective_cost)

bool PropagateLightweightVehicleBreaks(int path, DimensionValues &dimension_values, absl::Span< const std::pair< int64_t, int64_t > > interbreaks)

IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)

Returns a filter ensuring type regulation constraints are enforced.

IntVarLocalSearchFilter * MakeGlobalLPCumulFilter(GlobalDimensionCumulOptimizer *lp_optimizer, GlobalDimensionCumulOptimizer *mp_optimizer, bool filter_objective_cost)

Returns a filter checking global linear constraints and costs.

util_intops::StrongIntRange< ElementIndex > ElementRange

IntVarLocalSearchFilter * MakeActiveNodeGroupFilter(const RoutingModel &routing_model)

LocalSearchFilter * MakeDimensionFilter(Solver *solver, std::unique_ptr< DimensionChecker > checker, absl::string_view dimension_name)

The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...

Definition routing_filters.h:513

int64_t min

Definition routing_filters.h:514

int64_t num_positive_infinity

Definition routing_filters.h:517

int64_t num_negative_infinity

Definition routing_filters.h:516