NSF Collaborative Research: Non-Additive Network Routing and Assignment Models

Avinash Unnikrishnan, Portland State University


Network assignment models are widely used to study the flow of commodities on infrastructure with a network structure (such as roadway drivers or freight shipments) and form the basis of transportation planning for urban areas. Currently, most network assignment models assume that the travel costs for a route is simply the sum of the travel costs of the roadway segments comprising that route. While true for some costs (like trip time), this assumption is invalid when accounting for costs due to unreliability, late arrival penalties, and risk preferences. This award will develop new network assignment models which can capture broader user objectives in route choice decision making, particularly related to reliability. Accurately representing such objectives in network optimization models will lead to better infrastructure planning and management strategies in large-scale urban areas, ultimately leading to reduced emissions and other related health benefits. The research will support participation and training of graduate and undergraduate students from minority and underrepresented groups in research. The results of this research will be incorporated into several undergraduate and graduate courses and high school lesson plans.

Funded by the National Science Foundation, this project will investigate efficient algorithms for different variants of non-additive shortest path, minimum cost flow, and traffic assignment problems, with potential applications in freight. These algorithms will exploit and advance recent progress in cutting plane and decomposition-based global optimization algorithms, and the underlying network structure. The project has three specific research aims: (i) Develop efficient solution algorithms for non-additive shortest path variants and their time-dependent extensions. (ii) Develop mathematical models and solution algorithms for non-additive network flow models. (iii) Develop analytical formulation and solution algorithm for the non-additive traffic assignment problem. The researched work draws on and integrates principles of network optimization, transportation network analysis, bi-criterion search, and global optimization. The key contribution of this work is the potential to exploit the synergies and integrate theoretically rigorous decomposition and cutting plane based algorithms developed for convex mixed integer nonlinear programs and existing network optimization algorithms.

Project Details

Project Type:
Project Status:
In Progress
End Date:
August 31,2020
UTC Grant Cycle:
non-UTC project