Service network design problem with quality targets and stochastic travel time: new model and algorithm

Network design formulations in which time is explicitly taken as a stochastic parameter have been neglected in the service network design literature in favor of settings in which other stochastic parameters were taken into account (primarily demand). Nowadays, however, reliability is one of the major competitive dimensions of many firms. From a customer point of view, reliability - the on-time delivery of products - is a criterion that a firm must meet a priori, just to be considered as a possible supplier. From the point of view of carriers, reliability - the on-time occurrence of operations - is strictly related to the respect of an "ideal" or "imposed" schedule. This is particularly important, for consolidation-based transportation systems, where total system costs may also involve the costs raising from missing a proper sequencing of services for some commodities. In this work, we propose to study a service network design problem from a carrier point of view in which travel time is explicitly considered as a stochastic parameter in the decision process and in which the goal is to define a cost-efficient service network that satisfies given service quality targets consistently as close as possible in time. To the best of our knowledge, this is the first time such a problem has been investigated. The problem is modeled as a two-stage scenario-based stochastic programming model. In the first stage, planning decisions are made considering their future effects: the selection of the services and the routing of freight are determined with the objective of minimizing the fixed service-selection and variable demand-routing costs, plus the expected penalty costs following the application of the chosen plan to the observed realizations of travel times. The second stage addresses how to deal with delays for a given travel time realization and a chosen design. Network design problems are notoriously NP-Hard. A progressive hedging-based meta-heuristic algorithm able to provide good quality solutions to the problem is, also, proposed. The idea is to decompose the original scenario-based stochastic problem into single-scenario-sub-problems by relaxing first stage variables' non-anticipativity constraints. At each iteration, sub-problems are solved and non-anticipativity is gradually enforced trying to consolidate sub-problem solutions into a unique one, for the original problem. This is the first attempts to solve such a problem heuristically and, hence, to apply such a methodology to a SND problem with uncertainty in travel time. An extensive experimentation is reported to show the benefits in considering explicitly travel time stochasticity into the model rather having a deterministic time assumption, structural differences between stochastic and deterministic solutions and the performance of the proposed meta-heuristic algorithm. The scientific contribution of this thesis is four-fold: • to propose a new branch of research in the field of service network design problems by introducing uncertainty in time and the need of satisfying given service quality targets; • to provide an original two-stage stochastic linear mixed-integer programming formulation for the proposed SSND-SDT problem; • to show the attractiveness of the formulation and explore the role and importance of the various random parameters through an extensive numerical analysis; • to develop a progressive hedging-based meta-heuristic algorithm with a variable hierarchic approach able to efficiently find good quality solutions to the SSND-SDT.