Optimal Network Design with End-to-End Service Requirements
研究了在满足端到端服务指标（如运输时间、延迟、转运次数）的前提下，最小化网络总成本的多商品流网络设计问题，提出了基于多面体理论的强有效不等式和优化启发式算法，显著降低了计算时间并得到近优解，为交通、电信等服务提供商提供了规划工具。
Long-term planning for transportation, telecommunications, and other service operations entails designing networks that are both cost effective and responsive. Because infrastructure networks are expensive and the network’s design determines its service capabilities, planners must address complex trade-offs between minimizing the total cost of the network while meeting end-to-end service requirements such as limits on transit time, latency, and transshipments. To address this problem, we study a minimum cost multicommodity network design model to select arcs and route the required flows along these arcs so that each origin-to-destination route satisfies limits on various service metrics. To effectively solve this service network design problem, we focus on a polyhedral approach to strengthen its arc flow formulation. We develop several classes of strong cuts, with appropriate separation procedures, and propose an optimization-based heuristic method. We characterize the dimension of the problem’s feasible region and show that two classes of inequalities are facet-defining under appropriate conditions. Our computational results demonstrate that our Composite method, incorporating the valid inequalities and heuristic algorithm, significantly reduces computational time and generates near-optimal solutions. The model and methods developed in this paper provide a valuable planning tool for service providers in transportation, telecommunication, and other sectors. The online appendix is available at https://doi.org/10.1287/opre.2016.1579 .