Tabu search heuristic for inventory routing problem with stochastic demand and time windows

Authors

  • Meilinda Fitriani Nur Maghfiroh Universitas Islam Indonesia
  • Anak Agung Ngurah Perwira Redi Sampoerna University

DOI:

https://doi.org/10.30656/jsmi.v6i2.4813

Keywords:

Inventory routing problem, Stochastic demand, Time windows, Tabu search, Variable neighborhood descent

Abstract

This study proposes the hybridization of tabu search (TS) and variable neighbourhood descent (VND) for solving the Inventory Routing Problems with Stochastic Demand and Time Windows (IRPSDTW). Vendor Managed Inventory (VMI) is among the most used approaches for managing supply chains comprising multiple stakeholders, and implementing VMI require addressing the Inventory Routing Problem (IRP). Considering practical constraints related to demand uncertainty and time constraint, the proposed model combines multi-item replenishment schedules with unknown demand to arrange delivery paths, where the actual demand amount is only known upon arrival at a customer location with a time limit. The proposed method starts from the initial solution that considers the time windows and uses the TS method to solve the problem. As an extension, the VND is conducted to jump the solution from its local optimal. The results show that the proposed method can solve the IRPSDTW, especially for uniformly distributed customer locations.

References

H. Stadtler and C. Kilger, Supply Chain Management and Advanced Planning. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. doi: https://doi.org/10.1007/978-3-540-74512-9

A. Rusdiansyah and D. B. Tsao, ‘An integrated model of the periodic delivery problems for vending-machine supply chains’, J. Food Eng., vol. 70, no. 3, pp. 421–434, 2005, doi: https://doi.org/10.1016/j.jfoodeng.2004.05.073.

A. M. Campbell, M. Gendreau, and B. W. Thomas, ‘The orienteering problem with stochastic travel and service times’, Ann. Oper. Res., vol. 186, no. 1, pp. 61–81, Jun. 2011, doi: https://doi.org/10.1007/s10479-011-0895-2.

F. Neves-Moreira, B. Almada-Lobo, J.-F. Cordeau, L. Guimarães, and R. Jans, ‘Solving a large multi-product production-routing problem with delivery time windows’, Omega, vol. 86, pp. 154–172, Jul. 2019, doi: https://doi.org/10.1016/j.omega.2018.07.006.

Y. Qiu, J. Qiao, and P. M. Pardalos, ‘Optimal production, replenishment, delivery, routing and inventory management policies for products with perishable inventory’, Omega (United Kingdom), vol. 82, pp. 193–204, 2019, doi: https://doi.org/10.1016/j.omega.2018.01.006.

S.-H. Huang and P.-C. Lin, ‘A modified ant colony optimization algorithm for multi-item inventory routing problems with demand uncertainty’, Transp. Res. Part E Logist. Transp. Rev., vol. 46, no. 5, pp. 598–611, Sep. 2010, doi: https://doi.org/10.1016/j.tre.2010.01.006.

A. Al Shamsi, A. Al Raisi, and M. Aftab, ‘Pollution-Inventory Routing Problem with Perishable Goods’, P. Golinska, Ed. Cham: Springer International Publishing, 2014, pp. 585–596, doi: https://doi.org/10.1007/978-3-319-07287-6_42.

M. Soysal, J. M. Bloemhof-Ruwaard, R. Haijema, and J. G. A. J. van der Vorst, ‘Modeling an Inventory Routing Problem for perishable products with environmental considerations and demand uncertainty’, Int. J. Prod. Econ., vol. 164, pp. 118–133, Jun. 2015, doi: https://doi.org/10.1016/j.ijpe.2015.03.008.

J. E. Fokkema, M. J. Land, L. C. Coelho, H. Wortmann, and G. B. Huitema, ‘A continuous-time supply-driven inventory-constrained routing problem’, Omega, vol. 92, p. 102151, Apr. 2020, doi: https://doi.org/10.1016/j.omega.2019.102151.

S. Treitl, P. C. Nolz, and W. Jammernegg, ‘Incorporating environmental aspects in an inventory routing problem. A case study from the petrochemical industry’, Flex. Serv. Manuf. J., vol. 26, no. 1–2, pp. 143–169, Jun. 2014, doi: https://doi.org/10.1007/s10696-012-9158-z.

F. E. Achamrah, F. Riane, and S. Limbourg, ‘Spare parts inventory routing problem with transshipment and substitutions under stochastic demands’, Appl. Math. Model., vol. 101, pp. 309–331, Jan. 2022, doi: https://doi.org/10.1016/j.apm.2021.08.029.

P. L. Miranda, R. Morabito, and D. Ferreira, ‘Optimization model for a production, inventory, distribution and routing problem in small furniture companies’, TOP, vol. 26, no. 1, pp. 30–67, May 2017, doi: https://doi.org/10.1007/s11750-017-0448-1.

F. A. Touzout, A.-L. Ladier, and K. Hadj-Hamou, ‘An assign-and-route matheuristic for the time-dependent inventory routing problem’, Eur. J. Oper. Res., vol. 300, no. 3, pp. 1081–1097, Aug. 2022, doi: https://doi.org/10.1016/j.ejor.2021.09.025.

M. Mahjoob, S. S. Fazeli, S. Milanlouei, L. S. Tavassoli, and M. Mirmozaffari, ‘A modified adaptive genetic algorithm for multi-product multi-period inventory routing problem’, Sustain. Oper. Comput., vol. 3, pp. 1–9, 2022, doi: https://doi.org/10.1016/j.susoc.2021.08.002.

J. Skålnes, H. Andersson, G. Desaulniers, and M. Stålhane, ‘An improved formulation for the inventory routing problem with time-varying demands’, Eur. J. Oper. Res., vol. 302, no. 3, pp. 1189–1201, 2022, doi: https://doi.org/10.1016/j.ejor.2022.02.011.

V. F. Yu, A. T. Widjaja, A. Gunawan, and P. Vansteenwegen, ‘The Multi-Vehicle Cyclic Inventory Routing Problem: Formulation and a Metaheuristic Approach’, Comput. Ind. Eng., vol. 157, p. 107320, Jul. 2021, doi: https://doi.org/10.1016/j.cie.2021.107320.

M. Mahjoob, S. S. Fazeli, L. S. Tavassoli, M. Mirmozaffari, and S. Milanlouei, ‘A green multi-period inventory routing problem with pickup and split delivery: A case study in flour industry’, Sustain. Oper. Comput., vol. 2, pp. 64–70, 2021, doi: https://doi.org/10.1016/j.susoc.2021.04.002.

M. W. Friske, L. S. Buriol, and E. Camponogara, ‘A relax-and-fix and fix-and-optimize algorithm for a Maritime Inventory Routing Problem’, Comput. Oper. Res., vol. 137, p. 105520, Jan. 2022, doi: https://doi.org/10.1016/j.cor.2021.105520.

L. C. Coelho, A. De Maio, and D. Laganà , ‘A variable MIP neighborhood descent for the multi-attribute inventory routing problem’, Transp. Res. Part E Logist. Transp. Rev., vol. 144, p. 102137, Dec. 2020, doi: https://doi.org/10.1016/j.tre.2020.102137.

S. T. Vadseth, H. Andersson, and M. Stålhane, ‘An iterative matheuristic for the inventory routing problem’, Comput. Oper. Res., vol. 131, p. 105262, Jul. 2021, doi: https://doi.org/10.1016/j.cor.2021.105262.

A. Karoonsoontawong, O. Kobkiattawin, and C. Xie, ‘Efficient Insertion Heuristic Algorithms for Multi-Trip Inventory Routing Problem with Time Windows, Shift Time Limits and Variable Delivery Time’, Networks Spat. Econ., vol. 19, no. 2, pp. 331–379, Jun. 2019, doi: https://doi.org/10.1007/s11067-017-9369-7.

M. Seifbarghy and Z. Samadi, ‘A tabu search-based heuristic for a new capacitated cyclic inventory routing problem’, Int. J. Math. Oper. Res., vol. 6, no. 4, pp. 491–504, Jan. 2014, doi: https://doi.org/10.1504/IJMOR.2014.063159.

Y. Yu, C. Chu, H. Chen, and F. Chu, ‘Large scale stochastic inventory routing problems with split delivery and service level constraints’, Ann. Oper. Res., vol. 197, no. 1, pp. 135–158, Aug. 2012, doi: https://doi.org/10.1007/s10479-010-0772-4.

L. Bertazzi, A. Bosco, F. Guerriero, and D. Laganà , ‘A stochastic inventory routing problem with stock-out’, Transp. Res. Part C Emerg. Technol., vol. 27, pp. 89–107, Feb. 2013, doi: https://doi.org/10.1016/j.trc.2011.06.003.

L. C. Coelho, J.-F. Cordeau, and G. Laporte, ‘Heuristics for dynamic and stochastic inventory-routing’, Comput. Oper. Res., vol. 52, pp. 55–67, Dec. 2014, doi: https://doi.org/10.1016/j.cor.2014.07.001.

A. Gruler, J. Panadero, J. de Armas, J. A. Moreno Pérez, and A. A. Juan, ‘Combining variable neighborhood search with simulation for the inventory routing problem with stochastic demands and stock-outs’, Comput. Ind. Eng., vol. 123, pp. 278–288, Sep. 2018, doi: https://doi.org/10.1016/j.cie.2018.06.036.

E. Nikzad, M. Bashiri, and F. Oliveira, ‘Two-stage stochastic programming approach for the medical drug inventory routing problem under uncertainty’, Comput. Ind. Eng., vol. 128, pp. 358–370, Feb. 2019, doi: https://doi.org/10.1016/j.cie.2018.12.055.

W. W. Qu, J. H. Bookbinder, and P. Iyogun, ‘Integrated inventory-transportation system with modified periodic policy for multiple products’, Eur. J. Oper. Res., vol. 115, no. 2, pp. 254–269, 1999, doi: https://doi.org/10.1016/S0377-2217(98)00301-4.

W.-H. Yang, K. Mathur, and R. H. Ballou, ‘Stochastic Vehicle Routing Problem with Restocking’, Transp. Sci., vol. 34, no. 1, pp. 99–112, Feb. 2000, doi: https://doi.org/10.1287/trsc.34.1.99.12278.

C. Archetti, L. Bertazzi, G. Laporte, and M. G. Speranza, ‘A Branch-and-Cut Algorithm for a Vendor-Managed Inventory-Routing Problem’, Transp. Sci., vol. 41, no. 3, pp. 382–391, Aug. 2007, doi: https://doi.org/10.1287/trsc.1060.0188.

C. H. Christiansen and J. Lysgaard, ‘A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands’, Oper. Res. Lett., vol. 35, no. 6, pp. 773–781, Nov. 2007, doi: https://doi.org/10.1016/j.orl.2006.12.009.

R. Roldán, R. Basagoiti, and E. Onieva, ‘Inventory routing problem with stochastic demand and lead time: State of the art’, in Advances in Intelligent Systems and Computing, 2014, vol. 299, pp. 73–82, doi: https://doi.org/10.1007/978-3-319-07995-0_8.

M. Alinaghian, E. B. Tirkolaee, Z. K. Dezaki, S. R. Hejazi, and W. Ding, ‘An augmented Tabu search algorithm for the green inventory-routing problem with time windows’, Swarm Evol. Comput., vol. 60, p. 100802, Feb. 2021, doi: https://doi.org/10.1016/j.swevo.2020.100802.

H. Jia, Y. Li, B. Dong, and H. Ya, ‘An Improved Tabu Search Approach to Vehicle Routing Problem’, Procedia - Soc. Behav. Sci., vol. 96, pp. 1208–1217, Nov. 2013, doi: https://doi.org/10.1016/j.sbspro.2013.08.138.

G. Li and J. Li, ‘An Improved Tabu Search Algorithm for the Stochastic Vehicle Routing Problem With Soft Time Windows’, IEEE Access, vol. 8, pp. 158115–158124, 2020, doi: https://doi.org/10.1109/ACCESS.2020.3020093.

M. Gmira, M. Gendreau, A. Lodi, and J.-Y. Potvin, ‘Tabu search for the time-dependent vehicle routing problem with time windows on a road network’, Eur. J. Oper. Res., vol. 288, no. 1, pp. 129–140, Jan. 2021, doi: https://doi.org/10.1016/j.ejor.2020.05.041.

J. Ochelska-Mierzejewska, ‘Tabu search algorithm for vehicle routing problem with time windows’, in Lecture Notes on Data Engineering and Communications Technologies, vol. 40, A. Poniszewska-Marańda, N. Kryvinska, S. Jarząbek, and L. Madeyski, Eds. Cham: Springer International Publishing, 2020, pp. 117–136, doi: https://doi.org/10.1007/978-3-030-34706-2_7.

Z. Zeng, X. Yu, K. He, and Z. Fu, ‘Adaptive Tabu search and variable neighborhood descent for packing unequal circles into a square’, Appl. Soft Comput., vol. 65, pp. 196–213, Apr. 2018, doi: https://doi.org/10.1016/j.asoc.2017.11.051.

L. Barrero, F. Robledo, P. Romero, and R. Viera, ‘A GRASP/VND Heuristic for the Heterogeneous Fleet Vehicle Routing Problem with Time Windows’, in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2021, vol. 12559 LNCS, pp. 152–165, doi: https://doi.org/10.1007/978-3-030-69625-2_12.

A. Khmelev and Y. Kochetov, ‘A hybrid VND method for the split delivery vehicle routing problem’, Electron. Notes Discret. Math., vol. 47, pp. 5–12, Feb. 2015, doi: https://doi.org/10.1016/j.endm.2014.11.002.

F. Glover, ‘Future paths for integer programming and links to artificial intelligence’, Comput. Oper. Res., vol. 13, no. 5, pp. 533–549, Jan. 1986, doi: https://doi.org/10.1016/0305-0548(86)90048-1.

M. M. Solomon, ‘Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints’, Oper. Res., vol. 35, no. 2, pp. 254–265, Apr. 1987, doi: https://doi.org/10.1287/opre.35.2.254.

Downloads

Published

2022-11-23

Issue

Vol. 6 No. 2 (2022): December

Section

Research Article

License

All articles in Jurnal Sistem dan Manajemen Industri can be disseminated provided they include the identity of the article and the source of the article Jurnal Sistem dan Manajemen Industri. The publisher is not responsible for the contents of the article. The content of the article is the sole responsibility of the author

Creative Commons License

Jurnal Sistem dan Manajemen Industri is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

How to Cite

[1]
“Tabu search heuristic for inventory routing problem with stochastic demand and time windows”, j. sist. manaj. ind., vol. 6, no. 2, pp. 111–120, Nov. 2022, doi: 10.30656/jsmi.v6i2.4813.
Crossref
Scopus
Google Scholar
Europe PMC

Similar Articles

1-10 of 56

You may also start an advanced similarity search for this article.

Most read articles by the same author(s)