Stochastic Routing with Arrival Windows

Arriving at a destination within a specific time window is important in many transportation settings. For example, trucks may be penalized for early or late arrivals at compact terminals, and early and late arrivals at general practitioners, dentists, etc. are also discouraged, in part due to COVID. We propose foundations for routing with arrival-window constraints. In a setting, where the travel time of a road segment is modeled by a probability distribution, we define two problems where the aim is to find a route from a source to a destination that optimizes or yields a high probability of arriving within a time window while departing as late as possible. In this setting, a core challenge is to enable comparison between paths that may potentially be part of a result path with the goal of determining whether a path is uninteresting and can be disregarded given the existence of another path. We show that existing solutions cannot be applied in this problem setting and instead propose novel comparison methods. Additionally, we introduce the notion of Stochastic Arrival-Window Contraction Hierarchies that enable accelerated query processing in the paper’s setting. Next, we present routing algorithms that exploit the above comparison methods in combination with so-called pivot paths and contraction hierarchies to enable efficient processing of the two types of queries. Finally, a detailed experimental study provides empirical insights that justify the need for the two types of routing and also offers insight into key characteristics of the problem solutions.