The design of a service network is a complex planning problem involving interrelated and interdependent choices that can be classified in three planing steps: strategic, tactical and operational planning. Tactical planning step addresses medium term planning decisions, mostly related to the design of the service network: selection of the services to perform, schedules and routing of freight.
Service network design problems have mainly been studied under the assumption that all the necessary information needed to make decisions are available and completely known before the design decisions are made.
Instead, it is an inherently stochastic problem, involving making choices in a highly uncertain environment. Demands, costs, profits,travel time, service time and, sometimes, customers' locations are examples of needed and uncertain parameters in a tactical planning problem.
Service network design problems under uncertainty have already been treated [add references] in the literature. However, few contributions dealing with design of services and stochastic time have appeared. In many real-life applications, however, a considerable degree of variability in travel times could be observed, and thus a static and deterministic travel time assumption does not represent an accurate and realistic approximation of actual travel time. Instead, variability on time can lead to important changes, mostly related to the planned schedules.
Our research focuses on stochastic travel time. In particular, on a scheduled service network design problem with unexpected stochastic travel time variations
Several efforts have been directed towards the formulation of service network design models.
Most of the proposed formulations, however, assume that all the necessary information to build a service network is available and completely known at the moment of planning. As opposed,
planning usually means facing with the challenge of making decisions when only limited information is available. The presence of uncertainty in the network (demand, cost, profit, lead time, reliability of vehicles, customers' locations) is a critical issue to consider explicitly in the decision process to achieve the above mentioned carrier goals making of SND a very challenging problem to address [Powell and Topaloglu, 2003].
The most studied stochastic phenomenon in the SND literature is customers' demand. One aspect which received little attention is, instead, travel time (time needed to travel between two consecutive stops). The vast majority of proposed model formulations assume, in fact, travel time as a deterministic parameter, commonly built on point forecasts based on historical data. The travel time observed in actual operations may, however, differ from estimations due to a variety of influences such traffic congestion or heavy weather conditions, resulting in potential additional economical costs related to crews and resource utilization and, in addition to them, fines and loss of reputation for not respecting planned arrival times and agreed upon time of deliveries. A deterministic time assumption is, therefore, a strong assumption which not only do not represent a realistic approximation of this phenomenon, but also may lead to poor decisions with respect to economic and quality goals. Despite its importance, only few contributions dealing with design of transportation services and stochastic time have appeared in the literature till now and none of those focused on the definition of a reliable service network in terms of both schedules and freight deliveries as we do.
To the best of our knowledge, this problem has never been considered in the literature before. We have defined it as the Stochastic Service Network Design problem with Service and Demand Targets (SSND-SDT).
The first goal of our research is, therefore, to address the problem of defining a cost-efficient transportation plan such that the selected services and the specified routes of freight respect,
respectively, the scheduled arrival times at stops and due dates as much as possible over time. To achieve this purpose, we propose a stochastic SND original methodology, where the uncertainty of
travel time is explicitly accounted into the decision process and quality targets are modelled through penalties. Design and routing decisions are made before any travel time realization. The proposed
formulation, therefore, takes the form of a two-stage mixed-integer linear stochastic model. In the first stage, design and routing decisions are taken, while in the second stage, when travel time
realizations become known, the given targets are accounted and delays for a given travel time realization and a chosen design are properly penalized.
SND problems are notoriously NP-Hard. On the one hand small to medium-sized problem instances can be solved optimally, on the other hand heuristic methods are generally needed to find high-quality solution to real-life instances in acceptable time. Our second goal for this research is to propose an effective progressive hedging-based meta-heuristic (PHM) algorithm to tackle the above mentioned problem.