Mixed-integer programming approaches for the time-constrained maximal covering routing problem
研究了时间约束最大覆盖路径问题，提出两种基于混合整数规划的精确求解算法，在270个算例中为267个找到最优解，速度比之前方法快五个数量级。
Abstract In this paper, we study the recently introduced time-constrained maximal covering routing problem. In this problem, we are given a central depot, a set of facilities, and a set of customers. Each customer is associated with a subset of the facilities which can cover it. A feasible solution consists of k Hamiltonian cycles on subsets of the facilities and the central depot. Each cycle must contain the depot and must respect a given distance limit. The goal is to maximize the number of customers covered by facilities contained in the cycles. We develop two exact solution algorithms for the problem based on new mixed-integer programming models. One algorithm is based on a compact model, while the other model contains an exponential number of constraints, which are separated on-the-fly, i.e., we use branch-and-cut. We also describe preprocessing techniques, valid inequalities and primal heuristics for both models. We evaluate our solution approaches on the instances from literature and our algorithms are able to find the provably optimal solution for 267 out of 270 instances, including 123 instances, for which the optimal solution was not known before. Moreover, for most of the instances, our algorithms only take a few seconds, and thus are up to five magnitudes faster than previous approaches. Finally, we also discuss some issues with the instances from literature and present some new instances.