A generalized formulation for vehicle routing problems
A generalized formulation for vehicle routing problems
复制标题
车辆路径问题的通用公式
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
P. Munari
中科院分区：
文献类型：
--
作者：
P. Munari
文献中提出了不同类型的公式来模拟车辆路径问题。目前，最常用的可以分为两类，即车辆流公式和集合划分公式。这些类型的配方彼此不同，不仅因为它们的变量和约束，而且因为它们的主要特征。车辆流动公式的优点是模型紧凑，因此可以使用通用优化包直接求解它们。然而，它们通常表现出较弱的线性松弛并具有大量约束。也可以设计基于专门有效不等式的分支割法来求解这些公式，但它们尚未显示出对于大规模实例有效。另一方面，集合划分公式具有更强的线性松弛，但需要实施复杂的技术，例如列生成和专门的分支与价格方法。由于所有这些原因，到目前为止，车辆路径社区已经认识到这两种类型的表述是相当不同的。在本文中，我们表明它们实际上是密切相关的，因为它们对应于车辆路径问题的广义表述的特殊情况。
Different types of formulations are proposed in the literature to model vehicle routing problems. Currently, the most used ones can be fitted into two classes, namely vehicle flow formulations and set partitioning formulations. These types of formulations differ from each other not only due to their variables and constraints but also due to their main features. Vehicle flow formulations have the advantage of being compact models, so general-purpose optimization packages can be used to straightforwardly solve them. However, they typically show weak linear relaxations and have a large number of constraints. Branch-and-cut methods based on specialized valid inequalities can also be devised to solve these formulations, but they have not shown to be effective for large-scale instances. On the other hand, set partitioning formulations have stronger linear relaxations, but requires the implementation of sophisticate techniques such as column generation and specialized branch-and-price methods. Due to all these reasons, so far it is has been recognized in the vehicle routing community that these two types of formulations are rather different. In this paper, we show that they are actually strongly related as they correspond to special cases of a generalized formulation of vehicle routing problems.