(181e) Adaptive Robust Optimization for Tactical-Level Distribution Problems Under Customer Order Uncertainty

Tactical-level distribution operations over a short-term horizon are central to many transportation problems. In such operations, customer orders are often received dynamically over the planning horizon. Each order consists of a demand quantity and a set of time periods (e.g., days) during which service can take place. The supplier must then assign a visit day to each customer order and design routes for each day so as to minimize the overall transportation cost. The plan is usually implemented in a rolling horizon fashion: routes of the first day are executed while new requests are recorded; unfulfilled orders at the end of the first day and new requests accumulated during the day constitute the new portfolio of orders to be considered for scheduling the following day. In contrast to typical vehicle routing problems (VRPs), where the planning horizon consists of one period during which all customer requests must be serviced, in the tactical level scheduling and routing decisions must be made simultaneously over a multi-period horizon. This problem has been referred to as the Dynamic Multi-Period VRP [1] or as the Tactical Planning VRP [2] and is highly relevant to systems in which logistics and other services are provided by appointment. For example, applications arise in food distribution [1], automobile transportation [3] and in maintenance scheduling [4].

In most existing approaches to address this problem, no knowledge is assumed about potential customers that may call in to request service in future time periods; in other words, the uncertainty in future customer requests is completely ignored. While this setup may be unavoidable in some contexts, companies often have large amounts of historical data, which can be used to obtain suitable order forecasts. It is thus possible to take advantage of this information and generate better, risk-averse solutions. In fact, not accounting for this uncertainty may lead to situations which can either be (i) infeasible because too many vehicles were required on some day, or (ii) too expensive in terms of routing costs. In this regard, [4] consider uncertainty in future requests; they utilize a probabilistic description where, at any time period, they assume the probability of demand in subsequent time periods of every possible customer that does not have a pending request. They consider an adaptive policy by solving a VRP subproblem to identify the set of pending customers that should be serviced on the first day of the planning horizon, along with the actual vehicle routes.

In this work, we propose a novel Robust Optimization approach in which the uncertainty in future customer requests is captured via a purely discrete uncertainty set. This uncertainty set consists of a finite (but possibly very large) number of discrete scenarios and admits a polyhedral representation. Each scenario represents a possible combination of customer requests that may potentially realize during the planning horizon. This model of uncertainty is especially attractive in cases where historical record is not rich enough to regress out detailed probabilistic information. It is also very flexible, as it allows us to capture various practically meaningful correlations that link customer requests in temporal, geographical or other terms.

Our solution approach views the problem as a two-stage robust optimization problem, in which the routing and scheduling decisions for the known customers (i.e., customers who have a pending service request) are first-stage decisions while the assignment of future customer requests to the routing plan constitute second-stage decisions. We design routes for each day of the planning horizon such that customers who have already placed an order are visited exactly once throughout the planning horizon. Moreover, any realization of future customer requests from the uncertainty set can be assigned to the designed routing plan in a way that all vehicle capacities are respected. We guarantee that the routing decisions to which we commit to here-and-now will not render the overall operation infeasible when an admissible realization of future customers materializes.

We remark that a static robust policy, where all assignment decisions are made here-and-now, would be infeasible or overly conservative in this setting for all but the most favorable instances. To that end, we consider an adaptive strategy where the assignment decisions are allowed to adjust on the value of the observed realization, and we present algorithms to solve the resulting robust models to guaranteed optimality. We investigate the tradeoffs in using an adaptive strategy in terms of cost savings and computational time. Our study allows the decision-maker to quantify the cost increase in implementing a robust plan and to decide the level of robustness that is appropriate to the application. For the instances we considered in our computational experiments, robust routing plans can be obtained with a modest cost increase of less than 5%.

[1] M. Wen, J.-F. Cordeau, G. Laporte, and J. Larsen (2010). The dynamic multi-period vehicle routing problem. Computers & Operations Research, 37:1615â??1623.

[2] R. Baldacci, E. Bartolini, A. Mingozzi, and A. Valetta (2011). An exact algorithm for the period routing problem. Operations Research, 59(1):228â??241.

[3] J.-F. Cordeau, M. Dellâ??Amico, S. Falavigna, and M. Iori (2015). A rolling-horizon algorithm for auto-carrier transportation. Transportation Research Part B: Methodological, 76:68â??80.

[4] H. Tang, E. Miller-Hooks, and R. Tomastik (2007). Scheduling technicians for planned maintenance of geographically distributed equipment. Transportation Research Part E: Logistics and Transportation Review, 43(5):591â??609.

[5] M. Albareda-Sambola, E. Fernandez, and G. Laporte (2014). The dynamic multiperiod vehicle routing problem with probabilistic information. Computers & Operations Research, 48:31â??39.