The electric vehicle routing problem with nonlinear charging function
Introduction
In the last few years several companies have started to use electric vehicles (EVs) in their operations. For example, La Poste operates at least 250 EVs and has signed orders for an additional 10,000 (Kleindorfer et al., 2012); and the French electricity distribution company ENEDIS runs 2000 EVs, accounting for 10% of their fleet in 2016.1 Despite these developments, the large-scale adoption of EVs for service and distribution operations is still hampered by technical constraints such as battery charging times and limited battery capacity. For the most common EVs used in service operations, the minimum charging time is 0.5 h and the battery capacity is around 22 kWh. The latter leads to a nominal driving range of 142 km (Pelletier et al., 2014). In reality, the driving range could be significantly lower because the energy consumption increases with the slope of the road, the speed, and the use of peripherals (De Cauwer et al., 2015). For instance, Restrepo et al. (2014) documented that the heating and air conditioning respectively reduce the driving range of an EV by about 30% and 8% per hour of use.
Automakers and battery manufacturers are investing significant amounts of capital and effort into the development of new technology to improve EV autonomy and charging time. For instance, General Motors (GM) reinvested USD 20 million into the GM Global Battery Systems Lab to help the company developing new battery technology for their vehicles (Marcacci, 2013). The results of these efforts, however, are transferred only slowly to commercially available EVs. In the meantime, companies using EVs in their daily operations need fleet management tools that can take into account limited driving ranges and slow charging times (Felipe et al., 2014). To respond to this challenge, around 2012 the operations research community started to study a new family of vehicle routing problems (VRPs): the so-called electric VRPs (E-VRPs) (Afroditi, Boile, Theofanis, Sdoukopoulos, Margaritis, 2014, Pelletier, Jabali, Laporte, 2016). These problems consider the technical limitations of EVs. Because of the short driving range, E-VRP solutions frequently include routes with planned detours to charging stations (CSs). The need to detour usually arises in rural and semi-urban operations, where the distance covered by the routes on a single day is often higher than the driving range.
As has been the case for other optimization problems inspired by practical applications, research in E-VRPs started with primarily theoretical variants and is slowly moving toward problems that better capture reality. In general, E-VRP models make assumptions about the EV energy consumption, the charging infrastructure ownership, the capacity of the CSs, and the battery charging process. Most E-VRPs assume that energy consumption is directly and exclusively related to the traveled distance. However, as mentioned before, the consumption depends on a number of additional factors. To the best of our knowledge only Goeke and Schneider (2015) and Lin et al. (2016) use consumptions computed over actual road networks taking into account the EV parameters and their loads.
Similarly, most E-VRP models implicitly assume that the charging infrastructure is private. In this context, the decision-maker controls access to the CSs, so they are always available. However, in reality, mid-route charging is often performed at public stations and so the availability is uncertain. To our knowledge only Sweda et al. (2015) and Kullman et al. (2016) deal with public infrastructure and consider uncertainty in CS availability.
CS capacity is another area in which current E-VRP models are still a step behind reality. All existing E-VRP research that we are aware of assumes that the CSs can simultaneously handle an unlimited number of EVs. In practice, each CS is usually equipped with only a few chargers. In some settings this assumption may be mild (e.g., a few geographically distant routes and private CSs). However, in most practical applications CS capacity plays a restrictive role.
Finally, in terms of the battery charging process, E-VRP models make assumptions about the charging policy and the charging function approximation. The former defines how much of the battery capacity can (or must) be restored when an EV visits a CS, and the latter models the relationship between battery charging time and battery level. In this paper, we focus on these assumptions.
In terms of the charging policies, the E-VRP literature can be classified into two groups: studies assuming full and partial charging policies. As the name suggests, in full charging policies, the battery capacity is fully restored every time an EV reaches a CS. Some studies in this group assume that the charging time is constant (Conrad, Figliozzi, 2011, Erdoğan, Miller-Hooks, 2012, Adler, Mirchandani, 2014, Montoya, Guéret, Mendoza, Villegas, 2015, Hof, Schneider, Goeke, 2017). This is a plausible assumption in applications where the CSs replace a (partially) depleted battery with a fully charged one. Other researchers, including Schneider et al. (2014), Goeke and Schneider (2015), Schneider et al. (2015), Desaulniers et al. (2016), Hiermann et al. (2016), Lin et al. (2016), and Szeto and Cheng (2016), consider full charging policies with a linear charging function approximation (i.e., the battery level is assumed to be a linear function of the charging time). In their models, the time spent at each CS depends on the battery level when the EV arrives and on the (constant) charging rate of the CS. In partial charging policies, the level of charge (and thus the time spent at each CS) is a decision variable. To the best of our knowledge, all existing E-VRP models with partial charging consider linear function approximations (Felipe, Ortuño, Righini, Tirado, 2014, Sassi, Cherif-Khettaf, Oulamara, 2015, Bruglieri, Pezzella, Pisacane, Suraci, 2015, Schiffer, Walther, 2017, Desaulniers, Errico, Irnich, Schneider, 2016, Keskin, Çatay, 2016).
In general, the charging functions are nonlinear, because the terminal voltage and current change during the charging process. This process is divided into two phases. In the first phase, the charging current is held constant, and thus the battery level increases linearly with time. The first charging phase continues until the battery’s terminal voltage increases to a specific maximum value (see Fig. 1). In the second phase, the current decreases exponentially and the terminal voltage is held constant to avoid battery damage. The battery level then increases concavely with time (Pelletier et al., 2017).
Although the shape of the charging functions is known, devising analytical expressions to model them is complex because they depend on factors such as current, voltage, self-recovery, and temperature (Wang et al., 2013). The battery level is then described by differential equations. Since such equations are difficult to incorporate into E-VRP models, researchers rely on approximations of the actual charging functions. Bruglieri et al. (2014) use a linear approximation that considers only the linear segment of the charging function, i.e., between 0 and (around) 0.8Q, where Q represents the battery capacity. This approximation avoids dealing with the nonlinear segment of the charging function (i.e., from (around) 0.8Q to Q). Henceforth we refer to this approximation as first segment (FS). Felipe et al. (2014); Sassi et al. (2014); Bruglieri et al. (2015); Desaulniers et al. (2016); Schiffer and Walther (2017), and Keskin and C̆atay (2016) approximate the whole charging function using a linear expression. They do not explain how the approximation is calculated, but two options can be considered. In the first (L1) the charging rate of the function corresponds to the slope of its linear segment (see Fig. 2b). This approximation is optimistic: it assumes that batteries charge to the level Q faster than they do in reality. In the second approximation (L2) the charging rate is the slope of the line connecting the first and last observations (see Fig. 2c) of the charging curve. This approximation tends to be pessimistic: over a large portion of the curve, the charging rate is slower than in reality.
In this paper, we study a new E-VRP that captures the nonlinear behavior of the charging process using a piecewise linear approximation. The main contributions of this research are fivefold. First, we introduce the electric vehicle routing problem with nonlinear charging functions (E-VRP-NL). Second, we propose a hybrid metaheuristic, which combines simple components from the literature and components specifically designed for this new problem. Third, we propose a set of realistic and publicly available instances. Fourth, we demonstrate through extensive computational experiments the importance of better approximating the actual battery charging function. Fifth, we analyze our solutions and provide some insight into the characteristics of good E-VRP-NL solutions.
The remainder of this paper is organized as follows. Section 2 formally introduces the E-VRP-NL. Section 3 describes our hybrid metaheuristic, and Section 4 presents the computational experiments. Finally, Section 5 concludes the paper and discusses future research.
Section snippets
Problem description
Let I be the set of nodes representing the customers, F the set of CSs, and 0 a node representing the depot. Each customer i ∈ I has a service time pi. The E-VRP-NL is defined on a directed and complete graph where and F′ contains the set F and β copies of each CS (i.e., ). The value of corresponds to the number of times that each CS can be visited. Let be the set of arcs connecting vertices of V. Each arc (i, j) has two associated
Solving the E-VRP-NL
Lenstra and Rinnooy Kan (1981) demonstrated that the classical VRP, commonly known as the CVRP, is NP-hard. Since the CVRP is a special case of our E-VRP-NL, the latter is also NP-hard. We therefore propose a metaheuristic approach. Like many metaheuristics for other VRPs, our approach explores new solutions by building new routes or applying changes (moves) to existing ones. In this process, the algorithm makes sequencing and charging decisions. The former fix the order in which the route
Computational experiments
In this section, we present three computational studies. The first study assesses the benefits of better approximating the battery charging function. The second study evaluates the performance of our ILS+HC. The third study analyzes the characteristics of the best known solutions (BKSs) found by our ILS+HC. The goal of this analysis is to provide researchers with insight that may be useful in the design of new solution methods for the E-VRP-NL.
Conclusion and future work
In this paper, we have introduced a new E-VRP that captures the nonlinear charging behavior of the charging process using a piecewise linear approximation: the electric vehicle routing problem with nonlinear charging function (E-VRP-NL). To solve the problem we proposed an ILS enhanced with HC. At the heart of our method is a neighborhood scheme that solves a new variant of the FRVCP. This problem consists in optimizing the charging decisions (where and how much to charge) of a route serving a
Acknowledgement
The authors would like to thank the Universidad EAFIT scientific computing center (APOLO) for its support for the computational experiments. This research was partly funded in Colombia by Universidad EAFIT, Programa de Movilidad Doctoral hacia Francia (Colfuturo - Emb. de Francia - ASCUN - Colciencias - Min. de Educación), Programa Enlaza Mundos (Alcaldía de Medellín), and Universidad de Antoquia through project UdeA-2016-10705; and in France by Agence Nationale de la Recherche through project
References (45)
- et al.
Online routing and battery reservations for electric vehicles with swappable batteries
Transp. Res. Part B
(2014) - et al.
Electric vehicle routing problem with industry constraints: trends and insights for future research
Transp. Res. Procedia
(2014) - et al.
The vehicle relocation problem for the one-way electric vehicle sharing: an application to the Milan case
Procedia - Social Behav. Sci.
(2014) - et al.
A variable neighborhood search branching for the electric vehicle routing problem with time windows
Electron. Notes Discrete Math.
(2015) - et al.
A green vehicle routing problem
Transp. Res. Part E
(2012) - et al.
A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges
Transp. Res. Part E
(2014) - et al.
Routing a mixed fleet of electric and conventional vehicles
Eur. J. Oper. Res.
(2015) - et al.
The electric fleet size and mix vehicle routing problem with time windows and recharging stations
Eur. J. Oper. Res.
(2016) - et al.
Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops
Transp. Res. Part B
(2017) - et al.
Partial recharge strategies for the electric vehicle routing problem with time windows
Transp. Res. Part C
(2016)
The electric vehicle touring problem
Transp. Res. Part B
Electric vehicle routing problem
Transp. Res. Procedia
Variable neighborhood search
Comput. Oper. Res.
Performance testing of electric vehicles on operating conditions in Bogotá DC, Colombia
Transmission & Distribution Conference and Exposition-Latin America (PES T&D-LA), 2014 IEEE PES
Vehicle Routing Problem with Mixed fleet of Conventional and Heterogenous Electric Vehicles and Time Dependent Charging Costs
Technical Report
Adaptive routing and recharging policies for electric vehicles
Transp. Sci.
Charging of electric vehicles: technology and policy implications
J. Sci. Policy Governance
Electric Vehicles in the United States: A New Model with Forecasts to 2030
Technical Report
The recharging vehicle routing problem
Energy consumption prediction for electric vehicles based on real-world data
Energies
Exact algorithms for electric vehicle-routing problems with time windows
Oper. Res.
An ultrafast ev charging station demonstrator
Power Electronics, Electrical Drives, Automation and Motion (SPEEDAM), 2012 International Symposium on
Cited by (391)
An exact algorithm for maximum electric vehicle flow coverage problem with heterogeneous chargers, nonlinear charging time and route deviations
2024, European Journal of Operational ResearchA novel collaborative electric vehicle routing problem with multiple prioritized time windows and time-dependent hybrid recharging
2024, Expert Systems with ApplicationsAn effective matheuristic approach for solving the electric traveling salesperson problem with time windows and battery degradation
2024, Engineering Applications of Artificial IntelligenceA blockchain-enabled personalized charging system for electric vehicles
2024, Transportation Research Part C: Emerging TechnologiesA ridesharing routing problem for airport riders with electric vehicles
2024, Transportation Research Part E: Logistics and Transportation ReviewAdaptive robust electric vehicle routing under energy consumption uncertainty
2024, Transportation Research Part C: Emerging Technologies