Solving Capacitated Location Routing Problem by Variable Neighborhood Descent and GA-Artificial Neural Network Hybrid Method

  • Engin Pekel Yildiz Technical University
  • Selin Soner Kara Yildiz Technical University
Keywords: artificial neural network, capacitated location-routing problem, genetic algorithm, heuristics, k-nearest neighborhood, variable neighborhood descent

Abstract

This paper aims to find the optimal depot locations and vehicle routings for spare parts of an automotive company considering future demands. The capacitated location-routing problem (CLRP), which has been practiced by various methods, is performed to find the optimal depot locations and routings by additionally using the artificial neural network (ANN). A novel multi-stage approach, which is performed to lower transportation cost, is carried out in CLRP. Initially, important factors for customer demand are tested with an univariate analysis and used as inputs in the prediction step. Then, genetic algorithm (GA) and ANN are hybridized and applied to provide future demands. The location of depots and the routings of the vehicles are determined by using the variable neighborhood descent (VND) algorithm. Five neighborhood structures, which are either routing or location type, are implemented in both shaking and local search steps. GA-ANN and VND are applied in the related steps successfully. Thanks to the performed VND algorithm, the company lowers its transportation cost by 2.35% for the current year, and has the opportunity to determine optimal depot locations and vehicle routings by evaluating the best and the worst cases of demand quantity for ten years ahead.

Author Biographies

Engin Pekel, Yildiz Technical University

Engin PEKEL holds an MSc in Industrial Engineering and he is currently studying his PhD in Industrial Engineering. He has been working as a Research Assistant in the Department of Industrial Engineering.

Selin Soner Kara, Yildiz Technical University

Selin Soner Kara holds an MSc in Industrial Engineering and a PhD in Industrial Engineering. She is an Associate Professor in the department of Industrial Engineering at Yildiz Technical University.

References

[1] Karaoglan I, Altiparmak F. A memetic algorithm for the capacitated location-routing problem with mixed backhauls. Computers & Operations Research. 2015;55: 200-216.
[2] Drexl M. Applications of the vehicle routing problem with trailers and transshipments. European Journal of Operational Research. 2013;227(2): 275-283.
[3] Duhamel C, Lacomme P, Prins C, Prodhon C. A GRASP×ELS approach for the capacitated location-routing problem. Computers & Operations Research. 2010;37(11): 1912-1923.
[4] Escobar JW. Heuristic algorithms for the capacitated location-routing problem and the multi-depot vehicle routing problem. 4OR. 2014;12(1): 99.
[5] Chen HL, Yang B, Wang G, Liu J, Xu X, Wang SJ, Liu DY. A novel bankruptcy prediction model based on an adaptive fuzzy k-nearest neighbor method. Knowledge-Based Systems. 2011;24(8): 1348-1359.
[6] Kadiyala A, Kaur D, Kumar A. Development of hybrid genetic-algorithm-based neural networks using regression trees for modeling air quality inside a public transportation bus. Journal of the Air & Waste Management Association. 2013;63(2): 205-218.
[7] Pekel E, Soner Kara S. Passenger Flow Prediction Based on Newly Adopted Algorithms. Applied Artificial Intelligence. 2017;31(1): 64-79.
[8] Prodhon C, Prins C. A survey of recent research on location-routing problems. European Journal of Operational Research. 2014;238(1): 1-17.
[9] Jarboui B, Derbel H, Hanafi S, Mladenović N. Variable neighborhood search for location routing. Computers & Operations Research. 2013;40(1): 47-57.
[10] Hansen P, Mladenović N. Variable neighbourhood search. Handbook of metaheuristics. Boston, Dordrecht, London: Kluwer Academic Publisher. 2003; p. 145-184.
[11] Mladenović N, Hansen P. Variable neighbourhood search. Computers & Operations Research. 1997;24(11): 1097-1100.
[12] Nikbakhsh E, Zegordi SH. A heuristic algorithm and a lower bound for the two-echelon location-routing problem with soft time window constraints. Scientia Iranica Transaction E: Industrial Engineering. 2010;17(1): 36-47.
[13] Belenguer J, Benavent E, Prins C, Prodhon C, Calvo RW. A branch-and-cut method for the capacitated location-routing problem. Computers & Operations Research. 2011;38(6): 931-941.
[14] Riera-Ledesma J, Salazar-González JJ. Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach. Computers & Operations Research. 2012;39(2): 391-404.
[15] Ponboon S, Qureshi AG, Taniguchi E. Branch-and-price algorithm for the location-routing problem with time windows. Transportation Research Part E: Logistics and Transportation Review. 2016;86: 1-19.
[16] Marinakis Y, Marinaki M, Migdalas A. A hybrid clonal selection algorithm for the location routing problem with stochastic demands. Annals of Mathematics and Artificial Intelligence. 2016;76(1-2): 121-142.
[17] Golozari F, Jafari A, Amiri M. Application of a hybrid simulated annealing-mutation operator to solve fuzzy capacitated location-routing problem. The International Journal of Advanced Manufacturing Technology. 2013;67(5-8): 1791-1807.
[18] Bay SD. Nearest neighbor classification from multiple feature subsets. Intelligent Data Analysis. 1999;3(3): 191-209.
Published
2018-11-09
How to Cite
1.
Pekel E, Soner Kara S. Solving Capacitated Location Routing Problem by Variable Neighborhood Descent and GA-Artificial Neural Network Hybrid Method. Promet - Traffic & Transportation [Internet]. 9Nov.2018 [cited 20Nov.2018];30(5):563-78. Available from: https://traffic.fpz.hr/index.php/PROMTT/article/view/2640
Section
Articles