Modeling Parking Search on a Network by Using Stochastic Shortest Paths with History Dependence

A substantial amount of urban traffic is related to drivers searching for parking. This study developed an online stochastic shortest path model to represent the parking search process in which drivers must choose whether to park at an available space or continue searching for a space closer to their destination. Existing online shortest path algorithms had been formulated for the full-reset or no-reset assumptions on revisiting links. As described in this paper, neither assumption was fully suitable for the parking search process. Accordingly, this paper proposes an asymptotic reset model that generalizes the full-reset and no-reset cases and uses the concept of reset rate to characterize the temporal dependence of parking probabilities on earlier observations. In this model, drivers try to minimize their expected travel cost, which includes the driving cost and the cost of walking from a parking spot to the actual destination conditioned on the parking availability on m most recently traversed links. The problem was formulated as a Markov decision process and was demonstrated with a network representing the neighborhood of the University of Wyoming campus in Laramie. The case study successfully shows the extra time used by drivers to cruise for an acceptable parking space and illustrates the impact of m on the computation effort required to compute an optimal policy.