×

zbMATH — the first resource for mathematics

Multi-facility Green Weber problem. (English) Zbl 07128387
Summary: Locating facilities to satisfy the demands of customers is a strategic decision for a distribution system. In this article, we study the multi-facility green Weber problem (MF-GWP), an extension of the classical multi-facility Weber problem, that considers environmental concerns in a distribution system in the context of a planar facility location problem. In the MF-GWP, the vehicles are sent directly from the facilities to the assigned customers to satisfy their demands. Each customer has a deadline and the vehicles serving the customer must arrive at the location of the customer no later than the deadline. The MF-GWP determines the locations of \(p\) facilities on the plane, \(p > 1\), allocations of customers to the facilities, and the speeds of the distribution vehicles so as to minimize the total amount of \(\mathrm{CO_2}\) emission in the distribution system. We formulate this problem as a mixed integer second order cone programming (MISOCP) problem. This formulation turns out to be weak and therefore only small size instances can be solved to optimality within four hours. For larger size instances, a local search heuristic is proposed and some well-known heuristics developed for the multi-facility Weber problem, namely “location-allocation”, “transfer follow-up”, and “decomposition” are adapted for the MF-GWP. We use second order cone programming (SOCP) and the proposed MISOCP formulation as subproblems within the heuristics. We provide our computational experiments to compare the proposed solution methods in terms of solution quality and time. The results show that within a fixed computational time, even though the location-allocation heuristic is able to make more replications, the improvement heuristics considered, i.e., transfer or transfer followed by decomposition, usually find better solutions while using less number of replications. We also investigate how the total amount of \(\mathrm{CO_2}\) emitted by distribution vehicles changes with respect to the number of facilities located. We argue that in several real life applications from different sectors including aviation and robotics, MF-GWP and its extensions or modifications can be used to reduce the \(\mathrm{CO_2}\) emission or energy consumption. As an illustrative example, we show the applicability of the MF-GWP within an assembly line system, where the stations are fed by dedicated rail-guided vehicles.
MSC:
90B Operations research and management science
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aktürk, M. S.; Atamtürk, A.; Gürel, S., Aircraft rescheduling with cruise speed control, Oper. Res., 62, 4, 829-845 (2014) · Zbl 1302.90054
[2] Alizadeh, F.; Goldfarb, D., Second-order cone programming, Math. Program., 95, 1, 3-51 (2003) · Zbl 1153.90522
[3] Atashi Khoei, A.; Süral, H.; Tural, M. K., Time-dependent green Weber problem, Computers & Operations Research, 88, 316-323 (2017) · Zbl 1391.90394
[4] Barth, M.; Younglove, T.; Scora, G., Development of a Heavy-Duty Diesel Modal Emissions and Fuel Consumption Model, Technical Report (2005), UC Berkeley: California Partners for Advanced Transit and Highways, San Francisco
[5] Bektaş, T.; Laporte, G., The pollution-routing problem, Transp. Res. Part B, 45, 8, 1232-1250 (2011)
[6] Bongartz, I.; Calamai, P. H.; Conn, A. R., A projection method for ℓ_p norm location-allocation problems, Math. Program., 66, 1, 283-312 (1994) · Zbl 0829.90085
[7] Brimberg, J.; Drezner, Z., A new heuristic for solving the p-median problem in the plane, Comput. Oper. Res., 40, 1, 427-437 (2013) · Zbl 1349.90557
[8] Brimberg, J.; Hansen, P.; Mladenović, N.; Salhi, S., A survey of solution methods for the continuous location allocation problem, Int. J. Oper. Res., 5, 1, 1-12 (2008) · Zbl 1153.90487
[9] Brimberg, J.; Hansen, P.; Mladenović, N.; Taillard, E. D., Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem, Oper. Res., 48, 3, 444-460 (2000)
[10] Chen, C.; Qiu, R.; Hu, X., The location-routing problem with full truckloads in low-carbon supply chain network designing, Math. Prob. Eng., 2018, 1-13 (2018)
[11] Cooper, L., Heuristic methods for location-allocation problems, SIAM Rev., 6, 37-53 (1964) · Zbl 0956.90014
[12] de Armas, J.; Ferrer, A.; Juan, A. A.; Lalla-Ruiz, E., Modeling and solving the non-smooth arc routing problem with realistic soft constraints, Expert Syst. Appl., 98, 205-220 (2018)
[13] Demir, E.; Bektaş, T.; Laporte, G., A comparative analysis of several vehicle emission models for road freight transportation, Transp. Res. Part D, 16, 5, 347-357 (2011)
[14] Demir, E.; Bektaş, T.; Laporte, G., An adaptive large neighborhood search heuristic for the pollution-routing problem, Eur. J. Oper. Res., 223, 2, 346-359 (2012) · Zbl 1292.90045
[15] Demir, E.; Bektaş, T.; Laporte, G., The bi-objective pollution-routing problem, Eur. J. Oper. Res., 232, 3, 464-478 (2014) · Zbl 1305.90053
[16] Drezner, Z.; Brimberg, J.; Mladenović, N.; Salhi, S., New heuristic algorithms for solving the planar p-median problem, Comput. Oper. Res., 62, 296-304 (2015) · Zbl 1348.90388
[17] Drezner, Z.; Brimberg, J.; Mladenović, N.; Salhi, S., New local searches for solving the multi-source Weber problem, Ann. Oper. Res., 246, 1, 181-203 (2016) · Zbl 1357.90165
[18] Drezner, Z.; Hamacher, H., Facility Location: Applications and Theory (2002), Springer: Springer Berlin; New York · Zbl 0988.00044
[19] Drezner, Z.; Salhi, S., Incorporating neighborhood reduction for the solution of the planar p-median problem, Ann. Oper. Res., 258, 2, 639-654 (2017) · Zbl 1381.90043
[20] Dukkanci, O.; Bektaş, T.; Kara, B. Y., Chapter 7 - Green network design problems, (Faulin, J.; Grasman, S. E.; Juan, A. A.; Hirsch, P., Sustainable Transportation and Smart Logistics (2019), Elsevier), 169-206
[21] Estrada-Moreno, A.; Savelsbergh, M.; Juan, A. A.; Panadero, J., Biased-randomized iterated local search for a multiperiod vehicle routing problem with price discounts for delivery flexibility, Int. Trans. Oper. Res., 26, 4, 1293-1314 (2019)
[22] Gürel, S.; Gultekin, H.; Akhlaghi, V. E., Energy conscious scheduling of a material handling robot in a manufacturing cell, Rob. Comput.-Integr. Manuf., 58, 97-108 (2019)
[23] Harris, I.; Mumford, C. L.; Naim, M. M., A hybrid multi-objective approach to capacitated facility location with flexible store allocation for green logistics modeling, Trans. Res. Part E, 66, 1-22 (2014)
[24] IBM, 2015. IBM ILOG Cplex Optimization Studio (12.6). http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/, [Online; accessed 13-March-2019].
[25] Kara, İ.; Kara, B. Y.; Yetis, M. K., Energy minimizing vehicle routing problem, Combinatorial Optimization and Applications, 62-71 (2007), Springer: Springer Berlin, Heidelberg · Zbl 1175.90333
[26] Koç, Ç.; Bektaş, T.; Jabali, O.; Laporte, G., The impact of depot location, fleet composition and routing on emissions in city logistics, Trans. Res. Part B, 84, 81-102 (2016)
[27] Kramer, R.; Subramanian, A.; Vidal, T.; dos Anjos F. Cabral, L., A matheuristic approach for the pollution-routing problem, Eur. J. Oper. Res., 243, 2, 523-539 (2015) · Zbl 1346.90143
[28] Lobo, M.; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear Algebra Appl., 284, 193-228 (1998) · Zbl 0946.90050
[29] Lozano, S.; Guerrero, F.; Onieva, L.; Larrañeta, J., Kohonen maps for solving a class of location-allocation problems, Eur. J. Oper. Res., 108, 1, 106-117 (1998) · Zbl 0943.90007
[30] Megiddo, N.; Supowit, K. J., On the complexity of some common geometric location problems, SIAM J. Comput., 13, 1, 182-196 (1984) · Zbl 0534.68032
[31] OR Library, 2018. Multi-source Weber problems. http://mistic.heig-vd.ch/taillard/problemes.dir/location.html, [Online; accessed 13-March-2019].
[32] Piecyk, M.; Browne, M.; Whiteing, A.; McKinnon, A., Green Logistics: Improving the Environmental Sustainability of Logistics (2015), Kogan Page
[33] Sawik, B.; Faulin, J.; Pérez-Bernabeu, E., Multi-criteria optimization for fleet size with environmental aspects, Transp. Res. Procedia, 27, 61-68 (2017)
[34] Sawik, B.; Faulin, J.; Pérez-Bernabeu, E., A multicriteria analysis for the green VRP: a case discussion for the distribution problem of a Spanish retailer, Transp. Res. Procedia, 22, 305-313 (2017)
[35] Senzig, D.; Cumper, J., Fuel Consumption of ADS-B and Non-ADS-B Helicopter Operations in the Gulf of Mexico, Technical Report (2013), John A. Volpe National Transportation Systems Center (U.S.)
[36] The International Transport Forum, Paris, OECD (2010), 2010. Reducing transport greenhouse gas emissions: trends and data. https://www.itf-oecd.org/sites/default/files/docs/10ghgtrends.pdf, [Online; accessed 13-March-2019].
[37] Tokekar, P.; Karnad, N.; Isler, V., Energy-optimal velocity profiles for car-like robots, 2011 IEEE International Conference on Robotics and Automation, 1457-1462 (2011)
[38] Toro, E. M.; Franco, J. F.; Echeverri, M. G.; Guimarães, F. G., A multi-objective model for the green capacitated location-routing problem considering environmental impact, Comput. Ind. Eng., 110, 114-125 (2017)
[39] World Economic Forum, Geneva, 2009. Supply chain decarbonization. http://reports.weforum.org/supply-chain-decarbonization-info/, [Online; accessed 13-March-2019].
[40] Xiao, Y.; Zhao, Q.; Kaku, I.; Xu, Y., Development of a fuel consumption optimization model for the capacitated vehicle routing problem, Comput. Oper. Res., 39, 7, 1419-1431 (2012) · Zbl 1251.90063
[41] Xifeng, T.; Ji, Z.; Peng, X., A multi-objective optimization model for sustainable logistics facility location, Transp. Res. Part D, 22, 45-48 (2013)
[42] Zebrowski, P.; Litus, Y.; Vaughan, R. T., Energy efficient robot rendezvous, Fourth Canadian Conference on Computer and Robot Vision (CRV ’07), 139-148 (2007)
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.