Multi-period vehicle assignment with stochastic load availability

We investigate the following problem, which is faced by major forwarding companies active in road transportation (see [2]). A company owning a limited fl eet of vehicles wants to maximize its operational pro fit over an infi nite horizon divided into equal periods (days). The pro fit stems from revenues for transporting full truckloads and from costs derived from waiting idle and moving empty. A decision leading to a set of actions is made at every period and is based on the dispatcher's information over a restricted horizon, called rolling horizon, which subsequently rolls over period per period. The data provided by the customers concern their prospective loads, or requirements for transportation: locations of departure and destination cities, and a unique pick-up period for each load. Moreover, the dispatcher has data regarding travel times between cities, current location and status (empty or loaded) of trucks. These data are known with certainty and represent the deterministic component of the problem. The stochastic component of the problem arises from the uncertainty on the eff ective materialization of each transportation order. More precisely, the availability of each order can be either con rmed, or denied, a few periods ahead of the loading period (meaning that clients con firm their order, which the transporter may still decide to ful ll, or not). For prospective orders in the remote part of the rolling horizon, the dispatcher only knows the order con firmation probability which represents the stochastic load availability. In this setting, trucking orders are provided by the dispatching center to the drivers and to the customers on the eve of the pick-up period at the latest. Typically, the loading decisions are made when all orders are con firmed for the next day. The decision problem faced by the dispatcher is to select or to reject loads, and to assign the selected loads to trucks, taking into account con firmed and expected loads as well as the availability and current location of trucks. The main objective of this research is to provide e fficient algorithmic strategies to tackle this multi-period vehicle-load assignment problem over a rolling horizon including prospective transportation orders. This problem is computationally di fficult owing to the large number of possible realizations of the random variables, and to the combinatorial nature of the decision space. The methodology is based on optimizing decisions for deterministic scenarios. By solving the assignment problem for a sample of scenarios, by mixing solutions and by evaluating them at each period, we aim at finding actions per decision period leading to pro table policies in the long run. Several policies are generated in this way, from simple myopic heuristics to more complex approaches, such as consensus and restricted expectation algorithms [3], up to policies derived from network flow models formulated over subtrees of scenarios. Similar approaches have proved eff ective for other problems; see, e.g., [1]. Myopic and a-posteriori deterministic optimization models are used to compute bounds allowing for performance evaluation. Test are performed on various instances featuring di fferent numbers of loads, graph sizes, sparsity, and probability distributions. Performances are compared statistically over paired samples to assess the signi ficance of the observed differences among algorithmic policies. The robustness of various policies with respect to erroneous evaluations of the probability distributions is also analyzed. Numerical experiments show that the best algorithms close a signi ficant fraction of the gap between the worst (myopic) and best (a posteriori) bounds for a broad range of datasets and for several probability distributions. Furthermore, the subtree algorithm remains quite robust against a variety of probability distributions when it is calibrated with a distribution re flecting maximum uncertainty . Acknowledgements. The project leading to these results was partially funded by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy O ffice (grant P7/36). References [1] Arda, Y., Crama, Y., Kronus, D., Pironet, Th., and Van Hentenryck, P. (2013), Multi-period vehicle loading with stochastic release dates, EURO Journal on Transportation and Logistics, pp. 1-27, available on-line http://dx.doi.org/10.1007/s13676-013-0035-z. [2] Powell, W. B. (1996), A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers, Transportation Science, Vol. 30, pp. 195-219. [3] Van Hentenryck, P., and Bent,R. W. (2006), Online Stochastic Combinatorial Optimization, MIT Press, Cambridge, Massachussetts