On second thoughts, we can't just keep the old amount values for jobs because it does not allow to model a situation where there are both pickups and deliveries at the same job.

Example: say we have a delivery of 6 and a pickup of 5 (whatever metric) for a given job. We'd have to just pass the delta in the job amount as 1, but we'd then be loosing mandatory information for capacity checks. The vehicle need to have enough room for a 6 delivery from the start up to that job, and enough room for a 5 pickup from that job on to the end of its route...

Solution: add two pickup and delivery keys at job level and deprecate amount keys in both input and output. To maintain previous behaviour before deprecation is effective, we'll probably have to treat an amount as a delivery with an empty pickup.

More on point 4 from previous comment. I've been profiling executions with perf and doing some flame graphs on Solomon instance R203 at 42e901b (parent commit in master for this PR) and 4d46ca4 (current PR HEAD):

• 42e901b_R203.svg
• 4d46ca4_R203.svg

I'm puzzled by:

• the huge depth of the second one compared to the first, this looks wrong
• the fact that we see a lot of malloc and cfree@GLIBC_2.2.5 stuff appearing in the global view
• the changes observed when browsing to e.g. vroom::vrptw::CrossExchange::is_valid in both graphs. The one for 42e901b is totally expected (the usual TW checks with helper function, plus the calls to vroom::cvrp::CrossExchange::is_valid that consist mostly in operator<= checks for amounts). On the other hand for 4d46ca4, vroom::cvrp::CrossExchange::is_valid has a lot of stuff I don't get on top of the expected vroom::RawRoute::* checks, including some cfree, malloc, operator new, delete, etc.

The place where the latest start showing off is at f16aa71, the first check update:

$ git diff f16aa71~ f16aa71
diff --git a/src/problems/cvrp/operators/exchange.cpp b/src/problems/cvrp/operators/exchange.cpp
index 4f2a611..726a150 100644
--- a/src/problems/cvrp/operators/exchange.cpp
+++ b/src/problems/cvrp/operators/exchange.cpp
@@ -115,13 +115,19 @@ bool Exchange::is_valid() {
   bool valid = _input.vehicle_ok_with_job(t_vehicle, s_job_rank);
   valid &= _input.vehicle_ok_with_job(s_vehicle, t_job_rank);
 
-  valid &= (_sol_state.fwd_amounts[t_vehicle].back() -
-              _input.jobs[t_job_rank].amount + _input.jobs[s_job_rank].amount <=
-            _input.vehicles[t_vehicle].capacity);
-
-  valid &= (_sol_state.fwd_amounts[s_vehicle].back() -
-              _input.jobs[s_job_rank].amount + _input.jobs[t_job_rank].amount <=
-            _input.vehicles[s_vehicle].capacity);
+  valid &=
+    target.is_valid_addition_for_capacity(_input,
+                                          _input.jobs[s_route[s_rank]].pickup,
+                                          _input.jobs[s_route[s_rank]].delivery,
+                                          t_rank,
+                                          t_rank + 1);
+
+  valid &=
+    source.is_valid_addition_for_capacity(_input,
+                                          _input.jobs[t_route[t_rank]].pickup,
+                                          _input.jobs[t_route[t_rank]].delivery,
+                                          s_rank,
+                                          s_rank + 1);
 
   return valid;
 }

@krypt-n I suspect this might be related to the way I've been working with amounts for validity checks, any idea?

The 5-argument is_valid_addition_for_capacity from the diff is now called is_valid_addition_for_capacity_margins if I am not mistaken.

bool RawRoute::is_valid_addition_for_capacity_margins(
  const Input& input,
  const Amount& pickup,
  const Amount& delivery,
  const Index first_rank,
  const Index last_rank) const {
  assert(1 <= last_rank);
  assert(last_rank <= route.size() + 1);

  auto first_deliveries =
    (first_rank == 0) ? current_loads[0] : bwd_deliveries[first_rank - 1];

  auto first_pickups = (first_rank == 0) ? Amount(input.amount_size())
                                         : fwd_pickups[first_rank - 1];

  auto replaced_deliveries = first_deliveries - bwd_deliveries[last_rank - 1];

  return (fwd_peaks[first_rank] + delivery <=
          capacity + replaced_deliveries) and
         (bwd_peaks[last_rank] + pickup <=
          capacity + fwd_pickups[last_rank - 1] - first_pickups);
}

I'd suggest the following changes which get rid of the allocations that are noticeable in the flamegraph:

• auto first_deliveries -> auto& first_deliveries. This avoids copying Amounts which is expensive since they are basically std::vectors. We can do this change since the lifetime of current_loads and bwd_deliveries is longer than the lifetime of the reference and other threads don't write to them (hopefully).

• Replace Amount(input.amount_size()) with a global const Amount zero that is initialized once at the beginning to the correct size. Could be a new member of Input. This avoids allocating a new zero-Amount every time we use it.

• Now that both of the possible values are not temporaries, we can change auto first_pickups to auto& first_pickups. This avoids copying the involved Amount objects.

The declaration auto replaced_deliveries does not need to be turned into a reference since this just constructs an AmountDiff object, which does not involve allocations.

The other is_valid_addition... methods would need similar changes to get the performance back into the same ballpark as before.

Hope that helps

@krypt-n thanks a lot for your input, I've been able to reduce allocations following your suggestions. I still see some in the flame graph for the last commit but this is probably related to this Amount object creation we can't really get rid of.

As several other changes are related to the current work in this PR, I'm extending it's scope to also cover #266 and #267. I've updated the task list accordingly.

The last few commits to address #266 are really promising on the computing times side. Average computing time on master before this PR (42e901b) for Solomon benchmark instances was 604ms. It went up to 2052ms (more than a 3x increase!) at 474d6bc with the increase of complexity in the various is_valid implementations across local search operators.
Now reducing the number of validity checks altogether bring it down to 489ms for latest commit (cb5a4c8). It means that:

• we should be able to handle mixed pickups and deliveries as a new feature with similar computing times (maybe even a bit lower)
• we'll probably even get a nice speed-up for delivery-only instances when falling back to simpler validity checks for capacity