| 16 | } // namespace |
| 17 | |
| 18 | pyvrp::Cost SwapTails::evaluate(Route::Node *U, |
| 19 | Route::Node *V, |
| 20 | CostEvaluator const &costEvaluator) |
| 21 | { |
| 22 | stats_.numEvaluations++; |
| 23 | assert(!U->isEndDepot() && !U->isReloadDepot()); |
| 24 | assert(!V->isEndDepot() && !V->isReloadDepot()); |
| 25 | |
| 26 | auto const *uRoute = U->route(); |
| 27 | auto const *vRoute = V->route(); |
| 28 | |
| 29 | if (uRoute == vRoute) |
| 30 | return 0; // same route |
| 31 | |
| 32 | if (uRoute->idx() > vRoute->idx() && !uRoute->empty() && !vRoute->empty()) |
| 33 | return 0; // move will be tackled in a later iteration |
| 34 | |
| 35 | if (!onLastTrip(U) || !onLastTrip(V)) |
| 36 | // We cannot move reload depots, so we only evaluate a move if it does |
| 37 | // not include a reload depot. |
| 38 | return 0; |
| 39 | |
| 40 | Cost deltaCost = 0; |
| 41 | |
| 42 | // We're going to incur fixed cost if a route is currently empty but |
| 43 | // becomes non-empty due to the proposed move. |
| 44 | if (uRoute->empty() && !n(V)->isEndDepot()) |
| 45 | deltaCost += uRoute->fixedVehicleCost(); |
| 46 | |
| 47 | if (vRoute->empty() && !n(U)->isEndDepot()) |
| 48 | deltaCost += vRoute->fixedVehicleCost(); |
| 49 | |
| 50 | // We lose fixed cost if a route becomes empty due to the proposed move. |
| 51 | if (!uRoute->empty() && U->isStartDepot() && n(V)->isEndDepot()) |
| 52 | deltaCost -= uRoute->fixedVehicleCost(); |
| 53 | |
| 54 | if (!vRoute->empty() && V->isStartDepot() && n(U)->isEndDepot()) |
| 55 | deltaCost -= vRoute->fixedVehicleCost(); |
| 56 | |
| 57 | if (!n(U)->isEndDepot() && !n(V)->isEndDepot()) |
| 58 | { |
| 59 | auto const uProposal |
| 60 | = Route::Proposal(uRoute->before(U->idx()), |
| 61 | vRoute->between(V->idx() + 1, vRoute->size() - 2), |
| 62 | uRoute->at(uRoute->size() - 1)); |
| 63 | |
| 64 | auto const vProposal |
| 65 | = Route::Proposal(vRoute->before(V->idx()), |
| 66 | uRoute->between(U->idx() + 1, uRoute->size() - 2), |
| 67 | vRoute->at(vRoute->size() - 1)); |
| 68 | |
| 69 | costEvaluator.deltaCost(deltaCost, uProposal, vProposal); |
| 70 | } |
| 71 | else if (!n(U)->isEndDepot() && n(V)->isEndDepot()) |
| 72 | { |
| 73 | auto const uProposal = Route::Proposal(uRoute->before(U->idx()), |
| 74 | uRoute->at(uRoute->size() - 1)); |
| 75 | |