Higher cost for the same problem with a bigger fleet

[juanluisrto]

I have noticed that, in some cases and for the same set of jobs and a given fleet, the total cost is higher than if only part of the fleet was used.

For example, the total cost of the problem below returned by vroom is 396. However, if we use only vehicle 1 (commenting out vehicle 2) the total cost is 388. This does not make sense since in the first instance, vroom could have detected that using vehicle 2 is suboptimal and all jobs could have been assigned to vehicle 1.

I've detected that this only occurs when vehicles start and end at the same location.

{
  "vehicles": [
    {"id": 1, "start_index": 5, "end_index": 5},
    {"id": 2, "start_index": 6, "end_index": 6}
  ],
  "jobs": [
     {"id": 0, "location_index": 0},
     {"id": 1, "location_index": 1},
     {"id": 2, "location_index": 2},
     {"id": 3, "location_index": 3},
     {"id": 4, "location_index": 4}
  ],
  "matrices": {
    "car": {
      "durations": [
           [  0,  82,  54, 135, 130,  46,  68],
           [ 82,   0,  95, 134,  91,  73,  50],
           [ 54,  95,   0,  84,  97,  22,  52],
           [135, 134,  84,   0,  63,  90,  88],
           [130,  91,  97,  63,   0,  88,  63],
           [ 46,  73,  22,  90,  88,   0,  33],
           [ 68,  50,  52,  88,  63,  33,   0]
      ]
      
    }
  }
}

This conversation comes from this issue in pyvroom

[jcoupey]

TL;DR this behavior is related to a heuristic bias.

Thanks for sharing a json instance. I can reproduce the results you get:

• the route with a single vehicle is (using indices) 5 0 1 4 3 2 5 assigned to vehicle 1 with cost 388;
• the route with two vehicles is 6 4 3 2 0 1 6 assigned to vehicle 2 with cost 396.

Both solutions are the one provided with the initial solution building heuristics, i.e. none of the local search moves we have is able to improve the solutions.

The reason why a route is built for vehicle 2 in the first place when both vehicles are available is that its start/end location is closer to more jobs than vehicle 1 (3 jobs closer to vehicle 2 vs 2 jobs closer to vehicle 1). This is the usual heuristic process we use when dealing with a fleet that has heterogeneous locations, because it helps to start filling out routes first for vehicles that have a "dense" jobs area nearby.
In this specific situation, it simply turns out that this criterion is not optimal.

Another question is why we're not able to "fix" this as we could perform the following moves, available in the local search:

• 6 4 3 2 0 1 6 (initial solution with two vehicles)
• 5 4 3 2 0 1 5 (route moved from vehicle 2 to vehicle 1 using RouteExchange)
• 5 0 1 4 3 2 5 (move edge 0 -> 1 using IntraOrOpt)

The problem here is that the intermediate route has a higher cost (444), same when doing the IntraOrOpt move before (440), so those moves are discarded.

[jcoupey]

Using the latest release build (v1.14.0) fixes this for the provided example: both inputs above are now solved to the optimal cost of 388, no matter the fleet size.

Taking a closer look at what did the trick: it turns out that the adjustments made to the heuristic process, though not allowing to directly reach the "right" solution heuristically, do lead to another heuristic solution with the right vehicle that in turn can be improved with a single IntraMixedExchange move: 5 3 4 1 0 2 5 -> 5 0 1 4 3 2 5.

I'm not saying this kind of bias can't show up any more at all, but at least we can close this ticket.

[juanluisrto]

Great work! @jcoupey