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
Background
-
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
jsprit
with 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.
Extending Library
-
Extend the
TimeWindow
class to create aShadowTimeWindow
. -
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.
Insertion Logic
-
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 (SolutionCostCalculator
) -
The concern from Stefan, I think, on Braktar’s implementation was that insertion costs should be considered only examining jobs
i
,k
,j
, wherek
is the job to be inserted betweeni
andj
.
-
SHORT CIRCUIT. If
ShadowCount
is 0 andk
is 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
j
by insertingk
to 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
k
has a shadow window of 16:00-17:00, if it is inserted at 16:25 then you have 25 minutes. Call thisNewShadowAddition
.
-
Pass
((0.5*ShadowTime) + NewShadowAddition)
to the problem-level penalty function to return total cost penalty. -
Increment
ShadowCount
by 1,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
SolutionCompletenessRatio
to limit its impact -
Store
ShadowTime
as dual-feature data, where theShadowTime
is 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.
Josh