max_travel_time parameter has no effect on optimization

[fsty]

Hello!
I am using the following input data for the optimization with vroom v1.13.0
{ "vehicles":[ { "id":0, "start_index":0, "end_index":3, "max_travel_time":100, "profil":"car", "costs":{ "fixed":0, "per_hour":600000 } } ], "jobs":[ { "id":1414, "location_index":1 }, { "id":1515, "location_index":2 } ], "matrices":{ "car":{ "durations":[ [ 0, 21040, 1970, 12990 ], [ 21030, 0, 22550, 31520 ], [ 1970, 22560, 0, 11020 ], [ 12990, 31530, 11020, 0 ] ] } } }

However, I noticed that the max_travel_time constraint for the vehicle is not being taken into account in the result

[jcoupey]

Thanks for reporting, we indeed provide a solution that does not account for this constraint. Moreover when solving in debug mode, the matching assert is triggered all right upon route formatting:

vroom: ./utils/helpers.h:539: vroom::Solution vroom::utils::format_solution(const vroom::Input&, const RawSolution&): Assertion `v.ok_for_travel_time(eval_sum.duration)' failed.

The problem is "simply" that this instance is wrongly considered a TSP, so we run the ad-hoc TSP solving code on it, and the max_travel_time constraint is not accounted for in there. In other words we're missing a check for this constraint when deciding how to solve the problem.

Simple work-around before this gets fixed: adding any extra constraint (capacity, TW etc.), even a non-binding one, will send this instance to the right solving path.

[fsty]

You are right, it works when adding TW

[elkashefehab]

I did this and still not working

{
"jobs": [
{
"id": 1,
"service": 300,
"amount": [
1
],
"location": [
31.021359323473806, 30.030300709541248 ],
"skills": [
1
],
"time_windows": [
[
32400,
36000
]
]
},
{
"id": 2,
"service": 300,
"amount": [
1
],
"location": [
30.9753925901295, 30.017149336967645
],
"skills": [
1
],
"time_windows": [
[
32400,
36000
]
]
}
],
"vehicles": [
{
"id": 1,
"profile": "cycling-road",

  "start": [
    31.003840309233382, 30.014675513561293
  ],
  "end": [
    31.003840309233382, 30.014675513561293
  ]
  ,
  "max_travel_time":1
  ,
  "capacity": [
    3
  ],
  "skills": [
    1,
    14
  ]
}

]
}

[jcoupey]

@elkashefehab it is not possible to reproduce your solution without access to your routing stack, can you share a standalone problem instance?

[zahert]

@jcoupey , Hi there I also have an issue in using max_travel_time, for example in my problem I was expecting that the engine will exclude the only job I have as the max_travel_time equal "1"

{ "vehicles": [ { "id": 1, "profile": "car", "speed_factor": 0.1, "max_tasks": 2, "time_window": [ 1, 100000 ], "max_travel_time": 1, "start": [ 31.1969, 30.0451 ], "end": [ 31.1969, 30.0451 ], "start_index": 0, "end_index": 0 } ], "jobs": [ { "id": 1, "description": "ORDER1", "location": [ 31.200302884487147, 30.04051714641897 ], "location_index": 1 } ], "options": { "g": true }, "matrices": { "car": { "durations": [ [ 0, 131 ], [ 121, 0 ] ] } }

Also I tried defining TW in absolute values, but still the max_travel_time is not taken into consideration

{ "vehicles": [ { "id": 1, "time_window": [ 1680739899, 1680825599 ], "max_travel_time": 1, "start": [ 31.0045, 30.0139 ], "end": [ 31.0045, 30.0139 ], "capacity": [ 2 ], "start_index": 0, "end_index": 0 } ], "options": { "g": true }, "jobs": [ { "id": 1, "description": "WCK-4716493", "location": [ 31.0111, 30.0371 ], "service": 210, "time_windows": [ [ 1680097412, 1680098612 ] ], "location_index": 1 }, { "id": 2, "description": "DDS-9057654", "location": [ 31.0033, 30.0209 ], "service": 210, "time_windows": [ [ 1680739871, 1680741071 ] ], "location_index": 2 }, { "id": 3, "description": "DDD-9057654", "location": [ 31.0033, 30.0209 ], "service": 210, "time_windows": [ [ 1680739871, 1680741071 ] ], "location_index": 2 } ], "matrices": { "car": { "durations": [ [ 0, 544, 342 ], [ 497, 0, 394 ], [ 269, 398, 0 ] ] } } }

[jcoupey]

@zahert are you using a version of VROOM that supports the max_travel_time parameter at all? Both current master and v1.13.0 result in all jobs being unassigned in your examples.

[zahert]

@jcoupey I'm using v1.12.0 I will need to upgrade, thank you 👍

[jcoupey]

Running on the initial instance above now results in all jobs being unassigned as expected:

$ vroom '{ "vehicles":[ { "id":0, "start_index":0, "end_index":3, "max_travel_time":100, "profil":"car", "costs":{ "fixed":0, "per_hour":600000 } } ], "jobs":[ { "id":1414, "location_index":1 }, { "id":1515, "location_index":2 } ], "matrices":{ "car":{ "durations":[ [ 0, 21040, 1970, 12990 ], [ 21030, 0, 22550, 31520 ], [ 1970, 22560, 0, 11020 ], [ 12990, 31530, 11020, 0 ] ] } } }'
{"code":0,"summary":{"cost":0,"routes":0,"unassigned":2,"setup":0,"service":0,"duration":0,"waiting_time":0,"priority":0,"violations":[],"computing_times":{"loading":0,"solving":1}},"unassigned":[{"id":1515,"location_index":2,"type":"job"},{"id":1414,"location_index":1,"type":"job"}],"routes":[]}