A mixed integer linear programming model for dynamic route guidance

One of the major challenges facing ITS (Intelligent Transportation Systems) today is to offer route guidance to vehicular traffic so as to reduce trip time experienced. In a cooperative route guidance system, the problem becomes one of assigning routes to vehicles departing at given times from a set of origins to a set of destinations so as to minimize the average trip time experienced (a so-called system optimal criterion). Since the time to traverse a link will depend upon traffic volume encountered on that link, link times are dynamic. The complex interaction resulting between objective function and constraints makes the dynamic problem significantly more difficult to formulate and solve than the static version. We present a mixed integer linear programming (MILP) formulation of the problem which is formally derived from a set of traffic flow assumptions. Principal among these is the simplifying assumption that vehicles upon entering a link, assume the speed that traffic would attain were the traffic volume encountered on that link in steady-state. The integer variables correspond to selection of vehicle capacity constraints on the link while the continuous variables correspond to selection of vehicle routes. Implicit within this MILP formulation of the dynamic traffic assignment problem is therefore a decomposition of the problem which results in a conventional capacitated linear programming network flow problem. A small illustrative subnetwork extracted from the city of Sioux Falls is solved to optimality by IBM's OSL Branch-and-Bound algorithm.