Collaborative Research: Non-Additive Network Routing and Assignment Models

网络分配模型被广泛用于研究具有网络结构的基础设施(如道路司机或货运)上的商品流动，并构成城市地区交通规划的基础。目前，大多数网络分配模型都假定一条路线的出行成本简单地等于构成该路线的路段的出行成本之和。虽然对于某些成本(如出行时间)是正确的，但在考虑由于不可靠、迟到惩罚和风险偏好而导致的成本时，这一假设是无效的。该奖项将开发新的网络分配模型，能够在路线选择决策中捕捉到更广泛的用户目标，特别是与可靠性有关的目标。在网络优化模型中准确表示这些目标将导致大规模城市地区更好的基础设施规划和管理战略，最终导致减少排放和其他相关的健康益处。这项研究将支持来自少数群体和代表性不足群体的研究生和本科生参与和培训研究。这项研究的结果将被纳入几个本科生和研究生课程以及高中课程计划。这个项目将研究非可加最短路径、最小费用流和交通分配问题的不同变体的有效算法，并在货运方面有潜在的应用。这些算法将开发和推进切割平面和基于分解的全局优化算法以及底层网络结构方面的最新进展。该项目有三个具体的研究目标：(I)开发非加法最短路径变量及其时间相关扩展的高效求解算法。(2)建立非加性网络流模型的数学模型和求解算法。(3)建立了非加性交通分配问题的解析公式和求解算法。研究工作借鉴和融合了网络优化、交通网络分析、双准则搜索和全局优化的原理。这项工作的关键贡献是开发了协同作用，并将为凸混合整数非线性规划开发的理论上严格的分解和基于割面的算法与现有的网络优化算法相结合。

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. 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.