Fixed afternoon time task preventing any earlier that day

[VincentVanclef]

I am having a hard time figuring out what to do here, hope someone can help.

So the problem is I have a task that must be "handled/delivered" or what you call it, at a specific time, in this case 13:00. My driver starts his day at 7 in the morning, so that leaves him with 6 hours before having to arrive at the destination at 13:00 but vroom pushes all other tasks that day to be done after 13:00 for some reason even though they can perfectly fine be done before.

The 13:00 task is the #1 marker on the map here:

My request:

{
"vehicles": [
{
"id": 1,
"start": [
9.58629,
55.67334
],
"end": [
9.58629,
55.67334
],
"profile": "driving-car",
"costs": {
"per_km": 0,
"per_hour": 3600,
"per_task_hour": 0
},
"time_window": [
1776407400,
1778999400
]
}
],
"jobs": [
{
"id": 1,
"location": [
10.84848,
56.37063
],
"type": "task",
"description": "c62897f7-488f-409a-b11d-e3bdc97dfbd7",
"setup": 0,
"service": 1800,
"priority": 100,
"time_windows": [
[
1776423600,
1776423600
]
]
},
{
"id": 2,
"location": [
10.76094,
56.46703
],
"type": "task",
"description": "940d496e-98a2-467f-ae91-49f53a3785df",
"setup": 60,
"service": 10800,
"priority": 100
},
{
"id": 3,
"location": [
10.63425,
56.23158
],
"type": "task",
"description": "7813b1f1-d7cd-43dd-9b0a-387a7567343b",
"setup": 60,
"service": 10800,
"priority": 100
},
{
"id": 4,
"location": [
10.24973,
56.24855
],
"type": "task",
"description": "34481a86-d1ec-48fb-bf0f-f71b5b458e89",
"setup": 60,
"service": 1800,
"priority": 100
},
{
"id": 5,
"location": [
10.03319,
56.33494
],
"type": "task",
"description": "e1dc6865-99e0-402a-99ae-e6c0970bc15f",
"setup": 60,
"service": 1800,
"priority": 100
},
{
"id": 6,
"location": [
10.08728,
56.43093
],
"type": "task",
"description": "e1005ef9-63ac-4cee-8864-f2484b0f42eb",
"setup": 60,
"service": 900,
"priority": 100
},
{
"id": 7,
"location": [
10.09669,
56.47679
],
"type": "task",
"description": "ddc34661-0d19-4731-bb43-6c73d63cdbfc",
"setup": 60,
"service": 900,
"priority": 100
},
{
"id": 8,
"location": [
9.95469,
56.45803
],
"type": "task",
"description": "38c132d4-28d7-4464-9c0b-9078387edf27",
"setup": 60,
"service": 900,
"priority": 100
},
{
"id": 9,
"location": [
9.96688,
56.46026
],
"type": "task",
"description": "f8d128f8-6bdf-47a8-8447-a4047a1656d3",
"setup": 60,
"service": 900,
"priority": 100
}
],
"options": {
"g": true
}
}

The only thing i found working was to adjust the costs to:

            {
                per_km = 0,
                per_hour = 0,
                per_task_hour = 10000
            }

That made vroom put some tasks before the 13:00 task but that isnt feasible as it makes all routes much longer as vroom no longer prioritizes normal driving distance costs.

The result is:

{"code":0,"summary":{"cost":20790,"routes":1,"unassigned":0,"setup":480,"service":30600,"duration":20790,"waiting_time":0,"priority":900,"distance":396053,"violations":[],"computing_times":{"loading":27,"solving":2,"routing":8}},"unassigned":[],"routes":[{"vehicle":1,"cost":20790,"setup":480,"service":30600,"duration":20790,"waiting_time":0,"priority":900,"distance":396053,"steps":[{"type":"start","location":[9.58629,55.67334],"setup":0,"service":0,"waiting_time":0,"arrival":1776418159,"duration":0,"violations":[],"distance":0},{"type":"job","description":"c62897f7-488f-409a-b11d-e3bdc97dfbd7","location":[10.84848,56.37063],"id":1,"setup":0,"service":1800,"waiting_time":0,"job":1,"arrival":1776423600,"duration":5441,"violations":[],"distance":131504},{"type":"job","description":"940d496e-98a2-467f-ae91-49f53a3785df","location":[10.76094,56.46703],"id":2,"setup":60,"service":10800,"waiting_time":0,"job":2,"arrival":1776426778,"duration":6819,"violations":[],"distance":148962},{"type":"job","description":"7813b1f1-d7cd-43dd-9b0a-387a7567343b","location":[10.63425,56.23158],"id":3,"setup":60,"service":10800,"waiting_time":0,"job":3,"arrival":1776440223,"duration":9404,"violations":[],"distance":185982},{"type":"job","description":"34481a86-d1ec-48fb-bf0f-f71b5b458e89","location":[10.24973,56.24855],"id":4,"setup":60,"service":1800,"waiting_time":0,"job":4,"arrival":1776453351,"duration":11672,"violations":[],"distance":226372},{"type":"job","description":"e1dc6865-99e0-402a-99ae-e6c0970bc15f","location":[10.03319,56.33494],"id":5,"setup":60,"service":1800,"waiting_time":0,"job":5,"arrival":1776456739,"duration":13200,"violations":[],"distance":248406},{"type":"job","description":"e1005ef9-63ac-4cee-8864-f2484b0f42eb","location":[10.08728,56.43093],"id":6,"setup":60,"service":900,"waiting_time":0,"job":6,"arrival":1776459692,"duration":14293,"violations":[],"distance":263333},{"type":"job","description":"ddc34661-0d19-4731-bb43-6c73d63cdbfc","location":[10.09669,56.47679],"id":7,"setup":60,"service":900,"waiting_time":0,"job":7,"arrival":1776461664,"duration":15305,"violations":[],"distance":273741},{"type":"job","description":"38c132d4-28d7-4464-9c0b-9078387edf27","location":[9.95469,56.45803],"id":8,"setup":60,"service":900,"waiting_time":0,"job":8,"arrival":1776463833,"duration":16514,"violations":[],"distance":285328},{"type":"job","description":"f8d128f8-6bdf-47a8-8447-a4047a1656d3","location":[9.96688,56.46026],"id":9,"setup":60,"service":900,"waiting_time":0,"job":9,"arrival":1776465024,"duration":16745,"violations":[],"distance":286530},{"type":"end","location":[9.58629,55.67334],"setup":0,"service":0,"waiting_time":0,"arrival":1776470029,"duration":20790,"violations":[],"distance":396053}]

the vehicle’s allowed overall time window starts at 1776407400, but VROOM does not have to leave at that moment. It chooses to leave later, at 1776418159, so it can hit the fixed task exactly on time. Which confuses me as there should be plenty of time to do other tasks before the fixed time task.

Any idea what i can do or is this a bug?

[jcoupey]

The default optimization objective is overall travel time. In your situation starting with the 13:00 task is probably the cheapest option we found in terms of overall travel time, so that is the one we return. The fact that you have plenty of time to do the rest before does not really matter if the overall cost is higher: if both options are equally feasible we'll go for the cheapest one.

What you're actually after is a missing constraint that make it so that the overall plan does not end too late (even if more expensive). You could probably achieve that by reducing the vehicle time window, or adding time windows to other tasks so the current solution that spans too late is not valid anymore.

[VincentVanclef]

The default optimization objective is overall travel time. In your situation starting with the 13:00 task is probably the cheapest option we found in terms of overall travel time, so that is the one we return. The fact that you have plenty of time to do the rest before does not really matter if the overall cost is higher: if both options are equally feasible we'll go for the cheapest one.

What you're actually after is a missing constraint that make it so that the overall plan does not end too late (even if more expensive). You could probably achieve that by reducing the vehicle time window, or adding time windows to other tasks so the current solution that spans too late is not valid anymore.

@jcoupey I totally understand that from the cost / travel perspective, I just feel like we really need some sort of handle to control this as I tried tweaking the vehicle cost object and setting

{
per_km = 0,
per_hour = 0,
per_task_hour = 10000
}

"worked" but not really reliable and doing this

{
per_km = 0,
per_hour = 1,
per_task_hour = 10000
}

Made it go back to skipping all work prior to the 13:00 task, this seems crazy that such a little thing can change it.

I also tried changing the vehicle constraint so that the vehicle ends earlier, but that just made vroom "unassign" the other tasks :/

Also forgot to mention in my initial post, the distance from the start location to the tasks is ~45 minutes of driving. So if the user starts at 7 in the morning he could arrive at any of the other tasks around 8, leaving him with 5 hours before having to arrive at the 13:00 task, seems crazy to 😄

[jcoupey]

Using both per_km = per_hour = 0 does not really make sense from the modeling perspective, because all costs will be basically zero so it's like saying you don't care about any cost. The fallback here internally is to compare solutions based on travel time so essentially this is just like not setting costs in the first place.

I also tried changing the vehicle constraint so that the vehicle ends earlier, but that just made vroom "unassign" the other tasks :/

You don't have TW constraints on the other jobs so it sounds weird to have them unassigned while they could be performed earlier. I can't really reproduce what you get since I don't have access to your routing stack. If you want some more insights, can you share your instances in a reproducible format?

[VincentVanclef]

@jcoupey does setting per_km explicitly, change something, i assumed 0 was the default based on the docs?

https://github.com/VROOM-Project/vroom/blob/master/docs/API.md

I only have start time constraint on my vehicles, no end time (done by setting endtime extremely high), since i want to keep them in the route so that i can still display them in my UI and just mark that the task is outside the users workday

I will try the reproduceable format

Also thanks a lot for taking your time to answer my questions!