Microsoft Word - 8-2474_s Engineering, Technology & Applied Science Research Vol. 9, No. 1, 2019, 3715-3720 3715 www.etasr.com Badri-Koohi et al.: Optimizing Number and Locations of Alternative-Fuel Stations Using … Optimizing Number and Locations of Alternative- Fuel Stations Using a Multi-Criteria Approach Babak Badri-Koohi Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, VA, USA babakbk@vt.edu Reza Tavakkoli-Moghaddam School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran tavakkoli@ut.ac.ir Mahnaz Asghari Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, VA, USA mahnaz@vt.edu Abstract—The transition to alternative fuels is obligatory due to the finite amount of available fossil fuels and their rising prices. However, the transition cannot be done unless enough infrastructure exists. A very important infrastructure is the fueling station. As establishing alternative-fuel stations is expensive, the problem of finding the optimal number and locations of initial alternative-fuel stations emerges and it is investigated in this paper. A mixed-integer linear programming (MILP) formulation is proposed to minimize the costs using net present value (NPV) technique. The proposed formulation considers the criteria of the two most common models in the literature for such a problem, namely P-median model and flow refueling location model (FRLM). A decision support system is developed for the users to be able to control the parameter values and run different scenarios. For case study purposes, the method is used to find the optimal number and locations of the alternative-fuel stations in the city of Chicago. Some data wrangling techniques are used to overcome the inability of the method to solve very large-scale problems. Keywords-continuous location problem; multi-criteria decision making; alternative-fuel stations; mixed-integer linear programming; optimization; Chicago transportation network I. INTRODUCTION Since it is estimated that oil and gas resources will come to an end by the next 200 years, the use of alternative fuels such as hydrogen [1, 2], electricity [3], and natural gas [4] instead of gasoline and diesel is sensible. Hence, there’s a growing interest in vehicles powered by alternative fuels. Research has pointed out the significant impact that constructing refueling stations has on the promotion of alternative fuels [5-9]. Many researchers and industry representatives addressed the which- comes-first issue regarding alternative fuel (alt-fuel) stations and vehicles [10]. In [11] the which-comes-first question involving refueling stations and vehicles is stated to be like the “chicken-and-egg” dilemma. The research asserts that optimizing the location of refueling stations is inevitable to maximize the potential for consumers to use alt-fuel vehicles, especially in the early steps of transition to an alternative fuel. Whether existence of refueling stations leads to the appeal for alternative fuels or vice versa, it is evident that the establishment of fuel stations and the optimization of their location are crucial. Optimization techniques have long been used in supply chain design, logistics, and supply chain planning problems [12-16]. The use of optimization methods for finding optimal locations especially in energy application area has also been investigated in [17-19]. Various mathematical models are specifically proposed in the literature for optimally locating fuel stations. Some have addressed the problem with a p- median model which is a commonly used location-allocation model whose objective is to minimize the total distance traveled from demand nodes to a given number p of facilities by optimally locating the facilities and allocating the demand nodes to them [20, 21]. It has been used in [22-24] to optimally locate alt-fuel stations close to where people live since consumers usually prefer to refuel near their homes, according to empirical studies [3, 25]. The p-median model was first applied to fuel stations in [26] as an objective in a multi- objective programming model for relocating existing gas stations. Authors in [9] developed the “fuel travel-back” approach whose structure is very much like the p-median model. In this approach, however, nodes are weighted by the quantity of fuel consumed on road segments passing through them instead of population. Moreover, travel time between nodes is considered instead of distance. Vehicle-miles traveled (VMT) data is used in this approach for minimizing total travel time for all the fuel (in gallon-minutes) needed to travel from everywhere to the nearest fueling station. The advantage of this approach is that it only needs road network data and population data that are easily accessible in GIS format from a variety of sources. There is another approach that tries to locate fuel stations on high-traffic routes. For example, a second criterion that maximizes traffic flows on the roads that have fuel stations is considered in [26] along with the p-median criterion. A similar approach is proposed in [1] considering only high-traffic roads (with at least 20,000 passing vehicles per day). The logic behind this approach is that drivers usually refuel on their way to somewhere else and do not deviate much from their route to refuel. The criteria considered in [27] are a hybrid of the first two types, maximizing the population on covered links. Corresponding author: Babak Badri-Koohi Engineering, Technology & Applied Science Research Vol. 9, No. 1, 2019, 3715-3720 3716 www.etasr.com Badri-Koohi et al.: Optimizing Number and Locations of Alternative-Fuel Stations Using … However, the same trips by the same drivers are counted more than once in traffic-count or VMT methods if the trip travels multiple links, even if drivers might refuel only once. So, this approach could locate stations on several segments of a high- traffic freeway. Another approach for locating refueling stations was originally named flow-capturing location model [28] and later termed as the flow-intercepting location model (FILM) [29], that maximizes passing traffic flows without counting the traffic multiple times. Since the flows on paths across a network representing the routes people travel are considered as the demand in these models in substitute for population (p- median models) and road traffics (traffic-count models), these models are classified as path-based or flow demand models. Locating facilities in such a way that the number of trips captured or intercepted (i.e. there is a facility anywhere along its path) is maximized is the main criterion in FILM. The FILM is supporting the idea that drivers refuel along their ways to somewhere else rather than making trips for the sole reason of refueling and each flow intercepted is counted only once in the standard FILM, regardless of the number of existing stations in its route. The first problem with FILM is that the model needs a matrix of precise traffic flows from origins to destinations, namely “trip table” data that may not be accessible for all regions and is more complicated than population data. The other problem with this model is that, it considers a path intercepted if it passes by at least one fuel station regardless of the limited driving range of vehicles and the need for multiple times of refueling in longer inter-city trips to complete the path without running out of fuel. Given that electric vehicles and hydrogen-powered vehicles suffer from limited energy storage capabilities, the flow refueling location model (FRLM) was developed [30] to address this critical problem. In the FRLM, a flow is considered refueled or intercepted only if there are stations along the path in such a way that drivers can complete their round trip via the path without running out of fuel, given the limited driving range of their vehicles. The FRLM aims at maximizing the number of trips that can be potentially refueled by a given number of stations and it has been applied to real- world networks in Florida [31] and Arizona [32]. Maximizing trip-miles instead of trips [31], considering stations with limited capacities [11, 33], and considering locations along arcs [34] are some of the extensions to this model. Another advantage of the FRLM is that it also performs better with the p-median model’s objective than the p-median model does with the FRLM’s objective. However, the FRLM has two major problems. First, it locates stations far from people’s homes. Hence, the long distances may cause some people not to have access to any refueling station, thereby not being able to use alt-fuel vehicles. This reduces the robustness of the locations. Next, the model requires the flow data of all origin-destination pairs considering all possible combinations of stations which can capture a route. Thus, the applicability of the model is disputable. Another refueling-station-location model is proposed in [35] based on a set covering mixed-integer programming formulation and vehicle routing concept. The proposed technique only requires a matrix of origin-destination data that is usually very accessible. However, the study suffers from not considering flows of traffic as a crucial factor in its model. Building a true multi-objective model to tradeoff between the flow-refueling and the p-median objectives is proposed as the next logical step to solve the problem in the future work section of many research studies (e.g. [11]). A multi-objective model allows different decision-makers to increase or decrease the weights on these objectives. For example, covering most of the major regions could be more important for governmental decision-makers, while maximizing the profit could be more vital for the decision-makers in the private sector. II. PROBLEM DEFINITION Based on what is mentioned above, a multi-criteria model for locating alt-fuel stations in a region considering the p- median objective while considering traffic flows and construction costs of stations was developed. The model tries to locate stations close to people’s homes and close to the traffic flows at the same time while constructing as fewer stations as possible. In all the models mentioned above, the number of stations is considered determined. But, the question is how this number can be determined. Since constructing alt-fuel stations is very costly, covering as much of the consumers’ demand for fuel as possible while constructing the minimum number of stations possible is essential. Although several studies have independently addressed the general questions of how many refueling stations are needed and where the optimal locations for stations are, the literature has been mostly silent on how to tradeoff between the location of stations and the sufficient number of hydrogen stations. In this research, a multi-criteria mathematical model is formulated to minimize the total costs of constructing stations and the costs of the fuels used for all commutes with the purpose of refueling using the simple NPV (net present value) technique of engineering economics. This formulation can find the optimal locations while optimizing the number of stations. Moreover, candidate sites for stations in the literature are mostly considered discrete. However, it is very difficult to find all the candidate sites over the whole city in a big city like Tehran. Even by finding all candidate sites, we will have many binary variables which can make the problem harder to be solved optimally in a reasonable time. Furthermore, by considering a few of them as candidate sites, the problem of missing some parts of the solution space may occur. Therefore, the solution space for candidate sites is considered continuous in this paper. This makes the problem similar to a continuous location problem (Weber location problem). For taking into account traffic flows in the model, the most common method in the literature is using all origin- destination pairs, but finding all these pairs is very difficult for big cities like Tehran. Also, it is somehow impossible in places where GIS (geographic information system) is not deployed widely. To face the problem, we proposed using flow nodes like population nodes. For example, when there is a route (highway) about 40 kilometers long, it can be divided into two or more nodes with 20 kilometers or less length. Then, some weights proportionate to the traffic flow of the centers of these nodes can be assigned to them. Average daily traffic (ADT) data for cities conveys the same information. Population nodes Engineering, Technology & Applied Science Research Vol. 9, No. 1, 2019, 3715-3720 3717 www.etasr.com Badri-Koohi et al.: Optimizing Number and Locations of Alternative-Fuel Stations Using … can be determined similarly from census block population data. We can ignore population nodes with very low population and flow nodes with very low traffic flows. III. MATHEMATICAL FORMULATION A multi-criteria MILP (mixed-integer linear programming) mathematical formulation is proposed below to solve the problem of finding the optimal number and locations of alt-fuel stations. Some of the characteristics of the problem are listed below: • There can be at most I alt-fuel stations. • There is a set of J nodes for traffic flows determined beforehand. • The flow of each flow node is deterministic. • There is a set of K nodes for population distribution determined beforehand. • Population of each population node is deterministic. • Construction of each station costs C1 dollars. • T equal to 30 years is the time horizon for using newly- constructed stations. • There is an inflation rate equal to 15% for alternative fuels’ prices and depreciation equal to 10% for all costs. • Distance metric is assumed to be rectilinear (1-norm). This norm seems more reasonable than the Euclidean distance function (2-norm) since mostly in a network of streets of a city, there is no direct way from somewhere to somewhere else, but rectilinear way. • Total population TP and total number of cars TC in the region are deterministic. So, the average number of cars per person is TC/TP (TC divided by TP). • Traveling from an origin to a station for refueling requires consumption of some fuel. The cost of the fuel burned per unit of distance C2 is deterministic. • rj is considered as the radius of the identified node j. • The vehicle range is assumed 100km per full refueling. So, each flow will travel for 2*rj kilometers and in each 100km, the vehicle needs refueling, hence 2*rj/100 (2 times rj divided by 100) in the formulation. • Candidate space for stations is considered continuous. • Some weights W1, W2 and W3 are assigned to each objective function in order for the decision-maker to control the policy. Sum of the weights had better be equal to one. A. Notations 1) Indices • i=1,…, I index for stations • j=1,…, J index for flow nodes • k = 1,…, K index for population nodes 2) Parameters • W1, W2, W3 weights for objective functions • C1, C2 costs • fj flow of node j • pk population of node k • TC total number of cars • TP total population • fxj, pxk x-coordinates of flow node j and pop node k • fyj, pyk y-coordinates of flow node j and pop node k • M1, M2 sufficiently large numbers 3) Variables • xi x-coordinate of location of station i • yi y-coordinate of location of station i • fdj distance of flow node j from the nearest station • pdk distance of pop node k from the nearest station • fsij 1, if station i is the closest station to flow node j; 0, otherwise • psij 1, if station i is the closest station to pop node j; 0, otherwise • si 1, if station i is open; 0, otherwise • fxaij absolute horizontal distance of station i and flow node j • pxaij absolute horizontal distance of station i and pop node j • fybij absolute vertical distance of station i and flow node j • pybij absolute vertical distance of station i and pop node j IV. MODEL � ! " = #$%$ ∑ '( + #* + $,$../01 $,$../ 2 %* ∑ 34 + *56 $..24 374 + (1) #8 + $,$../01 $,$../ 2 %* ∑ + 9: 9;2 <= 37== >. ?. 3@A(4 + 3BC(4 ≤ 374 + E1 − 3'(4G�$ ∀ , I (2) <@A(= + =4 The size of population and traffic flow clusters are proportionate to the population and traffic volumes. The results Engineering, Technology & Applied Science Research Vol. 9, No. 1, 2019, 3715-3720 3719 www.etasr.com Badri-Koohi et al.: Optimizing Number and Locations of Alternative-Fuel Stations Using … for maximum number of stations equal to 1, 2, and 3 are shown in Figure 2. If the cost parameter C2 is increased to 300$ and the maximum number of stations is assumed to be 10, the DSS decides to open 10 stations as shown in Figure 3. Fig. 2. Optimal locations for maximum number of stations equal to 1, 2, and 3 from left to right. Fig. 3. Optimal locations for C2=300$ and maximum number of stations equal to 10 VII. CONCLUSIONS A mathematical modeling approach was proposed in this paper for determining the optimal number and locations of alternative-fuel stations. Net present value technique of engineering economics was used in this multi-criteria model. A decision support system using data wrangling techniques was developed in Python based on the proposed approach. The decision support system uses IBM ILOG CPLEX solver to solve the mixed-integer linear programming formulation. The approach is tested on a case study in Chicago City. The results highlight the effectiveness of the approach. They also point out the flexibility of the approach based on the decision makers’ wills. However, this flexibility comes with a price and that price is the high dependency of the results on the parameter values. As a perspective for future work, uncertainties can be considered in the proposed modeling approach to get more robust solutions to the problem. REFERENCES [1] M. Melendez, A. Milbrandt, “Analysis of the hydrogen infrastructure needed to enable commercial introduction of hydrogen-fueled vehicles”, National Hydrogen Association Annual Conference, Washington, DC, USA, March 29 - April 1, 2005 [2] B. Badri-Koohi, H. Shakouri Ganjavi, S. H. Nourbakhsh, “Using urine as a source of energy: Feasibility analysis”, 6th International Green Energy Conference, Eskisehir, Turkey, June 5-11, 2011 [3] D. Sperling, R. Kitamura, “Refueling and new fuels: an exploratory analysis”, Transportation Research Part A: General, Vol. 20, pp. 15-23, 1986 [4] I. Capar, M. Kuby, V. J. Leon, Y.-J. Tsai, “An arc cover--path-cover formulation and strategic analysis of alternative-fuel station locations”, European Journal of Operational Research, Vol. 227, pp. 142-151, 2013 [5] California Environmental Protection Agency, California Hydrogen Blueprint Plan, 2005 [6] N. Huleatt-James, Hydrogen Infrastructure Survey: 2008, 2008 [7] M. W. Melaina, “Initiating hydrogen infrastructures: preliminary analysis of a sufficient number of initial hydrogen stations in the US”, International Journal of Hydrogen Energy, Vol. 28, No. 7, pp. 743-755, 2003 [8] M. Melaina, J. Bremson, “Refueling availability for alternative fuel vehicle markets: sufficient urban station coverage”, Energy Policy, Vol. 36, No. 8, pp. 3233-3241, 2008 [9] Z. Lin, J. Ogden, Y. Fan, C. W. Chen, “The fuel-travel-back approach to hydrogen station siting”, International Journal of Hydrogen Energy, Vol. 33, No. 12, pp. 3096-3101, 2008 [10] M. Melendez, Transitioning to a Hydrogen Future: Learning from the Alternative Fuels Experience, National Renewable Energy Laboratory, 2006 [11] C. Upchurch, M. Kuby, “Comparing the p-median and flow-refueling models for locating alternative-fuel stations”, Journal of Transport Geography, Vol. 18, No. 6, pp. 750-758, 2010 [12] O. Berman, “Deterministic flow-demand location problems”, Journal of the Operational Research Society, Vol. 48, No. 1, pp. 75-81, 1997 [13] B. Badri-Koohi, R. Tavakkoli-Moghaddam, A. Mohamadi, “A Scheduling Problem with a Competitive Situation in Supply Chains”, 4th International Conference of Iranian Operations Research Society, Rasht, Guilan, Iran, May 18-19, 2011 [14] J. Current, S. Ratick, C. ReVelle, “Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach”, European Journal of Operational Research, Vol. 110, No. 3, pp. 597- 609, 1998 [15] A. Mohamadi, R. Tavakkoli-Moghaddam, B. Badri-Koohi, “No-Wait Open Shop Scheduling Problem with Sequence-Dependent Setup Times”, 4th International Conference of Iranian Operations Research Society, Rasht, Guilan, Iran, May 18-19, 2011 [16] M. J. Hodgson, K. E. Rosing, “A network location-allocation model trading off flow capturing andp-median objectives”, Annals of Operations Research, Vol. 40, No. 1, pp. 247-260, 1992 [17] M. S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications, John Wiley & Sons, 2011 [18] M. Asghari, H. Shakouri G., “Carbon Capture, Utilization, and Storage: An Optimization Model”, International Journal of Scientific & Engineering Research, Vol. 5, No. 6, pp. 808-812, 2014 [19] S. Lim, M. Kuby, “Heuristic algorithms for siting alternative-fuel stations using the flow-refueling location model”, European Journal of Operational Research, Vol. 204, No. 1, pp. 51-61, 2010 [20] S. L. Hakimi, “Optimum locations of switching centers and the absolute centers and medians of a graph”, Operations research, Vol. 12, No. 3, pp. 450-459, 1964 [21] C. S. ReVelle, R. W. Swain, “Central facilities location”, Geographical Analysis, Vol. 2, No. 1, pp. 30-42, 1970 [22] M. Nicholas, S. Handy, D. Sperling, “Using geographic information systems to evaluate siting and networks of hydrogen stations”, Engineering, Technology & Applied Science Research Vol. 9, No. 1, 2019, 3715-3720 3720 www.etasr.com Badri-Koohi et al.: Optimizing Number and Locations of Alternative-Fuel Stations Using … Transportation Research Record: Journal of the Transportation Research Board, Vol. 1880, No. 1, pp. 126-134, 2004 [23] M. Nicholas, J. Ogden, “Detailed analysis of urban station siting for California hydrogen highway network”, Transportation Research Record: Journal of the Transportation Research Board, Vol. 1983, pp. 121-128, 2006 [24] D. L. Greene, P. N. Leiby, B. James, J. Perez, M. Melendez, A. Milbrandt, S. Unnash, D. Rutherford, M. Hooks, Analysis of the Transition to Hydrogen Fuel Cell Vehicles and the Potential Hydrogen Energy Infrastructure Requirements, March 2008, Oak Ridge National Lab, Oak Ridge, USA, 2008 [25] R. Kitamura, D. Sperling, “Refueling behavior of automobile drivers”, Transportation Research Part A: General, Vol. 21, No. 3, pp. 235-245, 1987 [26] M. F. Goodchild, V. T. Noronha, “Location-allocation and impulsive shopping: the case of gasoline retailing”, in: Spatial Analysis and Location-Allocation Models, pp. 121-136, Van Nostrand Reinhold, 1987 [27] R. Bapna, L. S. Thakur, S. K. Nair, “Infrastructure development for conversion to environmentally friendly fuel”, European Journal of Operational Research, Vol. 142, No. 3, pp. 480-496, 2002 [28] M. J. Hodgson, “A flow-capturing location-allocation model”, Geographical Analysis, Vol. 22, No. 3, pp. 270-279, 1990 [29] O. Berman, R. C. Larson, N. Fouska, “Optimal location of discretionary service facilities”, Transportation Science, Vol. 26, No. 3, pp. 201-211, 1992 [30] M. Kuby, S. Lim, “The flow-refueling location problem for alternative- fuel vehicles”, Socio-Economic Planning Sciences, Vol. 39, No. 2, pp. 125-145, 2005 [31] M. Kuby, L. Lines, R. Schultz, Z. Xie, J. G. Kim, S. Lim, “Optimization of hydrogen stations in Florida using the flow-refueling location model”, International Journal of Hydrogen Energy, Vol. 34, No. 15, pp. 6045- 6064, 2009 [32] M. J. Kuby, S. Lim, K. Wang, “A model for optimal location of hydrogen refueling stations: a case study of Arizona”, National Hydrogen Association's 15th Annual US Hydrogen Conference, Los Angeles, USA, April 26-30, 2004 [33] C. Upchurch, M. Kuby, S. Lim, “A model for location of capacitated alternative-fuel stations”, Geographical Analysis, Vol. 41, No. 1, pp. 85- 106, 2009 [34] M. Kuby, S. Lim, “Location of alternative-fuel stations using the flow- refueling location model and dispersion of candidate sites on arcs”, Networks and Spatial Economics, Vol. 7, No. 2, pp. 129-152, 2007 [35] Y.-W. Wang, C. C. Lin, “Locating road-vehicle refueling stations”, Transportation Research Part E: Logistics and Transportation Review, Vol. 45, No. 5, pp. 821-829, 2009 [36] B. Badri-Koohi, R. Tavakkoli-Moghaddam, “Determining optimal number and locations of alternative-fuel stations with a multi-criteria approach”, 8th International Industrial Engineering Conference, Tehran, Iran, July 2, 2012 [37] T. H. Tran, G. Nagy, T. B. T. Nguyen, N. A. Wassan, “An efficient heuristic algorithm for the alternative-fuel station location problem”, European Journal of Operational Research, Vol. 269, No. 1, pp. 159- 170, 2018 [38] T. H. Tran, T. B. T. Nguyen, “Alternative-fuel station network design under impact of station failures”, in: Annals of Operations Research, pp. 1-36, Springer, 2018 [39] B. Scheiper, M. Schiffer, G. Walther, “The flow refueling location problem with load flow control”, Omega, Vol. 83, pp. 50-69, 2018 [40] R. M. Post, P. Buijs, M. A. J. Broek, J. A. L. Alvarez, N. B. Szirbik, I. F. A. Vis, “A solution approach for deriving alternative fuel station infrastructure requirements”, Flexible Services and Manufacturing Journal, Vol. 30, No. 3, pp. 592-607, 2018 [41] S. A. MirHassani, R. Ebrazi, “A flexible reformulation of the refueling station location problem”, Transportation Science, Vol. 47, No. 4, pp. 617-628, 2012 [42] M. Miralinaghi, Y. Lou, B. B. Keskin, A. Zarrinmehr, R. Shabanpour, “Refueling station location problem with traffic deviation considering route choice and demand uncertainty”, International Journal of Hydrogen Energy, Vol. 42, No. 5, pp. 3335-3351, 2017 [43] J. Ko, T. H. T. Gim, R. Guensler, “Locating refuelling stations for alternative fuel vehicles: a review on models and applications”, Transport Reviews, Vol. 37, No. 5, pp. 551-570, 2017 [44] J. G. Kim, M. Kuby, “The deviation-flow refueling location model for optimizing a network of refueling stations”, International Journal of Hydrogen Energy, Vol. 37, No. 6, pp. 5406-5420, 2012 [45] Chicago Data Portal, Boundaries-Census Blocks–2010, available at: https://data.cityofchicago.org/Facilities-Geographic-Boundaries/ Boundaries-Census-Blocks-2010/mfzt-js4n [46] Data.gov, Average Daily Traffic Counts, available at: https://catalog.data.gov/dataset/average-daily-traffic-counts-3968f