Scholarlink

<p>We consider the problem of upgrading edge capacities in a network in order to maximize the total flow over a time horizon. We are interested in determining both which edges to upgrade (network design decisions) and when to upgrade them (scheduling decisions) while also considering the fact that the capacities of edges undergoing their upgrading process will be downgraded. We introduce a novel heuristic method based on properties of the maximum flow to solve the problem on realistic networks and compare its performance to a mixed-integer programming (MIP) model for the problem. We further consider how to improve the heuristic solutions through simulated annealing. The heuristic method is tested on synthetic Manhattan Grid and CLARC County networks and real-world networks from Eastern Massachusetts, Anaheim, and Chicago. It is shown to produce high-quality solutions to the problem in a much shorter time than the MIP model.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Maxflow-Based Integrated Network Design and Scheduling Problems with Downgraded Capacities

  • 期刊论文

  • 发表日期：

    2026年3月14日

查看全文
  • Xiaowei Guo,
  • Thomas C. Sharkey

摘要

We consider the problem of upgrading edge capacities in a network in order to maximize the total flow over a time horizon. We are interested in determining both which edges to upgrade (network design decisions) and when to upgrade them (scheduling decisions) while also considering the fact that the capacities of edges undergoing their upgrading process will be downgraded. We introduce a novel heuristic method based on properties of the maximum flow to solve the problem on realistic networks and compare its performance to a mixed-integer programming (MIP) model for the problem. We further consider how to improve the heuristic solutions through simulated annealing. The heuristic method is tested on synthetic Manhattan Grid and CLARC County networks and real-world networks from Eastern Massachusetts, Anaheim, and Chicago. It is shown to produce high-quality solutions to the problem in a much shorter time than the MIP model.