"Infeasible route for vehicle" error for route from previous response

[joaemel]

When sending following request, vroom answers {"code": 2, "error": "Infeasible route for vehicle 33."}
However, if we do not include steps in vehicle 33, vroom returns the route passed in the request as solution.

The infeasability check is probably faulty in some way.

{
  "jobs": [],
  "shipments": [
    {
      "amount": [
        1,
        0,
        1
      ],
      "priority": 0,
      "pickup": {
        "service": 0,
        "id": 284,
        "time_windows": [
          [
            17842,
            18742
          ]
        ],
        "setup": 45,
        "description": "pickup|7682dcf2-113f-4a61-90a0-f6307855f844",
        "location": [
          12.130737,
          51.934853
        ]
      },
      "skills": [
        3,
        5
      ],
      "delivery": {
        "setup": 45,
        "id": 285,
        "description": "delivery|7682dcf2-113f-4a61-90a0-f6307855f844",
        "time_windows": [
          [
            17842,
            19869
          ]
        ],
        "service": 0,
        "location": [
          12.092393,
          51.967714
        ]
      }
    },
    {
      "delivery": {
        "description": "delivery|2ccf0c31-c9ed-4fc1-8d9d-6cf5816dbfa7",
        "time_windows": [
          [
            20538,
            23933
          ]
        ],
        "setup": 45,
        "id": 287,
        "service": 0,
        "location": [
          12.098087,
          51.97312
        ]
      },
      "priority": 0,
      "amount": [
        1,
        0,
        1
      ],
      "pickup": {
        "description": "pickup|2ccf0c31-c9ed-4fc1-8d9d-6cf5816dbfa7",
        "location": [
          11.913798,
          51.961952
        ],
        "time_windows": [
          [
            20538,
            21438
          ]
        ],
        "id": 286,
        "service": 0,
        "setup": 45
      },
      "skills": [
        3,
        5
      ]
    }
  ],
  "vehicles": [
    {
      "capacity": [
        6,
        1,
        100
      ],
      "id": 33,
      "end": [
        12.09324,
        51.95105
      ],
      "description": "7f24a42c-efc8-4688-bf64-826ed0fad753",
      "steps": [
      ],
      "start": [
        12.09324,
        51.95105
      ],
      "time_window": [
        0,
        36720
      ],
      "skills": [
        1048,
        2,
        3,
        4,
        5
      ],
      "breaks": [
        {
          "max_load": [
            0,
            0,
            0
          ],
          "id": 0,
          "time_windows": [
            [
              12420,
              20700
            ]
          ],
          "service": 2700
        }
      ],
      "speed_factor": 1
    }
  ]
}

[jcoupey]

Sounds odd indeed, but it is impossible to reproduce without access to the underlying costs. Could you please share an instance containing matrices?

[joaemel]

It can be reproduced using http://solver.vroom-project.org/ , by sending the request above, then copying the steps array from the answer into the request.

Nevertheless, here is a reproducing instance with duration matrix (created manually, from the durations in the response):

{
  "jobs": [],
  "shipments": [
    {
      "amount": [
        1,
        0,
        1
      ],
      "priority": 0,
      "pickup": {
        "service": 0,
        "id": 284,
        "time_windows": [
          [
            17842,
            18742
          ]
        ],
        "setup": 45,
        "description": "pickup|7682dcf2-113f-4a61-90a0-f6307855f844",
        "location_index": 0
      },
      "skills": [
        3,
        5
      ],
      "delivery": {
        "setup": 45,
        "id": 285,
        "description": "delivery|7682dcf2-113f-4a61-90a0-f6307855f844",
        "time_windows": [
          [
            17842,
            19869
          ]
        ],
        "service": 0,
        "location_index": 1
      }
    },
    {
      "delivery": {
        "description": "delivery|2ccf0c31-c9ed-4fc1-8d9d-6cf5816dbfa7",
        "time_windows": [
          [
            20538,
            23933
          ]
        ],
        "setup": 45,
        "id": 287,
        "service": 0,
        "location_index": 2
      },
      "priority": 0,
      "amount": [
        1,
        0,
        1
      ],
      "pickup": {
        "description": "pickup|2ccf0c31-c9ed-4fc1-8d9d-6cf5816dbfa7",
        "location_index": 3,
        "time_windows": [
          [
            20538,
            21438
          ]
        ],
        "id": 286,
        "service": 0,
        "setup": 45
      },
      "skills": [
        3,
        5
      ]
    }
  ],
  "vehicles": [
    {
      "capacity": [
        6,
        1,
        100
      ],
      "id": 33,
      "end_index": 4,
      "description": "7f24a42c-efc8-4688-bf64-826ed0fad753",
      "steps": [
        {
          "type": "pickup",
          "id": 284
        },
        {
          "type": "delivery",
          "id": 285
        },
        {
          "type": "pickup",
          "id": 286
        },
        {
          "type": "delivery",
          "id": 287
        }
      ],
      "start_index": 4,
      "time_window": [
        0,
        36720
      ],
      "skills": [
        1048,
        2,
        3,
        4,
        5
      ],
      "breaks": [
        {
          "max_load": [
            0,
            0,
            0
          ],
          "id": 0,
          "time_windows": [
            [
              12420,
              20700
            ]
          ],
          "service": 2700
        }
      ],
      "speed_factor": 1
    }
  ],
  "matrices": {
    "car": {
      "durations": [
        [0,450,1233,473,387],
        [457,0,945,1194,382],
        [1207,912,0,999,390],
        [478,140,1278,0,449],
        [379,387,1109,443,0]
        ]
    }
  }
}

Running it against vroom I get an infeasible route error, but if I remove steps and retry, it will find a solution ordering the steps identically.

[jcoupey]

Thanks for sharing, I can definitely reproduce the problem. We need to investigate the initial check we run on the route that is provided using steps.

[jorgedsol]

I also ran into this same issue.
I tried different ways of sending the vehicle steps (using and not using the upper and lower bounds for the time) based on a previous solution from VROOM but got the infeasibility response.
My goal is to be able to fit in extra jobs or shipments once an initial solution has been calculated , for incoming last hour requests

[jcoupey]

@jorgedsol thanks for reporting. I intend to look at this in the near future so if you could share the instance to reproduce your problem that would be very helpful.

[simonpalmqvist]

@jcoupey any updates on this issue? We also get this error when using steps (works fine when excluding them).

[jcoupey]

@simonpalmqvist no update yet, if you can share a reproducible example, that is definitely useful.

[jcoupey]

I've had a report from a customer for a similar problem so I've been taking a closer look. The instances I have at hand (thanks for sharing!) point to a couple improvements that can be done to the current heuristic process we have in place to decide break vs task ordering within routes. I've applied those changes in #1318 which helps for some instances but that is only part of the story.

The bottom line is that the process mentioned above (see TWRoute::order_choice used in a similar way in TWRoute::is_valid_addition_for_tw and TWRoute::replace) is inherently heuristic. This is a design decision to overcome the combinatorial nature of the break placement decision problem. As such, we'll never have a strong guarantee that a simple call to is_valid_addition_for_tw on a full route, as the current initial validity check is implemented, will be consistent with a previous valid solution. As a matter of fact, even if the above instance does now work with #1318, I've been able to slightly adjust some TW to trigger another subtle inconsistency.

The only way we have to get a strong guarantee that a previous (valid) solution won't be wrongly discarded is to implement a dedicated TWRoute constructor that takes into account not only the set of tasks, but also the provided break(s) ordering choice that is not currently being used by is_valid_addition_for_tw. That ctor would throw in case of timing violation and otherwise setup all the data we need within the route without having to call replace like we currently do.