Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. (English) Zbl 1125.90316
Summary: As shown in recent researches, the costs in distribution systems may be excessive if routes are ignored when locating depots. The location routing problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. This paper presents a new metaheuristic to solve the LRP with capacitated routes and depots. A first phase executes a GRASP, based on an extended and randomized version of Clarke and Wright algorithm. This phase is implemented with a learning process on the choice of depots. In a second phase, new solutions are generated by a post-optimization using a path relinking. The method is evaluated on sets of randomly generated instances, and compared to other heuristics and a lower bound. Solutions are obtained in a reasonable amount of time for such a strategic problem. Furthermore, the algorithm is competitive with a metaheuristic published for the case of uncapacitated depots.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90B80 | Discrete location and assignment |
References:
| [1] | Albareda-Sambola M, Díaz JA, Fernández E (2005) A compact model and tight bounds for a combined location-routing problem. Comput Oper Res 32(3):407–428 · Zbl 1061.90016 · doi:10.1016/S0305-0548(03)00245-4 |
| [2] | Barreto SS (2004) Análise e Modelização de Problemas de localização-distribuição (Analysis and modelization of location-routing problems)(in Portuguese). PhD thesis, University of Aveiro, campus universitário de Santiago, 3810–193 |
| [3] | Bruns A, Klose A (1995) An iterative heuristic for location-routing problems based on clustering. In: Proceedings of the 2nd international workshop on distribution logistics, Oegstgeest |
| [4] | Chan Y, Carter WB, Burnes MD (2001) A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands. Comput Oper Res 28:803–826 · Zbl 1027.90034 · doi:10.1016/S0305-0548(00)00009-5 |
| [5] | Chien TW (1993) Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems. Decis Sci 24(5):995–1021 · doi:10.1111/j.1540-5915.1993.tb00500.x |
| [6] | Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12:568–581 · doi:10.1287/opre.12.4.568 |
| [7] | Cordeau JF, Gendreau M, Hertz A, Laporte G, Sormany JS (2004) New heuristics for the vehicle routing problem. In: Technical Report G-2004-33, GERAD · Zbl 1130.90416 |
| [8] | Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J Glob Optim 2:1–27 · Zbl 0822.90110 |
| [9] | Fleurent C, Glover F (1999) Improved constructive multistart strategies for the quadratic assignment problem using adaptative memory. INFORMS J Comput 11:198–204 · Zbl 1040.90541 · doi:10.1287/ijoc.11.2.198 |
| [10] | Ghiani G, Laporte G (2001) Location-arc routing problems. OPSEARCH 38:151–159 |
| [11] | Labadi N (2003) Problèmes tactiques et stratégiques en tournées sur arcs (Tactical and strategic problems on arc routing). PhD thesis, University of Technology of Troyes |
| [12] | Laguna M, Martí R (1995) Grasp and path relinking for 2-layer straight line crossing minimization. INFORMS J Comput 11(1):44–52 · Zbl 1092.90544 · doi:10.1287/ijoc.11.1.44 |
| [13] | Laporte G, Gendreau M, Potvin JY, Semet F (2000) Classical and modern heuristics for the vehicle routing problem. Int Trans Oper Res 7:285–300 · doi:10.1111/j.1475-3995.2000.tb00200.x |
| [14] | Laporte G, Louveaux F, Mercure H (1989) Models and exact solutions for a class of stochastic location-routing problems. Eur J Oper Res 39:71–78 · Zbl 0676.90019 · doi:10.1016/0377-2217(89)90354-8 |
| [15] | Laporte G, Norbert Y, Taillefer S (1988) Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Sci 22(3):161–167 · Zbl 0662.90039 · doi:10.1287/trsc.22.3.161 |
| [16] | Lin S, Kernigham BW (1973) An effective heuristic algorithm for the traveling salesman problem. Oper Res 21:498–516 · Zbl 0256.90038 · doi:10.1287/opre.21.2.498 |
| [17] | Min H, Jayaraman V, Srivastava R (1998) Combined location-routing problems: a synthesis and future research directions. European J Oper Res 108:1–15 · Zbl 0943.90008 · doi:10.1016/S0377-2217(97)00172-0 |
| [18] | Piñana E, Plana I, Campos V, Martí R (2004) GRASP and path relinking for the matrix bandwidth minimization. Eur J Oper Res 153:200–210 · Zbl 1053.90057 · doi:10.1016/S0377-2217(02)00715-4 |
| [19] | Prais M, Ribeiro CC (2000) Reactive GRASP: an application to a matrix decomposition problem in TDMA traffic assignment. INFORMS J Comput 12(3):164–176 · Zbl 1040.90504 · doi:10.1287/ijoc.12.3.164.12639 |
| [20] | Prins C, Prodhon C, Wolfler Calvo R (2004) Nouveaux algorithmes pour le problème de localisation et routage sous contraintes de capacité. In: Dolgui A., Dauzère-Pérès S. (eds) MOSIM’04, vol 2. Ecole des Mines de Nantes, Lavoisier, pp 1115–1122 |
| [21] | Resende MGC, Rebeiro CC (2003) Greedy randomized adaptive search procedures. In: Glover F., Kochenberger G. (eds) Handbook of metaheuristics. Kluwer, Dordrecht, pp 219–249 · Zbl 1102.90384 |
| [22] | Resende MGC, Werneck RF (2002) A hybrid heuristic for the p-median problem. In: Technical report TD-SNWRCR, AT & TLab Research, Florham Park, NJ 07932 |
| [23] | Salhi S, Rand GK (1989) The effect of ignoring routes when locating depots. Eur J Oper Res 39:150–156 · Zbl 0658.90050 · doi:10.1016/0377-2217(89)90188-4 |
| [24] | Srivastava R (1993) Alternate solution procedures for the locating-routing problem. OMEGA Int J Manage Sci 21(4):497–506 · doi:10.1016/0305-0483(93)90082-V |
| [25] | Tuzun D, Burke LI (1999) A two-phase tabu search approach to the location routing problem. Eur J Oper Res 116:87–99 · Zbl 1009.90056 · doi:10.1016/S0377-2217(98)00107-6 |
| [26] | Wu TH, Low C, Bai JW (2002) Heuristic solutions to multi-depot location-routing problems. Comput Oper Res 29:1393–1415 · Zbl 0994.90019 · doi:10.1016/S0305-0548(01)00038-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
