论文标题
基于机器学习的弧选择，用于列生成的约束最短路径问题
Machine-learning-based arc selection for constrained shortest path problems in column generation
论文作者
论文摘要
列生成是一种迭代方法，用于解决各种优化问题。它将问题分解为两个部分：一个主问题和一个或多个定价问题（PP）。该方法所需的总计算时间分配在这两个部分之间。在路由或调度应用程序中，问题主要是在网络上定义的，并且PP通常是NP最短的路径问题，并且资源约束。在这项工作中，我们提出了一种基于机器学习的新启发式定价算法。通过利用先前执行期间收集的数据，目的是减小网络的大小并加速PP，仅保留有很大机会成为线性放松解决方案一部分的弧。该方法已应用于两个特定问题：公共交通中的车辆和机组人员调度问题以及时间窗口的车辆路由问题。可以获得多达40％的计算时间的减少。
Column generation is an iterative method used to solve a variety of optimization problems. It decomposes the problem into two parts: a master problem, and one or more pricing problems (PP). The total computing time taken by the method is divided between these two parts. In routing or scheduling applications, the problems are mostly defined on a network, and the PP is usually an NP-hard shortest path problem with resource constraints. In this work, we propose a new heuristic pricing algorithm based on machine learning. By taking advantage of the data collected during previous executions, the objective is to reduce the size of the network and accelerate the PP, keeping only the arcs that have a high chance to be part of the linear relaxation solution. The method has been applied to two specific problems: the vehicle and crew scheduling problem in public transit and the vehicle routing problem with time windows. Reductions in computational time of up to 40% can be obtained.
