A Novel Heuristic Based Simulated Annealing for the Capacitated Location Routing Problem

ABSTRACT

In this paper1 we are interested to study the capacitated location routing problem (CLRP). CLRP is defined like a combination of two difficult problems the facility location problem (FLP) and the Vehicle Routing Problem (VRP). CLRP consists in finding the depots to be opened, the vehicle routes to be assigned to each them to serve a set of customers in condition that not exceed the capacity constraints on depots and vehicles. To solve this problem, we propose a novel two-phase heuristic to construct a feasible CLRP solutions followed by a Simulated Annealing (SA) improvement phase. Our approach uses a new customers ordering technique based on a density metrics which is the ration between demands and distances of customers to minimize CLRP costs. In order to give the effectiveness of our heuristic, several LRP instances are used. The results given by our heuristic are very encouraging.

References

1. Rand G. Methodological choices in depot location studies. Operational Research Quarterly 1976;27(1):241--9.
2. R. B. Lopes, C. Ferreira, B. S. Santos, and S. Barreto. A taxonomical analysis, current methods and objectives on location-routing problems. International Transactions in Operational Research, 20(6):795--822, 2013.
3. Drexl and M. Schneider. A survey of variants and extensions of the location-routing problem. European Journal of Operational Research, 241(2):283--308, 2014a.
4. M. Drexl and M. Schneider. A survey of the standard location-routing problem. Working Paper LPIS-03/2014, Logistics Planning and Information Systems, TU Darmstadt, Germany, 2014b.
5. C. Prodhon and C. Prins. A survey of recent research on location-routing problems. European Journal of Operational Research, 238(1):1--17, 2014.
6. R. Cuda, G. Guastaroba, and M. G. Speranza. A survey on two-echelon routing problems. Computers & Operations Research, 55:185--199, 2015.
7. M. Albareda-Sambola. Location-routing and location-arc routing. In G. Laporte, S. Nickel, F. S danha da Gama, and M. Albareda-Sambola, editors, Location Science, chapter 15, pages 399--418. Springer, 2015.
8. H. Min, V. Jayaraman, and R. Srivastava. Combined location-routing problems: A synthesis and future research directions. European Journal of Operational Research, 108(1):1--15, 1998.
9. G. Nagy and S. Salhi. Location-routing: Issues, models and methods. European Journal of Opertional Research, 177(2):649--672, 2007.
10. AbdesslemLayeb, MeryemAmmi,Salim Chikhi. A GRASP Algorithm Based on New Randomized Heuristic for Vehicle Routing Problem. Journal of Computing and Information Technology,2013, CIT 21,1, 35--46.
11. Webb MHJ. Cost functions in the location of depots formultiple-delivery jou neys.OperResQ1968;19(3):311--20.
12. Christofides N,EilonS.An algorithm for the vehicle-dispatching problem.Oper ResQ1969;20(3):309.
13. Laporte, G., & Norbert, Y. An exact algorithm for minimizing routing and operating costs in depot location. European Journal of Operational Research. 1981. 6, 224--226.
14. Contardo, C., Cordeau, J.-F., &Gendron, B. A branch-and-cut-and-pric algorithm for the capacitated location-routing problem. INFORMS Journal on Computing, 2013a.
15. Jacobsen SK, Madsen OBG. A comparative study of heuristics for a two-level routing-location problem. EurJOperRes1980;5:378--87.
16. Nambiar JM,Gelders LF,Van Wassenhove LN.A large scale location-allocation problem in the natural rubber industry.Eur J Oper Res1981;6(2):183--9.
17. Ali Nadizadeh, RashedSahraeian, Ali SabzevariZadeh and Seyed Mahdi Homayouni, Using greedy clustering method to solve capacitated location-routing problem. African Journal of Business Management, 2011, 5(17), 7499--7506;
18. Lam, M. and Mittenthal, J. Capacitated hierarchical clustering heuristic for multi depot locationrouting problems, International Journal of Logistics Research and Applications, 2013,16(5): 433--444.
19. Helsgaun, K. An effective implementation of the Lin-Kernighan traveling salesman heuristic, European Journal of Operational Research, 2000, 126(1):106--130.
20. Perl J,Daskin MS.A unified warehouse location-routing methodology. J Bus Logist 1984;5(1):92--111.
21. Perl J,Daskin MS.A warehouse location-routing problem.Transp Res PartB 1985;19(5):381--96.
22. Hansen PH, Hegedahl B, Hjortkjær S, Obel B.A heuristic solution to the warehouse location-routing problem. Eur J Oper Res1994;76(1):111--27.
23. Tuzun D, Burke L. A two-phase tabu search approach to the location routing problem. European Journal of Operational Research 1999;116(1):87--99.
24. J. Melechovsky, C. Prins, R. Wolfler-Calvo, A metaheuristic to solve a location routing problem with non- linear costs, J. Heuristics, 2005, 11 (5-6), 375--391.
25. Albareda-Sambola, M., Díaz, J. A., &Fernáández, E. A compact model and tight bounds for a combined location-routing problem, Computers and Operations Research, 2005, 32(3), 407--428.
26. Wu. T, Low, C., & Bai, J. Heuristic solutions to multi-depot location-routing problems. Computers and Operations Research, 2002, 29, 1393--1415.
27. V.F. Yu, S.W. Lin, W. Lee, C.J. Ting, A simulated annealing heuristic for the capacitated location routing problem, Comput. Ind. Eng, 2010. 58, 288--299.
28. Prins. C, Prodhon. C, and WolerCalvo.R. Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR - A Quarterly Journal of Operations Research, 2006, 4(3):221--238.
29. Duhamel. C, Lacomme. P, Prins. C, and Prodhon. C. A GRASP_ELS approach for the capacitated location routing problem. Computers & Operations Research, 2010,37(11):1912--1923.
30. Derbel.H, Jarboui.B, Hana. S, and Chabchoub.H. Genetic algorithm with iterated local search for solving a location-routing problem. Expert Systems with Applications, 2012, 39(3):2865--2871.
31. Derbel.H, Jarboui.B, Chabchoub.B, Hana.S, and Mladenovi _c. A variable neighborhood search for the capacitated location-routing problem. In LOGISTIQUA, 2011.
32. Jabal-Amelia, M., Aryanezhada, M. and Ghaffari-Nasaba, N. A variable neighborhood descent based heuristic to solve the capacitated location-routing problem, International Journal of Industrial Engineering Computations, 2011, 2(1): 141--154.
33. Y. Marinakis, M. Marinaki, A bilevel genetic algorithm for a real life location routing problem, Int. J. Logist. Res. Appl, 2008, 11 (1) 49--65.
34. Jie Liu, VoratasKachitvichyanukul, Particle swarm optimization for solving location routing problem, Proceedings of the Asia Pacific Industrial Engineering & Management Systems Conference 2012
35. Ting, C.-J. and Chen, C.-H. A multiple ant colony optimization algorithm for the capacitated location routing problem, International Journal of Production Economics, 2013, 141(1): 34--44.
36. Bouhafs, L., Hajjam, A. and Koukam, A. A combination of simulated annealing and ant colony system for the capacitated location-routing problem, Knowledge-Based Intelligent Information and Engineering Systems, Vol. 4251 of LNCS, Springer, 2006, pp. 409--416.
37. Prins.C, Prodhon.C, and WolerCalvo.R. A memetic algorithm with population management (MA|PM) for the capacitated location-routing problem. (EvoCOP), vol.3906 of LNCS, pages 183--194. Springer, 2006.
38. Marinakis, Y. and Marinaki, M. A particle swarm optimization algorithm with path relinking for the location routing problem, Journal of Mathematical Modelling and Algorithms, 2008b, 7(1): 59--78.
39. Prins C, Prodhon C, Ruiz A, Soriano P, Wolfler-Calvo R. Solving the capacitated location routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic. Transportation Science 2007; 41(4):470--83.
40. Groer C, Golden B, Wasil E. A library of local search heuristics for the vehicle routing problem. Mathematical Programming Computation 2010;2(2): 79--101.
41. Laporte, G. Fifty years of vehicle routing. Transportation Science, 2009, 43(4): 408--416.
42. G. Laporte, F. Semet. Classical heuristics for the capacitated VRP. P. Toth, D. Vigo, eds.,The vehicle routing problem, Philadelphia, PA, 2001. pp. 109--128.
43. Sin C. Ho An iterated tabu search heuristic for the Single Source Capacitated Facility Location Problem; Applied Soft Computing 27, 2015, 169--178.
44. Yellow P. A computational modification to the savings method of vehicle scheduling. Operational Research Quarterly 1970;21(2):281--3.
45. Li F, Golden B, Wasil E. Very large-scale vehicle routing: new test problems, algorithms, and results. Computers and Operations Research 2005;32(5): 1165--79.