×

zbMATH — the first resource for mathematics

A math-heuristic for the warehouse location-routing problem in disaster relief. (English) Zbl 1348.90119
Summary: We consider a problem faced by international aid organizations after the occurrence of a natural disaster. A supply system with intermediate warehouses has to be established to provide affected people with relief goods. A three-objective optimization model with a medium-term economic, a short-term economic, and a humanitarian objective function is used. We apply the epsilon constraint method to determine the Pareto frontier. To solve the single-objective constrained optimization problem, we propose an exact solution method as well as a “math-heuristic” technique building on a MILP formulation with a heuristically generated constraint pool. As a subproblem, the multiple-depot, multiple-trip capacitated team orienteering problem is solved. We present a MIP formulation and a VNS procedure for this problem. Synthetically generated instances and a real-world illustration case are used for our computational studies. The results of the math-heuristic technique are compared to those obtained from an application of the NSGA-II metaheuristic and, where possible, to those of the exact solution approach.

MSC:
90B06 Transportation, logistics and supply chain management
90B80 Discrete location and assignment
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming
Software:
ParadisEO-MOEO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Altay, N.; Green, W. G., OR/MS research in disaster operations management, European Journal of Operational Research, 175, 475-493, (2006) · Zbl 1137.90574
[2] Ambrosino, D.; Scutellá, M. G., Distribution network design: new problems and related models, European Journal of Operational Research, 165, 610-624, (2005) · Zbl 1062.90008
[3] Bérubé, J.-F.; Gendreau, M.; Potvin, J.-Y., An exact \(\varepsilon - \operatorname{constraint}\) method for bi-objective combinatorial optimization problems: application to the traveling salesman problem with profits, European Journal of Operational Research, 194, 39-50, (2009) · Zbl 1179.90274
[4] Campbell, A. M.; Vandenbussche, D.; Hermann, W., Routing for relief efforts, Transportation Science, 42, 127-145, (2008)
[5] Chao, I. M.; Golden, B. L.; Wasil, E. A., The team orienteering problem, European Journal of Operational Research, 88, 464-474, (1996) · Zbl 0911.90145
[6] De Angelis, V.; Mecoli, M.; Nikoi, C.; Storchi, G., Multiperiod integrated routing and scheduling of world food programme cargo planes in angola, Computers and Operations Research, 34, 1601-1615, (2007) · Zbl 1159.90401
[7] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 182-197, (2002)
[8] Golden, B. L.; Levy, L.; Vohra, R., The orienteering problem, Naval Research Logistics, 34, 307-318, (2006) · Zbl 0647.90099
[9] Gutjahr, W. J., Two metaheuristics for multiobjective stochastic combinatorial optimization, (Stochastic algorithms: foundations and applications (Proceedings of SAGA 2005). Lecture notes in computer science, vol. 3777, (2005), Springer), 116-125 · Zbl 1159.68641
[10] Gutjahr, W. J., A provably convergent heuristic for stochastic bicriteria integer programming, Journal of Heuristics, 15, 227-258, (2009) · Zbl 1172.90477
[11] Hansen, P.; Hegedahl, B.; Hjortkjaer, S.; Obel, B., A heuristic solution to the warehouse location-routing problem, European Journal of Operational Research, 76, 111-127, (1994) · Zbl 0925.90245
[12] Hansen, P.; Mladenović, N., Variable neighborhood search: principles and applications, European Journal of Operational Research, 130, 449-467, (2001) · Zbl 0981.90063
[13] Jaszkiewicz, A., Evaluation of multiple objective metaheuristics, metaheuristics for multiobjective optimisation, (Lecture notes in economics and mathematical systems, vol. 535, (2004)), 65-89 · Zbl 1140.90488
[14] Jozefowiez, N.; Semet, F.; Talbi, E.-G., The bi-objective covering tour problem, Computers and Operations Research, 34, 1929-1942, (2007) · Zbl 1190.90044
[15] Laumanns, M.; Thiele, L.; Zitzler, E., An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method, European Journal of Operational Research, 169, 932-942, (2006) · Zbl 1079.90122
[16] Liefooghe, A.; Basseur, M.; Jourdan, L.; Talbi, E.-G., Combinatorial optimization of stochastic multi-objective problems: an application to the flow-shop scheduling problem, (Proceedings of the EMO 2007. Lecture notes in computer science, vol. 4403, (2007), Springer), 457-471
[17] Perl, J.; Daskin, M. S., Warehouse location-routing problem, Transportation Research, 19, 381-396, (1985)
[18] Rath S, Doerner KF, Gutjahr WJ. Ware house location routing problem for disaster relief. In: Voss Stefan, Caserta Marco, editors. Proceedings of the eighth metaheuristic international conference (MIC 2009), Hamburg, Germany, 13-16 July 2009
[19] Schott JR. Fault tolerant design using single and multicriteria genetic algorithm optimization. Storming Media; 1995.
[20] While, L.; Hingston, P.; Barone, L.; Huband, S., A faster algorithm for calculating hypervolume, IEEE Transactions on Evolutionary Computation, 10, 29-38, (2006)
[21] Yi, W.; Özdamar, L., A dynamic logistics coordination model for evacuation and support in disaster response activities, European Journal of Operational Research, 179, 1177-1193, (2007) · Zbl 1163.90377
[22] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case studyand the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 3, 257-271, (1999)
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.