A MIXED-INTEGER LINEAR-PROGRAMMING MODEL FOR DYNAMIC ROUTE GUIDANCE

One of the major challenges facing ITS (Intelligent Transportation Sys tems) today is to offer route guidance to vehicular traffic so as to r educe trip time experienced. In a cooperative route guidance system, t he problem becomes one of assigning routes to vehicles departing at gi ven times from a set of origins to a set of destinations so as to mini mize the average trip time experienced (a so-called system optimal cri terion). Since the time to traverse a link will depend upon traffic vo lume encountered on that link, link times are dynamic. The complex int eraction resulting between objective function and constraints makes th e dynamic problem significantly more difficult to formulate and solve than the static version. We present a mixed integer linear programming formulation of the problem which is formally derived from a set of tr affic flow assumptions. Principal among these is the simplifying assum ption that vehicles upon entering a link, assume the speed that traffi c would attain were the traffic volume encountered on that link in ste ady-state. The integer variables correspond to selection of vehicle ca pacity constraints on the link while the continuous variables correspo nd to selection of vehicle routes. Implicit within this MILP formulati on of the dynamic traffic assignment problem is therefore a decomposit ion of the problem which results in a conventional capacitated linear programming network flow problem. A small illustrative subnetwork extr acted from the city of Sioux Falls is solved to optimality by IBM's OS L Branch-and-Bound algorithm. (C) 1998 Elsevier Science Ltd. All right s reserved.