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:
 [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)