GRASP-based heuristic algorithm for the multi-product multi-vehicle inventory routing problem. (English) Zbl 1358.90115
Summary: In this paper, we introduce an improved Greedy Randomized Adaptive Search Procedure (GRASP) based heuristic for the multi-product multi-vehicle inventory routing problem (MMIRP). The inventory routing problem, which combines the vehicle-routing problem and the inventory control decisions, is one of the most important problems in combinatorial optimization field. To deal with the MMIRP, we develop a GRASP-based heuristic (GBH). Each GBH iteration consists of two sequential phases; the first phase is a Greedy Randomized Procedure, in which, the best tradeoff between the inventory holding cost and routing cost is looked. Then, in the second phase, as local search for the GRASP, we use the Tabu search (TS) meta-heuristic to improve the solution found in the first phase. The GBH two phases are repeated until some stopped criterion is met. Our proposed method is evaluated on two benchmark data sets, and successfully compared with two state-of-the-art algorithms.
MSC:
| 90C27 | Combinatorial optimization |
| 90B06 | Transportation, logistics and supply chain management |
| 90B05 | Inventory, storage, reservoirs |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
optimization; multi-product multi-vehicle inventory routing; meta-heuristics; GRASP; tabu searchReferences:
| [1] | Abdelmaguid TF (2004) Heuristic approaches for the integrated inventory distribution problem. PhD thesis, University of Southern California, Los Angeles, USA · Zbl 1348.90035 |
| [2] | Abdelmaguid TF, Dessouky MM (2006) A genetic algorithm approach to the integrated inventory-distribution problem. Int J Prod Res 44(21):4445-4464 · Zbl 1114.90302 · doi:10.1080/00207540600597138 |
| [3] | Adulyasak Y, Cordeau JF, Jans R (2012) Formulations and branch-and-cut algorithms for multi-vehicule production and inventory routing problems. GERAD, Technical report G-2012-14, Canada · Zbl 1356.90011 |
| [4] | Archetti C, Bertazzi L, Laporte G, Speranza MG (2007) A branch-and-cut algorithm for a vendor-managed inventory-routing problem. Transp Sci 41(3):382-391 · doi:10.1287/trsc.1060.0188 |
| [5] | Archetti C, Bertazzi L, Hertz A, Speranza MG (2012) A hybrid heuristic for an inventory routing problem. INFORMS J Comput 24(1):101-116 · Zbl 1460.90009 · doi:10.1287/ijoc.1100.0439 |
| [6] | Archetti C, Bianchessi N, Irnich S, Speranza MG (2014) Formulations for an inventory routing problem. Int Trans Oper Res 21(3):353-374 · Zbl 1291.90029 · doi:10.1111/itor.12076 |
| [7] | Coelho LC, Laporte G (2013a) The exact solution of several classes of inventory-routing problems. Comput Oper Res 40(2):558-565 · Zbl 1349.90016 · doi:10.1016/j.cor.2012.08.012 |
| [8] | Coelho LC, Laporte G (2013b) A branch-and-cut algorithm for the multi-product multi-vehicle inventory-routing problem. Int J Prod Res 51(23-24):7156-7169 · doi:10.1080/00207543.2012.757668 |
| [9] | Coelho LC, Cordeau JF, Laporte G (2012a) The inventory-routing problem with transshipment. Comput Oper Res 39(11):2537-2548 · Zbl 1251.90030 · doi:10.1016/j.cor.2011.12.020 |
| [10] | Coelho LC, Cordeau JF, Laporte G (2012b) Consistency in multi-vehicle inventory-routing. Transp Res Part C Emerg Technol 24(1):270-287 · doi:10.1016/j.trc.2012.03.007 |
| [11] | Coelho LC, Cordeau JF, Laporte G (2014) Thirty years of inventory-routing. Transp Sci 48(01):001-019 · doi:10.1287/trsc.2013.0472 |
| [12] | Cordeau JF, Laporte G (2003) A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transp Res Part B 37(06):579-594 · doi:10.1016/S0191-2615(02)00045-0 |
| [13] | Cordeau JF, Lagan D, Musmanno R, Vocaturo F (2015) A decomposition-based heuristic for the multiple-product inventory-routing problem. Comput Oper Res 55:153-166 · Zbl 1348.90076 · doi:10.1016/j.cor.2014.06.007 |
| [14] | Desaulniers G, Rakke JG, Coelho LC (2014) A branch-price-and-cut algorithm for the inventory-routing problem. GERAD, Technical report G-2014-12, Canada |
| [15] | Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J Glob Optim 06(2):109-133 · Zbl 0822.90110 · doi:10.1007/BF01096763 |
| [16] | Glover F (1989) Tabu search—part I. ORSA J Comput 01(03):190-206 · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190 |
| [17] | Harks T, Konig F, Matuschke J (2013) Approximation algorithms for capacitated location routing. Eur J Oper Res 47(1):3-22 |
| [18] | Lemouari A, Guemri O (2014) A two-phase scheduling method combined to the tabu search for the DARP. Int J Appl Metaheuristic Comput 05(02):001-021 · doi:10.4018/ijamc.2014040101 |
| [19] | Mjirda A, Jarboui B, Macedo R, Hanafi S, Mladenovic N (2014) A two phase variable neighborhood search for the multi-product inventory routing problem. Comput Oper Res 52:291-299 · Zbl 1348.90035 · doi:10.1016/j.cor.2013.06.006 |
| [20] | Moin NH, Salhi S, Aziz NAB (2011) An efficient hybrid genetic algorithm for the multi-product multi-period inventory routing problem. Inte J Prod Econ 133(1):334-343 · doi:10.1016/j.ijpe.2010.06.012 |
| [21] | Popovic D, Vidovic M, Radivojevic G (2012) Variable neighborhood search heuristic for the inventory routing problem in fuel delivery. Expert Syst Appl 39(18):13390-13398 · doi:10.1016/j.eswa.2012.05.064 |
| [22] | Solyali O, Sural H (2011) A branch-and-cut algorithm using a strong formulation and an a priori tour based heuristic for an inventory-routing problem. Transp Sci 45(3):335-345 · doi:10.1287/trsc.1100.0354 |
| [23] | Yu Y, Chen H, Chu F (2008) A new model and hybrid approach for large-scale inventory routing problems. Eur J Oper Res 189(3):1022-1040 · Zbl 1146.90011 · doi:10.1016/j.ejor.2007.02.061 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
