Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking.

*(English)*Zbl 1237.90047Summary: The two-echelon location-routing problem (LRP-2E) arises from recent transportation applications like city logistics. In this problem, still seldom studied, first-level trips serve from a main depot a set of satellite depots, which must be located, while second-level trips visit customers from these satellites. After a literature review on the LRP-2E, we present four constructive heuristics and a hybrid metaheuristic: A greedy randomized adaptive search procedure (GRASP) complemented by a learning process (LP) and path relinking (PR). The GRASP and learning process involve three greedy randomized heuristics to generate trial solutions and two variable neighbourhood descent (VND) procedures to improve them. The optional path relinking adds a memory mechanism by combining intensification strategy and post-optimization. Numerical tests show that the GRASP with LP and PR outperforms the simple heuristics and an adaptation of a matheuristic initially published for a particular case, the capacitated location-routing problem (CLRP). Additional tests on the CLRP indicate that the best GRASP competes with the best metaheuristics published.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90B80 | Discrete location and assignment |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

two-echelon location-routing problem; vehicle routing; facility location; GRASP; learning process; path relinking##### Software:

Tabu search
PDF
BibTeX
XML
Cite

\textit{V.-P. Nguyen} et al., Eur. J. Oper. Res. 216, No. 1, 113--126 (2012; Zbl 1237.90047)

Full Text:
DOI

##### References:

[1] | Angelelli, E.; Speranza, M.G., The periodic vehicle routing problem with intermediate facilities, European journal of operational research, 137, 233-247, (2002) · Zbl 0998.90021 |

[2] | Bard, J.F.; Huang, L.; Dror, M.; Jaillet, P., A branch and cut algorithm for the VRP with satellite facilities, IIE transactions, 30, 821-834, (1998) |

[3] | Belenguer, J.M.; Benavent, E.; Prins, C.; Prodhon, C.; Wolfler Calvo, R., A branch-and-cut method for the capacitated location-routing problem, Computers and operations research, 38, 931-941, (2011) · Zbl 1205.90172 |

[4] | Clarke, G.; Wright, J.W., Scheduling of vehicles from a central depot to a number of delivery points, Operations research, 12, 568-581, (1964) |

[5] | C. Contardo, J.F. Cordeau, B. Gendron, A branch-and-cut algorithm for the capacitated location-routing problem, in: Proceedings of the VI ALIO/EURO Workshop on Applied Combinatorial Optimization, Buenos Aires, Argentina, 2008. · Zbl 1356.90070 |

[6] | Crainic, T.G.; Ricciardi, N.; Storchi, G., Advanced freight transportation systems for congested urban areas, Transportation research part C, 12, 119-137, (2004) |

[7] | T.G. Crainic, N. Ricciardi, G. Storchi, Models for evaluating and planning city logistic transportation systems, Technical report, in: CIRRELT-2007-65, CIRRELT, Montreal, Canada, 2007. |

[8] | T.G. Crainic, S. Mancini, G. Perboli, R. Tadei, Lower bounds for the two-echelon capacitated vehicle routing problem, in: EU/MEeting, Annual Conference of the EURO Working Group on Metaheuristics, Troyes, France, July 23-24, 2008. |

[9] | Crainic, T.G.; Mancini, S.; Perboli, G.; Tadei, R., Two-echelon vehicle routing problem: A satellite location analysis, Procedia-social and behavioral sciences, 2, 5944-5955, (2010) |

[10] | Crevier, B.; Cordeau, J.-F.; Laporte, G., The multi-depot vehicle routing problem with inter-depot routes, European journal of operational research, 176, 756-773, (2007) · Zbl 1103.90032 |

[11] | Duhamel, C.; Lacomme, P.; Prins, C.; Prodhon, C., A GRASP × ELS approach for the capacitated location-routing problem, Computers and operations research, 37, 1912-1923, (2010) · Zbl 1188.90026 |

[12] | Gendron, B.; Semet, F., Formulations and relaxations of a multi-echelon capacitated location-distribution problem, Computers and operations research, 36, 1335-1355, (2009) · Zbl 1177.90247 |

[13] | J. Gonzalez-Feliu, Models and methods for the city logistics – the two-echelon capacitated vehicle routing problem. Ph.D. Thesis, Politecnico di Torino, Italy, 2008. |

[14] | J. Gonzalez-Feliu, The multi-echelon location-routing problem: Concepts and methods for tactical and operational planning, Technical report, Laboratoire d’Economie des Transports, Lyon, Franc, 2010. |

[15] | Feo, T.A.; Resende, M.G.C., A probabilistic heuristic for a computationally difficult set covering problem, Operations research letters, 8, 67-71, (1989) · Zbl 0675.90073 |

[16] | Glover, F.; Laguna, M., Tabu search, (), 70-150 |

[17] | Hansen, P.; Mladenović, N., Variable neighborhood search: principles and applications, European journal of operational research, 130, 449-467, (2001) · Zbl 0981.90063 |

[18] | Jacobsen, S.K.; Madsen, O.B.G., A comparative study of heuristics for a two-level routing-location problem, European journal of operational research, 5, 378-387, (1980) · Zbl 0441.90028 |

[19] | Jordan, W.C.; Burns, L.D., Truck backhauling on two terminal networks, Transportation research, 18B, 487-503, (1984) |

[20] | Kaufman, L.; Ecde, M.V.; Hansen, P., A plant and warehouse location problem, Operational research quarterly, 28, 547-554, (1977) · Zbl 0375.90074 |

[21] | Laporte, G.; Nobert, Y.; Arpin, D., An exact algorithm for solving a capacitated location-routing problem, Annals of operations research, 6, 293-310, (1986) |

[22] | J. Li, C. Prins, F. Chu, F A scatter search for a multi-type transhipment point location problem with multicommodity flow, Journal of Intelligent Manufacturing. doi:10.1007/s10845-010-0403-6. |

[23] | Madsen, O.B.G., Methods for solving combined two level location-routing problems of realistic dimensions, European journal of operational research, 12, 295-301, (1984) |

[24] | Mole, R.H.; Jameson, S.R., A sequential route-building algorithm employing a generalized savings criterion, Operational research quaterly, 27, 503-511, (1976) |

[25] | Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers and operations research, 31, 1985-2002, (2004) · Zbl 1100.90504 |

[26] | Prins, C.; Prodhon, C.; Wolfler Calvo, 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, 4, 221-238, (2006) · Zbl 1125.90316 |

[27] | Prins, C.; Prodhon, C.; Wolfler Calvo, R., A memetic algorithm with population management (MA∣PM) for the capacitated location-routing problem, (), 183-194 · Zbl 06858826 |

[28] | Prins, C.; Prodhon, C.; Soriano, P.; Ruiz, A.; Wolfler Calvo, R., Solving the capacitated location routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic, Transportation science, 41, 470-483, (2007) |

[29] | Ro, H.; Tcha, D., A branch and bound algorithm for the two-level uncapacited facility location problem with some side constraints, European journal of operational research, 18, 349-358, (1984) · Zbl 0555.90036 |

[30] | Scheuerer, S., A tabu search heuristic for the truck and trailer routing problem, Computers and operations research, 33, 894-909, (2006) · Zbl 1079.90116 |

[31] | Semet, F.; Taillard, E., Solving real-life vehicle routing problems efficiently using tabu search, Annals of operations research, 41, 469-488, (1993) · Zbl 0775.90156 |

[32] | Sheskin, J., Handbook of parametric and non-parametric statistical procedures, (2000), Chapman & Hall/CRC · Zbl 0955.62003 |

[33] | Taniguchi, E.; Thompson, R.G., Modelling city logistics, Transportation research record, 1790, 45-51, (2002) |

[34] | Tragantalerngsak, S.; Holt, J.; Ronnqvist, M., Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem, European journal of operational research, 102, 611-625, (1997) · Zbl 0951.90561 |

[35] | Villegas, J.G.; Prins, C.; Prodhon, C.; Medaglia, A.L.; Velasco, N., GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots, Engineering applications of artificial intelligence, 23, 780-794, (2011) |

[36] | Villegas, J.G.; Prins, C.; Prodhon, C.; Medaglia, A.L.; Velasco, N., GRASP/VNS with (evolutionary) path relinking for the truck and trailer routing problem, Computers and operations research, 38, 1319-1334, (2011) · Zbl 1208.90024 |

[37] | J.G. Villegas, J.M. Belenguer, E. Benavent, C. Prins, C. Prodhon, A cutting plane approach for the single truck and trailer routing problem with satellite depots, in: XXIV European Conference on Operational Research, Lisbon, Portugal, 2011. |

[38] | Wu, T.H.; Low, C.; Bai, J.W., Heuristic solutions to multi-depot location-routing problems, Computers and operations research, 29, 1393-1415, (2002) · Zbl 0994.90019 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.