Non-metric user-provided cost matrix crashes VROOM in specific cases

[sjoerddal-pti]

VROOM crashes when a user provided duration matrix is such that the travel time of LocA -> LocC is greater than LocA -> LocB -> LocC. And an initial route set for the vehicle with LocA -> LocB -> LocC already in place. Also TWs need to line up such that strictly LocA -> LocB -> LocC is possible. Here's a minimal repro:

Repro input JSON

{
  "vehicles": [
    {
      "id": 1,
      "start_index": 0,
      "end_index": 0,
      "steps": [
        {"type": "start"},
        {"type": "job", "id": 1},
        {"type": "job", "id": 2},
        {"type": "job", "id": 3},
        {"type": "job", "id": 4},
        {"type": "job", "id": 5},
        {"type": "end"}
      ]
    }
  ],
  "jobs": [
    {"id": 1, "location_index": 1, "service": 100},
    {"id": 2, "location_index": 2, "service": 100},
    {"id": 3, "location_index": 3, "service": 100, "time_windows": [[400, 400]]},
    {"id": 4, "location_index": 4, "service": 100},
    {"id": 5, "location_index": 5, "service": 100}
  ],
  "matrices": {
    "car": {
      "durations": [
        [    0,     0,   100,   300,   200,   300],
        [    0,     0,   100, 10000,   200,   300],
        [  100,   100,     0,   100,   200,   300],
        [  300,   300,   100,     0,   100,   200],
        [  200,   200,   200,   100,     0,   100],
        [  300,   300,   300,   200,   100,     0]
      ]
    }
  }
}

Thrown error by VROOM

vroom: algorithms/local_search/local_search.cpp:1328: void vroom::ls::LocalSearch::run_ls_step() [with Route = vroom::TWRoute; UnassignedExchange = vroom::vrptw::UnassignedExchange; CrossExchange = vroom::vrptw::CrossExc hange; MixedExchange = vroom::vrptw::MixedExchange; TwoOpt = vroom::vrptw::TwoOpt; ReverseTwoOpt = vroom::vrptw::ReverseTwoOpt; Relocate = vroom::vrptw::Relocate ; OrOpt = vroom::vrptw::OrOpt; IntraExchange = vroom::vrptw::IntraExchange; IntraCrossExchange = vroom::vrptw::IntraCrossExchange; IntraMixedExchange = vroom::vr ptw::IntraMixedExchange; IntraRelocate = vroom::vrptw::IntraRelocate; IntraOrOpt = vroom::vrptw::IntraOrOpt; IntraTwoOpt = vroom::vrptw::IntraTwoOpt; PDShift = v room::vrptw::PDShift; RouteExchange = vroom::vrptw::RouteExchange; SwapStar = vroom::vrptw::SwapStar; RouteSplit = vroom::vrptw::RouteSplit; PriorityReplace = vr oom::vrptw::PriorityReplace; TSPFix = vroom::vrptw::TSPFix]: Assertion `end_s_next > 1' failed.

Aborted (core dumped)

I realise such a matrix is something that should not happen in reality with a functioning routing engine. This did occur for us on a much more complex instance however, because our duration matrix is adjusted to force that existing routes remain feasible. We do this by tweaking the matrix if we detect that OSRM's current travel time is higher than what was readily planned. We do this to cope with small changes in OSRM output as we update OSM data. An update in mapdata, half patched duration matrix and zero-width TW all combined to trip this specific assert.

We did manage to fix this by changing the assert at local_search.cpp:1328 from assert(end_s_next > 1); to a simple continuation of the for loop like so:

if (end_s_next <= 1) {
  continue;
}

I didn't want to make a PR outright as I'm not sure if this is something VROOM even wants to allow/fix this way nor have I 100% tested if it won't mess things up elsewhere though it has worked as a hotfix for us, so let me know if you'd like a PR.

[jcoupey]

Thanks for sharing the instance, I can definitely reproduce hitting the assert with current master.

I realise such a matrix is something that should not happen in reality with a functioning routing engine.

We actually support this kind of situation transparently: the cost metric used by routing engines is usually not exactly duration or distance but some kind of weight derived from those, so we can't take it for granted that the triangle inequality holds.

changing the assert at local_search.cpp:1328 from assert(end_s_next > 1); to a simple continuation of the for loop like

Bypassing the assert is a way to not crash, but hitting the assert in the first place is a sign that something is probably wrong in the internal state of the solution at that point, so I would not consider this a proper fix.