×

zbMATH — the first resource for mathematics

Time-dependent green Weber problem. (English) Zbl 1391.90394
Summary: We consider an extension of the classical Weber problem, named as the green Weber problem (GWP), in which the customers have one-sided time windows. The GWP decides on the location of the single facility in the plane and the speeds of the vehicles serving the customers from the facility within the one-sided time windows so as to minimize the total amount of carbon dioxide emitted in the whole distribution system. We also introduce time-dependent congestion which limits the vehicle speeds in different time periods and refer to the resulting problem as to the time-dependent green Weber problem (TD-GWP). In the TD-GWP, the vehicles are allowed to wait during more congested time periods. We formulate the GWP and TD-GWP as second order cone programming problems both of which can be efficiently solved to optimality. We show that if the traffic congestion is non-increasing, then there exists an optimal solution in which the vehicles do not wait at all. Computational results are provided comparing the locations of the facility and the resulting carbon dioxide emissions of the classical Weber problem with those of the GWP and comparing the GWP with the TD-GWP in terms of carbon dioxide emissions in different traffic congestion patterns.

MSC:
90B85 Continuous location
90B06 Transportation, logistics and supply chain management
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
90B20 Traffic problems in operations research
90C25 Convex programming
91B76 Environmental economics (natural resource models, harvesting, pollution, etc.)
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agarwal, K. P.; Sharir, M.; Welzl, E., The discrete 2-center problem, Discrete Comput. Geom., 20, 3, 287-305, (1998) · Zbl 0910.68215
[2] Alizadeh, F.; Goldfarb, D., Second-order cone programming, Math. Program., 95, 1, 3-51, (2003) · Zbl 1153.90522
[3] 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
[4] Bektaş, T.; Laporte, G., The pollution-routing problem, Transp. Res. Part B, 45, 8, 1232-1250, (2011)
[5] Chandrasekaran, R.; Tamir, A., Open questions concerning weiszfeld’s algorithm for the Fermat-Weber location problem, Math. Program., 44, 1, 293-295, (1989) · Zbl 0683.90026
[6] 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)
[7] 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
[8] Demir, E.; Bektaş, T.; Laporte, G., The bi-objective pollution-routing problem, Eur. J. Oper. Res., 232, 3, 464-478, (2014) · Zbl 1305.90053
[9] Demir, E.; Bektaş, T.; Laporte, G., A review of recent research on Green road freight transportation, Eur. J. Oper. Res., 237, 3, 775-793, (2014) · Zbl 1338.90004
[10] Drezner, Z., Locational decisions, (1992), Baltzer Basel
[11] Drezner, Z.; Hamacher, H., Facility location: applications and theory, (2002), Springer Berlin; New York · Zbl 0988.00044
[12] Figliozzi, M. A., The impacts of congestion on time-definitive urban freight distribution networks CO_2 emission levels: results from a case study in Portland, oregon, Transp. Res. Part C, 19, 5, 766-778, (2011)
[13] IBM,. IBM ILOG Cplex Optimization Studio (12.6). Visited on 2016-06-13.
[14] Katz, I. N., Local convergence in fermat’s problem, Math. Program., 6, 1, 89-104, (1974) · Zbl 0291.90069
[15] 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
[16] Kuhn, H. W., A note on fermat’s problem, Math. Program., 4, 1, 98-107, (1973) · Zbl 0255.90063
[17] Lobo, M.; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear Algebra Appl., 284, 193-228, (1998) · Zbl 0946.90050
[18] The Population Division of the Department of Economic and Social Affairs of the United Nations,. World urbanization prospects: 2014 revision. Available at http://esa.un.org/unpd/wup/, accessed: March 1st, 2016.
[19] Urquhart, N.; Hart, E.; Scott, C., Building low CO_2 solutions to the vehicle routing problem with time windows using an evolutionary algorithm, Evolutionary Computation (CEC), 2010 IEEE Congress on, 1-6, (2010)
[20] Urquhart, N.; Scott, C.; Hart, E., Applications of evolutionary computation: evoapplications 2010: evocomnet, evoenvironment, evofin, evomusart, and evotranslog, Istanbul, Turkey, April 7-9, 2010, Proceedings, part II, using an evolutionary algorithm to discover low CO_2 tours within a travelling salesman problem, 421-430, (2010), Springer Berlin Heidelberg Berlin, Heidelberg
[21] Vardi, Y.; Zhang, C.-H., A modified weiszfeld algorithm for the Fermat-Weber location problem, Math. Program., 90, 3, 559-566, (2001) · Zbl 0990.65064
[22] Weiszfeld, E.; Plastria, F., On the point for which the sum of the distances to n given points is minimum, Ann. Oper. Res., 167, 1, 7-41, (2009) · Zbl 1176.90616
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.