×

A lexicographic optimization approach to the deviation-flow refueling station location problem on a general network. (English) Zbl 1489.90201

Summary: The problem of setting up an Alternative Fuel (AF) refueling infrastructure along traffic networks is gaining more interest as AF powered vehicles are becoming more popular due to environmental and economic reasons. This study addresses the refueling station location problem with allowed deviations on a general network. The primary objective is to maximize the amount of flow covered by a given number of stations. Unlike the common practice of having a predetermined set of candidate station locations that may not necessarily hold an optimal solution, this study considers the characteristics of the traffic network and vehicle driving range to discretize the continuous version of the problem and select a finite set of candidate locations that guarantees optimality. This is done by finding the greatest common divisor, \(g\), of the lengths of all edges in the network and half of the vehicle driving range. We prove that there is always an optimal solution where all refueling stations are located at distances that are integer multiples of \(g\) from network vertices. This result is used to define refueling sets along the network. The endpoints of these sets are then considered as candidate locations. A secondary objective is introduced to minimize the total travel distance of covered flows. This bi-objective approach does not only optimize the utility of available resources by maximizing covered flows, but also improves convenience, lowers travel cost, and reduces greenhouse gas emissions by minimizing the total travel distance. Finally, a numerical example is provided to illustrate the proposed methods.

MSC:

90C35 Programming involving graphs or networks
90B85 Continuous location
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbaas, O.F., and Ventura, J.A.: An edge scanning method for the continuous deviation-flow refueling station location problem on a general network. Networks (2021). doi:10.1002/net.22032
[2] Averbakh, I.; Berman, O., Locating flow-capturing units on a network with multi-counting and diminishing returns to scale, Eur. J. Oper. Res., 91, 3, 495-506 (1996) · Zbl 0924.90100 · doi:10.1016/0377-2217(94)00369-6
[3] Azevedo, I.; Horta, I.; Leal, VM, Analysis of the relationship between local climate change mitigation actions and greenhouse gas emissions—empirical insights, Energy Policy, 111, 204-213 (2017) · doi:10.1016/j.enpol.2017.09.032
[4] Berman, O.; Bertsimas, D.; Larson, RC, Locating discretionary service facilities, II: Maximizing market size, minimizing inconvenience, Oper. Res., 43, 4, 623-632 (1995) · Zbl 0862.90086 · doi:10.1287/opre.43.4.623
[5] Berman, O.; Larson, RC; Fouska, N., Optimal location of discretionary service facilities, Transp. Sci., 26, 3, 201-211 (1992) · Zbl 0762.90044 · doi:10.1287/trsc.26.3.201
[6] Capar, I.; Kuby, M., An efficient formulation of the flow refueling location model for alternative-fuel stations, IIE Trans., 44, 8, 622-636 (2012) · doi:10.1080/0740817X.2011.635175
[7] Gayah, V.; Daganzo, C., Analytical capacity comparison of one-way and two-way signalized street networks, Transp. Res. Rec., 2301, 1, 76-85 (2012) · doi:10.3141/2301-09
[8] Guo, F.; Yang, J.; Lu, J., The battery charging station location problem: impact of users’ range anxiety and distance convenience, Transp. Res. Part E, 114, 1-18 (2018) · doi:10.1016/j.tre.2018.03.014
[9] Hensher, DA, Climate change, enhanced greenhouse gas emissions and passenger transport - What can we do to make a difference?, Transp. Res. Part D, 13, 2, 95-111 (2008) · doi:10.1016/j.trd.2007.12.003
[10] Hodgson, JM, A flow-capturing location-allocation model, Geogr. Anal., 22, 3, 270-279 (1990) · doi:10.1111/j.1538-4632.1990.tb00210.x
[11] Hwang, S.; Kweon, S.; Ventura, J., Infrastructure development for alternative fuel vehicles on a highway road system, Transp. Res. Part E, 77, 170-183 (2015) · doi:10.1016/j.tre.2015.02.011
[12] Johnson, DB, Efficient algorithms for shortest paths in sparse networks, J. ACM, 24, 1, 1-13 (1977) · Zbl 0343.68028 · doi:10.1145/321992.321993
[13] Kim, J-G; Kuby, M., The deviation-flow refueling location model for optimizing a network of refueling stations, Int. J. Hydrogen Energy, 37, 6, 5406-5420 (2012) · doi:10.1016/j.ijhydene.2011.08.108
[14] Kim, J-G; Kuby, M., A network transformation heuristic approach for the deviation flow refueling location model, Comput. Oper. Res., 40, 4, 1122-1131 (2013) · doi:10.1016/j.cor.2012.10.021
[15] Ko, J.; Gim, T-H; Guensler, R., Locating refuelling stations for alternative fuel vehicles: a review on models and applications, Transp. Rev., 37, 5, 551-570 (2017) · doi:10.1080/01441647.2016.1273274
[16] Kuby, M.; Lim, S., The flow-refueling location problem for alternative-fuel vehicles, Socioecon. Plan. Sci., 39, 2, 125-145 (2005) · doi:10.1016/j.seps.2004.03.001
[17] Kuby, M.; Lim, S., Location of alternative-fuel stations using the flow-refueling location model and dispersion of candidate sites on arcs, Netw. Spat. Econ., 7, 2, 129-152 (2007) · Zbl 1144.90443 · doi:10.1007/s11067-006-9003-6
[18] Kweon, SJ; Hwang, SW; Ventura, JA, A continuous deviation-flow location problem for an alternative-fuel refueling station on a tree-like transportation network, J. Adv. Transp., 2017, 1-20 (2017) · doi:10.1155/2017/1705821
[19] Lemke, CE; Salkin, HM; Spielberg, K., Set covering by single-branch enumeration with linear-programming subproblems, Oper. Res., 19, 4, 998-1022 (1971) · Zbl 0232.90033 · doi:10.1287/opre.19.4.998
[20] Mollin, RA, Fundamental Number Theory With Applications (1998), London, United Kingdom: CRC-Press, London, United Kingdom · Zbl 0943.11001
[21] Nicholas, M.; Ogden, J., Detailed analysis of urban station siting for California hydrogen highway network, Transp. Res. Rec., 1983, 1, 121-128 (2006) · doi:10.1177/0361198106198300117
[22] Silvia, C.; Krause, RM, Assessing the impact of policy interventions on the adoption of plug-in electric vehicles: an agent-based model, Energy Policy, 96, 105-118 (2016) · doi:10.1016/j.enpol.2016.05.039
[23] Upchurch, C.; Kuby, M., Comparing the p-median and flow-refueling models for locating alternative-fuel stations, J. Transp. Geogr., 18, 6, 750-758 (2010) · doi:10.1016/j.jtrangeo.2010.06.015
[24] US Environmental Protection Agency (EPA). (2020). Inventory of US greenhouse gas emissions and sinks: 1990-2018. Retrieved from https://www.epa.gov/ghgemissions/inventory-us-greenhouse-gas-emissions-and-sinks-1990-2018
[25] Ventura, JA; Hwang, SW; Kweon, SJ, A continuous network location problem for a single refueling station on a tree, Comput. Oper. Res., 62, 257-265 (2015) · Zbl 1348.90433 · doi:10.1016/j.cor.2014.07.017
[26] Ventura, JA; Kweon, SJ; Hwang, SW; Tormay, M.; Li, C., Energy policy considerations in the design of an alternative-fuel refueling infrastructure to reduce GHG emissions on a transportation network, Energy Policy, 111, 427-439 (2017) · doi:10.1016/j.enpol.2017.09.035
[27] Yeh, S.; Witcover, J.; Lade, GE; Sperling, D., A review of low carbon fuel policies: principles, program status and future directions, Energy Policy, 97, 220-234 (2016) · doi:10.1016/j.enpol.2016.07.029
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.