Google OR-Tools: ortools/constraint_solver/routing

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

14#ifndef ORTOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_

15#define ORTOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_

17#include <stdbool.h>

19#include <cstdint>

20#include <functional>

21#include <string>

22#include <utility>

23#include <vector>

25#include "absl/log/check.h"

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

56template <bool ignore_path_vars>

58 public:

60 const std::vector<IntVar*>& vars,

61 const std::vector<IntVar*>& secondary_vars,

62 std::function<int(int64_t)> start_empty_path_class,

63 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

64 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

69 std::string DebugString() const override { return "RelocateNeighbors"; }

71 private:

78 bool MoveChainAndRepair(int64_t before_chain, int64_t chain_end,

79 int64_t destination);

88 int64_t Reposition(int64_t before_to_move, int64_t up_to);

91};

94 Solver* solver, const std::vector<IntVar*>& vars,

95 const std::vector<IntVar*>& secondary_vars,

96 std::function<int(int64_t)> start_empty_path_class,

97 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

98 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

100

102 Solver* solver, const std::vector<IntVar*>& vars,

103 const std::vector<IntVar*>& secondary_vars,

104 std::function<int(int64_t)> start_empty_path_class,

106

107

108

110 public:

112 std::vector<std::vector<int64_t>> alternative_sets,

115

116

117

118 absl::Span<const int64_t> GetShortestPath(int64_t source, int64_t sink,

119 absl::Span<const int64_t> chain);

120

121 private:

123 std::vector<std::vector<int64_t>> alternative_sets_;

124 std::vector<int> to_alternative_set_;

125 std::vector<int64_t> path_predecessor_;

126 std::vector<int64_t> path_;

127 std::vector<int64_t> current_values_;

129};

130

131

132

133

134template <bool ignore_path_vars>

136 public:

138 const std::vector<IntVar*>& vars,

139 const std::vector<IntVar*>& secondary_vars,

140 std::function<int(int64_t)> start_empty_path_class,

141 std::vector<std::vector<int64_t>> alternative_sets,

145 std::string DebugString() const override { return "TwoOptWithShortestPath"; }

146

147 protected:

149

150 return true;

151 }

155

157

158 private:

161 void ResetChainStatus() {

162 chain_status_.start = -1;

163 chain_status_.end = -1;

164 chain_status_.has_alternatives = false;

165 }

166

167 struct ChainStatus {

168 int64_t start = -1;

169 int64_t end = -1;

170 bool has_alternatives = false;

171 };

172 ChainStatus chain_status_;

173 ShortestPathOnAlternatives shortest_path_manager_;

174 std::vector<int64_t> chain_;

175};

176

178 Solver* solver, const std::vector<IntVar*>& vars,

179 const std::vector<IntVar*>& secondary_vars,

180 std::function<int(int64_t)> start_empty_path_class,

181 std::vector<std::vector<int64_t>> alternative_sets,

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202template <bool ignore_path_vars>

204 public:

206 const std::vector<IntVar*>& vars,

207 const std::vector<IntVar*>& secondary_vars,

208 std::function<int(int64_t)> start_empty_path_class,

209 std::vector<std::vector<int64_t>> alternative_sets,

214 return "SwapActiveToShortestPath";

215 }

216

217 private:

219 std::vector<int64_t> chain_;

220};

221

223 Solver* solver, const std::vector<IntVar*>& vars,

224 const std::vector<IntVar*>& secondary_vars,

225 std::function<int(int64_t)> start_empty_path_class,

226 std::vector<std::vector<int64_t>> alternative_sets,

228

233

234

235

236

237

238

239

252template <bool ignore_path_vars>

254 public:

256 const std::vector<IntVar*>& secondary_vars,

257 std::function<int(int64_t)> start_empty_path_class,

258 const std::vector<PickupDeliveryPair>& pairs);

261 std::string DebugString() const override { return "MakePairActive"; }

262

263 protected:

270

272

276

277 private:

279 int FindNextInactivePair(int pair_index) const;

280 bool ContainsActiveNodes(absl::Span<const int64_t> nodes) const;

281

282 int inactive_pair_;

283 int inactive_pair_first_index_;

284 int inactive_pair_second_index_;

285 const std::vector<PickupDeliveryPair> pairs_;

286};

287

289 Solver* solver, const std::vector<IntVar*>& vars,

290 const std::vector<IntVar*>& secondary_vars,

291 std::function<int(int64_t)> start_empty_path_class,

292 const std::vector<PickupDeliveryPair>& pairs);

293

295template <bool ignore_path_vars>

297 public:

299 const std::vector<IntVar*>& secondary_vars,

300 std::function<int(int64_t)> start_empty_path_class,

301 const std::vector<PickupDeliveryPair>& pairs);

302

304 std::string DebugString() const override { return "MakePairInActive"; }

305};

306

308 Solver* solver, const std::vector<IntVar*>& vars,

309 const std::vector<IntVar*>& secondary_vars,

310 std::function<int(int64_t)> start_empty_path_class,

311 const std::vector<PickupDeliveryPair>& pairs);

312

321template <bool ignore_path_vars>

323 public:

325 const std::vector<IntVar*>& secondary_vars,

326 std::function<int(int64_t)> start_empty_path_class,

327 const std::vector<PickupDeliveryPair>& pairs);

329

331 std::string DebugString() const override { return "PairRelocateOperator"; }

332

333 protected:

336 return base_index == kPairSecondNodeDestination;

337 }

339

341 return base_index == kPairFirstNode;

342 }

343

344 private:

346

347 static constexpr int kPairFirstNode = 0;

348 static constexpr int kPairFirstNodeDestination = 1;

349 static constexpr int kPairSecondNodeDestination = 2;

350};

351

353 Solver* solver, const std::vector<IntVar*>& vars,

354 const std::vector<IntVar*>& secondary_vars,

355 std::function<int(int64_t)> start_empty_path_class,

356 const std::vector<PickupDeliveryPair>& pairs);

357

360template <bool ignore_path_vars>

362 public:

364 const std::vector<IntVar*>& vars,

365 const std::vector<IntVar*>& secondary_vars,

366 std::function<int(int64_t)> start_empty_path_class,

367 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

368 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

369 const std::vector<PickupDeliveryPair>& pairs);

371

373 std::string DebugString() const override { return "GroupPairAndRelocate"; }

374};

375

377 Solver* solver, const std::vector<IntVar*>& vars,

378 const std::vector<IntVar*>& secondary_vars,

379 std::function<int(int64_t)> start_empty_path_class,

380 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

381 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

382 const std::vector<PickupDeliveryPair>& pairs);

383

385 Solver* solver, const std::vector<IntVar*>& vars,

386 const std::vector<IntVar*>& secondary_vars,

387 std::function<int(int64_t)> start_empty_path_class,

388 const std::vector<PickupDeliveryPair>& pairs);

389

399

400

401template <bool ignore_path_vars>

403 public:

405 const std::vector<IntVar*>& vars,

406 const std::vector<IntVar*>& secondary_vars,

407 std::function<int(int64_t)> start_empty_path_class,

408 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

409 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

410 const std::vector<PickupDeliveryPair>& pairs,

411 std::function<bool(int64_t)> force_lifo = nullptr);

413

416 return "LightPairRelocateOperator";

417 }

418

419 private:

420 std::function<bool(int64_t)> force_lifo_;

421};

422

424 Solver* solver, const std::vector<IntVar*>& vars,

425 const std::vector<IntVar*>& secondary_vars,

426 std::function<int(int64_t)> start_empty_path_class,

427 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

428 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

429 const std::vector<PickupDeliveryPair>& pairs,

430 std::function<bool(int64_t)> force_lifo = nullptr);

431

433 Solver* solver, const std::vector<IntVar*>& vars,

434 const std::vector<IntVar*>& secondary_vars,

435 std::function<int(int64_t)> start_empty_path_class,

436 const std::vector<PickupDeliveryPair>& pairs,

437 std::function<bool(int64_t)> force_lifo = nullptr);

438

445template <bool ignore_path_vars>

447 public:

449 const std::vector<IntVar*>& vars,

450 const std::vector<IntVar*>& secondary_vars,

451 std::function<int(int64_t)> start_empty_path_class,

452 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

453 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

454 const std::vector<PickupDeliveryPair>& pairs);

456

458 std::string DebugString() const override { return "PairExchangeOperator"; }

459

460 private:

462 bool ConsiderAlternatives(int64_t ) const override {

463 return true;

464 }

465 bool GetPreviousAndSibling(int64_t node, int64_t* previous, int64_t* sibling,

466 int64_t* sibling_previous) const;

467};

468

470 Solver* solver, const std::vector<IntVar*>& vars,

471 const std::vector<IntVar*>& secondary_vars,

472 std::function<int(int64_t)> start_empty_path_class,

473 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

474 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

475 const std::vector<PickupDeliveryPair>& pairs);

476

478 Solver* solver, const std::vector<IntVar*>& vars,

479 const std::vector<IntVar*>& secondary_vars,

480 std::function<int(int64_t)> start_empty_path_class,

481 const std::vector<PickupDeliveryPair>& pairs);

482

496template <bool ignore_path_vars>

498 public:

500 const std::vector<IntVar*>& vars,

501 const std::vector<IntVar*>& secondary_vars,

502 std::function<int(int64_t)> start_empty_path_class,

503 const std::vector<PickupDeliveryPair>& pairs);

505

508 return "PairExchangeRelocateOperator";

509 }

510

511 protected:

514

515 private:

517 bool GetPreviousAndSibling(int64_t node, int64_t* previous, int64_t* sibling,

518 int64_t* sibling_previous) const;

519 bool MoveNode(int pair, int node, int64_t nodes[2][2], int64_t dest[2][2],

520 int64_t prev[2][2]);

521 bool LoadAndCheckDest(int pair, int node, int64_t base_node,

522 int64_t nodes[2][2], int64_t dest[2][2]) const;

523

524 static constexpr int kFirstPairFirstNode = 0;

525 static constexpr int kSecondPairFirstNode = 1;

526 static constexpr int kFirstPairFirstNodeDestination = 2;

527 static constexpr int kFirstPairSecondNodeDestination = 3;

528 static constexpr int kSecondPairFirstNodeDestination = 4;

529 static constexpr int kSecondPairSecondNodeDestination = 5;

530};

531

533 Solver* solver, const std::vector<IntVar*>& vars,

534 const std::vector<IntVar*>& secondary_vars,

535 std::function<int(int64_t)> start_empty_path_class,

536 const std::vector<PickupDeliveryPair>& pairs);

537

549 public:

551 const std::vector<IntVar*>& path_vars,

552 const std::vector<PickupDeliveryPair>& pairs);

554

557 std::string DebugString() const override { return "SwapIndexPairOperator"; }

558

559 private:

562 bool UpdateActiveNodes();

564 void SetNext(int64_t from, int64_t to, int64_t path) {

565 DCHECK_LT(from, number_of_nexts_);

567 if (!ignore_path_vars_) {

568 DCHECK_LT(from + number_of_nexts_, Size());

569 SetValue(from + number_of_nexts_, path);

570 }

571 }

572

573 const std::vector<PickupDeliveryPair> pairs_;

574 int pair_index_;

575 int first_index_;

576 int second_index_;

577 int64_t first_active_;

578 int64_t second_active_;

579 std::vector<int64_t> prevs_;

580 const int number_of_nexts_;

581 const bool ignore_path_vars_;

582};

583

586template <bool ignore_path_vars>

588 public:

590 const std::vector<IntVar*>& vars,

591 const std::vector<IntVar*>& secondary_vars,

592 std::function<int(int64_t)> start_empty_path_class,

593 const std::vector<PickupDeliveryPair>& pairs);

595

599 return "IndexPairSwapActiveOperator";

600 }

601

602 private:

604

605 int inactive_node_;

606};

607

609 Solver* solver, const std::vector<IntVar*>& vars,

610 const std::vector<IntVar*>& secondary_vars,

611 std::function<int(int64_t)> start_empty_path_class,

612 const std::vector<PickupDeliveryPair>& pairs);

613

621template <bool ignore_path_vars>

622class RelocateExpensiveChain : public PathOperator<ignore_path_vars> {

623 public:

625 const std::vector<IntVar*>& secondary_vars,

626 std::function<int(int64_t)> start_empty_path_class,

627 int num_arcs_to_consider,

628 std::function<int64_t(int64_t, int64_t, int64_t)>

629 arc_cost_for_path_start);

631

634

635 std::string DebugString() const override { return "RelocateExpensiveChain"; }

636

639 void IncrementCurrentPath();

640 bool IncrementCurrentArcIndices();

644 bool FindMostExpensiveChainsOnRemainingPaths();

645

646 int num_arcs_to_consider_;

647 int current_path_;

648 std::vector<std::pair<int64_t, int>> most_expensive_arc_starts_and_ranks_;

651 std::pair< int, int>

652 current_expensive_arc_indices_;

653 std::function<int64_t( int64_t, int64_t,

654 int64_t)>

655 arc_cost_for_path_start_;

656 int end_path_;

659 bool has_non_empty_paths_to_explore_;

660};

661

663 Solver* solver, const std::vector<IntVar*>& vars,

664 const std::vector<IntVar*>& secondary_vars,

665 std::function<int(int64_t)> start_empty_path_class,

666 int num_arcs_to_consider,

667 std::function<int64_t(int64_t, int64_t, int64_t)> arc_cost_for_path_start);

668

676template <bool swap_first, bool ignore_path_vars>

678 public:

680 const std::vector<IntVar*>& secondary_vars,

681 std::function<int(int64_t)> start_empty_path_class,

682 const std::vector<PickupDeliveryPair>& pairs);

684

687 std::string DebugString() const override {

688 return "PairNodeSwapActiveOperator";

694

695 return true;

696 }

697

699

703

706

707 int inactive_pair_;

708 std::vector<PickupDeliveryPair> pairs_;

709};

710

711

712

713

714template <bool swap_first, bool ignore_path_vars>

717 const std::vector<IntVar*>& vars,

718 const std::vector<IntVar*>& secondary_vars,

719 std::function<int(int64_t)> start_empty_path_class,

720 const std::vector<PickupDeliveryPair>& pairs)

721 : PathOperator<ignore_path_vars>(vars, secondary_vars, 2, false, false,

722 std::move(start_empty_path_class), nullptr,

723 nullptr),

724 inactive_pair_(0),

725 pairs_(pairs) {}

726

727template <bool swap_first, bool ignore_path_vars>

729 swap_first, ignore_path_vars>::GetBaseNodeRestartPosition(int base_index) {

730

731 if (base_index == 0 ||

733 return this->StartNode(base_index);

734 } else {

735 return this->BaseNode(base_index - 1);

736 }

737}

738

739template <bool swap_first, bool ignore_path_vars>

741 ignore_path_vars>::OnNodeInitialization() {

742 for (int i = 0; i < pairs_.size(); ++i) {

743 if (this->IsInactive(pairs_[i].pickup_alternatives[0]) &&

744 this->IsInactive(pairs_[i].delivery_alternatives[0])) {

745 inactive_pair_ = i;

746 return;

747 }

748 }

749 inactive_pair_ = pairs_.size();

750}

751

752template <bool swap_first, bool ignore_path_vars>

755 while (inactive_pair_ < pairs_.size()) {

756 if (!this->IsInactive(pairs_[inactive_pair_].pickup_alternatives[0]) ||

757 !this->IsInactive(pairs_[inactive_pair_].delivery_alternatives[0]) ||

760 ++inactive_pair_;

761 } else {

762 return true;

763 }

764 }

765 return false;

766}

767

768template <bool swap_first, bool ignore_path_vars>

770 const int64_t base = this->BaseNode(0);

771 if (this->IsPathEnd(base)) {

772 return false;

773 }

774 const int64_t pair_first = pairs_[inactive_pair_].pickup_alternatives[0];

775 const int64_t pair_second = pairs_[inactive_pair_].delivery_alternatives[0];

776 if (swap_first) {

777 return this->MakeActive(pair_second, this->BaseNode(1)) &&

780 } else {

781 return this->MakeActive(pair_second, this->BaseNode(1)) &&

782 this->MakeActive(pair_first, base) &&

784 }

785}

786

787template <bool swap_first>

789 Solver* solver, const std::vector<IntVar*>& vars,

790 const std::vector<IntVar*>& secondary_vars,

791 std::function<int(int64_t)> start_empty_path_class,

792 const std::vector<PickupDeliveryPair>& pairs) {

793 if (secondary_vars.empty()) {

795 vars, secondary_vars, std::move(start_empty_path_class), pairs));

796 }

798 vars, secondary_vars, std::move(start_empty_path_class), pairs));

799}

800

802class PickupAndDeliveryData {

803 public:

805 absl::Span<const PickupDeliveryPair> pairs);

807 DCHECK_LT(node, is_pickup_node_.size());

808 return is_pickup_node_[node];

811 DCHECK_LT(node, is_delivery_node_.size());

812 return is_delivery_node_[node];

815 DCHECK_LT(node, pair_of_node_.size());

816 return pair_of_node_[node];

818

819 private:

820 std::vector<bool> is_pickup_node_;

821 std::vector<bool> is_delivery_node_;

822 std::vector<int> pair_of_node_;

823};

824

827

836template <bool ignore_path_vars>

837class RelocateSubtrip : public PathOperator<ignore_path_vars> {

838 public:

840 const std::vector<IntVar*>& vars,

841 const std::vector<IntVar*>& secondary_vars,

842 std::function<int(int64_t)> start_empty_path_class,

843 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

844 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

845 absl::Span<const PickupDeliveryPair> pairs);

846

847 std::string DebugString() const override { return "RelocateSubtrip"; }

849

850 private:

851

852 bool RelocateSubTripFromPickup(int64_t chain_first_node,

853 int64_t insertion_node);

855 bool RelocateSubTripFromDelivery(int64_t chain_last_node,

856 int64_t insertion_node);

857 void SetPath(absl::Span<const int64_t> path, int path_id);

858

860

861

862

863 std::vector<bool> opened_pairs_set_;

864

865 std::vector<int64_t> rejected_nodes_;

866 std::vector<int64_t> subtrip_nodes_;

867};

868

870 Solver* solver, const std::vector<IntVar*>& vars,

871 const std::vector<IntVar*>& secondary_vars,

872 std::function<int(int64_t)> start_empty_path_class,

873 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

874 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

875 absl::Span<const PickupDeliveryPair> pairs);

876

878 Solver* solver, const std::vector<IntVar*>& vars,

879 const std::vector<IntVar*>& secondary_vars,

880 std::function<int(int64_t)> start_empty_path_class,

881 absl::Span<const PickupDeliveryPair> pairs);

882

883template <bool ignore_path_vars>

885 public:

887 const std::vector<IntVar*>& vars,

888 const std::vector<IntVar*>& secondary_vars,

889 std::function<int(int64_t)> start_empty_path_class,

890 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

891 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

892 absl::Span<const PickupDeliveryPair> pairs);

893

894 std::string DebugString() const override { return "ExchangeSubtrip"; }

896

897 private:

898

899

900

901

902

903

904

905

906 bool ExtractChainsAndCheckCanonical(int64_t base_node,

907 std::vector<int64_t>* rejects,

908 std::vector<int64_t>* subtrip);

909

910

911

912

913

914 bool ExtractChainsFromPickup(int64_t base_node, std::vector<int64_t>* rejects,

915 std::vector<int64_t>* subtrip);

916

917

918

919

920

921 bool ExtractChainsFromDelivery(int64_t base_node,

922 std::vector<int64_t>* rejects,

923 std::vector<int64_t>* subtrip);

924 void SetPath(absl::Span<const int64_t> path, int path_id);

925

927

928 std::vector<bool> opened_pairs_set_;

929

930 std::vector<int64_t> rejects0_;

931 std::vector<int64_t> subtrip0_;

932 std::vector<int64_t> rejects1_;

933 std::vector<int64_t> subtrip1_;

934 std::vector<int64_t> path0_;

935 std::vector<int64_t> path1_;

936};

937

939 Solver* solver, const std::vector<IntVar*>& vars,

940 const std::vector<IntVar*>& secondary_vars,

941 std::function<int(int64_t)> start_empty_path_class,

942 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

943 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,

944 absl::Span<const PickupDeliveryPair> pairs);

945

947 Solver* solver, const std::vector<IntVar*>& vars,

948 const std::vector<IntVar*>& secondary_vars,

949 std::function<int(int64_t)> start_empty_path_class,

950 absl::Span<const PickupDeliveryPair> pairs);

951

952}

953

954#endif

bool MakeNeighbor() override

std::string DebugString() const override

Definition routing_neighborhoods.h:898

ExchangeSubtrip(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, absl::Span< const PickupDeliveryPair > pairs)

std::string DebugString() const override

Definition routing_neighborhoods.h:373

GroupPairAndRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, const std::vector< PickupDeliveryPair > &pairs)

bool MakeNeighbor() override

~GroupPairAndRelocateOperator() override=default

IndexPairSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

bool MakeNeighbor() override

bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override

std::string DebugString() const override

Definition routing_neighborhoods.h:598

~IndexPairSwapActiveOperator() override=default

void SetValue(int64_t index, int64_t value)

IntVarLocalSearchOperator(const std::vector< IntVar * > &vars, bool keep_inverse_values=false)

~LightPairRelocateOperator() override=default

LightPairRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, const std::vector< PickupDeliveryPair > &pairs, std::function< bool(int64_t)> force_lifo=nullptr)

std::string DebugString() const override

Definition routing_neighborhoods.h:415

bool MakeNeighbor() override

The base class for all local search operators.

virtual bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta)=0

bool MakeOneNeighbor() override

MakeNextNeighbor() in a subclass of IntVarLocalSearchOperator.

bool OnSamePathAsPreviousBase(int64_t) override

it's currently way more complicated to implement.

Definition routing_neighborhoods.h:265

MakePairActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

std::string DebugString() const override

Definition routing_neighborhoods.h:261

~MakePairActiveOperator() override=default

bool RestartAtPathStartOnSynchronize() override

Definition routing_neighborhoods.h:275

bool MakeNeighbor() override

int64_t GetBaseNodeRestartPosition(int base_index) override

MakePairInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

std::string DebugString() const override

Definition routing_neighborhoods.h:304

bool MakeNeighbor() override

~MakeRelocateNeighborsOperator() override=default

std::string DebugString() const override

Definition routing_neighborhoods.h:69

MakeRelocateNeighborsOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, RoutingTransitCallback2 arc_evaluator)

PairExchangeOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, const std::vector< PickupDeliveryPair > &pairs)

bool MakeNeighbor() override

std::string DebugString() const override

Definition routing_neighborhoods.h:458

~PairExchangeOperator() override=default

int64_t GetBaseNodeRestartPosition(int base_index) override

PairExchangeRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

bool MakeNeighbor() override

std::string DebugString() const override

Definition routing_neighborhoods.h:507

bool OnSamePathAsPreviousBase(int64_t base_index) override

it's currently way more complicated to implement.

~PairExchangeRelocateOperator() override=default

bool RestartAtPathStartOnSynchronize() override

Definition routing_neighborhoods.h:704

bool MakeNeighbor() override

Definition routing_neighborhoods.h:772

bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override

Definition routing_neighborhoods.h:756

std::string DebugString() const override

Definition routing_neighborhoods.h:689

PairNodeSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

Definition routing_neighborhoods.h:719

int64_t GetBaseNodeRestartPosition(int base_index) override

Definition routing_neighborhoods.h:732

~PairNodeSwapActiveOperator() override=default

bool OnSamePathAsPreviousBase(int64_t) override

it's currently way more complicated to implement.

Definition routing_neighborhoods.h:694

PairRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

bool OnSamePathAsPreviousBase(int64_t base_index) override

it's currently way more complicated to implement.

Definition routing_neighborhoods.h:334

bool ConsiderAlternatives(int64_t base_index) const override

Definition routing_neighborhoods.h:340

std::string DebugString() const override

Definition routing_neighborhoods.h:331

~PairRelocateOperator() override=default

int64_t GetBaseNodeRestartPosition(int base_index) override

bool MakeNeighbor() override

virtual void ResetIncrementalism()

virtual void OnNodeInitialization()

PathOperator(const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, IterationParameters iteration_parameters)

Builds an instance of PathOperator from next and path variables.

virtual bool RestartAtPathStartOnSynchronize()

bool IsInactive(int64_t node) const

Returns true if node is inactive.

int64_t StartNode(int i) const

Returns the start node of the ith base node.

int64_t BaseNode(int i) const

Returns the ith base node of the operator.

A utility class to maintain pickup and delivery information of nodes.

Definition routing_neighborhoods.h:805

int GetPairOfNode(int64_t node) const

Definition routing_neighborhoods.h:817

PickupAndDeliveryData(int num_nodes, absl::Span< const PickupDeliveryPair > pairs)

bool IsDeliveryNode(int64_t node) const

Definition routing_neighborhoods.h:813

bool IsPickupNode(int64_t node) const

Definition routing_neighborhoods.h:809

RelocateExpensiveChain(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int num_arcs_to_consider, std::function< int64_t(int64_t, int64_t, int64_t)> arc_cost_for_path_start)

~RelocateExpensiveChain() override=default

bool MakeOneNeighbor() override

This method should not be overridden. Override MakeNeighbor() instead.

bool MakeNeighbor() override

std::string DebugString() const override

Definition routing_neighborhoods.h:637

bool MakeNeighbor() override

std::string DebugString() const override

Definition routing_neighborhoods.h:851

RelocateSubtrip(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, absl::Span< const PickupDeliveryPair > pairs)

bool HasAlternatives(int node) const

absl::Span< const int64_t > GetShortestPath(int64_t source, int64_t sink, absl::Span< const int64_t > chain)

ShortestPathOnAlternatives(int num_nodes, std::vector< std::vector< int64_t > > alternative_sets, RoutingTransitCallback2 arc_evaluator)

std::string DebugString() const override

Definition routing_neighborhoods.h:213

bool MakeNeighbor() override

SwapActiveToShortestPathOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::vector< std::vector< int64_t > > alternative_sets, RoutingTransitCallback2 arc_evaluator)

~SwapActiveToShortestPathOperator() override=default

SwapIndexPairOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &path_vars, const std::vector< PickupDeliveryPair > &pairs)

~SwapIndexPairOperator() override=default

std::string DebugString() const override

Definition routing_neighborhoods.h:557

bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override

~TwoOptWithShortestPathOperator() override=default

bool RestartAtPathStartOnSynchronize() override

Definition routing_neighborhoods.h:156

bool OnSamePathAsPreviousBase(int64_t) override

it's currently way more complicated to implement.

Definition routing_neighborhoods.h:148

int64_t GetBaseNodeRestartPosition(int base_index) override

Definition routing_neighborhoods.h:152

std::string DebugString() const override

Definition routing_neighborhoods.h:145

bool MakeNeighbor() override

TwoOptWithShortestPathOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::vector< std::vector< int64_t > > alternative_sets, RoutingTransitCallback2 arc_evaluator)

LocalSearchOperator * MakePairNodeSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

Definition routing_neighborhoods.h:791

LocalSearchOperator * MakeExchangeSubtrip(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, absl::Span< const PickupDeliveryPair > pairs)

LocalSearchOperator * MakePairActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

LocalSearchOperator * MakeLightPairRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, const std::vector< PickupDeliveryPair > &pairs, std::function< bool(int64_t)> force_lifo)

LocalSearchOperator * MakePairExchangeRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

LocalSearchOperator * MakeGroupPairAndRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, const std::vector< PickupDeliveryPair > &pairs)

LocalSearchOperator * MakePairInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

LocalSearchOperator * MakePairRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

LocalSearchOperator * MakeSwapActiveToShortestPath(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::vector< std::vector< int64_t > > alternative_sets, RoutingTransitCallback2 arc_evaluator)

LocalSearchOperator * MakeRelocateExpensiveChain(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int num_arcs_to_consider, std::function< int64_t(int64_t, int64_t, int64_t)> arc_cost_for_path_start)

LocalSearchOperator * MakeIndexPairSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const std::vector< PickupDeliveryPair > &pairs)

LocalSearchOperator * MakeChainInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

--— MakeChainInactive --—

LocalSearchOperator * MakeRelocateSubtrip(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, absl::Span< const PickupDeliveryPair > pairs)

LocalSearchOperator * MakeTwoOptWithShortestPath(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::vector< std::vector< int64_t > > alternative_sets, RoutingTransitCallback2 arc_evaluator)

std::function< int64_t(int64_t, int64_t)> RoutingTransitCallback2

LocalSearchOperator * MakeRelocateNeighbors(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, RoutingTransitCallback2 arc_evaluator)

LocalSearchOperator * MakePairExchange(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors, const std::vector< PickupDeliveryPair > &pairs)

LocalSearchOperator * MakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)

--— MakeActive --—

trees with all degrees equal to