Lower bounds for the mixed capacitated arc routing problem
Lower bounds for the mixed capacitated arc routing problem
复制标题
混合电容弧布线问题的下界
DOI：
10.1016/j.cor.2009.06.018
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
L. Pinto
中科院分区：
文献类型：
--
作者：
L. Gouveia;M. C. Mourão;L. Pinto
容量弧路由问题 (CARP) 出现在分配或收集问题中，其中活动由容量有限的车辆执行，并沿着网络的某些预定义链路连续分配。 CARP 被定义为无向问题或有向问题，具体取决于所需链路是无向还是有向。混合容量弧路由问题 (MCARP) 模拟了更现实的场景，因为它考虑了关联网络中的定向和无向所需链路。我们提出了一个基于紧凑流的 MCARP 模型。由于其大量的变量和约束，我们创建了原始模型的聚合版本。尽管该模型不再有效，但我们表明它提供了与原始模型相同的线性规划界限。还导出了不同组的有效不等式。模型的质量在基准实例上进行了测试，结果非常有希望。
Capacitated arc routing problems (CARP) arise in distribution or collecting problems where activities are performed by vehicles, with limited capacity, and are continuously distributed along some pre-defined links of a network. The CARP is defined either as an undirected problem or as a directed problem depending on whether the required links are undirected or directed. The mixed capacitated arc routing problem (MCARP) models a more realistic scenario since it considers directed as well as undirected required links in the associated network. We present a compact flow based model for the MCARP. Due to its large number of variables and constraints, we have created an aggregated version of the original model. Although this model is no longer valid, we show that it provides the same linear programming bound than the original model. Different sets of valid inequalities are also derived. The quality of the models is tested on benchmark instances with quite promising results.