(343g) Robust Multi-Period Vehicle Routing: Construction of Uncertainty Sets and Evaluation Via Rolling-Horizon Simulations

The Vehicle Routing Problem (VRP) is fundamental to transportation operations in industrial and commercial supply chains. It is concerned with the design of cost-optimal routes for a fleet of capacity-constrained vehicles (e.g., trucks) to serve a set of geographically distributed customers.

Traditional VRP variants are of an operational nature since they involve the design of vehicle routes over a single period (e.g., a work day). However, several transportation problems arising in practice are of a tactical nature since they involve the scheduling and routing of vehicles over multiple time periods (e.g., a week). This is particularly the case when customers may dynamically place service requests/orders on any given day, and each request specifies a set of future days (also called "day window") during which service can take place. At the end of each day, the distributor must make scheduling decisions consisting of assigning a visit day to each unfulfilled service request, along with the standard routing decisions, so as to minimize the long-run transportation costs. It is important to note that the computed schedule is implemented in a rolling horizon fashion: only routes of the first day are executed while new orders are received; unfulfilled requests at the end of the first day and new customer requests accumulated during the day constitute the new portfolio of orders to be considered for scheduling the following day. Such decision-making setups are typical in systems in which services are provided by appointment; relevant examples include scheduling of maintenance personnel [1, 2], food distribution and collection [3], and auto-carrier transportation [4]. We refer to this class of problems as Multi-Period VRPs.

Existing approaches for the Multi-Period VRP (e.g., see [3, 5]) essentially ignore the uncertainty in future customer orders, arising from the dynamic aspect of the problem. In other words, the models are agnostic to potential service requests that may be received in the future, even those that may be received within the current planning horizon. Consequently, the computed schedules lead to situations which can either be infeasible, leading to additional costs that must be incurred to recover feasible schedules (e.g., commissioning additional vehicles), or too expensive in terms of transportation costs. In contrast, we can generate better, risk-averse schedules by explicitly accounting for customer order uncertainty during the planning process. This is supported by the fact that companies and distributors often have large amounts of historical data, which can be used to obtain demand forecasts and provide information regarding calls for service in future time periods.

In a recent paper [6], we proposed a modeling and solution methodology that explicitly hedges against customer order uncertainty in Multi-Period VRP variants. The specific highlights of this paper were as follows. First, we modeled future customer orders as binary random variables, and encapsulated the set of probable future scenarios in an uncertainty set of finite (but possibly very large) cardinality. Second, we used this model of uncertainty in a robust optimization framework. The "true" model is multi-stage with binary recourse decisions and, hence, is computationally intractable. Therefore, we developed two tractable two-stage surrogate models (each with binary recourse decisions) that provide an upper bound and a lower bound to the true multi-stage model, respectively. Notably, the upper bounding model is practically implementable and its solutions can be adopted by the practitioner for daily operations. Third, we developed an efficient integer programming formulation and branch-and-cut solution algorithm for the two-stage models. The computational experiments showed that (i) we can obtain robust schedules for 100-customer, 5-period problems in less than 2 hours, by paying an additional transportation cost of about 1.5% (on average), and, (ii) the approximation gap of our two-stage model against the "true" multi-stage model is less than 1% (on average).

In this work, we extend the above mentioned paper in three important directions. The contributions are enabled by a rolling-horizon simulation platform that we developed to mimic the day-to-day operations of distributors. Notably, the simulation platform allows us to evaluate the true long-run cost of any decision policy for the Multi-Period VRP, and thus, allows us to draw practically meaningful insights.

Our specific contributions are as follows. First, we use statistical models to construct uncertainty sets from historical data, and show how to update these sets in a rolling-horizon context. The size of our constructed uncertainty sets can be easily tuned to reflect distributors’ risk tolerance. Second, we use our simulation platform to identify the ideal length of the planning horizon which appropriately trades-off computational tractability with cost savings. To elaborate, a longer horizon can yield higher cost savings, but is also more difficult to optimize; therefore, the potential benefits may not be realizable as the computed schedules may be suboptimal in practice. Third, we adopt the constructed uncertainty sets and optimal planning horizon in our simulations, and analyze the impact of multiple operating policies on distribution costs. Specifically, we analyze the impact of (i) day-window widths (e.g., next-day service vs. two-day service), (ii) fleet size and capacity, (iii) vehicle commissioning costs, and (iv) advance notice periods (i.e., number of days elapsed between the day an order was placed and the first feasible service day). In all, our contribution is a holistic decision-making framework that practitioners can utilize for tactical planning of their distribution operations.

References:
[1] N. Bostel, P. Dejax, P. Guez and F. Tricoire (2008). Multiperiod planning and routing on a rolling horizon for field force optimization logistics. In Vehicle Routing: Latest Advances and New Challenges, B. Golden, S. Raghavan, and E. Wasil (editors), 503—525, Springer US, Boston, MA.
[2] 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.
[3] M. Wen, J.-F. Cordeau, G. Laporte, and J. Larsen (2010). The dynamic multi-period vehicle routing problem. Computers & Operations Research, 37:1615—1623.
[4] 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.
[5] R. Baldacci, E. Bartolini, A. Mingozzi, and A. Valetta (2011). An exact algorithm for the period routing problem. Operations Research, 59(1):228—241.
[6] A. Subramanyam, F. Mufalli, J.M. Pinto, and C.E. Gounaris (2017). Robust multi-period vehicle routing under customer order uncertainty. Available at Optimization Online (2017/04/5947).