(52g) Strategic Time Window Assignment in Vehicle Routing Operations

The delivery (or pickup) of goods within a scheduled time window is widespread in several real world distribution networks. In many industries, these time windows are mutually agreed upon by the distributor and customer through long-term (e.g., annual) delivery contracts. From the customer’s point of view, this is crucial for efficient inventory management and scheduling of personnel to process the delivery. From the distributor's point of view, this is crucial for reducing the variability across repetitive deliveries and can expose efficiencies that add up to significant cost savings. Examples of applications where such operations are typical include, among others, retail distribution [1], vendor-managed inventory routing [2] and courier services [3].

Once a time window has been agreed upon and communicated to the customer, the distributor must attempt to meet it on an operational (e.g., daily) basis as well as possible. This is done by solving a Vehicle Routing Problem with Time Windows (VRPTW) [4] to determine a delivery schedule that adheres to the agreed time windows. The assigned time windows strongly influence the structure of feasible schedules and, hence, the daily incurred distribution costs. Therefore, a natural choice is to assign time windows based on the arrival times at customer locations in the optimal (i.e., minimum cost) vehicle routing schedule computed under nominal conditions. However, this seemingly optimal decision may become highly suboptimal in the presence of operational uncertainty, particularly in situations that deviate from the nominal case. For example, the demand volume of a customer typically fluctuates per delivery. Similarly, travel times vary on a day-to-day basis (e.g., because of unpredictable traffic conditions). The true values of these parameters become known only on the day of delivery before the vehicles are dispatched. This makes the strategic assignment of time windows a non-trivial task.

In this work, we study the Time Window Assignment Vehicle Routing Problem (TWAVRP), which consists of strategically assigning long-term delivery time windows to customers. Feasible time windows may either be of pre-specified width within some exogenous windows (e.g., representing operating hours or government regulations) or selected from a set of a priori windows (e.g., AM/PM). A finite set of scenarios, each describing a possible realization of the uncertainty, is also assumed to be given with known probability of occurrence. This information is used to formulate a two-stage stochastic program, in which the first-stage decisions are to assign time windows, while the second-stage decisions are to design vehicle routing schedules satisfying the assigned time windows, one for each of the scenarios. The objective is to minimize the total routing costs, averaged over the postulated scenarios.

Our first contribution is to show that the two-stage stochastic programming formulation of the TWAVRP can be reduced to a variant of a large class of problems, popularly known as Consistent Vehicle Routing Problems (ConVRP) [5]. The goal of the ConVRP is to design minimum cost vehicle routes over a finite, multi-day horizon which remain "consistent" over time. We formally prove that the endogenous time windows in the TWAVRP serve to satisfy the arrival-time consistency requirement of the ConVRP [6], which requires that every customer be visited at roughly the same time whenever service is requested.

Our second contribution is to leverage the above stated result to develop a new, efficient scenario decomposition algorithm, to solve the TWAVRP. We demonstrate that our algorithm strongly outperforms all existing solution methods [1, 7, 8], and furthermore, that it is both modular and scalable. From a modeling viewpoint, it can accommodate general scenario-based models of uncertainty for several routing-specific parameters as well as continuous or discrete sets of feasible time window assignments. From an algorithmic viewpoint, it can be easily parallelized, can utilize any available vehicle routing solver in a black box fashion, and can be readily modified as a heuristic for large-scale instances. Notably, we show that our algorithm strongly outperforms all previous state-of-the-art methods, solving for the first time 54 previously open instances. Among other features, our algorithm also incorporates a new class of path-based disjunctions for the TWAVRP; in view of the relationship between the TWAVRP and ConVRP, these disjunctions are new for the ConVRP as well.

Our third contribution is to conduct computational experiments with a parallel implementation of our algorithm to solve instances consisting up to fifteen scenarios, representing a five-fold increase compared to existing methods. Using our algorithm, and via out-of-sample simulations, we numerically quantify the tradeoff between computational tractability and expected cost savings when considering more scenarios of future uncertainty during strategic time window assignment. Our business insights are that long-term costs are expected to decrease by modeling more scenarios of future uncertainty but the marginal benefits rapidly diminish as a function of the number of postulated scenarios. In other words, a few scenarios are sufficient to obtain time window assignments that would incur lower long-term costs compared to those that would be obtained by completely ignoring uncertainty.

References:
[1] R. Spliet, and A.F. Gabor (2015). The Time Window Assignment Vehicle Routing Problem. Transportation Science, 49(4):721—731.
[2] C. Zhang, G. Nemhauser, J. Sokol, M.-S. Cheon, and D. Papageorgiou (2015). Robust Inventory Routing with Flexible Time Window Allocation. Available at Optimization Online (2015/01/4744).
[3] O. Jabali, R. Leus, T. van Woensel, and T. de Kok (2015). Self-imposed Time Windows in Vehicle Routing Problems. OR Spectrum, 37(2):331—352.
[4] G. Desaulniers, O.B.G. Madsen, and S. Ropke (2014). Chapter 5: The Vehicle Routing Problem with Time Windows. In Vehicle Routing: Problems, Methods and Applications, P. Toth, and D. Vigo (editors), 119—159, Society for Industrial and Applied Mathematics, Philadelphia, PA.
[5] C. Gröer, B. Golden and E. Wasil (2009). The Consistent Vehicle Routing Problem. Manufacturing & Service Operations Management, 11(4):630—643.
[6] A. Subramanyam, and C.E. Gounaris (2018). A Decomposition Algorithm for the Consistent Traveling Salesman Problem with Vehicle Idling. Transportation Science, 52(2):386—401.
[7] R. Spliet, and G. Desaulniers (2015). The Discrete Time Window Assignment Vehicle Routing Problem. European Journal of Operational Research, 244(2):379—391.
[8] K. Dalmeijer, and R. Spliet (2018). A Branch-and-cut Algorithm for the Time Window Assignment Vehicle Routing Problem. Computers & Operations Research, 89:140—152.