dkastl
commented
2 years ago Good thoughts.
Being very strict with already allocated tasks unfortunately isn't good for the overall optimisation result. Maybe this constraint could be less severe, if we allow a certain time window around the previously allocated times.
Another constraint could be, that already allocated tasks can change the time but not the vehicle.
Here some practical scenario of an on-demand bus: The system allows bookings until the very last minute. This means that passengers may already have boarded when a new transportation request is allocated. But this means the passengers already in the vehicle can not be re-allocated to a different one. However, it would be OK to change the arrival times even of already travelling passengers, if they don't violate any other constraint.
For this, we will need to ensure two things for existing tasks:
1. Existing tasks must not get unallocated
Solution: Give a very high priority to existing tasks (say 100). Range of allowed values of priority = [0, 100]. But that this cannot guarantee that all "mandatory" jobs will be included in the solution if there are lots of jobs and strict constraints (e.g. time windows). [Reference]
There are several methods of implementing this:
1: Keep allowing the end users to give custom priority to tasks (in the priority field). Give 100 priority to existing tasks. It may happen that someone gives a priority of 100 to a new task. So, this task and the existing task will be considered the same in terms of priority, and the existing task’s might get unallocated.
2: Give 0 priority to new tasks (restrict users from giving custom priority), and 100 priority to existing tasks. This will always work, provided we remove the priority feature from the user side, and thus, all the new tasks will have the same 0 priority.
3: Restrict the priority given by API users in the range [0, 10]. Give priority = 100 to existing tasks. Better chance of success than the first method, and will also allow the users to give custom priority. A task priority tries to minimize the sum of priority scores over unassigned tasks [Reference]. But in case there are 11 jobs with priority = 10, then it will be preferred (110) over an existing job with priority 100. So, this might fail if there are a lot of jobs and strict constraints.
4: Restrict the priority given by API users in the range [0, 100]. Give priority = 10^6 to existing tasks. Priority 10^6 can be given to the tasks because the range [0,100] is restricted only on the Vroom JSON API side, and not on the C++ side (libvroom). So, this bug (or feature) can be exploited to get this done. It has a far better chance of success than method 1 or 3. This will fail if say 10^4+ jobs with priority 100 are used. If the restriction [0, 100] is added on the libvroom side too, then this will not work.
The restriction imposed in methods 3 and 4 will only work in the web API version, not in the database version.
Which method would be most suitable? Most of these methods can’t guarantee that the schedule of existing tasks remains unchanged. Method 2 has good chances of success, followed by method 3. Still, there will be some instances where the existing task becomes unallocated when someone tries to schedule new tasks.
2. Existing tasks must have same pickup/delivery time as it was before
This will first require that existing tasks must not get allocated (1st point).
This would also require adding very strict time window constraints (which can decrease the chance of success of the 1st point), because any time window constraints are always hard constraints. So, if an existing task is scheduled during the time [t1, t2], this would mean that while scheduling new tasks, the time window of the existing task is set to [t1, t1] so that it always starts at the time t1. We can add some flexibility in the time window, say [t1 - Δ, t1 + Δ], but this would mean that with each successive scheduling, the time of existing tasks can change by Δ.
Any comments on what would be better?