A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints
A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints
复制标题
DOI：
10.1016/j.disopt.2014.03.001
复制
发表时间：
2014-05-01
影响因子：
1.1
通讯作者：
Martinelli, Rafael
中科院分区：
文献类型：
--
作者：
Contardo, Claudio;Martinelli, Rafael
本文提出了一种在容量和路线长度约束下的多站点车辆路径问题 (MDVRP) 的精确算法。 MDVRP 使用车辆流和集合划分公式来制定，这两者都在算法的不同阶段使用。使用车辆流量公式计算的下界用于消除无希望的边缘，从而降低用于求解集合划分公式的定价子问题的复杂性。添加了几类有效的不等式来加强这两种公式，包括用于禁止任意长度的循环的新的有效不等式族。为了验证我们的方法，我们还将容量车辆路径问题（CVRP）视为 MDVRP 的一个特例，并对文献中的几个实例进行了广泛的计算实验，以证明其有效性。计算结果表明，对于这两类车辆路径问题，所提出的算法与最先进的方法相比具有竞争力，并且能够最优地解决一些先前开放的实例。此外，对于所提出的算法无法解决的情况，最终的下界证明比早期方法获得的下界更强。 (C) 2014 Elsevier B.V. 保留所有权利。
This article presents an exact algorithm for the multi-depot vehicle routing problem (MDVRP) under capacity and route length constraints. The MDVRP is formulated using a vehicle-flow and a set-partitioning formulation, both of which are exploited at different stages of the algorithm. The lower bound computed with the vehicle-flow formulation is used to eliminate non-promising edges, thus reducing the complexity of the pricing sub-problem used to solve the set-partitioning formulation. Several classes of valid inequalities are added to strengthen both formulations, including a new family of valid inequalities used to forbid cycles of an arbitrary length. To validate our approach, we also consider the capacitated vehicle routing problem (CVRP) as a particular case of the MDVRP, and conduct extensive computational experiments on several instances from the literature to show its effectiveness. The computational results show that the proposed algorithm is competitive against state-of-the-art methods for these two classes of vehicle routing problems, and is able to solve to optimality some previously open instances. Moreover, for the instances that cannot be solved by the proposed algorithm, the final lower bounds prove stronger than those obtained by earlier methods. (C) 2014 Elsevier B.V. All rights reserved.