论文标题
通过列的生成优化模式中的传输网络
Optimizing intermodal transportation networks at scale via column generation
论文作者
论文摘要
鉴于对联运系统的设计和分析的需求，我们提出了一个算法框架，以确定系统最佳的模式运输系统的最佳。为此，我们通过结合网络优化的两个核心原理（分层图形结构和（部分）时间扩展的网络）来对一个模式的运输系统进行建模，以在图表上提出我们的问题，以使我们能够隐式编码与模型间的特定问题。这使我们能够解决标准整数最小成本多商品流问题，以获得模式运输系统的最佳系统。为了有效地解决此整数最小成本多商品流问题，我们提出了一种列生成方法，以找到连续的最小成本多商品流解决方案，我们将其与价格和分支机构相结合，以获取整数解决方案。为了加快我们的专栏生成，我们进一步开发了一个定价过滤器和可接受的距离近似，以利用$ a^*$算法来解决定价问题。我们通过将其应用于慕尼黑市的真实案例研究来展示框架的效率，在该研究中，我们在该案例研究中最多可以通过使用定价过滤器和其他90 \％的$ a^$ a^$ a^$ a^$ a^$ a^$ a^$ a^$ a^$ a^$ a^$ a^$ a^a^$ a^$ a^$ a^$ a^$ a^$ a^a^。
In light of the need for design and analysis of intermodal transportation systems, we propose an algorithmic framework to determine the system optimum of an intermodal transportation system. To this end, we model an intermodal transportation system by combining two core principles of network optimization - layered-graph structures and (partially) time-expanded networks - to formulate our problem on a graph that allows us to implicitly encode problem specific constraints related to intermodality. This enables us to solve a standard integer minimum-cost multi-commodity flow problem to obtain the system optimum for an intermodal transportation system. To solve this integer minimum-cost multi-commodity flow problem efficiently, we present a column generation approach to find continuous minimum-cost multi-commodity flow solutions, which we combine with a price-and-branch procedure to obtain integer solutions. To speed up our column generation, we further develop a pricing filter and an admissible distance approximation to utilize the $A^*$ algorithm for solving the pricing problems. We show the efficiency of our framework by applying it to a real-world case study for the city of Munich, where we solve instances with up to 56,295 passengers to optimality, and show that the computation time of our algorithm can be reduced by up to 60\% through the use of our pricing filter and by up to additional 90\% through the use of the $A^*$-based pricing algorithm.
