Allow defining immutable tasks in initial route plan

[fbaierl]

Motivation

I think VROOM would greatly benefit from the possibility to be used in more dynamic environments. What I mean by this is that VROOM is very well suited for making a complete plan for one day, which is not deviated from. However, with the current solution, it is difficult to schedule new requests while part of the plan is already fixed/immutable. Because of this use-case, it would be very beneficial if we could define vehicle steps as input that are already fixed. VROOM should no longer change these steps (apart from maybe picking up more loads along the way if they fit into the time-window restrictions) but use the remaining free time-slots to plan the other given shipments.

Previously, I thought that steps on vehicles are used for exactly this use-case - which is not the case. Previous discussion: 753.

Feature

It would be great if we could somehow define steps for vehicles that are already immutable, e.g. like this:

{
  "vehicles": [
    {
      "id": 0,
      "description": "vehicle0",
      "start": [
        12.304373066846503,
        51.62270653765847
      ],
      "end": [
        12.304373066846503,
        51.62270653765847
      ],
      "capacity": [7],
      "skills": [],
      "time_window": [
        1644188400,
        1644274740
      ],
      "breaks": [],
      "steps": [
        {
          "id": 0,
          "type": "job",
          "fixed": true
        },
        {
          "id": 1,
          "type": "job",
          "fixed": true
        }
      ]
    }
  ],
  "shipments": [
    {
      "amount": [3],
      "skills": [],
      "pickup": {
        "id": 7,
        "service": 120,
        "location": [
          12.175563,
          51.694164
        ],
        "time_windows": [
          [
            1644199440,
            1644199440
          ]
        ],
        "description": "pickup|1001"
      },
      "delivery": {
        "id": 7,
        "service": 120,
        "location": [
          12.219437,
          51.715622
        ],
        "time_windows": [
          [
            1644198918,
            1644198918
          ]
        ],
        "description": "delivery|1001"
      }
    }
  ],
  "jobs": [
    {
      "id": 0,
      "pickup": [0],
      "delivery": [0],
      "description": "",
      "location": [
        12.304373066846503,
        51.62270653765847
      ],
      "timeWindow": [
        [
          1644197801,
          1644197801
        ]
      ]
    },
    {
      "id": 1,
      "pickup": [0],
      "delivery": [0],
      "description": "",
      "location": [
        12.219437,
        51.715622
      ],
      "timeWindow": [
        [
          1644198798,
          1644198798
        ]
      ]
    }
  ]
}

Here, vehicle0 already has job 0 and job 1 that is has to do and vroom should check if the additional shipment can additionally be added to this vehicles schedule.

To discuss

• what should happen, if the fixed jobs are not doable (should this even be checked?)

Current workaround

My current workaround is described here. This workaround seems to work at the moment, but it is:

• not robust
• very cumbersome/error-prone pre-/post-processing of VROOM input/output

[jcoupey]

Thanks for the comprehensive description! To be honest, I've already thought of this as a potential interesting addition for the situation where (a lot of) replanning occurs. The raw sketch of the changes for the solving approach would be:

1. Fill vehicles with their initial route as described in steps (already happening for solve).
2. Carry on the usual heuristic process with whatever remaining unassigned tasks.
3. Discard any local search move that would remove or change vehicle for an "immutable" task.

As a result, immutable tasks would stay in their initial vehicle and in their respective input order while other tasks (either in steps or not) would be able to move freely.

schedule new requests while part of the plan is already fixed/immutable

Note that the "already fixed" part here is somehow subjective. Consider the example of a task with a [8:00, 12:00] TW that is first pinned to a vehicle in a given order, say first in the day with a 8:00 ETA. Then if you submit that exact same task in a next solving round, you could potentially pack the morning shift with new tasks before that one and have it end up happening at 12:00, albeit prior to the other immutable next tasks. My point is that ETA would potentially be subject to significant changes so you'd still need some TW constraint processing between solving rounds, e.g. if you commit to a narrow time frame for a client ETA after a given optimization round like above. Of course the process of iteratively fixing plans like this can potentially derive toward quite sub-optimal solutions, but you can't have your cake and eat it too.

what should happen, if the fixed jobs are not doable (should this even be checked?)

I think this should be a case of error (it is currently when using vehicle.steps in solve mode). If the route as a whole is not doable, then deciding what should be included or not is both non-trivial and somehow totally arbitrary.

[fbaierl]

Note that the "already fixed" part here is somehow subjective. Consider the example of a task with a [8:00, 12:00] TW that is first pinned to a vehicle in a given order, say first in the day with a 8:00 ETA. Then if you submit that exact same task in a next solving round, you could potentially pack the morning shift with new tasks before that one and have it end up happening at 12:00, albeit prior to the other immutable next tasks.

Of course, this is completely logical in the context of VROOM.

It would not be a problem for our special use-case in particular, since we would always give a time-window of exactly one second for those fixed tasks. Like in my example:

"timeWindow": [
        [
          1644197801,
          1644197801
        ]
      ]

For us, "fixed" means that we have communicated the exact time of arrival to both the driver and the passenger (since we are transporting people), that is why we would not give VROOM any margin to work with here.

[K-Leon]

This feature would solve us a lot of headaches!

We have on our end the challenge that we have a route which needs to stay roughly the same. (Small switches are okay but the broad picture has to stay because the vehicles are already loaded and the can’t get resorted when two or three late tasks are added). A tour has usually around 100 stops to make the picture clear.

So the timing doesn‘t matter - it is just about the rough stop order and inserting new stops appropriately. (Switching geographically near stops which each other is also fine - or would even be better!) It is just about the big picture which should stay the same.

[stewgloves]

Agree this would be a great addition. Not sure how /if this is progressing but we have a similar use case where we use the solver to determine the vehicle's initial route (containing both jobs and shipments).

We want to answer the question - "What vehicles can deliver this new shipment based on their existing routes within the time windows (10-11,11-12,12-1,1-2-3....8-9.)?"

Currently, this requires a lot of pre-processing of the data by making use of skills and sending large data sets to vroom (which ultimately impacts performance). I had hoped Plan mode would accomplish this. Whereby you provide a vehicle, their existing vehicle.steps plus the new shipment or job and it would output constraints that have not been met.

Our use case differs slightly from the initial one described by @fbaierl as we don't mind if shipments that have not yet completed the pickup portion are redistributed to other vehicles should it be more optimal.