Mohamed Salim Amri Sakhri Profile Mohamed Salim Amri Sakhri

A memetic algorithm for the inventory routing problem

  • Authors Details :  
  • Mounira Tlili ,  
  • Mohamed Salim Amri Sakhri ,  
  • Ouajdi Korbaa

Journal title : Journal of Heuristics

Publisher : Springer Science and Business Media LLC

Online ISSN : 1572-9397

Page Number : 351-375

Journal volume : 28

Journal issue : 3

845 Views Original Article

In this article, we study an Inventory Routing Problem with deterministic customer demand in a two-tier supply chain. The supply chain network consists of a supplier using a single vehicle with a given capacity to deliver a single product type to multiple customers. We are interested in population-based algorithms to solve our problem. A Memetic Algorithm (MA) is developed based on the Genetic Algorithm (GA) and Variable Neighborhood Search methods. The proposed meta-heuristics are tested on small and large reference benchmarks. The results of the MA are compared to those of the classical GA and to the optimal solutions in the literature. The comparison shows the efficiency of using MA and its ability to generate high quality solutions in a reasonable computation time.

Article DOI & Crossmark Data

DOI : https://doi.org/10.1007/s10732-022-09497-1

Article Subject Details


Article Keywords Details



Article File

Full Text PDF


Article References

  • (1). Abid, H., Yousaf-Shad, M., Nauman, S., Ijaz, H., Alaa, M., Showkat, G.: Genetic algorithm for traveling salesman problem with modified cycle crossover operator. Comput. Intell. Neurosci. (2017). https://doi.org/10.1155/2017/7430125
  • (2). Amri Sakhri, M.S.: Comparative analysis of different crossover structures for solving a periodic inventory routing problem. Int. J. Data Sci. Anal. (2021). https://doi.org/10.1007/s41060-021-00280-2
  • (3). Amri Sakhri, M.S., Tlili, M., Allaoui, H., Korbaa, O.: Order crossover for the inventory routing problem. In: European Symposium on Artificial Neural Networks, pp. 697–702. Bruges, Belgium (2018)
  • (4). Archetti, C., Bertazzi, L., Laporte, G., Speranza, M.G.: A branch-and-cut algorithm for a vendor-managed inventory-routing problem. Transp. Sci. 41, 382–391 (2007). https://doi.org/10.1287/trsc.1060.0188
  • (5). Archetti, C., Bertazzi, L., Hertz, A., Speranza, M.G.: A hybrid heuristic for an inventory routing problem. INFORMS J. Comput. 24, 101–116 (2012). https://doi.org/10.1287/ijoc.1100.0439
  • (6). Azadeh, A., Elahi, S., Farahani, M.H., Nasirian, B.: A genetic algorithm-Taguchi based approach to inventory routing problem of a single perishable product with transshipment. Comput. Ind. Eng. 104, 124–133 (2017). https://doi.org/10.1016/j.cie.2016.12.019
  • (7). Baniamerian, A., Bashiri, M., Tavakkoli-Moghaddam, R.: Modified variable neighborhood search and genetic algorithm for profitable heterogeneous vehicle routing problem with cross-docking. Appl. Soft Comput. 75, 441–460 (2019). https://doi.org/10.1016/j.asoc.2018.11.029
  • (8). Bell, W.J., Dalberto, L.M., Fisher, M.L., Greeneld, A.J., Jaikumar, R., Kedia, P., Mack, R.G., Prutzman, P.J.: Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer. Interfaces 13(6), 4–23 (1983). https://doi.org/10.1287/inte.13.6.4
  • (9). Bertazzi, L., Speranza, M.G.: Continuous and discrete shipping strategies for the single link problem. Transp. Sci. 36, 314–325 (2002). https://doi.org/10.1287/trsc.36.3.314.7828
  • (10). Bertazzi, L., Paletta, G., Speranza, M.G.: Deterministic order-up-to level policies in an inventory routing problem. Transp. Sci. 36, 119–132 (2002). https://doi.org/10.1287/trsc.36.1.119.573
  • (11). Chen, R.M., Shen, Y.M., Hong, W.Z.: Neural-like encoding particle swarm optimization for periodic vehicle routing problems. Expert Syst. Appl. 138, 112833 (2019). https://doi.org/10.1016/j.eswa.2019.112833
  • (12). Coelho, L.C., Laporte, G.: An optimized target level inventory replenishment policy for vendor managed inventory systems. Int. J. Prod. Res. 53, 3651–3660 (2015). https://doi.org/10.1080/00207543.2014.986299
  • (13). Cooray, P.L.N.U., Thashika, D.R.: Machine learning-based parameter tuned genetic algorithm for energy minimizing vehicle routing problem. J. Ind. Eng. (2017). https://doi.org/10.1155/2017/3019523
  • (14). Ece, Y., Saadettin, E.K.: Multi-trip heterogeneous vehicle routing problem coordinated with production scheduling: memetic algorithm and simulated annealing approaches. Comput. Ind. Eng. 161, 107649 (2021). https://doi.org/10.1016/j.cie.2021.107649
  • (15). Eleftherios, M., Panagiotis, R., Emmanouil, Z., Christos, T.: Improved branch-and-cut for the Inventory Routing Problem based on a two-commodity flow formulation. Eur. J. Oper. Res. 290(3), 870–885 (2021). https://doi.org/10.1016/j.ejor.2020.08.047
  • (16). Fardi, K., Ghoushchi, S.J., Hafezalkotob, A.: An extended robust approach for a cooperative inventory routing problem. Expert Syst. Appl. 116, 310–327 (2019). https://doi.org/10.1016/j.eswa.2018.09.002
  • (17). Gizem, Ö.T., Esra, K., Hande, Y.: An exact solution approach for the inventory routing problem with time windows. Comput. Oper. Res. 134, 105371 (2021). https://doi.org/10.1016/j.cor.2021.105371
  • (18). Gruler, A., Panadero, J., Armas, J., Moreno-Pérez, J.A., Juan, A.A.: Combining variable neighborhood search with simulation for the inventory routing problem with stochastic demands and stock-outs. Comput. Ind. Eng. 123, 278–288 (2018). https://doi.org/10.1016/j.cie.2018.06.036
  • (19). Hewitt, M., Nemhauser, G., Savelsbergh, M., Song, J.H.: A branch-and-price guided search approach to maritime inventory routing. Comput. Oper. Res. 40, 1410–1419 (2013). https://doi.org/10.1016/j.cor.2012.09.010
  • (20). Jahangir, H., Mohammadi, M., Pasandideh Reza, S.H., Neda, Z.N.: Comparing performance of genetic and discrete invasive weed optimization algorithms for solving the inventory routing problem with an incremental delivery. J. Intell. Manuf. 30, 2327–2353 (2019). https://doi.org/10.1007/s10845-018-1393-z
  • (21). Labadi, N., Prins, C., Reghioui, M.: A memetic algorithm for the vehicle routing problem with time windows. RAIRO Oper. Res. 42(3), 415–431 (2008). https://doi.org/10.1051/ro:2008021
  • (22). Mahdi, A., Erfan, B.T., Zahra, K.D., Seyed, R.H., Weiping, D.: An augmented Tabu search algorithm for the green inventory-routing problem with time windows. Swarm Evolut. Comput. 60, 100802 (2021). https://doi.org/10.1016/j.swevo.2020.100802
  • (23). Meysam, M., Seyed, S.F., Soodabeh, M., Leyla, S.T., Mirpouya, M.: A modified adaptive genetic algorithm for multi-product multi-period inventory routing problem. Sustain. Oper. Comput. 3, 1–9 (2021). https://doi.org/10.1016/j.susoc.2021.08.002
  • (24). Mirzaei, S., Seifi, A.: Genetic algorithm for traveling salesman problem with modified cycle crossover operator. Comput. Ind. Eng. 87, 213–227 (2015). https://doi.org/10.1016/j.cie.2015.05.010
  • (25). Mjirda, A., Jarboui, B., Macedo, R., Hanafi, S., Mladenovic, N.: A two phase variable neighborhood search for the multi-product inventory routing problem. Comput. Oper. Res. 52, 291–299 (2014). https://doi.org/10.1016/j.cor.2013.06.006
  • (26). Mladenovic, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997). https://doi.org/10.1016/S0305-0548(97)00031-2
  • (27). Molina, J.C., Salmeron, J.L., Eguia, I.: An ACS-based memetic algorithm for the heterogeneous vehicle routing problem with time windows. Expert Syst. Appl. 157, 113379 (2020). https://doi.org/10.1016/j.eswa.2020.113379
  • (28). Olgun, M.O., Aydemir, E.: A new cooperative depot sharing approach for inventory routing problem. Ann. Oper. Res. 307, 417–441 (2021). https://doi.org/10.1007/s10479-021-04122-z
  • (29). Park, Y., Yoo, J., Park, H.: A genetic algorithm for the vendor-managed in ventory routing problem with lost sales. Expert Syst. Appl. 53, 149–159 (2016). https://doi.org/10.1016/j.eswa.2016.01.041
  • (30). Prasetyo, H., Putri, A.L., Fauza, G.: Biased random key genetic algorithm design with multiple populations to solve capacitated vehicle routing problem with time windows. In: Proceedings AIP Conference (2018). https://doi.org/10.1063/1.5042908
  • (31). Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 31(12), 1985–2002 (2004). https://doi.org/10.1016/S0305-0548(03)00158-8
  • (32). Qin, L., Miao, L., Ruan, Q., Zhang, Y.: A local search method for periodic inventory routing problem. Expert Syst. Appl. 41, 765–778 (2014). https://doi.org/10.1016/j.eswa.2013.07.100
  • (33). Rau, H., Budiman, S.D., Widyadana, G.A.: Optimization of the multi-objective green cyclical inventory routing problem using discrete multi-swarm PSO method. Transp. Res. Part E Logist. Transp. Rev. 120, 51–75 (2018). https://doi.org/10.1016/j.tre.2018.10.006
  • (34). Sabar, N.R., Bhaskar, A., Chung, E., Turky, A., Song, A.: An adaptive memetic approach for heterogeneous vehicle routing problems with two-dimensional loading constraints. Swarm Evolut Comput 58, 100730 (2020). https://doi.org/10.1016/j.swevo.2020.100730
  • (35). Sbai, I., Krichen, S., Limam, O.: Two meta-heuristics for solving the capacitated vehicle routing problem: the case of the Tunisian Post Office. Oper. Res. (2020). https://doi.org/10.1007/s12351-019-00543-8
  • (36). Tinós R, Helsgaun K, Whitley D (2018) Efficient recombination in the Lin–Kernighan–Helsgaun traveling salesman heuristic. In: International Conference on Parallel Problem Solving from Nature, pp. 95–107. Springer, Cham. https://doi.org/10.1007/978-3-319-99253-2_8



More Article by Mohamed Salim Amri Sakhri

Comparative analysis of different crossover structures for solving a periodic inventory routing problem

One of the most important challenges for a company is to manage its supply chain efficiently. one way to do this is to control and minimize its various logistics costs together to ...