1

2

3

4

5

6

7

8

9

10

11

12

13

14#include <math.h>

15

16#include <algorithm>

17#include <cstdint>

18#include <functional>

19#include <limits>

20#include <utility>

21#include <vector>

22

23#include "absl/algorithm/container.h"

24#include "absl/container/flat_hash_map.h"

25#include "absl/container/flat_hash_set.h"

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

35

37

38namespace {

39

40template <typename Disjunctions>

41void AddDisjunctionsFromNodes(const RoutingModel& model,

42 absl::Span<const int64_t> nodes,

43 Disjunctions* disjunctions) {

44 for (int64_t node : nodes) {

45 for (const auto disjunction : model.GetDisjunctionIndices(node)) {

46 disjunctions->insert(disjunction);

47 }

48 }

49}

50}

51

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

150

151bool RoutingModel::SolveMatchingModel(

154

155

156 return false;

157 }

158 VLOG(2) << "Solving with flow";

159 assignment->Clear();

160

161

162

163

164 const std::vector<RoutingDimension*> dimensions =

166 std::vector<LocalDimensionCumulOptimizer> optimizers;

167 optimizers.reserve(dimensions.size());

169 optimizers.emplace_back(

171 }

172

173 int num_flow_nodes = 0;

174 std::vector<std::vector<int64_t>> disjunction_to_flow_nodes;

175 std::vector<int64_t> disjunction_penalties;

176 std::vector<bool> in_disjunction(Size(), false);

177

178

179

180 absl::flat_hash_map<int, std::pair<int64_t, int64_t>> flow_to_pd;

182 disjunction_to_flow_nodes.push_back({});

183 absl::flat_hash_set<DisjunctionIndex> disjunctions;

184 AddDisjunctionsFromNodes(*this, pickups, &disjunctions);

185 AddDisjunctionsFromNodes(*this, deliveries, &disjunctions);

186 for (int64_t pickup : pickups) {

187 in_disjunction[pickup] = true;

188 for (int64_t delivery : deliveries) {

189 in_disjunction[delivery] = true;

190 flow_to_pd[num_flow_nodes] = {pickup, delivery};

191 disjunction_to_flow_nodes.back().push_back(num_flow_nodes);

192 num_flow_nodes++;

193 }

194 }

195 DCHECK_LE(disjunctions.size(), 2);

196 int64_t penalty = 0;

197 if (disjunctions.size() < 2) {

199 } else {

204 break;

205 }

206 penalty = CapAdd(penalty, d_penalty);

207 }

208 }

209 disjunction_penalties.push_back(penalty);

210 }

211

212 absl::flat_hash_map<int, int64_t> flow_to_non_pd;

213 for (int node = 0; node < Size(); ++node) {

214 if (IsStart(node) || in_disjunction[node]) continue;

215 const std::vector<DisjunctionIndex>& disjunctions =

217 DCHECK_LE(disjunctions.size(), 1);

218 disjunction_to_flow_nodes.push_back({});

219 disjunction_penalties.push_back(

222 if (disjunctions.empty()) {

223 in_disjunction[node] = true;

224 flow_to_non_pd[num_flow_nodes] = node;

225 disjunction_to_flow_nodes.back().push_back(num_flow_nodes);

226 num_flow_nodes++;

227 } else {

229 in_disjunction[n] = true;

230 flow_to_non_pd[num_flow_nodes] = n;

231 disjunction_to_flow_nodes.back().push_back(num_flow_nodes);

232 num_flow_nodes++;

233 }

234 }

235 }

236

237 std::vector<FlowArc> arcs;

238

239

240

241

242 absl::flat_hash_map<int, int> flow_to_disjunction;

243 for (int i = 0; i < disjunction_to_flow_nodes.size(); ++i) {

244 const std::vector<int64_t>& flow_nodes = disjunction_to_flow_nodes[i];

245 if (flow_nodes.size() == 1) {

246 flow_to_disjunction[flow_nodes.back()] = i;

247 } else {

248 flow_to_disjunction[num_flow_nodes] = i;

249 for (int64_t flow_node : flow_nodes) {

250 arcs.push_back({flow_node, num_flow_nodes, 1, 0});

251 }

252 num_flow_nodes++;

253 }

254 }

255

256

257

258

259

260

261 std::vector<int> vehicle_to_flow;

262 absl::flat_hash_map<int, int> flow_to_vehicle;

263 for (int vehicle = 0; vehicle < vehicles(); ++vehicle) {

264 const int64_t start = Start(vehicle);

265 const int64_t end = End(vehicle);

266 for (const std::vector<int64_t>& flow_nodes : disjunction_to_flow_nodes) {

267 for (int64_t flow_node : flow_nodes) {

268 std::pair<int64_t, int64_t> pd_pair;

269 int64_t node = -1;

270 int64_t cost = 0;

271 bool add_arc = false;

272 if (gtl::FindCopy(flow_to_pd, flow_node, &pd_pair)) {

273 const int64_t pickup = pd_pair.first;

274 const int64_t delivery = pd_pair.second;

277 add_arc = true;

278 cost =

282 const absl::flat_hash_map<int64_t, int64_t> nexts = {

283 {start, pickup}, {pickup, delivery}, {delivery, end}};

284 for (LocalDimensionCumulOptimizer& optimizer : optimizers) {

285 int64_t cumul_cost_value = 0;

286

287

288 if (optimizer.ComputeRouteCumulCostWithoutFixedTransits(

289 vehicle, 1.0,

290 [&nexts](int64_t node) {

291 return nexts.find(node)->second;

292 },

293 nullptr, &cumul_cost_value) !=

295 cost = CapAdd(cost, cumul_cost_value);

296 } else {

297 add_arc = false;

298 break;

299 }

300 }

301 }

302 } else if (gtl::FindCopy(flow_to_non_pd, flow_node, &node)) {

304 add_arc = true;

307 const absl::flat_hash_map<int64_t, int64_t> nexts = {{start, node},

308 {node, end}};

309 for (LocalDimensionCumulOptimizer& optimizer : optimizers) {

310 int64_t cumul_cost_value = 0;

311

312

313 if (optimizer.ComputeRouteCumulCostWithoutFixedTransits(

314 vehicle, 1.0,

315 [&nexts](int64_t node) {

316 return nexts.find(node)->second;

317 },

318 nullptr, &cumul_cost_value) !=

320 cost = CapAdd(cost, cumul_cost_value);

321 } else {

322 add_arc = false;

323 break;

324 }

325 }

326 }

327 } else {

328 DCHECK(false);

329 }

330 if (add_arc) {

331 arcs.push_back({num_flow_nodes, flow_node, 1, cost});

332 }

333 }

334 }

335 flow_to_vehicle[num_flow_nodes] = vehicle;

336 vehicle_to_flow.push_back(num_flow_nodes);

337 num_flow_nodes++;

338 }

339

340 const int source = num_flow_nodes + 1;

341 const int sink = source + 1;

342

343 for (int vehicle = 0; vehicle < vehicles(); ++vehicle) {

344 arcs.push_back({source, vehicle_to_flow[vehicle], 1, 0});

345 }

346

347

348 const int unperformed = num_flow_nodes;

349 const int64_t flow_supply = disjunction_to_flow_nodes.size();

350 arcs.push_back({source, unperformed, flow_supply, 0});

351 for (const auto& flow_disjunction_element : flow_to_disjunction) {

352 const int flow_node = flow_disjunction_element.first;

353 const int64_t penalty =

354 disjunction_penalties[flow_disjunction_element.second];

356 arcs.push_back({unperformed, flow_node, 1, penalty});

357 }

358

359 arcs.push_back({flow_node, sink, 1, 0});

360 }

361

362

363

364

365

366 int64_t scale_factor = 1;

367 const FlowArc& arc_with_max_cost = *std::max_element(

368 arcs.begin(), arcs.end(),

369 [](const FlowArc& a, const FlowArc& b) { return a.cost < b.cost; });

370

371

372 const int actual_flow_num_nodes = num_flow_nodes + 3;

373 if (log(static_cast<double>(arc_with_max_cost.cost) + 1) +

374 2 * log(actual_flow_num_nodes) >

375 log(std::numeric_limits<int64_t>::max())) {

376 scale_factor = CapProd(actual_flow_num_nodes, actual_flow_num_nodes);

377 }

378

379 SimpleMinCostFlow flow;

380

381 for (const FlowArc& arc : arcs) {

382 flow.AddArcWithCapacityAndUnitCost(arc.tail, arc.head, arc.capacity,

383 arc.cost / scale_factor);

384 }

385

386

387 flow.SetNodeSupply(source, flow_supply);

388 flow.SetNodeSupply(sink, -flow_supply);

389

390

391 search_stats_.num_min_cost_flow_calls++;

393 return false;

394 }

395

396

397 std::vector<bool> used_vehicles(vehicles(), false);

398 absl::flat_hash_set<int> used_nodes;

399 for (int i = 0; i < flow.NumArcs(); ++i) {

400 if (flow.Flow(i) > 0 && flow.Tail(i) != source && flow.Head(i) != sink) {

401 std::vector<int> nodes;

402 std::pair<int64_t, int64_t> pd_pair;

403 int node = -1;

404 int index = -1;

405 if (gtl::FindCopy(flow_to_pd, flow.Head(i), &pd_pair)) {

406 nodes.push_back(pd_pair.first);

407 nodes.push_back(pd_pair.second);

408 } else if (gtl::FindCopy(flow_to_non_pd, flow.Head(i), &node)) {

409 nodes.push_back(node);

410 } else if (gtl::FindCopy(flow_to_disjunction, flow.Head(i), &index)) {

411 for (int64_t flow_node : disjunction_to_flow_nodes[index]) {

412 if (gtl::FindCopy(flow_to_pd, flow_node, &pd_pair)) {

413 nodes.push_back(pd_pair.first);

414 nodes.push_back(pd_pair.second);

415 } else if (gtl::FindCopy(flow_to_non_pd, flow_node, &node)) {

416 nodes.push_back(node);

417 }

418 }

419 }

420 int vehicle = -1;

421 if (flow.Tail(i) == unperformed) {

422

423 for (int node : nodes) {

425 used_nodes.insert(node);

426 }

427 } else if (gtl::FindCopy(flow_to_vehicle, flow.Tail(i), &vehicle)) {

428

429 used_vehicles[vehicle] = true;

430 int current = Start(vehicle);

431 for (int node : nodes) {

433 used_nodes.insert(node);

434 current = node;

435 }

437 }

438 }

439 }

440

441 for (int node = 0; node < Size(); ++node) {

442 if (!IsStart(node) && used_nodes.count(node) == 0) {

444 }

445 }

446

447 for (int vehicle = 0; vehicle < vehicles(); ++vehicle) {

448 if (!used_vehicles[vehicle]) {

450 }

451 }

452 return true;

453}

454

455}