I’m trying to unpick the issue of soft time windows to see if there might be a shortcut implementation using existing features and approaches. I’m hoping to address the remaining issues with the huge implementation effort from Braktar but I might have misunderstood so I would also appreciate a sanity check
In a lot of cases, “unassigned” jobs don’t have a whole lot of meaning. I have my jobs, I have my fleet and if I get something unassigned for something as petty as a 1 min violation of a time window then I have problems. The jobs need to be done.
The response to (1) is often to rerun the whole simulation again, potentially with some attempt to pre-load
jspritwith the previous solution. But there’s overhead too on the logic of whether I need to re-call a solution.
Why was a job unassigned? More overhead in trying to understand the issue. Of my 5 unassigned jobs, what restrictions need to be relaxed in order to get them in the route?
In other words, I believe overhead should be considered in context of the problem. I would rather handle time window violations in a predictable way with limits, within the initial problem specification, even if it adds some overhead to calculation (which I can turn off/on). If even this condition leads to unassigned jobs then I consider it an error – I have a real-world issue.
TimeWindowclass to create a
Define a problem-level penalty function for late jobs; this may be confined to a linear function of time with this idea, more later.
When defining job time windows, we could specify a “shadow” period that immediately follows on from the hard time windows. For example, a 14:00-16:00 job might also have a shadow of 60 minutes. Under the hood, the shadow window is just an identifiable tag for a normal secondary time window from 16:00-17:00.
The underlying insertion heuristic should not be any different than the existing implementation for multiple time windows. However, all insertions should always prefer to insert a job that is available in its non-shadow time window. Simple filter on the pool of jobs to insert.
A route-level counter for how many jobs in the route are currently being serviced in their shadow window (
ShadowCount) and also a tally of number of time units (
ShadowTime). I’m under the impression that this can be cleanly implemented in Modular objective function (
The concern from Stefan, I think, on Braktar’s implementation was that insertion costs should be considered only examining jobs
kis the job to be inserted between
SHORT CIRCUIT. If
ShadowCountis 0 and
kis not being inserted in a shadow time window, bypass the rest. (Apologies, I can’t seem to get a nested list) Else:
Calculate the pushback caused on
kto be before it. An A to B matrix lookup.
Multiply pushback by ShadowCount (i.e. to apply to all jobs in route that are currently late). Add this to ShadowTime.
Subtract the shadow window opening time from the current route time of insertion. So job
khas a shadow window of 16:00-17:00, if it is inserted at 16:25 then you have 25 minutes. Call this
((0.5*ShadowTime) + NewShadowAddition)to the problem-level penalty function to return total cost penalty.
ShadowTime = ShadowTime + NewShadowAddition.
Limitations and Going Forwards
The factor of 0.5 in (8) is a bit fudged. You cannot currently know that insertion
k will have any impact on the existing jobs that are being serviced in their shadow window because they may precede job
k. On average, half of jobs would be affected by each insertion. I think a non-linear cost penalty function might exasperate this issue. Two options I see, I’m hoping you might have another way:
Accept the limitation but tie the penalty to
SolutionCompletenessRatioto limit its impact
ShadowTimeas dual-feature data, where the
ShadowTimeis stored against an index of where it is in the route so that you can filter. I’m not sure if there’s a clean way of doing this or whether we degenerate to something like parsing whole route on each iteration.
Any thoughts? The implementation should be a lot shallower than the current effort, and also allows the user to define acceptable deviations from the time window rather than leaving the cost function open-ended. Due to short circuiting, it does absolutely nothing to affect the current solution progress so can be easily turned off by simply not defining a shadow period.