Horizon CDT Research Highlights

Research Highlights

Scenario Tree Compression for Stochastic Freight Service Network Design

  Xiaoping Jiang (2014 cohort)   www.nottingham.ac.uk/~psxxj1

The emergence and increasing prosperity of e-commerce in the past few years have transformed the landscape and expanded the scale of traditional freight transportation market. Due to various physical locations and shopping time of online shoppers, as well as different types and quantities of items purchased, the demand uncertainties have made freight service network design extremely difficult [1]. Freight transportation companies are struggling to find a way out. Therefore, Service network design with uncertainties is badly needed to address the problem more efficiently.

In my research, I will revolve around stochastic service network design problem at a tactical level [2]. In addition, less-than-truckload transportation and express delivery are my main focuses, for which consolidations are widely adopted in order to maximize the utilization of the logistic resources.

To properly account for uncertainties in service network design problems, stochastic programming as the existing mainstream methodology harnesses a finite set of scenarios. Generally modeling uncertainty with scenarios yields very large instances [3]. With appropriate set of scenarios generated, a two-stage stochastic network design problem presents itself and heuristic methods typically based on progressive hedging [4] are needed to produce high-quality designs.

Current scenario decomposition strategies used by meta-heuristic generate multiple single-scenario sub-problems. In an iteration of a progressive hedging approach, multiple sub-problems are solved with each sub-problem solution representing a potentially different network design [5]. A progressive hedging approach converges when all sub-problems yield the same design through multiple iterations.

Suppose the sub-problems are comprised of multiple scenarios, what will happen then? Potentially fewer iterations are needed to reach convergence if there are fewer sub-problems at an iteration[5]. A recent study[3] has shown that grouping scenarios to yield multi-scenario sub-problems is more efficient. However, how to group scenarios remains a problem. How can we turn single-scenario sub-problems into multi-scenario sub-problems in a manner that significantly reduces the number of iterations? This is the research gap.

Overall, my research will be carried out in three levels. Firstly, scenario trees in stochastic programming will be used to model uncertainties, notably demands. Secondly, two different scenario tree compression methods will be investigated. I plan to develop a dynamic scenario clustering method where reinforcement learning will be introduced to dynamically adjust the parameters for grouping scenarios. Short of this method, evolutionary computation is expected to be introduced into scenario classification. Finally, efficient algorithms will be developed to improve the performance of existing stochastic service network design methods. Freight service network design with rerouting will also be considered.


  1. Bai, R., Wallace, S.W., Li, J., Chong, A. Y.-L., 2014. Stochastic service network design with rerouting. Transportation Research Part B Methodological 60, 50-65.
  2. Crainic, T.G., 2000. Service network design in freight transportation. European Journal of Operational Research 122 (2), 272–288.
  3. Crainic, T.G., Hewitt M., Rei, W., 2014. Scenario grouping in a progressive hedging-based meta-heuristic for stochastic network design. Computers & Operations Research 43, 90-99.
  4. Crainic, T.G., Fu, X., Gendreau, M., Rei, W., Wallace, S.W., 2011. Progressive hedging-based meta-heuristics for stochastic network design. Networks 58 (2), 114–124.
  5. Crainic, T.G., Hewitt, M., Rei, W., 2012. Scenario clustering in a progressive hedging-based meta-heuristic for stochastic network design. Publication CIRRELT 2013 (52), 1–25.

This work was carried out at the International Doctoral Innovation Centre (IDIC). The authors acknowledge the financial support from Ningbo Education Bureau, Ningbo Science and Technology Bureau, China's MOST, and the University of Nottingham. The work is also partially supported by EPSRC grant no EP/L015463/1.