Incorporating random delays into an existing vehicle schedule: a method comparison

In this thesis we address the problem of adapting an existing schedule to random delays by deciding on how to allocate available buffer time to different legs of the route and what actions to take in case delay has been incurred. We build upon the work of Mulder and Dekker (2016), who formulated the problem of deciding on the actions as a linear program based on a Markov Decision Process and presented a mixed integer programming formulation for the full problem. They also proposed two exchange heuristics, which compute or estimate the cost reduction for each possible exchange of buffer between legs and make the best exchange. We propose several more methods and recommend three of them based on computational experiments. The best slow and steady method is the exchange heuristic that computes cost exactly. A similar heuristic that does not analyse every exchange but draws them randomly should be used for fast approximations of an optimum. An exchange heuristic that does not recompute cost at every iteration, but uses previously computed values, provides the best balance between solution quality and computation time. In addition, we show that the estimation method is inaccurate and should be treated with care.