Improved solutions for inventory-routing problems through valid inequalities and input ordering
Improved solutions for inventory-routing problems through valid inequalities and input ordering
复制标题
DOI：
10.1016/j.ijpe.2013.11.019
复制
发表时间：
2014-09-01
影响因子：
12
通讯作者：
Laporte, Gilbert
中科院分区：
文献类型：
--
作者：
Coelho, Leandro C.;Laporte, Gilbert
库存路径问题（IRP）结合联合收割机库存控制和车辆路径，有效地优化库存和补货决策在几个时期内在一个集中的水平。在本文中，我们提供了一个精确的配方，其中包括几个著名的有效不等式的某些类的IRP。然后，我们提出了三个新的有效的不平等的基础上的需求和可用容量之间的关系。然后，提出的二进制聚类和作业调度问题的想法后，我们还展示了如何输入数据的顺序可以有一个主要影响的线性松弛的IRP模型。大量的计算实验证实了我们的算法的成功。我们使用了两个可用的数据集，并在2013年确定了新的解决方案。在一组有249个开放实例的基准实例上，我们改进了98个下界，计算了96个新的最佳解，并证明了11个实例的最优性。在由较大实例组成的另一个数据集上，其中63个是开放的，我们改进了32个下界，我们获得了20个新的最佳已知解，我们证明了三个实例的最优性。(C)2013爱思唯尔有限公司版权所有。
Inventory-routing problems (IRP) combine inventory control and vehicle routing, effectively optimizing inventory and replenishment decisions over several periods at a centralized level. In this paper we provide an exact formulation which includes several well-known valid inequalities for some classes of IRPs. We then propose three new valid inequalities based on the relation between demand and available capacities. Then, following an idea proposed for the binary clustering and for the job scheduling problems, we also show how the order of the input data can have a major effect on the linear relaxation of the proposed model for the IRP. Extensive computational experiments confirm the success of our algorithm. We have used two available datasets with new solutions identified as recently as 2013. On one set of benchmark instances with 249 open instances, we have improved 98 lower bounds, we have computed 96 new best known solutions, and we have proved optimality for 11 instances. On the other dataset composed of larger instances, of which were 63 open, we have improved 32 lower bounds, we have obtained 20 new best known solutions, and we proved optimality for three instances. (C) 2013 Elsevier B.V. All rights reserved.