1 Introduction

With great interest, I read the paper Perspectives on Integer Programming for Time-Dependent Models (Boland and Savelsbergh 2019). Evidenced by the growing stream of literature (as referenced in their paper), dynamic discretization discovery (DDD) is, and will be, a very rich future path for time-dependent models. I very much enjoyed reading the paper and I would like to congratulate Natashia and Martin for presenting this challenging material in a clear and comprehensive manner.

Time-dependent (TD) problems are everywhere and are a more realistic representation of real life than their time-independent (TID) counterpart. Additionally, solutions based on a TID model formulation are usually suboptimal or more likely to be infeasible in a TD world. In this comment, I elaborate on the importance of the DDD and present some additional thoughts. In the vehicle routing research domain, I did some work on the incorporation of time-dependent travel times (Dabia et al. 2013; Franceschetti et al. 2017; Sever et al. 2018; Sun et al. 2018a, b; Van Woensel et al. 2008). Interested readers are also referred to the excellent review paper by Gendreau et al. (2015).

2 Importance of dynamic discretization discovery

Time-dependent models are difficult. Using continuous variables leads to weak relaxations. Using binary variables leads to an explosion of the number of variables (Boland and Savelsbergh 2019). In the latter case, the original number of variables (of the time-independent model) needs to be multiplied with the number of time slices to have the needed variables. The variable definition now also identifies on what time unit t something will happen. In a routing context, the vehicle goes from customer i to customer j at time unit t. As noted by Boland and Savelsbergh (2019), the time bucketing is very important (Van Woensel et al. 2008). It has a direct effect on the needed granularity of information changing over time (e.g., speeds or traffic flows), on the amount of decision variables one needs to consider in the programming model, and, consequently on the solution times for the algorithms (both exact and heuristics).

In my opinion, it is for these cases that DDD has a key role: being able to use the finest granularity without all the above-mentioned problems. As such, this indeed allows for solving “a TD model based on a fine discretization without ever fully constructing it” (Boland and Savelsbergh 2019). Good to note is that often the availability of the information sometimes drives or limits the possible granularity that can be used in the modeling.

The price of adding time in the model formulations and the related solution methods is clear. On the other hand, adding time also leads to interesting new explicit decisions related to departure times or waiting at nodes. This gave rise to some literature related to departure time and speed optimization (see, e.g., Franceschetti et al. 2018; Wen et al. 2017), but also waiting at the customer nodes. Interestingly, only very few publications allow for idle waiting after service completion as a strategy to cope with time-dependent conditions, e.g., avoiding congestion which varies over time (Franceschetti et al. 2017). This issue is also pointed out by the authors as a challenging setting for the DDD.

3 Heuristics and dynamic discretization discovery

The authors already discussed, in their Research Opportunities section, many extensions that can be considered. In this second part of my comment, I would like to focus on the possible role of DDD in relation to heuristics. Scaling up the proposed algorithms seems promising, but so far only relatively small instances are handled, up to 100 locations for the TD-TSPTW (Boland and Savelsbergh 2019). Combining the DDD into heuristics, either metaheuristics or matheuristics, might overcome this scaling challenge, with a possible price of losing optimality.

In their paper, Visser and Spliet (2017) introduce some new methods for efficiently evaluating moves in a neighborhood search for a time-dependent routing problem. Evaluating several neighborhoods is computationally expensive in a TD setting. The authors develop a new tree-based data structure to improve the complexity of computations and memory usage. On 1000 customer instances, the authors show significant speedups in the algorithm. The expensive feasibility and cost calculation of a route can be done in \(\mathcal {O}(np \log n)\) time rather than in \(\mathcal {O}(n^2 p)\) time, where n is the number of customers on the route and p is the number of breakpoints coming from the time-dependent travel time functions.

The latter parameter p is actually a representation of the granularity of the time dependency considered (i.e., buckets). An interesting question would be how DDD could be used to determine the p dynamically, potentially decreasing the evaluation times further. Note that a similar question arises when solving the TD-VRPTW in an exact manner using traditional branch-and-price methodologies (Dabia et al. 2013). Here, dominance rules are extended, which consider the predefined time discretizations (via the ready time functions). Comparing two partial paths, potentially having a different time discretization (originating from DDD), is not straightforward.

In most (if not all) TD papers, it is assumed that the time discretization is given a priori, leading to the above discussed problems. Alternatively, using DDD in (meta-) heuristics as an additional neighborhood function, where the time discretization could be refined as part of the evaluation, seems interesting. Open questions remain on how to do this exactly, but also how to coordinate discretizations over the iterations and/or neighborhoods. In this case, it could be foreseeable that every neighborhood has possibly its own time refinement, necessitating some overall structure, or aligning time somehow.

Finally, coming up with a more general DDD policy could be an interesting research venue as well, but might only be feasible for specific problem families. Similar to Ulmer et al. (2019), who, for a single-vehicle routing problem with stochastic service requests, incrementally improved the granularity of their lookup table depending upon the received rewards, some learning aspects could be incorporated, leading to a policy (Powell 2019). Specifically, reinforcement learning techniques (Sutton and Barto 2018), like actor–critic approaches, could help to develop a good policy for DDD. The critic would then measure how good the discretization is (e.g., based on the obtained bounds) and the actor would suggest a change in the discretization (i.e., the discovery of new time points in Fig. 5 of Boland and Savelsbergh 2019). Rewards could also be related to the number of repairs needed. A disadvantage could be the training time needed with this type of methodology. But once the policy is there, it would help to instantly identify a good discretization. Some first steps in terms of combining reinforcement learning in a time-dependent environment (with given time discretizations) can be found in Mao and Shen (2018).

4 Concluding remarks

All in all, I very much enjoyed reading the paper and its presented material. It has the potential to be a large research area applying the proposed methodology to a variety of time-dependent problems. This paper gives a good and clear summary of the interested reader aiming to start working in this field. Moreover, it provides valuable pointers for future research.