Hot Most Recent
|Ver.||Summary||Created by||Modification||Content Size||Created at||Operation|
|1||+ 3367 word(s)||3367||2020-11-11 06:35:55|
The growth of environmental awareness and more robust enforcement of numerous regulations to reduce greenhouse gas (GHG) emissions have directed efforts towards addressing current environmental challenges. Considering the Vehicle Routing Problem (VRP), one of the effective strategies to control greenhouse gas emissions is to convert the fossil fuel-powered fleet into Environmentally Friendly Vehicles (EFVs). Given the multitude of constraints and assumptions defined for different types of VRPs, as well as assumptions and operational constraints specific to each type of EFV, many variants of environmentally friendly VRPs (EF-VRP) have been introduced. In this paper, studies conducted on the subject of EF-VRP are reviewed, considering all the road transport EFV types and problem variants, and classifying and discussing with a single holistic vision. The aim of this paper is twofold. First, it determines a classification of EF-VRP studies based on different types of EFVs, i.e., Alternative-Fuel Vehicles (AFVs), Electric Vehicles (EVs) and Hybrid Vehicles (HVs). Second, it presents a comprehensive survey by considering each variant of the classification, technical constraints and solution methods arising in the literature.
The increased social and environmental awareness has created growing support for environmental regulations to control GHG emissions. This trend and the rising energy costs have led to increased attempts to address emerging environmental challenges. Generally, state-owned and private sectors are both responsible for the GHG emissions (i.e., CO2, N2O) and pollutants (i.e., CO, SOx, NOx, soot, PM10, contrails, etc.) across the world as well as the associated negative consequences by various activities in construction, transportation, manufacturing, etc. . However, the environmental efforts in these two sectors mainly affect transportation because it influences the environment in several ways by various modes including road, rail, waterborne transports, and air freight. The vehicles used in these modes are responsible for emissions of air pollutants and GHG, and the environment is also affected by the infrastructure required by the vehicles. For instance, the transportation sector in Europe accounts for 30% of CO2 emissions, a share that rises to 40% in urban areas . To address this issue, the European Union plans to achieve a 40% reduction by 2030 . The Green Vehicle Routing Problem (G-VRP), which seeks to incorporate the environmental aspects of transportation into VRP, is one of the most interesting problems in the field of logistics and transportation. The goal of this problem is to earn economic benefits while also taking into account environmental considerations. It is necessary to specify the recipients of these benefits to catch their value proposition. Thus, it is necessary to define the main actors involved in logistics and transportation and analyze their business models and the interaction between them. In this context, some studies have explored the business models based on new transportation options (e.g., green vehicles adoption, etc.) and on collaborative strategies for achieving reasonable levels of sustainability and efficiency in logistics activities. Examples of the operational advantages of an integrated vision of the business models and methods can be found in Perboli and Rosano , Rosano et al. , Perboli et al. , and Brotcorne et al..
One of the available strategies for achieving the goals of the G-VRP is to use environmentally friendly vehicles (EFVs). The sustainability benefits of alternative and green fuel resources, such as biodiesel, electricity, ethanol, hydrogen, methanol, natural gas, as a potential substitute for Internal Combustion Engine Vehicles (ICEVs) leads to the adoption of alternative fuel utilization in VRP by defining Alternative Fuel Vehicles (AFVs) as a general type of EFVs. In the relevant literature, some of the studies have been presented as Alternative-Fuel Vehicle Routing Problem (AF-VRP) and do not explicitly refer to the type of vehicle fuel. In particular, Electric Vehicles (EVs) and Hybrid Vehicles (HVs) have been considered as specialized types of AFVs and studied separately with their special characteristics. In most of the studies, EVs have been considered as an idealistic alternative to the ICEVs for freight distribution, as they are emission-free when used, and produce little noise pollution . However, due to the occurrence of combustion emissions for EVs in generating electricity, the different assumptions in the time of charging and the country-specific electricity generation mix, assessing combustion emissions of EVs in different countries is an important issue (see Jochem et al.  and Ji et al.  for examples of assessments of the EVs emissions in Germany and China, respectively). According to the U.S. Department of Energy, EVs can convert around 59–62% of the received electrical energy to the power in the wheels, but for ICEVs, this ratio is as low as 17–21% . However, there are still constraints on the EVs usage, including the limited availability of recharging stations, the limited driving range of EVs, and the relatively long time used for recharging of these vehicles. Another alternative that has been used in the literature is the HVs, which can consume both electricity and conventional fuel. This capability of HVs provides a solution to reduce transportation costs and emissions while avoiding the operational constraints of EVs . So, two other problems in the routing of EFVs have been introduced in the literature: Electric VRP (E-VRP) and Hybrid VRP (H-VRP). As a result, the classification scheme on the EFVs routing problem (EF-VRP) can be constituted based on the problem characteristics and their application scenarios, by considering three different variants of routing problem as follows: Alternative-Fuel VRP (AF-VRP), Electric VRP (E-VRP), and Hybrid VRP (H-VRP). (Figure 1).
Figure 1. Variants of Environmentally Friendly Vehicle Routing Problem.
Despite the significant volume of works published in the field of EF-VRPs, there is no review paper focusing on EF-VRPs, considering all the different road EFVs types and problem variants, and classifying and discussing with a single holistic vision. The review papers that are somewhat related to this area are those published by Pelletier et al. , Juan et al. , Margaritis et al. , Crainic et al. , Schiffer et al. , and Erdelić and Carić . These works have addressed the general usage of EVs in transportation and logistics and have partly mentioned the studies in the field of routing problem with AFVs, EVs, and HVs. The mentioned reviews did not present a proper classification for the EF-VRPs and did not discuss the technical characteristics of the variety of problems in this area. These points are crucial both from a modeling and solving point of view. First, technical constraints can drastically change the behavior and properties of the model. Second, a similar characteristic can arise in different settings, giving a plethora of solving methods and redefining the same characteristics or constraints with different names. Thus, the literature presents some lacks.
Therefore, this study is aimed to fulfill this gap along two axes: First, it determines a classification of EF-VRP studies based on different types of EFVs, i.e., Alternative-Fuel Vehicles (AFVs), Electric Vehicles (EVs), and Hybrid Vehicles (HVs). All of the existing problems which have applied environmentally friendly vehicles are classified under the name of Environmentally Friendly Vehicle Routing Problem (EF-VRP). Given the variety of vehicles with unique characteristics that can be considered in EF-VRPs, they are far more complex than VRP that uses a fleet of fossil-fueled vehicles. The first studies in the field of EF-VRP were those carried out by Conrad and Figliozzi , Erdoğan and Miller-Hooks , Abdallah , and Schneider et al. . Later, and particularly in recent years, many other works in the form of journal papers, conference papers, research reports, thesis, and books have been published in this area. Second, it presents a comprehensive survey by considering each variant of the classification, technical constraints, and solution methods arising in the literature. The search conducted on the databases is based on 125 studies on EF-VRP extracted from the main relevant databases, making our study the one based on the largest database of works from the literature. As a result, the main contributions of this paper may be summarized as follows:
The remainder of the paper is organized as follows: Section 2 describes the technical constraints and assumptions used in EF-VRPs. Section 3 investigates the studies on AFV routing problems. The EVs routing problem and its variants are reviewed in Section 4. Section 5 describes the HEV routing problem and studies in this area. Section 6 reviews the solution methods for EF-VRPs, followed by conclusions and potential future research directions in Section 7.
The classical VRP is one of the fundamental problems in operational research, which seeks to determine how a set of vehicles can serve a set of customers in such a way as to minimize the total cost of travel in a transportation network. The green VRP is a variant of VRP, which seeks to minimize both the economic cost and the environmental cost of vehicle routing . According to Lin et al. , the VRPs that follow a green approach can be divided into three broad categories: Green-VRP, Pollution-Routing Problem (PRP), and VRP in Reverse Logistics (VRPRL) (Figure 2). One of the subcategories of the Green-VRP is to use EFVs (EF-VRP in Figure 2) .
Figure 2. Classification of studies on green vehicle routing problem (G-VRP) according to Lin et al. .
The search for the existing works on the EF-VRP was conducted in prominent databases including Scopus, Web of Science, Science Direct, Springer Link EBSCO, Taylor & Francis Elsevier, Wiley, Springer, and IEEE Xplore. To cover a wide range of research, including books, papers, journals, and conferences, and according to the availability of certain information, data were gathered from Google Scholar, extracting from the pages with a minimum number of publications equal to 10. After filtering them by keywords (environmentally friendly vehicles, electric vehicle, hybrid vehicle routing, hybrid electric vehicle routing, plug-in hybrid electric vehicle routing, time windows, pickup and delivery, time-dependent, mixed fleet, alternative fuel vehicle routing problem, green-VRP, and green vehicle routing problem), the data sources were limited to 125 studies. Since the first study on the EF-VRP subject was published in 2011, the time span of this study was limited to the period of 2011–2020. After a manual filtering based on the analysis of the abstracts, our final database was then based on 125 studies on EF-VRP.
The unique characteristics of EFVs have limited their use in VRPs. These characteristics include maximum battery capacity and maximum travel distance without refueling (recharging or battery swapping), duration of refueling (recharging or battery swapping), location of refueling (recharging or battery swapping) stations, fuel (charge) consumption rate, etc. These technical constraints and characteristics can be addressed by a variety of creative solutions, such as establishing battery swapping stations and partial recharge or refueling stations at customer sites. In this section, some of the significant constraints and assumptions of EFVs are explained, as follows:
Full refueling (recharging): In this assumption, a vehicle that visits a refueling (recharging) station is fully refueled (recharged) and continues its service as long as its fuel tank (battery) can support it.
Partial refueling (recharging): In this assumption, a vehicle can decide to only partially fill its fuel tank (recharge its battery) to spend less time at the refueling (recharging) station. Felipe et al.  were the first researchers to consider the partial recharging in EF-VRPs. A significant portion of recent studies on EF-VRPs have chosen to use this assumption.
No intraroute recharging (refueling) facility: In some studies, it is possible to refuel (recharge) vehicles only in the depot and there are no intraroute facilities for refueling (recharging) in the middle of the route. Hence, in order to cover the fuel tank or battery capacity constraints, authors cover the vehicles’ maximum driving range, and consider the refueling (recharging) process in the base location of the EFVs where the vehicles can be parked overnight and recharged.
Battery swapping: One method to recharge a group of vehicles along a route is to establish some stations for swapping batteries. Logistics companies can benefit from this approach in several ways. The most significant benefit of the battery swapping approach is the increased recharging speed and reduced time loss. A battery swapping operation can be completed in less than 10 min, which makes it significantly faster than recharging operation . Another advantage of battery swapping is that the used-up batteries can be recharged at night when electricity is charged at a discount .
Refueling (recharging) or battery swapping at customers sites: In this assumption, it is supposed that refueling (recharging) or battery swapping services are made available at all or some of the customers’ sites .
Refueling (recharging) or battery swapping at specific vertices: In this approach, refueling (recharging) or battery swapping services are not permissible at all customer sites. The assumption of having specific vertices on the network as refueling (recharging) stations was first introduced by Li-ying and Yuan-bin .
Simultaneous refueling (recharging) station siting: EFVs have a shorter driving range than ICEVs. Thus, the proper placement of refueling (recharging) stations can result in a timely provision of the energy needed by vehicles to continue visiting the remaining customers. This assumption involves combining the routing problem with the location problem, and therefore, the expansion of the EF-VRP into Environmentally Friendly Location Routing Problem (EF-LRP). Given the investment needed to construct refueling (recharging or battery swapping) stations at multiple sites, many studies have focused on the goal of minimizing the number of refueling (recharging) stations in the distribution network. Yang and Sun  were the first to consider the problem of establishing and operating battery swapping stations to minimize the number of these facilities in a network.
Fixed refueling (recharging) time: The time spent for refueling (recharging or battery swapping) is one of the critical factors in the use of EFVs. One assumption commonly used in the vehicle routing literature is that the refueling (recharging) time is constant across a network.
Nonlinear refueling (recharging) process: This assumption involves considering a more realistic nonlinear relationship between the time spent on recharging (refueling) and the amount of fuel (energy) transferred to the vehicle . In most of the existing E-VRP models, the battery charging level is assumed to be a linear function of charging time, but in reality, this function is nonlinear. Accordingly, the use of a practical linear estimation for nonlinear charging behavior can significantly contribute to making the problem and its solutions more realistic.
Battery life degradation: The investment loss due to battery degradation is too costly to be ignored. Battery life degradation can be considered as a function of three factors: temperature, State of Charge (SOC), and Depth of Discharge (DOD). In a study by Barco et al. , battery degradation in E-VRP was modeled alongside other assumptions of this problem. In this model, the three factors mentioned above are integrated into a degradation cost (), which is defined as follows:
where is the initial cost of the battery and ,, and are the initial cost of the battery, the percentages of battery degradation due to temperature, SOC and DOD, respectively. Further details on battery degradation and other technical characteristics of electric vehicles are available in the study of Pelletier et al. .
Effect of load, traveling speed, and ambient temperature on fuel (charge) consumption: Speed and weight variation are essential determinants of the vehicles energy consumption while traveling . Additionally, temperature affects energy consumption due to heater use and decreased battery efficiency in cold temperatures, and increased use of air conditioning in hot temperatures . In the literature related to EFVs, these factors are referred to as load, speed, and ambient temperature effects. In this regard, Lin et al.  stated that the effect of the load on routing strategies of EFVs could not be ignored. They developed a model for the E-VRP, where the effect of the load on the battery consumption rate was considered and evaluated in a case study. According to this study, the rate of acceleration/deceleration, which is affected by traffic conditions and environmental factors, plays a significant role in vehicle energy consumption . Furthermore, Rastani et al.  investigated the impact of ambient temperature on the fleet sizing, battery recharging, and routing decisions of EVs in logistics operations for the first time.
Refueling (recharging or battery swapping) cost: Generally, the refueling (recharging or swapping) process is a costly operation that should be optimized to minimize the total cost of a distribution network. The assumption of time-dependent charging cost was first introduced by Sassi et al. , who considered three different charging technologies, namely, slow charging, moderate charging, and fast charging with different costs.
Different charging technologies: Decision-making on the selection of possible charging technologies could also be an effective way to better control charging time in the E-VRP context. For customers who have narrow time windows, this issue could make them more accessible by fast charging at recharging stations, or if the time windows are long, a better economic approach could be slow charging . Sassi et al.  and Felipe et al.  analyzed the effect of different charging technologies on the recharge cost for the first time.
Multiple driving modes (Multi-mode): A Hybrid Electric Vehicle (HEV) is powered by two power sources, it consumes both electricity and gasoline during driving. The energy consumption of an HEV on each road segment depends on the HEV driving modes. For the first time, Doppstadt et al.  assumed four different modes of operation: pure combustion (conventional) mode, pure electric mode, charging mode in which the battery is charged while driving with the combustion engine, and a boost mode in which combustion and electric engines are combined for the drive. Further, Zhen et al.  considered this conception and defined four modes including the electric motor (battery-based mode), being mainly powered by the engine (gasoline-based mode), the two being jointly driven (balance mode), or only powered by the engine (only gasoline mode).
Wait in queue before the recharging (refueling) service: The number of chargers or servers in a recharging (refueling) station is limited and the chargers or servers may be occupied and may not be available at the time of the vehicle’s arrival. Hence, the EFV may need to queue for some time before it starts recharging (refueling) its battery or fuel tank . Recently, Keskin et al.  and Poonthalir and Nadarajan  extended the EF-VRP by considering queue formation at the recharging (refueling) stations using M/M/1 and M/G/1 queueing systems.
As a result, it should be noted that the limited driving range of EFVs, the existence of a set of refueling (recharging) stations vertices which may be visited more than once or not at all, and the possibility of the vehicles’ driving range extension due to the facilities visiting, represent the complications that were not be presented in the classical VRP or most variants thereof. Thus, heuristics and exacts solutions used for the classical VRP or related variants cannot directly be applied in solving the EF-VRPs. Not only might such heuristics and exact algorithms result in solutions that perform poorly, but these solutions may not even be feasible . So, AF-VRP, E-VRP, and H-VRP can be considered as distinct classes of the VRP and particular variants of the EF-VRP because of its complexity, technical constraints, and new solution methods which have been implemented to solve them.
Vehicle types. 23 (18%), 90 (72%), and 12 (10%) studies belong to the AF-VRP, E-VRP, and H-VRP, respectively. Figure 3 shows the share of research on the EF-VRP variants. As indicated in this figure, previous works have mostly been focused on E-VRPs, and there exists a research gap on the other two variants of the problem, especially the H-VRP. Figure 4 shows the number of papers published on each variant of the problem since 2011. In the mentioned subcategories, there are multiple and technical constraints that can create different variants of the EF-VRP. The most important constraints and assumptions are described in the following subsections.
Figure 3. Contribution of research on Alternative-Fuel VRP (AF-VRP), Electric VRP (E-VRP), and Hybrid VRP (H-VRP) from all studies related to the Environmentally Friendly Vehicle Routing Problem (EF-VRP).
Figure 4. The number of papers published on AF-VRP, E-VRP, and H-VRP.