max_travel_time parameter not being considered for single vehicle in request

[SimonBradley1993]

Hi, we've recently implemented the max_travel_time parameter with Vroom 1.13.0, and we've noticed that for 1 vehicle in a request this max travel time parameter is ignored. We pass in 7200 as the max travel time value and the response has the duration for the route as 10957. The request to replicate this is very large, so the snippet for the vehicle in this request is : { "max_tasks": 5, "end": [ -4.557433, 55.956531 ], "id": 18, "skills": [ 3, 4, 1, 2, 0, 5, 6, 7, 8, 9, 10, 11 ], "start": [ -4.557433, 55.956531 ], "time_window": [ 27900, 62100 ], "breaks": [], "max_travel_time": 7200 }

Let me know if you would like the whole request for replication purposes.

[jcoupey]

Sounds like a duplicate of #884. Can you check if the fix from #934 (now in master) changes the behavior?

[SimonBradley1993]

Hi, I did see that bug and tried adding capacity back in to our request to Vroom but the same thing happened.

I've just tried building Vroom on master and am now getting the following error with both the original request, and one with capacity added :

Vroom errors: Assertion failed: (_input.vehicles[v_rank].ok_for_travel_time( _sol_state.route_evals[v_rank].duration)), function run_ls_step, file local_search.cpp, line 1724

[jcoupey]

Right, on second thoughts it would have been weird to hit #884 with time windows in input. Was worth trying anyway, thanks for the feedback.

Can you share a standalone problem instance in order to reproduce? If your input is too big, you can probably narrow it to a minimum (non-)working example.

[SimonBradley1993]

Yeah sure, I've run the script and it's generated an issue matrix json file. Is that what you need?

[jcoupey]

Yep.

[SimonBradley1993]

Github wouldn't let me upload a JSON file and it was too big to paste into the comment box. Hopefully this is OK as a txt file

issue_matrix.txt

[jcoupey]

Thanks for sharing the instance, I can reproduce all right. With a release build we provide a solution that does not meet the max_travel_time constraint for vehicle 18. With a dev build (current master) the search stops early as an assert spots the broken constraint at some point.

[jcoupey]

OK, what happens here is we apply a RouteSplit operator (empty one vehicle route by dispatching it to two other empty vehicles) at some point, resulting in an invalid route wrt max_travel_time.

Support for max_travel_time landed in #780, merged in September 2022. Then the RouteSplit operator was added in the local search later on (November 2022) as part of #788. Turns out I forgot to include max_travel_time related checks in that operator.

[jcoupey]

Fixed in #961.