When solving a routing problem with time windows, unless you go for the arc-based math program that describes it, you have to check time windows "manually." For example, generating routes with any procedure would require this verification in the route generation process. Are there computational (or numerical or mathematical) tricks to perform this constraint verification quickly for a given route (sequence of nodes)? In particular (and this is the harder case) when you can't wait until the time window starts (meaning, can't arrive way too early to a location).
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Indeed, as you pointed out already, checking time windows feasibility is only doable in linear time for a given, static, route.
However, you may exploit preprocessing techniques and partial paths concatenation to achieve constant time worst-case complexity to assess time windows feasibility within a typical routing metaheuristic. Take a look at the article by T Vidal et al on the subject.
Best
-
1$\begingroup$ Visser, T.R. & Spliet, R. (2017). Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems. Econometric Institute Research Papers, EI2017-23, may also be a useful reference. The main focus of this paper is on time-dependent travel times, but results for the not time-dependent case are also stated (e.g., see Tables 1 and 2). $\endgroup$ Commented Jul 9, 2019 at 20:54
-
$\begingroup$ I guess what you mean by "partial paths concatenation" is described in Savelsbergh, Martin WP. "Local search in routing problems with time windows." Annals of Operations research 4.1 (1985): 285-305. With this approach constant time evaluation can be achieved. Note that it is only efficient if the time windows are evaluated for all moves. $\endgroup$– ktnrCommented Aug 21, 2019 at 15:38
$\begingroup$
$\endgroup$
The standard slack time calculation used by various authors takes the last stop in a route (which could be the 'depot' stop), works out the latest feasible time it can be served without breaking its time window, and then propagates this 'latest feasible time' backwards in the route (i.e. to the stop before, the stop before that etc). The back propagation calculation uses open time, travel time etc. Each time it propagates this 'latest feasible time' backwards, it takes the min of 'latest feasible time' from the stops later in the route and the current stop. The result is that for each stop, you get the latest feasible time it can be served without breaking its time window constraint or those later in the route.
Regarding not being able to wait until the time window starts, I'm guessing - but haven't proved mathematically - that you could use this methodology but for each stop calculate the 'earliest feasible time' it can be served instead and when you back propagate, take the max of 'earliest feasible time' instead? You'd presumably only use this 'earliest feasible time' if you're removing or swapping a stop in a route though?
answered Jul 9, 2019 at 22:40