1 Introduction

Environmental and social concerns about the use of fossil fuel in the transportation sector have generated a keen interest in the development of alternative transportation fuels, such as liquefied natural/bio gas and hydrogen. A broad adoption of alternative fuels would significantly reduce the environmental impact of the transportation sector and decrease the world’s dependence on fossil fuels. Realizing these advantages requires a well-established and efficient infrastructure that enables a broadly available alternative fuel at low distribution cost. When introducing a new fuel, however, the infrastructure through which that fuel is made available to its potential users is typically underdeveloped—due to the need for new facilities with highly specialized equipment.

In the early market phases of an alternative fuel, infrastructure developers and potential users of the fuel often face the so-called “chicken and egg problem”. Infrastructure developers do not yet invest in the required infrastructure because there is a limited and highly volatile demand for the alternative fuel. Potential users are unlikely to adopt an alternative fuel when the infrastructure is not yet sufficiently developed. A lack of alternative fuel stations (AFS) imposes detours for refueling, which leads to higher fuel costs. Moreover, it causes “range anxiety”, i.e., the fear that a vehicle has insufficient range to reach its destinations, which considerably reduces acceptance of the alternative fuel (Dong et al. 2014).

Too much infrastructural development, on the other hand, results in high construction costs, which drive the distribution costs of the alternative fuel—and eventually its market price. Hence, it is important to determine a minimum required infrastructure to enable a rapid adoption of a new fuel in the transportation sector. In this study, we aim to design an approach to derive such minimum infrastructure requirements in terms of the number of AFS.

Thus far, academic literature has addressed a specific set of the challenges outlined above. Kuby and Lim (2005) and Upchurch et al. (2009) have proposed models that seek to find the best locations for a given number of AFS so as to maximize the coverage of a known demand for the alternative fuel or to minimize the investment necessary. In these papers, no methods are provided to determine the required number of AFS. MirHassani and Ebrazi (2013) study the problem of determining an optimal number of AFS and their location by minimizing the construction costs to cover the entire demand for the alternative fuel. Yang and Sun (2015) combine such facility location decisions with the construction of vehicle routes to serve a given set of customers in the context of battery swap stations for electric vehicles. Neither of these papers consider a growing and unpredictable demand for the alternative fuel.

In reality, demand is typically very limited when an alternative fuel is introduced while future demand is difficult to predict and may depend on the number and locations of yet to be established AFS. The level of demand for an alternative fuel is the result of transportation service providers deciding to adopt vehicles that operate on that fuel—the so-called alternative fuel vehicles (AFV). An important aspect of that decision is a fuel cost comparison between AFV and vehicles that operate on conventional fuel. The fuel cost per unit of distance travelled with an AFV may well be lower than for conventional vehicles due to for example tax incentives. However, if the routes that an AFV can make to serve a set of customers requires large detours for refueling that cost advantage may diminish. The environmental benefits associated with AFV follow a similar rational. An increase in route length for the AFV, compared to conventional vehicles, may quickly diminish the pollutant emissions and greenhouse gas reductions associated with the alternative fuel.

An additional challenge of estimating the economic and/or environmental impact of AFV is that customer demand is highly unpredictable. That is, over the lifespan of a vehicle, both the number and location of customers to be served by the transportation service providers may vary strongly. Accordingly, Davis and Figliozzi (2013), Figliozzi (2009) and Jabali et al. (2012) use continuous approximations, based on the average distribution of customer locations, to estimate the total length of the vehicle routes. In comparing the operating cost of electric vehicles with conventional vehicles, Davis and Figliozzi (2013) approximate the total route length only once, i.e., they assume the route length for electric and conventional vehicles to be the same. In reality, AFV often require a detour for refueling as long as the alternative refueling infrastructure is not yet fully developed. In those cases, AFV will take longer routes for serving the same set of customers than the conventional vehicles. It is important to take this difference into account when calculating operational costs for AFV—especially during the early stages of infrastructure development.

Another stream of academic literature focuses on methods for solving green vehicle routing problems (G-VRP), which address environmental objectives and consider some of the difficulties faced by transportation service providers that operate a fleet of AFV (Lin et al. 2014). Those difficulties mainly arise from the shorter driving ranges of AFV in conjunction with a limited number of AFS (Erdogan and Miller-Hooks 2012; Juan et al. 2014; Montoya et al. 2016). Hence, G-VRP solution methods seek to efficiently incorporate stops at AFS to avoid the risk of running out of fuel. Recently, the G-VRP has been extended with time-window and capacity constraints (Schneider et al. 2014) and partial refueling/recharging (Desaulniers et al. 2016; Felipe et al. 2014).

In this paper, we propose a new solution approach that can be used to derive minimum infrastructure requirements in early market phases of an alternative fuel. Those market phases are characterized by a growing infrastructure and highly unpredictable customer demand. Our premise is that, while the use of alternative fuels will likely result in lower emissions (e.g., greenhouse gas, NOx, SOx and particles) and reduced fuel costs per unit of distance travelled, it will also result in longer routes for AFV as long as the alternative fuel station infrastructure is underdeveloped. Hence, the adoption of AFV can only be more cost-effective or environmentally friendly up to a certain increase in route length.

Our study extends prior research by designing an iterative simulation-based approach that supports infrastructure development decisions for alternative fuels, while considering the differences in route length of AFV and conventional vehicles in detail. Moreover, it takes into account the unpredictable customer demand and a gradually maturing refueling infrastructure. Rather than to focus on finding optimal locations for the AFS, we are interested in the minimum number of AFS required to render the adoption of AFV economically and/or environmentally beneficial.

The paper is organized as follows. Section 2 describes the problem that is addressed by our solution approach. The approach is presented in Sect. 3. In Sect. 4 we apply our approach to the case of introducing liquefied natural gas (LNG) as a transportation fuel in the Netherlands and show how it can be used to determine the minimum number of LNG fuel stations required to realize the potential environmental benefits of that fuel. The results of this study are presented in Sect. 5. In Sect. 6, we conclude the paper and discuss opportunities for future research.

2 Problem description

The problem addressed in this paper concerns finding the minimum alternative refueling infrastructure needed to efficiently perform a set of vehicle routes, each of which starts at the depot, visits a set of customers and AFS, and returns to the depot without exceeding the driving range of the AFV. Due to the shorter driving ranges of AFV and a limited alternative refueling infrastructure, AFV usually require detours for refueling. The increase in route length associated with those detours is a function of the alternative refueling infrastructure maturity—where a larger number of AFS would generally result in shorter detours. Therefore, our problem seeks to find the number of AFS from which the increase in total route length required to serve a set of customers with a fleet of AFV—compared to conventional vehicles—becomes lower than an economic and/or environmental threshold value. This requires computing the differences in total route length associated with serving a set of customers at different maturity levels of the alternative refueling infrastructure.

We consider a transportation service provider with a homogenous fleet of uncapacitated vehicles that travel with constant speed v. The transportation service provider operates a service area represented by a square with a given size p, containing a set U with AFS that can be used to refuel AFV when needed and a set C with customers that need to be visited. Each customer must be visited exactly once and a known handling time h is incurred at each customer visit. Vehicle routes cannot violate maximum route duration τ and fuel tank capacity limitations reduce the driving range t of the vehicles, i.e., their range without refueling. We assume conventional vehicles have no such driving range constraints—an assumption that reflects the highly mature infrastructure for conventional fuels and the much larger fuel tank capacity of conventional vehicles. Vehicles can visit an unlimited number of AFS where, during a known refueling time f, the vehicle’s fuel tank is always refueled to its maximum capacity. Due to the high investment cost associated with opening an AFS, most transportation service providers rely on the public alternative refueling infrastructure. Accordingly, we assume that refueling at the depot is not possible. Hence, vehicles should return to the depot with a fuel level α that at least allows reaching an AFS from the start of its next route.

In this paper, we address the situation in which a transportation service provider considers investing in a fleet of AFV, while at the same, infrastructure developers make decisions about the number and locations of AFS. The market for transportation service providers is highly competitive and customer contracts are therefore typically short-term (i.e., up to 1 year), whereas the economic lifetime an AFV is mid-term (i.e., around 5 years). Alternative refueling infrastructure investment decisions are long-term (i.e., around 10–15 years) and the number and locations of AFS will depend how the demand for the alternative fuel develops. Overall, both the locations of the AFS and the customers that will be served with the AFV are largely unknown at the time a transportation service provider decides whether to invest in AFV.

We evaluate several scenarios—that differ in service area size, driving range of AFV, and infrastructure maturity—to address the abovementioned uncertainties and to consider the impact of the alternative refueling infrastructure maturity for different types of transportation service providers. The number of AFS in the service area reflects the maturity of the alternative refueling infrastructure. The exact locations of these AFS in the service area (u x, u y) are assumed to be uncertain and are, therefore, drawn from a probability distribution k. Similarly, we assume that the exact locations of customers in the service area (c x, c y) are uncertain and, therefore, draw those locations from a probability distribution k as well. The number of customers served by a transportation service provider is assumed to be constant. To summarize, Table 1 presents an overview of the variables and parameters addressed in our problem.

Table 1 An overview of the variables and parameters addressed in our problem
Full size table

3 Solution approach

We developed a new solution approach that can cope with a growing alternative refueling infrastructure and uncertain customer and AFS locations. The outcome of this solution approach provides an overview of the increase in the expected total route length of AFV, compared to conventional vehicles, for different scenarios in terms of the AFS infrastructure maturity |U|, service areas size p, and driving range t.

We generate multiple instances to represent the uncertain customer and AFS locations for a transportation service provider. Specifically, an instance of a transportation service provider j consists of the locations of the depot, customers (c x, c y) ∊ C, and AFS (u x, u y) ∊ U, as visualized in Fig. 1. Different instances are considered within a single scenario, i.e., with different values for (c x, c y) and (u x, u y) drawn from probability distribution k, but using the same values for p, |U|, and j. Without loss of generality, we assume the depot is always located in the center of the service area.

Fig. 1
figure 1

Visualization of an instance representing a service area

Full size image

Figure 2 depicts the logic flow diagram to evaluate a scenario. It shows how the solution approach repeatedly calls the method used to solve the G-VRP. In principle, any exact or heuristic method suitable for solving the G-VRP can be implemented in our solution approach. In this paper, we apply the G-VRP heuristic developed by Montoya et al. (2016) to construct vehicle routes. In contrast to the heuristic proposed in Montoya et al. (2016), we consider a setting where a transportation service provider has not invested in an alternative fuel installation on-site of its depot—and hence has to rely fully upon the public alternative refueling infrastructure. Consequently, an AFV does not start its route with a full fuel tank and cannot return with an (almost) empty tank. Indeed, the remaining fuel level not only needs to enable an AFV to return to the depot, but should also suffice to efficiently visit an AFS from the start of its next route.

Fig. 2
figure 2

Logic flow diagram for solving a scenario

Full size image

Considering multiple instances, the outcome of each scenario is a value for the expected total route length required to visit all customers in the service area—taking into account the uncertain customer and AFS locations. The expected value is derived by computing the mean value of the minimum total route length for all instances of the scenario. This mean value converges due to the independent and identically distributed input for the customer and AFS locations in each instance. Hence, we can estimate the mean using the confidence interval method (Law 2014). Our approach creates a new instance as long as the estimated relative error from the real mean (ε) is larger than 2%, with a 95% confidence interval. This serves as a stopping rule that determines when the scenario is solved.

Figure 3 shows how our solution approach systematically creates new scenarios for the above-described process. As initialization, the size of the service area p and infrastructure maturity |U| are set to their pre-defined minimum values, p min and |U| min . Then, a base scenario is created by computing the total route length for conventional vehicles in that scenarioFootnote 1 per the logic described in Fig. 2. The resulting route length is defined as the conventional vehicle setting, to which the different AFV settings will be compared. Subsequently, the value of driving range t is set to its pre-defined minimum value t min to solve the first AFV scenario.

Fig. 3
figure 3

Logic flow diagram of the overall solution approach

Full size image

To create the next scenarios, the value of the infrastructure maturity |U| is increased with step size step U . This infrastructure maturity loop is continued until the difference \( \Delta \) between the outcome of a scenario and the prior scenario is smaller than 1%. At that point, increasing the infrastructure maturity level is considered to no longer considerably affect the expected route length. After this, the driving range loop starts, where the driving range t is increased with step size step t until the pre-defined maximum value t max is reached. Then, the service area loop iteratively increases the size of the service area p with step size step p until its pre-defined maximum value p max is reached. Note that increasing the service area also influences the conventional fuel setting.

The outcome of the overall solution approach is a collection of values for R(p, |U|, t) that represent the expected total route length for each service area size, infrastructure maturity, and driving range considered. Together with additional case specific data such as the costs and emissions of AFV and traditional vehicles, these values can be used to evaluate for which AFS infrastructure maturity the expected total route length becomes economically and/or environmentally beneficial.

4 The case of introducing LNG in the Netherlands

In this section, we apply our solution approach to the introduction of liquefied natural gas (LNG) as a transportation fuel in the Netherlands. Generally, LNG trucks involve higher initial investments, compared to conventional diesel trucks, but can reduce the fuel cost—albeit the latter is highly dependent on the rather volatile price spread between diesel and LNG. From an economic point of view, the need to limit detours for refueling is evident. Any increase in route length for LNG trucks, compared to diesel trucks, quickly diminishes the per kilometer cost advantage of LNG as a fuel.

On top of possible cost savings, the reduction of pollutant emissions and greenhouse gasses are important drivers for investing in LNG fueled transportation. Pollutant emissions include NOx, SOx and particle matter. These pollutants are emitted only when the vehicle is in use—that is, the so-called tank-to-wheel emissions. LNG trucks emit almost no particle matter and significantly less NOx, compared to diesel (Verbeek and Verbeek, 2015). For greenhouse gas emissions, such as CO2 and methane, the emissions in earlier phases of the energy chain—that is, the so-called well-to-tank emissions—are relevant too. Considering only the tank-to-wheel greenhouse gas emissions, LNG can yield a 23% reduction compared to diesel (Withers et al. 2014). When considering the well-to-tank emissions as well (i.e., including the total life cycle of imported LNG), greenhouse gas emissions can be reduced between 5 and 20% (Graham et al. 2008; Arteconi et al. 2010; Ou and Zhang 2013). The comprehensive study of Arteconi et al. (2010) indicates a 10% emission reduction for heavy vehicle road-freight transportation in Europe, which is similar to our case. Accordingly, we assume that the use of LNG as a transportation fuel enables a 10% emission reduction per unit distance travelled.

By applying our solution approach, we can derive insight in the minimum required LNG fuel station infrastructure to render the adoption of LNG trucks economically and environmentally beneficial. When we consider the potential detours needed for refueling in early market phases of an alternative fuel, a 10% emission reduction per unit distance travelled implies that the increase in route length to serve a set of customers with an LNG truck cannot be larger than 10% in order to obtain lower greenhouse gas emissions. Since 10% is also a reasonable estimate of the cost difference between LNG and diesel, we use a 10% increase in route length as threshold value in the remainder of this paper.

Table 2 shows the parameter values used for the experiments in this case. These values are obtained from interviews with three Dutch transportation service providers that already perform distribution operations with LNG trucks or considered to start doing so in the near-future. Thus, the parameter values closely reflect the real-world introduction of LNG as a transportation fuel in the Netherland. The interviews were conducted in 2014.

Table 2 Specific parameter values and ranges for LNG case in the Netherlands
Full size table

In order to consider different types of transportation service providers in the Netherlands, we vary the size of the service area from 50 by 50 km up to 300 by 300 km with a step size of 50 km. The vast majority of freight movements in the Netherlands travel a distance under 300 km and are thus considered in our largest service area size. The number of customers located in the service area is kept constant at 50. To address the uncertain customer locations, their x and y coordinates are drawn from a uniform distribution. We start with an LNG fuel station infrastructure maturity of one station and iteratively increase the number of LNG fuel stations with one until the difference between the outcome of a scenario and the prior scenario is smaller than 1%. The x and y coordinates of each LNG fuel station are drawn from a uniform distribution. We vary the driving ranges of LNG trucks from 600 to 1200 km with a step size of 200 km—where a range of 600 and 1200 is typical for LNG trucks with one and two fuel tanks, respectively. According to the analysis of Kuby and Lim (2005), we have set the minimum returning fuel level at half the driving range.

We implemented our solution method in C++ and ran the experiments on 2.5 GHz Intel Xeon E5 2680v3 CPU. Computational times for one instance range from seconds to an hour for the above-mentioned parameter values. For each scenario, the number of instances required per the stopping rule can go up to 20. Overall, the expected total route length was obtained for 448 scenarios.

5 Results

In this section, we present the results from applying our solution approach to the LNG case described in the previous section. We use our solution approach to determine the LNG infrastructure maturity level upon which a further increase in the number of LNG stations does not significantly reduce the total route length anymore. The outcomes of the solution approach are presented in 3D-plots to provide insight in the relation between the LNG fuel station infrastructure maturity, the driving range of LNG trucks and the size of the service area. The colors used in Figs. 4–6 illustrate the threshold value of 10% from which operating LNG trucks becomes economically and environmentally beneficial, i.e., corresponding to the green area.

Fig. 4
figure 4

Increase in total route length to serve 50 customers in a 200 by 200 km service area for different LNG truck driving ranges and AFS infrastructure maturity levels

Full size image

Figure 4 provides insight in the relation between the LNG fuel station infrastructure maturity and driving ranges of LNG trucks. For this plot, we have fixed the size of the service area at 200 by 200 km with 50 customers. Figure 4 indicates that shorter-range LNG trucks (i.e., with smaller fuel tanks) are more sensitive to the maturity of the LNG fuel station infrastructure than longer-range LNG trucks. More generally, Fig. 4 shows that when the number of LNG fuel stations is increased linearly, the increase in total route length decreases exponentially. This decrease displays asymptotic behavior: at some point, the decrease in total route length becomes negligibly small when the number of LNG fuel stations is further increased. This confirms our expectation that a minimum LNG fuel station infrastructure exists.

Figure 5 provides insight in the relation between the size of the service area and the LNG fuel station infrastructure maturity, for LNG trucks with a range of 600 km. Figure 6 displays the same relation for LNG trucks with a range of 1200 km. Figure 5 clearly shows that, for trucks with a range of 600 km, increases in the size of the service area require a considerably more matured infrastructure in terms of the number of LNG fuel stations. In all settings, no noticeable improvement in route length appears from 12 LNG fuel stations, which is an indication for the minimum required AFS infrastructure.

Fig. 5
figure 5

Increase in total route length to serve 50 customers with an LNG truck with a range of 600 km in service areas with different size and different LNG fuel station maturity levels

Full size image
Fig. 6
figure 6

Increase in total route length to serve 50 customers with an LNG truck with a range of 1200 km in service areas with different size and different LNG fuel station maturity levels

Full size image

Similar to the shorter-range LNG trucks, Fig. 6 indicates a minimum required LNG fuel station infrastructure maturity of 12 stations. Compared to the shorter-range trucks, the environmental and economic benefits of longer-range LNG trucks appear to be less sensitive to an increase of the service area size. Environmental and economic benefits can already be expected from an infrastructure with five LNG fuel stations, regardless of the service area size. For shorter-range LNG trucks operated on large service areas, such benefits emerge at 12 LNG fuel stations. Interestingly, there were three public LNG fuel stations in the Netherlands—and only a handful of transportation service providers that operated LNG trucks—when we started our study. At the end of 2016, the maturity of the public LNG fuel station infrastructure has grown to 18 stations, which are used by about 500 LNG trucks.

5.1 Sensitivity analysis

We performed a sensitivity analysis on the scenario with 12 LNG fuel stations, a service area size of 200 by 200 km, and LNG trucks with a range of 600 km. The outcome of that scenario was a 4.6% increase in total route length for the LNG trucks—compared to diesel trucks. In the sensitivity analysis, we change the values of the parameters that were given a fixed value in the experiments, namely the number of customers, the maximum route duration, vehicle speed, and the refueling time. Table 3 shows the values used in the sensitivity analyses.

Table 3 Values used for the fixed parameters in the sensitivity analysis
Full size table

Figure 7 depicts the results of the sensitivity analysis. It shows that all parameters related to driving time restrictions have a considerable impact on the results—the maximum route duration most notably. The original values of these parameters used in our experiments do, however, reflect the situation in the Netherlands well. The maximum route duration of 10 h, for example, stems from strict driving time regulations.

Fig. 7
figure 7

Increase in expected total route length

Full size image

From the parameters displayed in Fig. 7, the number of customers to be served has the largest impact on the outcome of the scenario. Further analyses revealed that this can be explained by the fact that economies of scale affect settings with alternative fuel differently than the conventional fuel setting, particularly for low AFS infrastructure maturity levels. In the conventional fuel setting, a higher customer density implies that more customers can be combined in a single route, i.e., before driving time and range constraints are reached. Such economies of scale have a different impact on settings with LNG trucks, however. A higher customer density results in routes that typically cover a smaller part of the service area. Consequently, an AFV has a smaller probability of encountering a conveniently located LNG fuel station on its route. This implies that a more matured AFS infrastructure is required to obtain the same routing performance compared to settings with a lower customer density. A similar effect was observed for parameters that restrict driving time and range. The maximum route duration restricts the time available for driving, customer service and refueling. Therefore, fewer customers can generally be served in a single route when the vehicle speed or the maximum trip duration decrease. Again, this results in routes that typically cover a smaller part of the service area and a smaller probability to encounter an LNG fuel station on-route.

An important managerial insight from our sensitivity analysis is that infrastructure developers should acknowledge that a denser LNG fuel station infrastructure is required in areas where transportation providers’ customers cover only a small part of their service area. Similarly, transportation service providers need to take these characteristics into account when deciding whether to invest in LNG trucks. Moreover, transportation service providers that are confronted with an underdeveloped LNG fuel station infrastructure should acknowledge that some managerial decisions—such as reducing the maximum driving times or using vehicles with smaller capacity—could have a larger negative impact on their operating efficiency than it would have had for diesel trucks.

6 Conclusion and future research

In this paper, we proposed a new solution approach that can be used to derive minimum infrastructure requirements in early market phases of an alternative fuel. Specifically, our simulation-based approach addresses the uncertain customer demand and a gradually maturing alternative refueling infrastructure associated with such early market phases while seeking to find the minimum number of AFS necessary to render the adoption of AFV economically and/or environmentally beneficial.

Our study contributes to science and practice in several ways. Firstly, it further bridges the gap between strategic and operational decision-making in the context of alternative fuel transportation systems by simultaneously considering AFS infrastructure development decisions and AFV routing decisions. This results in novel insights on the introduction of alternative fuels for transportation.

Secondly, from applying our solution approach to the case of introducing LNG as a transportation fuel in the Netherlands, we learn that the approach is effective for determining the minimum required LNG fuel station infrastructure. The results show that establishing 5 LNG fuel stations in the Netherlands may already render the adoption of LNG trucks economically and environmentally beneficial. Moreover, developing the refueling infrastructure beyond 12 AFS does not lead to significant additional improvements in total route length. The results also point to the importance of considering the driving range constraints of AFV. For example, transportation service providers that acquire readily available longer-range LNG trucks appear to be less vulnerable to an underdeveloped alternative refueling infrastructure. The implications from our research can support the development of more robust business cases for investing in AFV. Overall, we expect that the results of our study provide a more constructive starting point for discussions between infrastructure developers and transportation service providers that are necessary to address the current chicken and egg problem.

Lastly, our study provides ample opportunities for future research. Additional parameters, such as vehicle capacity, and exact methods can easily be incorporated in the proposed approach without the need for large modifications. Moreover, future work could apply location routing modelling to find suitable AFS locations based on the infrastructure maturity levels found by the approach proposed in this paper.