论文标题
局部路线和有效车辆路线的有效不平等
Local Area Routes and Valid Inequalities for Efficient Vehicle Routing
论文作者
论文摘要
在这项研究中，我们介绍了用于提高解决车辆路由问题（VRP）的柱子生成效率和紧密度的局部区域（LA）途径。 LA-ROUTES依赖于每种元组的最低成本基本子路由（称为LA-ARC），包括以下内容：（1）a（第一个）la-arc开始开始的客户，（2）遥远的客户（第一个）（从第一个）la-arc End，以及（3）Intermediate Endimed Ander Midediate客户附近的客户。 LA-Routes是通过与LA-ARCS串联建造的，在给定LA-ARC中的最终客户是随后的LA-ARC中的第一个客户。在CG的定价步骤中，使用LA-ROUTES上采用了降低状态空间松弛方法，以构建最低的成本基本途径。基于LA-Route的求解器可用于使用子集行不等式的变体有效地拧紧标准盖VRP，这不会改变定价的结构。我们将LA-ARCS纳入一种新型的CG稳定方案中。具体而言，定价期间生成的每个列都映射到与该列一致的客户列表。 LA-ARC与订购一致，如果ARC中的第一个/最后一个客户分别在LA-ARC中分别在相关订单中的所有其他客户。然后将每个这样的订购映射到一个多图片，其中节点对应于（客户/需求），而边缘对应于与该订购相一致的LA-ARCS。因此，从源到下沉的任何路径都是可行的基本路线。一列的订购将客户在订购的附近位置将客户在附近的位置上放置，以便可以生成路线，以便可以允许在空间附近的客户被访问而无需远离遥远的情况。我们在这些图上解决了受限制的主问题，该图具有特殊的结构，可以快速解决方案。
In this research we introduce Local Area (LA) routes for improving the efficiency and tightness of column generation (CG) methods for solving vehicle routing problems (VRP). LA-routes rely on pre-computing the lowest cost elementary sub-route (called an LA-arc) for each tuple consisting of the following: (1) a (first) customer where the LA-arc begins, (2) a distant customer (from the first) where the LA-arc ends, and (3) a set of intermediate customers near the first customer. LA-routes are constructed by concatenating LA-arcs where the final customer in a given LA-arc is the first customer in the subsequent LA-arc. A Decremental State Space Relaxation method is applied over LA-routes to construct the lowest reduced cost elementary route during the pricing step of CG. LA-route based solvers can be used to efficiently tighten the standard set cover VRP using a variant of subset row inequalities, which do not alter the structure of pricing. We incorporate LA-arcs into a novel CG stabilization scheme. Specifically each column generated during pricing is mapped to an ordered list of customers consistent with that column. An LA-arc is consistent with an ordering if the first/last customer in the arc come before/after all other customers in the LA-arc in the associated ordering respectively. Each such ordering is then mapped to a multi-graph where nodes correspond to (customer/demand) and edges correspond to LA-arcs consistent with that ordering. Hence any path from source to sink on the multi-graph is a feasible elementary route. The ordering for a column places customers spatially nearby in nearby positions on the ordering so that routes can be generated so as to permit spatially nearby customers to be visited without traveling far away first. We solve the restricted master problem over these graphs, which has special structure allowing for fast solution.
