| 276 | } |
| 277 | |
| 278 | void LocalSearch::applyOptionalClientMoves(Route::Node *U, |
| 279 | CostEvaluator const &costEvaluator) |
| 280 | { |
| 281 | ProblemData::Client const &uData = data.location(U->client()); |
| 282 | |
| 283 | if (uData.required && !U->route()) // then we must insert U |
| 284 | { |
| 285 | solution_.insert(U, searchSpace_, costEvaluator, true); |
| 286 | update(U->route(), U->route()); |
| 287 | searchSpace_.markPromising(U); |
| 288 | } |
| 289 | |
| 290 | // Required clients are not optional, and have just been inserted above |
| 291 | // if not already in the solution. Groups have their own operator and are |
| 292 | // not processed here. |
| 293 | if (uData.required || uData.group) |
| 294 | return; |
| 295 | |
| 296 | if (removeCost(U, data, costEvaluator) < 0) // remove if improving |
| 297 | { |
| 298 | searchSpace_.markPromising(U); |
| 299 | auto *route = U->route(); |
| 300 | route->remove(U->idx()); |
| 301 | update(route, route); |
| 302 | } |
| 303 | |
| 304 | if (U->route()) |
| 305 | return; |
| 306 | |
| 307 | // Attempt to re-insert U using a first-improving neighbourhood search. |
| 308 | for (auto const vClient : searchSpace_.neighboursOf(U->client())) |
| 309 | { |
| 310 | auto *V = &solution_.nodes[vClient]; |
| 311 | auto *route = V->route(); |
| 312 | |
| 313 | if (!route) |
| 314 | continue; |
| 315 | |
| 316 | if (insertCost(U, V, data, costEvaluator) < 0) // insert if improving |
| 317 | { |
| 318 | route->insert(V->idx() + 1, U); |
| 319 | update(route, route); |
| 320 | searchSpace_.markPromising(U); |
| 321 | return; |
| 322 | } |
| 323 | |
| 324 | // We prefer inserting over replacing, but if V is not required, not in |
| 325 | // a group, and replacing V with U is improving, we also do that now. |
| 326 | ProblemData::Client const &vData = data.location(V->client()); |
| 327 | if (!vData.required && !vData.group |
| 328 | && inplaceCost(U, V, data, costEvaluator) < 0) |
| 329 | { |
| 330 | searchSpace_.markPromising(V); |
| 331 | auto const idx = V->idx(); |
| 332 | route->remove(idx); |
| 333 | route->insert(idx, U); |
| 334 | update(route, route); |
| 335 | searchSpace_.markPromising(U); |