A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand
A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand
复制标题
单一需求下有能力多车出行购买者问题的分支价格切割算法
DOI：
10.1016/j.dam.2020.08.014
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Christian Tilk
中科院分区：
文献类型：
--
作者：
Nicola Bianchessi;Stefan Irnich;Christian Tilk
多车辆旅行购买者问题（MVTPP）包括同时选择供应商和路由的同质车辆车队购买不同的产品在选定的供应商，使所有的产品需求得到满足，旅行和采购成本最小化。我们考虑了MVTPP的变体，其中车辆的容量可以成为约束力，并且对每种产品的需求是一个单位。相应的解决方案的算法，从文献中的分支和切割或分支和价格算法，在后者的情况下，路由生成子问题是解决了一个扩展的图形，通过应用标准的动态规划技术。我们的分支价格和切割算法采用了一种新的标签算法，直接在原始网络上工作，并推迟购买决策，直到路线已经完全定义。此外，我们定义了一个新的分支规则一般适用于单一的产品需求的情况下，引入一个新的家庭的有效的不平等适用于供应商可以访问最多一次，并显示如何产品不兼容可以处理，而不考虑额外的资源在定价问题。在全面的计算实验与标准的基准集，我们证明了新的分支价格和削减的方法是非常有竞争力的。
The multiple vehicle traveling purchaser problem (MVTPP) consists of simultaneously selecting suppliers and routing a fleet of homogeneous vehicles to purchase different products at the selected suppliers so that all product demands are fulfilled and traveling and purchasing costs are minimized. We consider variants of the MVTPP in which the capacity of the vehicles can become binding and the demand for each product is one unit. Corresponding solution algorithms from the literature are either branch-and-cut or branch-and-price algorithms, where in the latter case the route-generation subproblem is solved on an expanded graph by applying standard dynamic-programming techniques. Our branch-price-and-cut algorithm employs a novel labeling algorithm that works directly on the original network and postpones the purchasing decisions until the route has been completely defined. Moreover, we define a new branching rule generally applicable in case of unitary product demands, introduce a new family of valid inequalities to apply when suppliers can be visited at most once, and show how product incompatibilities can be handled without considering additional resources in the pricing problem. In comprehensive computational experiments with standard benchmark sets we prove that the new branch-price-and-cut approach is highly competitive.
登录
查看更多内容
DOI：
10.1287/trsc.2018.0825
发表时间：
2019-01
期刊：
Transp. Sci.
影响因子：
--
作者：
Nicola Bianchessi;Stefan Irnich
通讯作者：
Nicola Bianchessi;Stefan Irnich
二进制混合整数规划问题的 Dantzig-Wolfe 重构分类
DOI：
10.1016/j.ejor.2009.11.014
发表时间：
2010
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
R. Jans
通讯作者：
R. Jans
多次旅行购买者问题
DOI：
--
发表时间：
2010
期刊：
The 40th International Conference on Computers & Indutrial Engineering
影响因子：
--
作者：
M. Choi;Sang
通讯作者：
Sang
私人车队和公共承运人车辆路径问题的上限和下限
影响因子：
1.1
作者：
Dominik Goeke;Timo Gschwind;Michael Schneider
通讯作者：
Michael Schneider
基于列生成的原始启发法
DOI：
--
发表时间：
2010
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
C. Joncour;S. Michel;R. Sadykov;Dmitry Sverdlov;François Vanderbeck
通讯作者：
François Vanderbeck