Minimum costs paths in intermodal transportation networks with stochastic travel times and overbookings

In intermodal transportation, it is essential to balance the trade-off between the cost and duration of a route. The duration of a path is inherently stochastic because of delays and the possibility of overbooking. We study a problem faced by a company that supports shippers with advice for the route selection. The challenge is to find Pareto-optimal solutions regarding the route’s costs and the probability of arriving before a specific deadline. We show how this probability can be calculated in a network with scheduled departure times and the possibility of overbookings. To solve this problem, we give an optimal algorithm, but as its running time becomes too long for larger networks, we also develop a heuristic. The idea of this heuristic is to replace the stochastic variables by deterministic risk measures and solve the resulting deterministic optimization problem. The heuristic produces, in a fraction of the optimal algorithm’s running time, solutions of which the costs are only a few percent higher than the optimal costs.