Shortest Path Problems with a Crash Risk Objective

Abstract

With more and more data related to driving, traffic, and road conditions becoming available, there has been renewed interest in predictive modeling of traffic incident risk and corresponding risk factors. New machine learning approaches in particular have recently been proposed, with the goal of forecasting the occurrence of either actual incidents or their surrogates, or estimating driving risk over specific time intervals, road segments, or both. At the same time, as evidenced by our review, prescriptive modeling literature (e.g., routing or truck scheduling) has yet to capitalize on these advancements. Indeed, research into risk-aware modeling for driving is almost entirely focused on hazardous materials transportation (with a very distinct risk profile) and frequently assumes a fixed incident risk per mile driven. We propose a framework for developing data-driven prescriptive optimization models with risk criteria for traditional trucking applications. This approach is combined with a recently developed machine learning model to predict driving risk over a medium-term time horizon (the next 20 min to an hour of driving), resulting in a biobjective shortest path problem. We further propose a solution approach based on the k-shortest path algorithm and illustrate how this can be employed.