A mean-variance model for route guidance in advanced traveler information systems

Traditional models of route generation are based on choosing routes that minimize expected travel-time between origin and destination. Such approaches do not account for the fact that travelers often incorporate travel-time variability within their decision making. Thus, a route with lower travel-time variability is preferred by some travelers, even if such a route is not one with the lowest mean travel-time. Such traveler behavior is best captured by a multiobjective model in which the choice of a route is based on the mean as well as the variance of the path travel-time. Our route-planning model is intended to help travelers make choices that reflect their decision-making process better. We formulate a network flow multiobjective model in which one of the objectives (expectation) is linear, whereas the other (variance) is quadratic. In order to present the user with a series of options, we solve a series of parametric 0–1 quadratic integer programs. By utilizing the network structure of the problem, we devise an effective algorithm in which the 0–1 quadratic program is solved by using a continuous relaxation together with an enumeration of some selected paths. Finally, we note that the data requirements for the model can be easily satisfied in practice.