Stochastic service network design for transportation planning of consolidation carriers

Service network design (SND) has long been used in freight transportation to assist consolidation carriers with tactical planning. Defined on a directed graph, SND entails deciding which arcs to open and how to route commodities on selected arcs, so that customers' shipping demands are met at minimum cost. Most studies on SND assume that customers' demands are known with certainty. This assumption is rarely observed in real-life applications, however. Indeed, consolidation carriers are often faced with demand uncertainty at the decision-making point. In order to build a robust service network that functions well for various demand realizations, it is necessary to take demand uncertainty explicitly into account. SND with demand uncertainty is referred to as stochastic service network design (SSND). Despite its significance, SSND has received relatively little attention by the research community due to its intractability. This thesis advances the research on SSND in three respects. Firstly, a scenario bundling method is presented to improve the progressive hedging heuristic for SSND. With demand uncertainty represented by scenarios, the mathematical model of SSND naturally possesses a scenario-wise decomposable structure. The progressive hedging heuristic takes advantage of this special structure to solve SSND. An attractive algorithmic enhancement to progressive hedging is the bundle-wise decomposition, which divides the model according to scenario bundles rather than individual scenarios. At the heart of bundle-wise decomposition is the method for grouping scenarios into bundles. This thesis presents a soft clustering-based scenario bundling method to fill the need. The proposed method differs from existing methods in that the membership relation between a scenario and a bundle is described by probabilities rather than by Boolean values. The probabilistic membership scores bring many advantages. When fuzzy c-means is used to calculate the membership scores, various degrees of overlap between scenario bundles can be easily created. When Gaussian mixture models are used to calculate the membership scores, various covariance structures can be freely specified for scenario bundles. The impacts of degrees of overlap and covariance structures on the computational performance of the progressive hedging heuristic are empirically studied in this thesis. The experimental results show that the progressive hedging heuristic based on Gaussian mixture models yields better computational performance than that based on k-means, fuzzy c-means or the cover method. Secondly, a method for computing lower bounds of SSND is developed. Lower bounds play an important role in the development of solution approaches to SSND. Exact methods rely on lower bounds to prune regions of the search space that do not contain any optimal solution. Heuristic methods depend on lower bounds to assess the solution quality. This thesis attempts to derive lower bounds for SSND from its Lagrange dual problem, which is obtained by performing scenario-wise decomposition of the SSND model and relaxing the resulting nonanticipativity constraints. For a tighter lower bound, scenario-wise decomposition is replaced with bundle-wise decomposition. Theoretical analyses establish the superiority of bundle-wise decomposition over scenario-wise decomposition in the quality of lower bounds. In order to solve the Lagrange dual problem, the recently proposed FW-PH algorithm that combines progressive hedging with a Frank-Wolfe-like method is employed. Although convergence to the optimal Lagrange dual value is assured, the FW-PH algorithm may exhibit slow convergence speed. For a quick convergence, the FW-PH algorithm is extended by replacing scenario-wise decomposition with bundle-wise decomposition. Scenario bundles are constructed using Gaussian mixture models. Theoretical analyses and computational experiments establish that this extension yields a dramatic speedup without spoiling the convergence property. Lastly, a method for deriving vehicle routes from an optimized service network is proposed. Given an optimized service network from SND, one immediately obtains a set of commodity paths. In practice, consolidation carriers often need to design a set of vehicle routes, on which some real-life restrictions are placed. Cyclic vehicle routes are usually required so that drivers can periodically return to their domiciles. Due to the presence of commodity transshipment and consolidation, commodity paths and vehicle routes are usually different. Seeing the mismatch, this thesis introduces a new problem of how to generate a set of cyclic vehicle routes based on an optimized service network. A three-phase scheme is proposed to address this problem, with the first phase searching for all different cyclic routes, the second phase pruning poor cyclic routes and the third phase covering the given service network by cyclic routes. In the proposed scheme, many real-life constraints can be taken into account by appropriate parameter setting, making the resulting vehicle routes more suitable for practical applications. Experimental results show that the proposed solution scheme is quite effective with regard to solution quality and computing efficiency