Capacitated location routing problem with simultaneous pickup and delivery under the risk of disruption

Dehghan, Milad; Hejazi, Seyed Reza; Karimi-Mamaghan, Maryam; Mohammadi, Mehrdad; Pirayesh, Amir

doi:10.1051/ro/2021050

Dehghan, Milad ; Hejazi, Seyed Reza ; Karimi-Mamaghan, Maryam ; Mohammadi, Mehrdad ; Pirayesh, Amir

RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 1371-1399

Résumé

This paper develops a new mathematical model to study a location-routing problem with simultaneous pickup and delivery under the risk of disruption. A remarkable number of previous studies have assumed that network components (e.g., routes, production factories, depots, etc.) are always available and can permanently serve the customers. This assumption is no longer valid when the network faces disruptions such as flood, earthquake, tsunami, terrorist attacks and workers strike. In case of any disruption in the network, tremendous cost is imposed on the stockholders. Incorporating disruption in the design phase of the network will alleviate the impact of these disasters and let the network resist disruption. In this study, a mixed integer programming (MIP) model is proposed that formulates a reliable capacitated location-routing problem with simultaneous pickup and delivery (RCLRP-SPD) services in supply chain distribution network. The objective function attempts to minimize the sum of location cost of depots, routing cost of vehicles and cost of unfulfilled demand of customers. Since the model is NP-Hard, three meta-heuristics are tailored for large-sized instances and the results show the outperformance of hybrid algorithms comparing to classic genetic algorithm. Finally, the obtained results are discussed and the paper is concluded.

MR

DOI : 10.1051/ro/2021050

Classification : 90C59
Keywords: Reliable capacitated location-routing problem, simultaneous pickup and delivery, disruptions, hybrid algorithms

@article{RO_2021__55_3_1371_0,
     author = {Dehghan, Milad and Hejazi, Seyed Reza and Karimi-Mamaghan, Maryam and Mohammadi, Mehrdad and Pirayesh, Amir},
     title = {Capacitated location routing problem with simultaneous pickup and delivery under the risk of disruption},
     journal = {RAIRO. Operations Research},
     pages = {1371--1399},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {3},
     doi = {10.1051/ro/2021050},
     mrnumber = {4269468},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021050/}
}

TY  - JOUR
AU  - Dehghan, Milad
AU  - Hejazi, Seyed Reza
AU  - Karimi-Mamaghan, Maryam
AU  - Mohammadi, Mehrdad
AU  - Pirayesh, Amir
TI  - Capacitated location routing problem with simultaneous pickup and delivery under the risk of disruption
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 1371
EP  - 1399
VL  - 55
IS  - 3
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021050/
DO  - 10.1051/ro/2021050
LA  - en
ID  - RO_2021__55_3_1371_0
ER  -

%0 Journal Article
%A Dehghan, Milad
%A Hejazi, Seyed Reza
%A Karimi-Mamaghan, Maryam
%A Mohammadi, Mehrdad
%A Pirayesh, Amir
%T Capacitated location routing problem with simultaneous pickup and delivery under the risk of disruption
%J RAIRO. Operations Research
%D 2021
%P 1371-1399
%V 55
%N 3
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021050/
%R 10.1051/ro/2021050
%G en
%F RO_2021__55_3_1371_0

Dehghan, Milad; Hejazi, Seyed Reza; Karimi-Mamaghan, Maryam; Mohammadi, Mehrdad; Pirayesh, Amir. Capacitated location routing problem with simultaneous pickup and delivery under the risk of disruption. RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 1371-1399. doi: 10.1051/ro/2021050

Bibliographie
Cité par

[1] A. Ahmadi-Javid and A. H. Seddighi, A location-routing problem with disruption risk. Transp. Res. Part E: Logistics Transp. Rev. 53 (2013) 63–82. | DOI

[2] M. Albareda-Sambola, E. Fernández and G. Laporte, Heuristic and lower bound for a stochastic location-routing problem. Eur. J. Oper. Res. 179 (2007) 940–955. | Zbl | DOI

[3] E. Ardjmand, G. Weckman, N. Park, P. Taherkhani and M. Singh, Applying genetic algorithm to a new location and routing model of hazardous materials. Int. J. Prod. Res. 53 (2015) 916–928. | DOI

[4] S. Babaie-Kafaki, R. Ghanbari and N. Mahdavi-Amiri, Hybridizations of genetic algorithms and neighborhood search metaheuristics for fuzzy bus terminal location problems. Appl. Soft Comput. 46 (2016) 220–229. | DOI

[5] C.-L. Chen and W.-C. Lee, Multi-objective optimization of multi-echelon supply chain networks with uncertain product demands and prices. Comput. Chem. Eng. 28 (2004) 1131–1144. | DOI

[6] H. Chentli, R. Ouafi and W. R. Cherif-Khettaf, A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services. RAIRO:OR 52 (2018) 1295–1328. | MR | Zbl | Numdam | DOI

[7] H. Chentli, R. Ouafi and W. R. Cherif-Khettaf, Impact of iterated local search heuristic hybridization on vehicle routing problems: application to the capacitated profitable tour problem. In: Impact of iterated local search heuristic hybridization on vehicle routing problems: application to the capacitated profitable tour problem. Springer, Cham (2018) 80–101.

[8] W. R. Cherif-Khettaf, M. H. Rachid, C. Bloch and P. Chatonnay, New notation and classification scheme for vehicle routing problems. RAIRO:OR 49 (2015) 161–194. | MR | Zbl | Numdam | DOI

[9] T. Cui, Y. Ouyang and Z.-J. M. Shen, Reliable facility location design under the risk of disruptions. Oper. Res. 58 (2010) 998–1011. | MR | Zbl | DOI

[10] E. Dehghani, M. S. Pishvaee and M. S. Jabalameli, A hybrid Markov process-mathematical programming approach for joint location-inventory problem under supply disruptions. RAIRO:OR 52 (2018) 1147–1173. | MR | Zbl | Numdam | DOI

[11] H. Derbel, B. Jarboui, S. Hanafi and H. Chabchoub, Genetic algorithm with iterated local search for solving a location-routing problem. Expert Syst. App. 39 (2012) 2865–2871. | DOI

[12] M. Drexl and M. Schneider, A survey of variants and extensions of the location-routing problem. Eur. J. Oper. Res. 241 (2015) 283–308. | MR | DOI

[13] A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing. Springer 53 (2003). | MR | Zbl | DOI

[14] J. W. Escobar, R. Linfati and P. Toth, A two-phase hybrid heuristic algorithm for the capacitated location-routing problem. Comput. Oper. Res. 40 (2013) 70–79. | MR | DOI

[15] J. W. Escobar, R. Linfati, M. G. Baldoquin and P. Toth, A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem. Transp. Res. Part B: Methodol. 67 (2014) 344–356. | DOI

[16] K. M. Ferreira and T. A. De Queiroz, Two effective simulated annealing algorithms for the Location-Routing Problem. Appl. Soft Comput. 70 (2018) 389–422. | DOI

[17] N. Ghaffari-Nasab, M. S. Jabalameli, M. B. Aryanezhad and A. Makui, Modeling and solving the bi-objective capacitated location-routing problem with probabilistic travel times. Int. J. Adv. Manuf. Technol. 67 (2013) 2007–2019. | DOI

[18] J. Holland, Adaptation in natural and artificial systems: an introductory analysis with application to biology. Control Artif. Intell. (1975). | MR | Zbl

[19] S.-H. Huang, Solving the multi-compartment capacitated location routing problem with pickup–delivery routes and stochastic demands. Comput. Ind. Eng. 87 (2015) 104–113. | DOI

[20] S. Karakatič and V. Podgorelec, A survey of genetic algorithms for solving multi depot vehicle routing problem. Appl. Soft Comput. 27 (2015) 519–532. | DOI

[21] A. Karaoglan and F. Altiparmak, A memetic algorithm for the capacitated location-routing problem with mixed backhauls. Comput. Oper. Res. 55 (2015) 200–216. | MR | DOI

[22] I. Karaoglan, F. Altiparmak, I. Kara and B. Dengiz, A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery. Eur. J. Oper. Res. 211 (2011) 318–332. | MR | Zbl | DOI

[23] A. Karaoglan, F. Altiparmak, I. Kara and B. Dengiz, The location-routing problem with simultaneous pickup and delivery: formulations and a heuristic approach. Omega 40 (2012) 465–477. | DOI

[24] M. Karimi-Mamaghan, M. Mohammadi, B. Pasdeloup, R. Billot and P. Meyer, An online learning-based metaheuristic for solving combinatorial optimization problems. In: 21ème congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF) (2020).

[25] M. Karimi-Mamaghan, M. Mohammadi, P. Jula, A. Pirayesh and H. Ahmadi, A learning-based metaheuristic for a multi-objective agile inspection planning model under uncertainty. Eur. J. Oper. Res. 285 (2020) 513–537. | MR | DOI

[26] M. Karimi-Mamaghan, M. Mohammadi, A. Pirayesh, A. M. Karimi-Mamaghan and H. Irani, Hub-and-spoke network design under congestion: a learning based metaheuristic. Transp. Res. Part E: Logistics Transp. Rev. 142 (2020). | DOI

[27] K. Khalili-Damghani, A.-R. Abtahi and A. Ghasemi, A new bi-objective location-routing problem for distribution of perishable products: evolutionary computation approach. J. Math. Model. Algorithms Oper. Res. 14 (2015) 287–312. | MR | DOI

[28] Q. Li, B. Zeng and A. Savachkin, Reliable facility location design under disruptions. Comput. Oper. Res. 40 (2013) 901–909. | MR | DOI

[29] R. B. Lopes, C. Ferreira and B. S. Santos, A simple and effective evolutionary algorithm for the capacitated location-routing problem. Comput. Oper. Res. 70 (2016) 155–162. | MR | DOI

[30] S. Majidi, S.-M. Hosseini-Motlagh, S. Yaghoubi and A. Jokar, Fuzzy green vehicle routing problem with simultaneous pickup – delivery and time windows. RAIRO:OR 51 (2017) 1151–1176. | MR | Zbl | Numdam | DOI

[31] Y. Marinakis, An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands. Appl. Soft Comput. 37 (2015) 680–701. | DOI

[32] E. Mehdizadeh, R. Tavakkoli-Moghaddam and M. Yazdani, A vibration damping optimization algorithm for a parallel machines scheduling problem with sequence-independent family setup times. Appl. Math. Model. 39 (2015) 6845–6859. | MR | DOI

[33] M. T. Melo, S. Nickel and F. Saldanha-Da-Gama, Facility location and supply chain management – A review. Eur. J. Oper. Res. 196 (2009) 401–412. | MR | Zbl | DOI

[34] D. M. Miranda, J. Branke and S. V. Conceição, Algorithms for the multi-objective vehicle routing problem with hard time windows and stochastic travel time and service time. Appl. Soft Comput. 70 (2018) 66–79. | DOI

[35] N. Mladenović and P. Hansen, Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097–1100. | MR | Zbl | DOI

[36] M. Mohammadi and R. Tavakkoli-Moghaddam, Design of a fuzzy bi-objective reliable $p$ -hub center problem. J. Intell. Fuzzy Syst. 30 (2016) 2563–2580. | DOI

[37] M. Mohammadi, R. Tavakkoli-Moghaddam, H. Tolouei and M. Yousefi, Solving a hub covering location problem under capacity constraints by a hybrid algorithm. J. Appl. Oper. Res. 2 (2010) 109–116.

[38] M. Mohammadi, R. Tavakkoli-Moghaddam, A. Siadat and J.-Y. Dantan, Design of a reliable logistics network with hub disruption under uncertainty. Appl. Math. Model. 40 (2016) 5621–5642. | MR | DOI

[39] M. Mohammadi, P. Jula and R. Tavakkoli-Moghaddam, Design of a reliable multi-modal multi-commodity model for hazardous materials transportation under uncertainty. Eur. J. Oper. Res. 257 (2017) 792–809. | MR | DOI

[40] M. Mohammadi, J. Y. Dantan, A. Siadat and R. Tavakkoli-Moghaddam, A bi-objective robust inspection planning model in a multi-stage serial production system. Int. J. Prod. Res. 56 (2018) 1432–1457. | DOI

[41] M. Moshref-Javadi and S. Lee, The latency location-routing problem. Eur. J. Oper. Res. 255 (2016) 604–619. | MR | DOI

[42] A. Nadizadeh and B. Kafash, Fuzzy capacitated location-routing problem with simultaneous pickup and delivery demands. Transp. Lett. 11 (2019) 1–19. | DOI

[43] A. Nadizadeh and H. H. Nasab, Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm. Eur. J. Oper. Res. 238 (2014) 458–470. | MR | DOI

[44] G. Nagy and S. Salhi, Location-routing: issues, models and methods. Eur. J. Oper. Res. 177 (2007) 649–672. | MR | Zbl | DOI

[45] F. Oudouar, M. Lazaar, Z. E. Miloud, A novel approach based on heuristics and a neural network to solve a capacitated location routing problem. Simul. Model. Pract. Theory 100 (2020). | DOI

[46] E. Pekel, S. Soner Kara, Solving fuzzy capacitated location routing problem using hybrid variable neighborhood search and evolutionary local search. Appl. Soft. Comput. 83 (2019). | DOI

[47] K. Pichka, A. H. Bajgiran, M. E. Petering, J. Jang and X. Yue, The two echelon open location routing problem: mathematical model and hybrid heuristic. Comput. Ind. Eng. 121 (2018) 97–112. | DOI

[48] O. Polat, C. B. Kalayci, O. Kulak and H.-O. Günther, A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery with time limit. Eur. J. Oper. Res. 242 (2015) 369–382. | MR | DOI

[49] C. Prodhon and C. Prins, A survey of recent research on location-routing problems. Eur. J. Oper. Res. 238 (2014) 1–17. | MR | DOI

[50] J. Respen, N. Zufferey and J.-Y. Potvin, Impact of vehicle tracking on a routing problem with dynamic travel times. RAIRO:OR 53 (2019) 401–414. | MR | Zbl | Numdam | DOI

[51] S. Salhi and G. K. Rand, The effect of ignoring routes when locating depots. Eur. J. Oper. Res. 39 (1989) 150–156. | MR | Zbl | DOI

[52] L. V. Snyder, Supply chain robustness and reliability: models and algorithms. Ph.D diss.Northwestern University (2003).

[53] L. V. Snyder and M. S. Daskin, Reliability models for facility location: the expected failure cost case. Transp. Sci. 39 (2005) 400–416. | DOI

[54] J. Wang, K. Su and Y. Wu, The reliable facility location problem under random disruptions. Wireless Pers. Commun. 102 (2018) 2483–2497. | DOI

[55] W. Xie, Y. Ouyang and S. C. Wong, Reliable location-routing design under probabilistic facility disruptions. Transp. Sci. 50 (2015) 1128–1138. | DOI

[56] F. Yu and S.-Y. Lin, Solving the location-routing problem with simultaneous pickup and delivery by simulated annealing. Int. J. Prod. Res. 54 (2016) 526–549. | DOI

[57] F. Yu, S.-W. Lin and W. Lee, C.-J. Ting, A simulated annealing heuristic for the capacitated location routing problem. Comput. Ind. Eng. 58 (2010) 288–299. | DOI

[58] X. Yu, Y. Zhou, X.-F. Liu, A novel hybrid genetic algorithm for the location routing problem with tight capacity constraints. Appl. Soft. Comput. 85 (2019).

[59] B. Zahiri, S. A. Torabi, M. Mohammadi and M. Aghabegloo, A multi-stage stochastic programming approach for blood supply chain planning. Comput. Ind. Eng. 122 (2018) 1–14. | DOI

[60] M. H. F. Zarandi, A. Hemmati and S. Davari, The multi-depot capacitated location-routing problem with fuzzy travel times. Expert Syst. App. 38 (2011) 10075–10084. | DOI

[61] M. H. F. Zarandi, A. Hemmati, S. Davari and I. B. Turksen, Capacitated location-routing problem with time windows under uncertainty. Knowl.-Based Syst. 37 (2013) 480–489. | DOI

[62] Y. Zare Mehrjerdi and A. Nadizadeh, Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. Eur. J. Oper. Res. 229 (2013) 75–84. | MR | Zbl | DOI

[63] M. Zhalechian, R. Tavakkoli-Moghaddam, B. Zahiri and M. Mohammadi, Sustainable design of a closed-loop location-routing-inventory supply chain network under mixed uncertainty. Transp. Res. Part E: Logistics Transp. Rev. 89 (2016) 182–214. | DOI

[64] Y. Zhang, M. Qi, W.-H. Lin and L. Miao, A metaheuristic approach to the reliable location routing problem under disruptions. Transp. Res. Part E: Logistics Transp. Rev. 83 (2015) 90–110. | DOI

[65] B. Zhang, H. Li, S. Li and J. Peng, Sustainable multi-depot emergency facilities location-routing problem with uncertain information. Appl. Math. Comput. 333 (2018) 506–520. | MR | Zbl

Cité par Sources :