| 132 | } |
| 133 | |
| 134 | bool Solution::insert(Route::Node *U, |
| 135 | SearchSpace const &searchSpace, |
| 136 | CostEvaluator const &costEvaluator, |
| 137 | bool required) |
| 138 | { |
| 139 | assert(size_t(std::distance(nodes.data(), U)) < nodes.size()); |
| 140 | |
| 141 | Route::Node *UAfter = routes[0][0]; // fallback option |
| 142 | auto bestCost = insertCost(U, UAfter, data_, costEvaluator); |
| 143 | |
| 144 | // First attempt a neighbourhood search to place U into routes that are |
| 145 | // already in use. |
| 146 | for (auto const vClient : searchSpace.neighboursOf(U->client())) |
| 147 | { |
| 148 | auto *V = &nodes[vClient]; |
| 149 | |
| 150 | if (!V->route()) |
| 151 | continue; |
| 152 | |
| 153 | auto const cost = insertCost(U, V, data_, costEvaluator); |
| 154 | if (cost < bestCost) |
| 155 | { |
| 156 | bestCost = cost; |
| 157 | UAfter = V; |
| 158 | } |
| 159 | } |
| 160 | |
| 161 | // Next consider empty routes, of each vehicle type. We insert into the |
| 162 | // first improving route. |
| 163 | for (auto const &[vehType, offset] : searchSpace.vehTypeOrder()) |
| 164 | { |
| 165 | auto const begin = routes.begin() + offset; |
| 166 | auto const end = begin + data_.vehicleType(vehType).numAvailable; |
| 167 | auto const pred = [](auto const &route) { return route.empty(); }; |
| 168 | auto empty = std::find_if(begin, end, pred); |
| 169 | |
| 170 | if (empty == end) |
| 171 | continue; |
| 172 | |
| 173 | auto const cost = insertCost(U, (*empty)[0], data_, costEvaluator); |
| 174 | if (cost < bestCost) |
| 175 | { |
| 176 | bestCost = cost; |
| 177 | UAfter = (*empty)[0]; |
| 178 | break; |
| 179 | } |
| 180 | } |
| 181 | |
| 182 | if (required || bestCost < 0) |
| 183 | { |
| 184 | auto *route = UAfter->route(); |
| 185 | route->insert(UAfter->idx() + 1, U); |
| 186 | return true; |
| 187 | } |
| 188 | |
| 189 | return false; |
| 190 | } |